ラベル比率からブール関数を学習する難しさ

近年、ラベル比率から学習する枠組み（LLP）が機械学習において重要性を増しています。この設定では、トレーニング例がサブセットまたはバッグに集約され、例レベルの予測器を学習するためにはバッグごとの平均ラベルのみが利用可能です。これは、単位サイズのバッグの特別なケースである従来のPAC学習を一般化しています。LLPの計算学習の側面は、最近の研究（Saket, NeurIPS'21; Saket, NeurIPS'22）で調査され、LLP設定における半空間の学習のためのアルゴリズムと困難さが示されました。本研究では、LLPによるブール関数の学習の困難さに焦点を当てます。最初の結果は、OR関数と整合性のある最大2サイズのバッグのコレクションが与えられた場合、任意の常数分数のバッグを満たすための定数数のクローズを持つCNFを見つけることがNP困難であることを示しています。これは、半空間を使用してORを学習するための(2/5) -近似を提供した(Saket, NeurIPS'21)の研究とは対照的です。このため、我々の結果は、LLPによるOR学習の仮説として定数クローズCNFと半空間の分離を提供します。次に、定数tに対して、tリテラルを持つDNF（t-DNF）を使用して、そのようなバッグの1/2 + o (1) の分数を満たす困難さを証明します。通常のPAC学習において、このような困難は、ノイズのあるORを学習するためにのみ知られていました（Khot-Saket, FOCS'08）。また、パリティの学習可能性についても研究し、パリティと整合性のあるqサイズのバッグの(q/2^q-1 + o (1) ) -分数を満たすことがNP困難であることを示します。一方、ランダムパリティに基づくアルゴリズムは(1/2^q-2) -近似を達成します。