部分フィードバックによるオンライン学習
arXiv stat.ML / 2026/4/3
💬 オピニオンIdeas & Deep AnalysisModels & Research
要点
- 本論文では、新しい学習プロトコルである部分フィードバックオンライン学習を提案する。各入力には複数の許容ラベルがある一方で、学習者は各ラウンドで許容ラベルのうち1つしか受け取らない。
- 古典的なバージョンスペース手法はこの部分フィードバック設定には直接適用できないことを示し、学習可能性の解析を可能にするためにコレクション・バージョンスペースを導入する。
- 著者らは、集合が実現可能（set-realizable）な状況において、2つの新しい複雑度指標：部分フィードバックリトルストーン次元（PFLdim）および部分フィードバック測度シャッタリング次元（PMSdim）を用いて、厳密な学習可能性およびミニマックス・リグレットの特徴付けを導出する。
- 決定論的な学習可能性と確率論的な学習可能性が一致することをもたらすネストされた包含条件を特定し、Ramanら（2024b）による未解決問題を解決する。
- 集合実現可能性を超えて、本論文は強い限界も示す。仮説空間のサイズが2であっても、ミニマックス・リグレットが線形になり得ることを示し、有利な理論を拡張することへの根本的な障壁を示唆する。
