图 书 馆
线性阈值函数的独立分布的可扩展性Distribution-Independent Evolvability of Linear Threshold Functions |
|
| 课程网址: | http://videolectures.net/colt2011_feldman_functions/ |
| 主讲教师: | Vitaly Feldman |
| 开课单位: | IBM公司 |
| 开课时间: | 2011-08-02 |
| 课程语种: | 英语 |
| 中文简介: |  Valiant（2007）的可演化性模型对获取有用功能的演化过程进行了建模，这些功能是从随机示例中学习的一种受限形式。线性阈值函数及其各种子类（例如，合取和决策列表）在学习理论中起着基本作用，因此，其可扩展性一直是Valiant框架研究的主要重点（2007年）。有关模型的主要开放问题之一是合取是否独立于可演化的分布（Feldman和Valiant，2008年）。我们证明答案是否定的。我们的证明基于概念类的新组合参数，该参数降低了从关联中学习的复杂性。我们用一个证明来比较下限，该证明是通过简单的变异算法独立地在数据点上具有不可忽略的余量的线性阈值函数是可演化的分布。我们的算法依赖于非线性损失函数来选择假设，而不是Valiant（2007）原始定义中的0 1损失。可进化性的证明要求损失函数满足若干温和条件，例如，可以通过其他几项研究中的二次损失函数来满足这些条件（Michael，2007； Feldman，2009； P.Valiant，2010）。我们的进化算法的一个重要属性是单调性，即该算法在不降低性能的情况下保证了可进化性。以前，单调演化仅在与二次损失结合时才表现出来（Feldman，2009），或者在域上的分布受到严格限制时才表现出来（Michael，2007； Feldman，2009； Kanade等人，2010）。 |
| 课程简介: | Valiant’s (2007) model of evolvability models the evolutionary process of acquiring useful functionality as a restricted form of learning from random examples. Linear threshold functions and their various subclasses, such as conjunctions and decision lists, play a fundamental role in learning theory and hence their evolvability has been the primary focus of research on Valiant’s framework (2007). One of the main open problems regarding the model is whether conjunctions are evolvable distribution-independently (Feldman and Valiant, 2008). We show that the answer is negative. Our proof is based on a new combinatorial parameter of a concept class that lower-bounds the complexity of learning from correlations. We contrast the lower bound with a proof that linear threshold functions having a non-negligible margin on the data points are evolvable distribution-independently via a simple mutation algorithm. Our algorithm relies on a non-linear loss function being used to select the hypotheses instead of 0-1 loss in Valiant’s (2007) original definition. The proof of evolvability requires that the loss function satisfies several mild conditions that are, for example, satisfied by the quadratic loss function studied in several other works (Michael, 2007; Feldman, 2009; P. Valiant, 2010). An important property of our evolution algorithm is monotonicity, that is the algorithm guarantees evolvability without any decreases in performance. Previously, monotone evolvability was only shown for conjunctions with quadratic loss (Feldman, 2009) or when the distribution on the domain is severely restricted (Michael, 2007; Feldman, 2009; Kanade et al. , 2010). |
| 关 键 词: | 机械学习; 线性模型; 分布函数 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2021-01-30：nkq |
| 阅读次数: | 48 |