使用增强的框架,我们证明所有基于杂质的决策树学习算法(包括经典的ID3,C4.5和CART)都具有很高的噪音耐受性。我们的保证在讨厌的噪声的最强噪声模型下保持,我们在允许的噪声速率上提供了近乎匹配的上和下限。我们进一步表明,这些算法简单,长期以来一直是日常机器学习的核心,在嘈杂的环境中享受可证明的保证,这些环境是由关于决策树学习的理论文献中现有算法无与伦比的。综上所述,我们的结果增加了一项持续的研究线,该研究旨在将这些实际决策树算法的经验成功放在牢固的理论基础上。
translated by 谷歌翻译
我们提供了$ n ^ {o(\ log \ log n)} $ - 时间成员资格查询算法,用于在统一分布下统一分发的统一分布\ {\ pm 1 \} ^ n $。即使在可实现的设置中,上一个最快的运行时也是$ n ^ {o(\ log n)} $,这是ehrenfeucht和haussler的经典算法的结果。我们的算法与学习决策树的实用启发式分享了相似性,我们增加了额外的想法,以避免已知的这些启发式措施。为了分析我们的算法,我们证明了决策树的新结构结果,增强了O'Donnell,Saks,Schramm和Servedio的定理。虽然OSS定理表明每个决策树都有一个有影响力的变量,但我们展示了每个决策树如何“修剪”,以便产生的树中的每个变量都是有影响力的。
translated by 谷歌翻译
我们研究了算法收到I.I.D的统计问题中对抗噪声模型的基本问题。从分发$ \ mathcal {d} $绘制。这些对手的定义指定了允许的损坏类型(噪声模型)以及可以进行这些损坏(适应性);后者区别了唯一可以损坏分发$ \ mathcal {d} $和适应性对手的疏忽,这些对手可以损坏他们的腐败依赖于从$ \ mathcal {d} $绘制的特定样本$ s $。在这项工作中,我们调查了在文献中研究的所有噪声模型中是否有效地相当于自适应对手。具体而言,算法$ \ mathcal {a} $的行为可以在不受算法$ \ mathcal {a}'$的情况下始终受到适应性对手的存在的良好近似?我们的第一个结果表明,这确实是在所有合理的噪声模型下广泛的统计查询算法的情况。然后,我们显示在附加噪声的具体情况下,这种等价物适用于所有算法。最后,我们将所有算法和所有合理的噪声模型中的最丰富的一般性映射到最完整的普遍性的方法。
translated by 谷歌翻译
我们设计了一种算法,用于查找具有强大理论保证其性能的反事实算法。对于任何单调模型$ f:x^d \ to \ {0,1 \} $和instance $ x^\ star $,我们的算法make \ [{s(f))} \ cdot \ log d} \]查询到$ f $并返回{哪个$ f(x')\ ne f(x^\ star)$。这里$ s(f)$是$ f $的灵敏度,lipschitz常数的分散类似物,$ \ delta_f(x^\ star)$是从$ x^\ star $到其最近的反事实的距离。以前最著名的查询复杂性是$ d^{\,o(\ delta_f(x^\ star))} $,可以通过Brute-Force Local Search实现。我们进一步证明了$ s(f)^{\ omega(\ delta_f(x^\ star))} + \ omega(\ log d)$的下限我们的算法本质上是最佳的。
translated by 谷歌翻译
标签排名(LR)对应于学习一个假设的问题,以通过有限一组标签将功能映射到排名。我们采用了对LR的非参数回归方法,并获得了这一基本实际问题的理论绩效保障。我们在无噪声和嘈杂的非参数回归设置中介绍了一个用于标签排名的生成模型,并为两种情况下提供学习算法的示例复杂性界限。在无噪声环境中,我们研究了全排序的LR问题,并在高维制度中使用决策树和随机林提供计算有效的算法。在嘈杂的环境中,我们考虑使用统计观点的不完整和部分排名的LR更通用的情况,并使用多种多组分类的一种方法获得样本复杂性范围。最后,我们与实验补充了我们的理论贡献,旨在了解输入回归噪声如何影响观察到的输出。
translated by 谷歌翻译
在这项工作中,我们研究了鲁布利地学习Mallows模型的问题。我们给出了一种算法,即使其样本的常数分数是任意损坏的恒定分数,也可以准确估计中央排名。此外,我们的稳健性保证是无关的,因为我们的整体准确性不依赖于排名的替代品的数量。我们的工作可以被认为是从算法稳健统计到投票和信息聚集中的中央推理问题之一的视角的自然输注。具体而言,我们的投票规则是有效的可计算的,并且通过一大群勾结的选民无法改变其结果。
translated by 谷歌翻译
我们研究了在存在$ \ epsilon $ - 对抗异常值的高维稀疏平均值估计的问题。先前的工作为此任务获得了该任务的样本和计算有效算法,用于辅助性Subgaussian分布。在这项工作中,我们开发了第一个有效的算法,用于强大的稀疏平均值估计,而没有对协方差的先验知识。对于$ \ Mathbb r^d $上的分布,带有“认证有限”的$ t $ tum-矩和足够轻的尾巴,我们的算法达到了$ o(\ epsilon^{1-1/t})$带有样品复杂性$的错误(\ epsilon^{1-1/t}) m =(k \ log(d))^{o(t)}/\ epsilon^{2-2/t} $。对于高斯分布的特殊情况,我们的算法达到了$ \ tilde o(\ epsilon)$的接近最佳错误,带有样品复杂性$ m = o(k^4 \ mathrm {polylog}(d)(d))/\ epsilon^^ 2 $。我们的算法遵循基于方形的总和,对算法方法的证明。我们通过统计查询和低度多项式测试的下限来补充上限,提供了证据,表明我们算法实现的样本时间 - 错误权衡在质量上是最好的。
translated by 谷歌翻译
可实现和不可知性的可读性的等价性是学习理论的基本现象。与PAC学习和回归等古典设置范围的变种,近期趋势,如对冲强劲和私人学习,我们仍然缺乏统一理论;等同性的传统证据往往是不同的,并且依赖于强大的模型特异性假设,如统一的收敛和样本压缩。在这项工作中,我们给出了第一个独立的框架,解释了可实现和不可知性的可读性的等价性:三行黑箱减少简化,统一,并在各种各样的环境中扩展了我们的理解。这包括没有已知的学报的模型,例如学习任意分布假设或一般损失,以及许多其他流行的设置,例如强大的学习,部分学习,公平学习和统计查询模型。更一般地,我们认为可实现和不可知的学习的等价性实际上是我们调用属性概括的更广泛现象的特殊情况:可以满足有限的学习算法(例如\噪声公差,隐私,稳定性)的任何理想性质假设类(可能在某些变化中)延伸到任何学习的假设类。
translated by 谷歌翻译
我们研究了清单可解放的平均估计问题,而对手可能会破坏大多数数据集。具体来说,我们在$ \ mathbb {r} ^ $和参数$ 0 <\ alpha <\ frac 1 2 $中给出了一个$ $ n $ points的$ t $ points。$ \ alpha $ -flaction的点$ t $是iid来自乖巧的分发$ \ Mathcal {D} $的样本,剩余的$(1- \ alpha)$ - 分数是任意的。目标是输出小型的vectors列表,其中至少一个接近$ \ mathcal {d} $的均值。我们开发新的算法,用于列出可解码的平均值估计,实现几乎最佳的统计保证,运行时间$ O(n ^ {1 + \ epsilon_0} d)$,适用于任何固定$ \ epsilon_0> 0 $。所有先前的此问题算法都有额外的多项式因素在$ \ frac 1 \ alpha $。我们与额外技术一起利用此结果,以获得用于聚类混合物的第一个近几个线性时间算法,用于分开的良好表现良好的分布,几乎匹配谱方法的统计保证。先前的聚类算法本身依赖于$ k $ -pca的应用程序,从而产生$ \ omega(n d k)$的运行时。这标志着近二十年来这个基本统计问题的第一次运行时间改进。我们的方法的起点是基于单次矩阵乘法权重激发电位减少的$ \ Alpha \至1 $制度中的新颖和更简单的近线性时间较强的估计算法。在Diakonikolas等人的迭代多滤波技术的背景下,我们迫切地利用了这种新的算法框架。 '18,'20,提供一种使用一维投影的同时群集和下群点的方法 - 因此,绕过先前算法所需的$ k $ -pca子程序。
translated by 谷歌翻译
解决机器学习模型的公平关注是朝着实际采用现实世界自动化系统中的至关重要的一步。尽管已经开发了许多方法来从数据培训公平模型,但对这些方法对数据损坏的鲁棒性知之甚少。在这项工作中,我们考虑在最坏情况下的数据操作下进行公平意识学习。我们表明,在某些情况下,对手可能会迫使任何学习者返回过度偏见的分类器,无论样本量如何,有或没有降解的准确性,并且多余的偏见的强度会增加数据中数据不足的受保护组的学习问题,而数据中有代表性不足的组。我们还证明,我们的硬度结果紧密到不断的因素。为此,我们研究了两种自然学习算法,以优化准确性和公平性,并表明这些算法在损坏比和较大数据限制中受保护的群体频率方面享有订单最佳的保证。
translated by 谷歌翻译
我们考虑解释任意黑箱型号的预测的问题$ f $:给定查询访问$ f $和实例$ x $,输出一小组$ x $的功能,其中有基本上确定$ f( x)$。我们设计了一种高效的算法,可提供证明的简洁和返回的解释的精度。现有算法是有效的,但缺乏这种保证,或实现了这种保证,但效率低下。我们通过连接{\ SL隐式}学习决策树的问题获得算法。这种学习任务的隐式性质即使在$ F $的复杂程度需要一个艰难的大代理决策树时也允许有效的算法。我们通过从学习理论,局部计算算法和复杂性理论中汇集技术来解决隐式学习问题。我们的“通过隐式学习解释”的方法,共享两个先前分散的分歧方法的元素,用于后期的解释,全局和本地解释,我们使它享有两者的优势。
translated by 谷歌翻译
给定真实的假设类$ \ mathcal {h} $,我们在什么条件下调查有一个差异的私有算法,它从$ \ mathcal {h} $给出的最佳假设.I.i.d.数据。灵感来自最近的成果的二进制分类的相关环境(Alon等,2019; Bun等,2020),其中显示了二进制类的在线学习是必要的,并且足以追随其私人学习,Jung等人。 (2020)显示,在回归的设置中,$ \ mathcal {h} $的在线学习是私人可读性所必需的。这里的在线学习$ \ mathcal {h} $的特点是其$ \ eta $-sequentient胖胖子的优势,$ {\ rm sfat} _ \ eta(\ mathcal {h})$,适用于所有$ \ eta> 0 $。就足够的私人学习条件而言,Jung等人。 (2020)显示$ \ mathcal {h} $私下学习,如果$ \ lim _ {\ eta \ downarrow 0} {\ rm sfat} _ \ eta(\ mathcal {h})$是有限的,这是一个相当限制的健康)状况。我们展示了在轻松的条件下,\ LIM \ INF _ {\ eta \ downarrow 0} \ eta \ cdot {\ rm sfat} _ \ eta(\ mathcal {h})= 0 $,$ \ mathcal {h} $私人学习,为\ \ rm sfat} _ \ eta(\ mathcal {h})$ \ eta \ dockarrow 0 $ divering建立第一个非参数私人学习保证。我们的技术涉及一种新颖的过滤过程,以输出非参数函数类的稳定假设。
translated by 谷歌翻译
我们在高斯分布下使用Massart噪声与Massart噪声进行PAC学习半个空间的问题。在Massart模型中,允许对手将每个点$ \ mathbf {x} $的标签与未知概率$ \ eta(\ mathbf {x})\ leq \ eta $,用于某些参数$ \ eta \ [0,1 / 2] $。目标是找到一个假设$ \ mathrm {opt} + \ epsilon $的错误分类错误,其中$ \ mathrm {opt} $是目标半空间的错误。此前已经在两个假设下研究了这个问题:(i)目标半空间是同质的(即,分离超平面通过原点),并且(ii)参数$ \ eta $严格小于$ 1/2 $。在此工作之前,当除去这些假设中的任何一个时,不知道非增长的界限。我们研究了一般问题并建立以下内容:对于$ \ eta <1/2 $,我们为一般半个空间提供了一个学习算法,采用样本和计算复杂度$ d ^ {o_ {\ eta}(\ log(1 / \ gamma) )))}} \ mathrm {poly}(1 / \ epsilon)$,其中$ \ gamma = \ max \ {\ epsilon,\ min \ {\ mathbf {pr} [f(\ mathbf {x})= 1], \ mathbf {pr} [f(\ mathbf {x})= -1] \} \} $是目标半空间$ f $的偏差。现有的高效算法只能处理$ \ gamma = 1/2 $的特殊情况。有趣的是,我们建立了$ d ^ {\ oomega(\ log(\ log(\ log(\ log))}}的质量匹配的下限,而是任何统计查询(SQ)算法的复杂性。对于$ \ eta = 1/2 $,我们为一般半空间提供了一个学习算法,具有样本和计算复杂度$ o_ \ epsilon(1)d ^ {o(\ log(1 / epsilon))} $。即使对于均匀半空间的子类,这个结果也是新的;均匀Massart半个空间的现有算法为$ \ eta = 1/2 $提供可持续的保证。我们与D ^ {\ omega(\ log(\ log(\ log(\ log(\ epsilon))} $的近似匹配的sq下限补充了我们的上限,这甚至可以为同类半空间的特殊情况而保持。
translated by 谷歌翻译
我们建立了最佳的统计查询(SQ)下限,以鲁棒地学习某些离散高维分布的家庭。特别是,我们表明,没有访问$ \ epsilon $ -Cruntupted二进制产品分布的有效SQ算法可以在$ \ ell_2 $ -error $ o(\ epsilon \ sqrt {\ log(\ log(1/\ epsilon))内学习其平均值})$。同样,我们表明,没有访问$ \ epsilon $ - 腐败的铁磁高温岛模型的有效SQ算法可以学习到总变量距离$ O(\ Epsilon \ log(1/\ Epsilon))$。我们的SQ下限符合这些问题已知算法的错误保证,提供证据表明这些任务的当前上限是最好的。在技​​术层面上,我们为离散的高维分布开发了一个通用的SQ下限,从低维矩匹配构建体开始,我们认为这将找到其他应用程序。此外,我们介绍了新的想法,以分析这些矩匹配的结构,以进行离散的单变量分布。
translated by 谷歌翻译
我们给出了\ emph {list-codobable协方差估计}的第一个多项式时间算法。对于任何$ \ alpha> 0 $,我们的算法获取输入样本$ y \ subseteq \ subseteq \ mathbb {r}^d $ size $ n \ geq d^{\ mathsf {poly}(1/\ alpha)} $获得通过对抗损坏I.I.D的$(1- \ alpha)n $点。从高斯分布中的样本$ x $ size $ n $,其未知平均值$ \ mu _*$和协方差$ \ sigma _*$。在$ n^{\ mathsf {poly}(1/\ alpha)} $ time中,它输出$ k = k(\ alpha)=(1/\ alpha)^{\ mathsf {poly}的常数大小列表(1/\ alpha)} $候选参数,具有高概率,包含$(\ hat {\ mu},\ hat {\ sigma})$,使得总变化距离$ tv(\ Mathcal {n}(n})(n}(n})( \ mu _*,\ sigma _*),\ Mathcal {n}(\ hat {\ mu},\ hat {\ sigma}))<1-o _ {\ alpha}(1)$。这是距离的统计上最强的概念,意味着具有独立尺寸误差的参数的乘法光谱和相对Frobenius距离近似。我们的算法更普遍地适用于$(1- \ alpha)$ - 任何具有低度平方总和证书的分布$ d $的损坏,这是两个自然分析属性的:1)一维边际和抗浓度2)2度多项式的超收缩率。在我们工作之前,估计可定性设置的协方差的唯一已知结果是针对Karmarkar,Klivans和Kothari(2019),Raghavendra和Yau(2019和2019和2019和2019和2019年)的特殊情况。 2020年)和巴克西(Bakshi)和科塔里(Kothari)(2020年)。这些结果需要超级物理时间,以在基础维度中获得任何子构误差。我们的结果意味着第一个多项式\ emph {extcect}算法,用于列表可解码的线性回归和子空间恢复,尤其允许获得$ 2^{ - \ Mathsf { - \ Mathsf {poly}(d)} $多项式时间错误。我们的结果还意味着改进了用于聚类非球体混合物的算法。
translated by 谷歌翻译
我们研究了$ N $节点上稳健地估计参数$ P $'ENY ACLY图的问题,其中$ \ gamma $小点的节点可能是对抗的。在展示规范估计器的缺陷之后,我们设计了一种计算上有效的频谱算法,估计$ P $高精度$ \ tilde o(\ sqrt {p(1-p)} / n + \ gamma \ sqrt {p(1-p)} / \ sqrt {n} + \ gamma / n)$ for $ \ gamma <1/60 $。此外,我们为所有$ \ Gamma <1/2 $,信息定理限制提供了一种效率低下的算法。最后,我们证明了几乎匹配的统计下限,表明我们的算法的错误是最佳的对数因子。
translated by 谷歌翻译
我们研究无名概率分布的无分发物业测试和学习问题是超过$ \ mathbb {r} ^ d $的产品分布。对于许多重要的功能,例如半空间,多项式阈值函数,凸集和$ k $ -alternation函数的交叉点,所知的算法具有复杂性,这取决于分配的支持大小,或者仅被证明仅工作对于产品分布的具体例子。我们介绍了一般方法,我们调用DownS采样,解决了这些问题。 Downs采样使用对产品分布的“直线等异仪”的概念,这进一步加强了等偏移,测试和学习之间的连接。使用这种技术,我们在$ \ mathbb {r} ^ d $的产品分布下获得了新的高效分布算法:1。用于函数$ [n] ^ d \的非自适应,单调单调测试的更简单证明\ {0,1 \} $,并改进了对未知产品分布的单调性的样本复杂性,从$ O(d ^ 7)$ [黑色,chakrabarty,&seshadhri,soda 2020]到$ \ widetilde o(d ^ 3)$。 2.多项式禁止学习算法,用于恒定数量的半空间和恒定程度多项式阈值函数。 3. $ \ exp(o(d \ log(dk)))$ - 时间不可知学习算法,以及$ \ exp(o(d \ log(dk)))$ - 样本容差测试仪,用于$的函数K $凸套;和2 ^ {\ widetilde o(d)} $ satmas的单面测试仪,用于凸套。 4. $ \ exp(\ widetilde o(k \ sqrt d))$ - 时间可靠学习算法,以$ k $ -alternation函数,以及具有相同复杂性的基于样本的容忍测试仪。
translated by 谷歌翻译
Many scientific and engineering challenges-ranging from personalized medicine to customized marketing recommendations-require an understanding of treatment effect heterogeneity. In this paper, we develop a non-parametric causal forest for estimating heterogeneous treatment effects that extends Breiman's widely used random forest algorithm. In the potential outcomes framework with unconfoundedness, we show that causal forests are pointwise consistent for the true treatment effect, and have an asymptotically Gaussian and centered sampling distribution. We also discuss a practical method for constructing asymptotic confidence intervals for the true treatment effect that are centered at the causal forest estimates. Our theoretical results rely on a generic Gaussian theory for a large family of random forest algorithms. To our knowledge, this is the first set of results that allows any type of random forest, including classification and regression forests, to be used for provably valid statistical inference. In experiments, we find causal forests to be substantially more powerful than classical methods based on nearest-neighbor matching, especially in the presence of irrelevant covariates.
translated by 谷歌翻译
我们考虑从数据学习树结构ising模型的问题,使得使用模型计算的后续预测是准确的。具体而言,我们的目标是学习一个模型,使得小组变量$ S $的后海报$ p(x_i | x_s)$。自推出超过50年以来,有效计算最大似然树的Chow-Liu算法一直是学习树结构图形模型的基准算法。 [BK19]示出了关于以预测的局部总变化损耗的CHOW-LIU算法的样本复杂性的界限。虽然这些结果表明,即使在恢复真正的基础图中也可以学习有用的模型是不可能的,它们的绑定取决于相互作用的最大强度,因此不会达到信息理论的最佳选择。在本文中,我们介绍了一种新的算法,仔细结合了Chow-Liu算法的元素,以便在预测的损失下有效地和最佳地学习树ising模型。我们的算法对模型拼写和对抗损坏具有鲁棒性。相比之下,我们表明庆祝的Chow-Liu算法可以任意次优。
translated by 谷歌翻译
公司跨行业对机器学习(ML)的快速传播采用了重大的监管挑战。一个这样的挑战就是可伸缩性:监管机构如何有效地审核这些ML模型,以确保它们是公平的?在本文中,我们启动基于查询的审计算法的研究,这些算法可以以查询有效的方式估算ML模型的人口统计学率。我们提出了一种最佳的确定性算法,以及具有可比保证的实用随机,甲骨文效率的算法。此外,我们进一步了解了随机活动公平估计算法的最佳查询复杂性。我们对主动公平估计的首次探索旨在将AI治理置于更坚定的理论基础上。
translated by 谷歌翻译