SYNTHESIS OF THE SECONDARY STRUCTURE OF ALGEBRAIC BAYESIAN NETWORKS: AN INCREMENTAL ALGORITHM AND STATISTICAL ESTIMATION OF ITS COMPLEXITY
Annotation
An improved algorithm for the synthesis of the secondary structure of algebraic Bayesian networks represented by a minimal join graph is proposed in the paper. The algorithm differs from the previously offered one so that it relies on the incremental principle, uses specially selected edges and, finally, eliminates redundant edges by a greedy algorithm. The correct operation of the incremental algorithm is mathematically proved. Comparison of the computational complexity of the new (incremental) algorithm implementation and two well-known (greedy and direct) is made by means of statistical estimates of complexity, based on the sample values of the runtime ratio of software implementations of two compared algorithms. Theoretical complexity estimates of the greedy and direct algorithms have been obtained earlier, but are not suitable for comparative analysis, as they are based on the hidden characteristics of the secondary structure, which can be calculated only when it is built. To minimize the influence of random factors at calculating the ratio average program runtime is used obtained by N launches on the same set of workloads. The sample values of ratio is formed for M sets of equal power K. According to the sample values the median is calculated, as well as the other statistics that characterize the spread: borders of the 97% confidence interval along with the first and the third quartiles. Sets of loads are stochastically generated according to the specified parameters using the algorithm described in the paper. The stochastic algorithms generating a set of loads with given power, as well as collecting the statistical data and calculating of statistical estimates of the ratio of forward and greedy algorithm to the incremental algorithm runtimes is described in the paper. A series of experiments is carried out in which N is changed in the range 1, 2 ... 9, 10, 26, 42 ... 170.They have showed that the incremental algorithm speed exceeds the forward and greedy ones, moreover in the 10-170 load sets power range this finding is statistically significant (97% level). The results of experiments are visualized using a graphs library Highcharts. The developed incremental algorithm is designed for application in problems solving of algebraic Bayesian networks machine learning.
Keywords
Постоянный URL
Articles in current issue
- TRENDS IN THE DEVELOPMENT OF DETONATION ENGINES FOR HIGH-SPEED AEROSPACE AIRCRAFTS AND THE PROBLEM OF TRIPLE CONFIGURATIONS OF SHOCK WAVES. Part I. Research of detonation engines
- SPECIAL ASPECTS OF INITIAL OPTICAL SCHEME SELECTION FOR DESIGN OF NON-IMAGING OPTICAL SYSTEMS
- APPLICATION OF CHEMOMETRICS FOR ANALYSIS OF BIOAEROSOLS BY FLOW-OPTICAL METHOD
- APPROACH TO AUTOMATION OF LENS COMPONENTS CENTERING FOR ASSEMBLING OF DIFFERENT DESIGN OBJECTIVES
- METHOD FOR CREATION OF SPHERICAL PANORAMAS FROM IMAGES OBTAINED BY OMNIDIRECTIONAL OPTOELECTRONIC SYSTEMS
- LINE-FIELD SWEPT-SOURCE OPTICAL COHERENCE TOMOGRAPHY SYSTEM FOR NEAR INFRARED SPECTRAL REGION
- BACKSTEPPING ALGORITHM FOR LINEAR SISO PLANTS UNDER STRUCTURAL UNCERTAINTIES
- RESEARCH OF FREE MOTION TRAJECTORIES FEATURES OF CONTINUOUS SYSTEM DEFINED AS A CONSECUTIVE CHAIN OF IDENTICAL FIRST-ORDER APERIODIC LINKS
- SPECTRAL CHARACTERISTICS OF MID-INFRARED LIGHT-EMITTING DIODES BASED ON InAs (Sb,P)
- SIMULATION OF SENSING ELEMENT OF TEMPERATURE SENSOR BASED ON SILICATE GLASS WITH SODIUM NANOPARTICLES
- (IN-) PRIVACY IN MOBILE APPS. CUSTOMER OPPORTUNITIES (in Engl.)
- PRINCIPLES OF INDICATION FOR EN-ROUTE FLIGHT PATHS OF THE AIRCRAFT ON THE SCREEN OF ON-BOARD DISPLAY DEVICES
- ERROR CORRECTION METHOD FOR SEQUENCING DATA WITH INSERTIONS AND DELETIONS
- CHOICE OF OPTION FOR IMPLEMENTATION OF THE MULTILEVEL SECURE ACCESS TO THE EXTERNAL NETWORK
- EFFECT OF MICROPHONES NON-IDENTITY ON THE MICROPHONE ARRAYS CHARACTERISTICS
- QUALITY CONTROL AUTOMATED LASER-ULTRASONIC METHOD FOR SOLDER JOINTS OF NOZZLES OF CHAMBERS IN LIQUID ROCKET ENGINES
- ROBUST MODIFICATION OF THE LASSO METHOD FOR GENOME-WIDE ASSOCIATION STUDY IN VIEW OF TARGET PHENOTYPE VALUES
- BENCHMARK SOLUTIONS FOR STOKES EQUATIONS WITH VARIABLE VISCOSITY IN CYLINDRICAL AND SPHERICAL COORDINATES
- INFORMATIONAL MODEL OF MENTAL ROTATION OF FIGURES
- WENO SCHEMES FOR SOLUTION OF UNSTEADY ONE-DIMENSIONAL GAS DYNAMICS TEST PROBLEMS
- AUTOMATED CONTROL SIMULATION OF PROFESSIONAL SKILLS FORMATION FOR PRODUCTION SYSTEM OPERATOR
- STUDY OF OPTICAL AND LUMINESCENT PROPERTIES OF POTASSIUM-ALUMINA-BORATE GLASS DOPED WITH Cr3+ IONS
- SPEAKER-DEPENDENT FEATURES FOR SPONTANEOUS SPEECH RECOGNITION