The famine of forte: Few search problems greatly favor your algorithm
The famine of forte: Few search problems greatly favor your algorithm
复制标题
强项饥荒：很少有搜索问题对你的算法有很大帮助
DOI：
10.1109/smc.2017.8122651
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
George D. Montañez
中科院分区：
文献类型：
--
作者：
George D. Montañez
将机器学习视为一种搜索，我们证明了有利于固定算法的问题比例是严格有限的，因此没有任何一种算法可以在其中的很大一部分上表现良好。如果一个算法在一类问题（例如凸问题）上表现出色，那么该类问题必然很小。我们根据目标和信息资源（例如训练数据集）之间的互信息给出了搜索算法的预期性能上限，证明了机器学习中某些类型的依赖性的重要性。最后，考虑到算法的预期每次查询成功概率在数学上等于分布（称为搜索策略）下的单个查询成功概率，我们证明有利策略的比例也是严格有界的。因此，无论是固定搜索算法并考虑所有可能的问题，还是固定搜索问题并考虑所有可能的搜索策略，有利的匹配都极其罕见。任何算法的长处（强度）都是受到量化限制的。
Casting machine learning as a type of search, we demonstrate that the proportion of problems that are favorable for a fixed algorithm is strictly bounded, such that no single algorithm can perform well over a large fraction of them. If an algorithm greatly excels on a class of problems (e.g., convex problems), that class must necessarily be small. We give an upper bound on the expected performance for a search algorithm as a function of the mutual information between the target and the information resource (e.g., training dataset), proving the importance of certain types of dependence for machine learning. Lastly, given that the expected per-query probability of success for an algorithm is mathematically equivalent to a single-query probability of success under a distribution (called a search strategy), we prove that the proportion of favorable strategies is also strictly bounded. Thus, whether one holds fixed the search algorithm and considers all possible problems or one fixes the search problem and looks at all possible search strategies, favorable matches are exceedingly rare. The forte (strength) of any algorithm is quantifiably restricted.
DOI：
10.1613/jair.4806
发表时间：
2013-01
期刊：
J. Artif. Intell. Res.
影响因子：
--
作者：
Ziyun Wang;M. Zoghi;F. Hutter;David Matheson;Nando de Freitas
通讯作者：
Ziyun Wang;M. Zoghi;F. Hutter;David Matheson;Nando de Freitas