2012年4月15日,星期日

互动式PAC

最近,我受到启发,总结了以下方面的应用进展 PAC风格 交互式设置的算法设计,最后得到了这个小表格。
P很好地 A近似地 C直立的
被动批量学习 wrt绘制数据集 IID浓度
被动在线学习 wrt绘制数据集 (``在线到批量''转换)
积极的在线学习 wrt绘制数据集和标签检查决定的顺序 ting(风俗?)
情境强盗 wrt绘制数据集和选择的操作顺序 ting(弗里德曼风格)
两件事跳了出来。首先是多功能性 ting 驯服交互式学习。这种推理方式还能走多远?毫无把握地预言是愚蠢的,但是感觉仍然有一定的发展空间。最终,当然存在随机设置的限制:并非所有环境都被很好地近似为遗忘的。所以最终我们都会进行博弈论,除非 像这样 杀死了所有人在此之前,我担心尝试解决强化学习中的学分分配问题时实际上难以克服的样本复杂性问题。人们已经可以看到这种情况的提示,例如,对于不可知论的随机上下文强盗来说,最坏情况的瞬时遗憾表明数据需求与可能采取的行动数量呈线性比例关系。另一方面,数据量的扩展速度甚至比计算速度还要快。如果相对增长无限期地持续下去,那么计算复杂性将胜过样本复杂性,这是一个算法设计问题。

第二是在线学习的基本性质。在1990年代,如果您(像我一样!)将在线学习视为实现细节,那是一种宽恕,这是一种优化策略,特别适合于机器学习中出现的目标函数类型(我完全没有意识到) 预测单个序列)。借助事后观察的优势,很明显,在线学习更适合考虑随着时间的流逝如何向算法显示信息(或由其收集信息),而被动批处理学习更像是具有特定实现可能性的特殊情况。

4条评论:

  1. Ran into your blog. You might be interested in another application of a 弗里德曼风格 inequality (http://arxiv.org/abs/1002.4058). Here, the data can be adversarial (e.g. not necessarily iid), but the algorithm can act randomly and still do well. This doesn't get into game theory, however, because of how regret is defined -- this may be a limitation of the model.

    回复删除
    回覆
    1. 感谢您指出,我'把它放在我的阅读清单上。

      Re: game theory, I may have been too hasty in declaring the future to be all game theory :) proposition 2 of http://arxiv.org/abs/1104.5070 indicates for OCO-style problems there is always a minimax strategy for the adversary which is oblivious (but nonstationary). So maybe statistical reasoning will be sufficient to master these problems.

      删除
    2. 好吧,我显然需要花一会儿时间,但总的观点是显而易见的:您可以在对抗性环境中使用mar,以证明有关您自己的随机化结果。

      万岁mar!

      删除