在许多机器学习问题中,您通常有一个想要最小化的目标函数(例如,成本、损失、错误)。我有时不是直接最小化这个目标函数,而是看到导出目标函数上限的论文,然后最小化上限版本。其原因似乎是我们手头的数据无法获得最初的目标,或者由于某些原因难以最小化。
我的问题是,最小化上限有意义吗?是否有保证它们会导致相同的解决方案?我担心的是,在这两种情况下,最小化器显然会变得不同。如果是这种情况,我们知道两者可以有多接近吗?有没有很好的教科书或论文可以解释这些问题?
非常感谢您的帮助!
在许多机器学习问题中,您通常有一个想要最小化的目标函数(例如,成本、损失、错误)。我有时不是直接最小化这个目标函数,而是看到导出目标函数上限的论文,然后最小化上限版本。其原因似乎是我们手头的数据无法获得最初的目标,或者由于某些原因难以最小化。
我的问题是,最小化上限有意义吗?是否有保证它们会导致相同的解决方案?我担心的是,在这两种情况下,最小化器显然会变得不同。如果是这种情况,我们知道两者可以有多接近吗?有没有很好的教科书或论文可以解释这些问题?
非常感谢您的帮助!
在许多情况下,您想要最小化的真正函数是您无法合理地明确计算的东西(例如,在贝叶斯统计中,您经常有一个公式整合某物的所有可能组合,即使是最好的超级计算机也太多了) ,或者没有已知的公式或程序可以直接最小化它(例如在离散优化中)。
在这种情况下,如果您无法计算或最小化函数本身,那么最小化与函数高度相关的事物(例如,采样估计,或用其他估计替换真实值的近似值)或上限是有意义的(只要它是合理的) - 在第二种情况下,你知道如果你从类似的东西中取这个上限到,初始参数很可能会导致函数的值比您通过最小化上限获得的值更差。
在某些情况下,可以证明函数的最优值在最大化上限的解的某个百分比范围内(在离散优化中很常见),但通常情况并非如此(例如在贝叶斯统计中),并且你得到的绝不是原始函数的真正全局最优值,而是比随机更好的东西,而且在你的计算机上计算是可行的。
现在,您可能会争辩说,存在诸如进化搜索之类的黑盒方法可以最小化几乎任何您可以直接评估的函数,但是这些通常会导致比最小化上限更糟糕的解决方案,需要更多的函数评估,很多,如果参数太多,速度会慢得多,而且不切实际,而上限通常可以通过依赖于可微性、平滑度、Lipschitz 连续性等假设的更快方法合理地最小化。
简而言之:原函数的最优解和上界的最优解确实是不同的,但是如果不能直接最小化原函数,你仍然可以通过最小化上界得到一个像样的解(不是最好的解)。