Evolutionary Learning. Advances in Theories and Algorithms

Description

Preface......Page 3 Notations......Page 5 Contents......Page 7 1.1 Machine Learning......Page 11 1.2 Evolutionary Learning......Page 12 1.3 Multi-objective Optimization......Page 14 1.4 Organization of the Book......Page 17 2.1 Evolutionary Algorithms......Page 19 2.2 Pseudo-Boolean Functions......Page 23 2.3 Running Time Complexity......Page 25 2.4 Markov ChainModeling......Page 27 2.5 Analysis Tools......Page 29 --- Analysis Methodology......Page 35 3 Running Time Analysis - Convergence-based Analysis......Page 36 3.1 Convergence-based Analysis: Framework......Page 37 3.2 Convergence-based Analysis: Application Illustration......Page 41 3.3 Summary......Page 46 4.1 Switch Analysis: Framework......Page 47 4.2 Switch Analysis: Application Illustration......Page 52 4.3 Summary......Page 56 5.1 Analysis Approaches: Formalization......Page 57 5.2 Switch Analysis vs. Fitness Level......Page 59 5.3 Switch Analysis vs. Drift Analysis......Page 63 5.4 Switch Analysis vs. Convergence-based Analysis......Page 67 5.5 Analysis Approaches: Unification......Page 71 5.6 Summary......Page 73 6 Approximation Analysis - SEIP......Page 74 6.1 SEIP: Framework......Page 75 6.2.1 Set Cover ......Page 82 6.2.2 Approximation Ratios of SEIP ......Page 83 6.3 Summary......Page 85 --- Theoretical Perspectives......Page 86 7 Boundary Problems of EAs......Page 87 7.1 Boundary Problem Identification......Page 88 7.2 Case Study......Page 91 7.3 Summary......Page 96 8 Recombination......Page 97 8.1 Recombination andMutation......Page 99 8.2 Recombination Enabled MOEAs......Page 101 8.3 Case Study......Page 104 8.3.1 Weighted LPTNO ......Page 105 8.3.2 COCZ ......Page 109 8.4 Empirical Verification......Page 110 8.5 Summary......Page 112 9 Representation......Page 113 9.1 Genetic Programming Representation......Page 115 9.2.1 Solution Representation and Fitness Calculation ......Page 117 9.2.2 Analysis of (1+1)-GP ......Page 119 9.3.1 Solution Representation and Fitness Calculation ......Page 123 9.3.2 Analysis of (1+1)-GP ......Page 124 9.3.3 Analysis of SMO-GP ......Page 127 9.4 Empirical Verification......Page 129 9.5 Summary......Page 132 10 Inaccurate Fitness Evaluation......Page 133 10.1 Noisy Optimization......Page 134 10.2.1 Noise Helpful Cases......Page 136 10.2.2 Noise Harmful Cases ......Page 139 10.3.1 Threshold Selection......Page 140 10.3.2 Smooth Threshold Selection......Page 144 10.4 Denoise by Sampling......Page 145 10.4.1 Robustness against Prior Noise......Page 146 10.4.2 Robustness against Posterior Noise ......Page 150 10.5.1 Noise Helpful Cases ......Page 152 10.5.3 Discussion......Page 154 10.6 Summary......Page 156 11 Population......Page 158 11.1 Influence of Population......Page 159 11.2.1 Parent Population ......Page 163 11.2.2 Offspring Population ......Page 171 11.3 Summary......Page 175 12 Constrained Optimization......Page 177 12.1.1 Conditions for Exploring Infeasible Solutions ......Page 179 12.1.2 Case Study ......Page 183 12.2 Effectiveness of Pareto Optimization......Page 185 12.2.1 MinimumMatroid Optimization ......Page 188 12.2.2 Minimum Cost Coverage ......Page 191 12.2.3 Pareto Optimization vs. Greedy Algorithm ......Page 194 12.3 Summary......Page 196 --- Learning Algorithms......Page 197 13 Selective Ensemble......Page 198 13.1 Selective Ensemble......Page 199 13.2 The POSE Algorithm......Page 201 13.3 Theoretical Analysis......Page 203 13.3.1 POSE Can Do All of OSE ......Page 204 13.3.2 POSE Can Do Better Than OSE ......Page 205 13.3.3 POSE/OSE Can Do Better Than SOSE ......Page 207 13.4 Empirical Study......Page 209 13.4.1 Binary Classification ......Page 210 13.4.2 Multiclass Classification ......Page 212 13.4.3 Application ......Page 213 13.5 Summary......Page 215 14 Subset Selection......Page 216 14.1 Subset Selection......Page 217 14.1.2 InfluenceMaximization ......Page 219 14.1.4 Sensor Placement ......Page 220 14.1.5 Sparse Regression......Page 221 14.2 The POSS Algorithm......Page 222 14.3.1 The General Problem ......Page 223 14.3.2 Sparse Regression ......Page 225 14.4 Empirical Study......Page 227 14.4.1 Optimization Performance......Page 228 14.4.2 Generalization Performance ......Page 229 14.4.3 Running Time ......Page 230 14.5 Summary......Page 231 15 Subset Selection - k-Submodular Maximization......Page 233 15.1 Monotone k-Submodular Function Maximization ......Page 235 15.2 The POkSS Algorithm......Page 238 15.3 Theoretical Analysis......Page 241 15.4.1 InfluenceMaximization ......Page 246 15.4.2 Information Coverage Maximization ......Page 247 15.4.3 Sensor Placement ......Page 250 15.4.4 Discussion ......Page 251 15.5 Summary......Page 254 16 Subset Selection - RatioMinimization......Page 255 16.1 RatioMinimization of Monotone Submodular Functions......Page 256 16.2 The PORM Algorithm......Page 259 16.3 Theoretical Analysis......Page 261 16.4 Empirical Study......Page 266 16.5 Summary......Page 268 17 Subset Selection - Noise......Page 269 17.1 Noisy Subset Selection......Page 270 17.1.1 The Greedy Algorithm ......Page 271 17.1.2 The POSS Algorithm ......Page 272 17.2 The PONSS Algorithm......Page 275 17.3 Theoretical Analysis......Page 277 17.4 Empirical Study......Page 281 17.5 Summary......Page 283 18.1 The PPOSS Algorithm......Page 284 18.2 Theoretical Analysis......Page 286 18.3 Empirical Study......Page 290 18.4 Summary......Page 292 A.1 Proofs in Chapter 4......Page 293 A.2 Proofs in Chapter 5......Page 296 A.3 Proofs in Chapter 8......Page 304 A.4 Proofs in Chapter 9......Page 308 A.5 Proofs in Chapter 10......Page 310 A.6 Proofs in Chapter 11......Page 332 A.7 Proofs in Chapter 12......Page 333 A.8 Proofs in Chapter 15......Page 337 A.9 Proofs in Chapter 17......Page 338 Refs......Page 340