我们调查了布尔功能多任务函数多任务的计算效率,这些函数在$ d $二维的超立方体上通过大小$ k \ ll d $在所有任务中共享的功能表示相关。我们提供了一个多项式时间多任务学习算法,用于带有保证金$ \ gamma $的概念类别的概念类别,该算法基于同时增强技术,仅需要$ \ textrm {poly}(k/\ gamma)和$ \ textrm {poly}(k \ log(d)/\ gamma)$样本总共。此外,我们证明了一个计算分离,表明假设存在一个无法在属性效率模型中学习的概念类,我们可以构建另一个可以在属性效率模型中学到的概念类,但不能是多任务。有效学习的 - 多任务学习此概念类要么需要超级顺序的时间复杂性,要么需要更大的样本总数。
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 谷歌翻译
作者最近给出了$ n^{o(\ log \ log n)} $时间成员资格查询算法,用于在统一分布下正确学习决策树(Blanc等,2021)。此问题的先前最快算法以$ n^{o(\ log n)} $ time运行,这是Ehrenfeucht和Haussler(1989)的经典算法,这是无分配设置的经典算法。在本文中,我们强调了获得多项式时间算法的自然开放问题,讨论获得它的可能途径以及我们认为具有独立利益的状态中级里程碑。
translated by 谷歌翻译
使用增强的框架,我们证明所有基于杂质的决策树学习算法(包括经典的ID3,C4.5和CART)都具有很高的噪音耐受性。我们的保证在讨厌的噪声的最强噪声模型下保持,我们在允许的噪声速率上提供了近乎匹配的上和下限。我们进一步表明,这些算法简单,长期以来一直是日常机器学习的核心,在嘈杂的环境中享受可证明的保证,这些环境是由关于决策树学习的理论文献中现有算法无与伦比的。综上所述,我们的结果增加了一项持续的研究线,该研究旨在将这些实际决策树算法的经验成功放在牢固的理论基础上。
translated by 谷歌翻译
我们研究了算法收到I.I.D的统计问题中对抗噪声模型的基本问题。从分发$ \ mathcal {d} $绘制。这些对手的定义指定了允许的损坏类型(噪声模型)以及可以进行这些损坏(适应性);后者区别了唯一可以损坏分发$ \ mathcal {d} $和适应性对手的疏忽,这些对手可以损坏他们的腐败依赖于从$ \ mathcal {d} $绘制的特定样本$ s $。在这项工作中,我们调查了在文献中研究的所有噪声模型中是否有效地相当于自适应对手。具体而言,算法$ \ mathcal {a} $的行为可以在不受算法$ \ mathcal {a}'$的情况下始终受到适应性对手的存在的良好近似?我们的第一个结果表明,这确实是在所有合理的噪声模型下广泛的统计查询算法的情况。然后,我们显示在附加噪声的具体情况下,这种等价物适用于所有算法。最后,我们将所有算法和所有合理的噪声模型中的最丰富的一般性映射到最完整的普遍性的方法。
translated by 谷歌翻译
我们考虑解释任意黑箱型号的预测的问题$ f $:给定查询访问$ f $和实例$ x $,输出一小组$ x $的功能,其中有基本上确定$ f( x)$。我们设计了一种高效的算法,可提供证明的简洁和返回的解释的精度。现有算法是有效的,但缺乏这种保证,或实现了这种保证,但效率低下。我们通过连接{\ SL隐式}学习决策树的问题获得算法。这种学习任务的隐式性质即使在$ F $的复杂程度需要一个艰难的大代理决策树时也允许有效的算法。我们通过从学习理论,局部计算算法和复杂性理论中汇集技术来解决隐式学习问题。我们的“通过隐式学习解释”的方法,共享两个先前分散的分歧方法的元素,用于后期的解释,全局和本地解释,我们使它享有两者的优势。
translated by 谷歌翻译
我们提供了$ n ^ {o(\ log \ log n)} $ - 时间成员资格查询算法,用于在统一分布下统一分发的统一分布\ {\ pm 1 \} ^ n $。即使在可实现的设置中,上一个最快的运行时也是$ n ^ {o(\ log n)} $,这是ehrenfeucht和haussler的经典算法的结果。我们的算法与学习决策树的实用启发式分享了相似性,我们增加了额外的想法,以避免已知的这些启发式措施。为了分析我们的算法,我们证明了决策树的新结构结果,增强了O'Donnell,Saks,Schramm和Servedio的定理。虽然OSS定理表明每个决策树都有一个有影响力的变量,但我们展示了每个决策树如何“修剪”,以便产生的树中的每个变量都是有影响力的。
translated by 谷歌翻译
Although many studies have successfully applied transfer learning to medical image segmentation, very few of them have investigated the selection strategy when multiple source tasks are available for transfer. In this paper, we propose a prior knowledge guided and transferability based framework to select the best source tasks among a collection of brain image segmentation tasks, to improve the transfer learning performance on the given target task. The framework consists of modality analysis, RoI (region of interest) analysis, and transferability estimation, such that the source task selection can be refined step by step. Specifically, we adapt the state-of-the-art analytical transferability estimation metrics to medical image segmentation tasks and further show that their performance can be significantly boosted by filtering candidate source tasks based on modality and RoI characteristics. Our experiments on brain matter, brain tumor, and white matter hyperintensities segmentation datasets reveal that transferring from different tasks under the same modality is often more successful than transferring from the same task under different modalities. Furthermore, within the same modality, transferring from the source task that has stronger RoI shape similarity with the target task can significantly improve the final transfer performance. And such similarity can be captured using the Structural Similarity index in the label space.
translated by 谷歌翻译
Modern deep neural networks have achieved superhuman performance in tasks from image classification to game play. Surprisingly, these various complex systems with massive amounts of parameters exhibit the same remarkable structural properties in their last-layer features and classifiers across canonical datasets. This phenomenon is known as "Neural Collapse," and it was discovered empirically by Papyan et al. \cite{Papyan20}. Recent papers have theoretically shown the global solutions to the training network problem under a simplified "unconstrained feature model" exhibiting this phenomenon. We take a step further and prove the Neural Collapse occurrence for deep linear network for the popular mean squared error (MSE) and cross entropy (CE) loss. Furthermore, we extend our research to imbalanced data for MSE loss and present the first geometric analysis for Neural Collapse under this setting.
translated by 谷歌翻译
In this paper we derive a PAC-Bayesian-Like error bound for a class of stochastic dynamical systems with inputs, namely, for linear time-invariant stochastic state-space models (stochastic LTI systems for short). This class of systems is widely used in control engineering and econometrics, in particular, they represent a special case of recurrent neural networks. In this paper we 1) formalize the learning problem for stochastic LTI systems with inputs, 2) derive a PAC-Bayesian-Like error bound for such systems, 3) discuss various consequences of this error bound.
translated by 谷歌翻译