从标签比例学习布尔函数的难度

Mar, 2024

Hardness of Learning Boolean Functions from Label Proportions

Venkatesan Guruswami, Rishi Saket

TL;DR学习标签比例 (LLP) 框架在机器学习中日益重要。该研究关注 LLP 学习布尔函数的不可计算性，发现寻找满足 OR 函数一部分常数比例的子集 (包) 的恒定个子句的 CNF 是 NP 困难问题，同时探讨了学习偶函数的可行性，发现利用随机偶算法可以得到近似解。

Abstract

In recent years the framework of learning from label proportions (llp) has been gaining importance in machine learning. In this setting, the training examples are aggregated into subsets or bags and only the aver

learning from label proportions llp computational learning boolean functions halfspaces

发现论文，激发创造

学习标签比例的复杂性

本文研究了一种学习模型，即以标签比例学习为代表的 LLP 学习模型，通过计算学习复杂度和 PAC 学习的比较，以及 VC 类的研究，得出了该模型的基础特性。

Apr, 2020

从标签比例中 PAC 学习线性阈值

基于标签比例（LLP）的学习是一种监督学习的推广，通过一些包含特征向量集合或袋子（实例），以及每个袋子的平均实例标签来提供训练数据，目标是训练一个良好的实例分类器。在本文中，我们展示了使用 LTFs 能够在给定某些具有一定标签比例的随机袋子时，通过访问这些数据对线性阈值函数（LTFs）进行有效学习的可能性。我们的算法使用次高斯浓度界限估计均值和协方差矩阵，并展示了如何应用于有效采样袋子以近似法向量。通过在袋子设置中提供新的泛化误差界限，我们展示了如何识别具有较低误差的假设 LTF。

Oct, 2023

从标签比例中学习的乐观速率

弱监督学习问题中的主题是来自标签比例的学习，研究了多种实现分类损失的标准，包括经典的实证比例风险最小化、去偏差的比例平方损失和最近提出的 EasyLLP 学习规则，这些规则在可实现和不可知设置中均取得了 “乐观速率”，并且在样本复杂度上接近最优（log 因子）。

Jun, 2024

学习半空间的复杂性理论限制

该研究讨论了在固定且未知的分布和自然条件下的半空间学习问题，证明了最坏情况下的性能和效率的复杂性。

May, 2015

学习标签比例

该文章针对基于 Label Proportions 的学习环境提出了一个新的学习框架 ——Empirical Proportion Risk Minimization，利用该学习框架可以构建更好的学习算法，在政治学、营销、医疗保健和计算机视觉等领域有广泛应用。

Feb, 2014

基于标签比例学习的两阶段训练

该论文研究了从标签比例中学习的问题，针对现有基于深度学习的方法中优化目标与给定比例不一致的问题，通过对分类器施加比例验证的连续训练阶段以及引入混合策略和 Symmetric Crossentropy 方法来降低标签噪声，提高了分类性能。

May, 2021

利用一致性正则化学习标签比例

本文提出了一种新的方法，通过引入半监督学习中的一种流行概念 - 一致性正则化，解决了标签比例学习（LLP）的问题，实现了更好的分类器表现，同时也提供了更好符合实际应用场景的非均匀背景生成和基于验证的参数选择过程。

Oct, 2019

基于标签比例的文本分类学习

在隐私设置和弱监督下，我们提出了一种新的基线技术 DLLP 的不规则性，以及与 LLP 下的通用性边界争论相结合的基于自我监督目标的新公式，该方法在 87% 的实验配置中比基线模型取得更好的结果，实验涵盖了长篇和短篇文本的大规模模型，并使用多个度量标准进行评估。

Oct, 2023

可解释的二级布尔规则学习用于分类

本文提出以布尔规则为基础的分类方法，并通过基于整数规划和 Hamming 距离的算法，寻求简单分类规则和分类准确性之间的平衡，实现优于一级规则的分类效果。

Nov, 2015

LLP-Bench：一种用于从标签比例学习的大规模表格基准

该研究论文介绍了学习标签比例（LLP）任务，提出了一个包含大规模表格 LLP 基准数据集（LLP-Bench），并在该数据集上评估了 9 种先进的和流行的表格 LLP 技术的性能。

Oct, 2023