## Abstract

Many machine learning algorithms aim at finding "simple" rules to explain training data. The expectation is: the "simpler" the rules, the better the generalization on test data (-_ Occam's razor). Most practical implementations, however, use measures for "simplicity" that lack the power, universality and elegance of those based on Kolmogorov complexity and SolomonofT's algorithmic probability. Likewise, most previous approaches (especially those of the "Bayesian" kind) suffer from the problem of choosing appropriate priors. This paper addresses both issues. It first reviews some basic concepts of algorithmic complexity theory relevant to machine learning, and how the Solomonoff-Levin distribution (or universal prior) deals with the prior problem. The universal prior leads to a probabilistic method for finding "algorithmically simple" problem solutions with high generalization capability. The method is based on Levin complexity (a time-bounded extension of Kolmogorov complexity) and inspired by Levin's optimal universal search algorithm. With a given problem, solution candidates are computed by efficient "self-sizing" programs that influence their own runtime and storage size. The probabilistic search algorithm finds the "good" programs (the ones quickly computing algorithmically probable solutions fitting the training data). Experiments focus on the task of discovering "algorithmically simple" neural networks with low Kolmogorov complexity and high generalization capability. These experiments demonstrate that the method, at least with certain toy problems where it is computationally feasible, can lead to generalization results unmatchable by previous neural net algorithms.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 12th International Conference on Machine Learning, ICML 1995 |

Editors | Armand Prieditis, Stuart Russell |

Publisher | Morgan Kaufmann Publishers, Inc. |

Pages | 488-496 |

Number of pages | 9 |

ISBN (Electronic) | 1558603778, 9781558603776 |

State | Published - 1995 |

Event | 12th International Conference on Machine Learning, ICML 1995 - Tahoe City, United States Duration: Jul 9 1995 → Jul 12 1995 |

### Publication series

Name | Proceedings of the 12th International Conference on Machine Learning, ICML 1995 |
---|

### Conference

Conference | 12th International Conference on Machine Learning, ICML 1995 |
---|---|

Country/Territory | United States |

City | Tahoe City |

Period | 07/9/95 → 07/12/95 |

### Bibliographical note

Publisher Copyright:© ICML 1995.All rights reserved

## ASJC Scopus subject areas

- Artificial Intelligence
- Human-Computer Interaction
- Software
- Theoretical Computer Science