回帰最小化による敵対的セミバンディット・フィードバックを用いたオンライン・コンフォーマル予測

要旨: 不確実性の定量化は、安全性が極めて重要なシステムにおいて極めて重要であり、不確実性のもとで意思決定を行わなければなりません。とりわけ、本稿では、データ点が逐次的に到着するオンライン不確実性定量化の問題を考えます。オンライン予測適合（conformal prediction）は、各時点において予測集合を動的に構築する、原理に基づくオンライン不確実性定量化の手法です。既存のオンライン予測適合の手法は、分布に関する仮定を置かずに長期的なカバレッジ保証を与える一方で、通常は真のラベルが常に観測される「完全フィードバック」設定を仮定しています。本論文では、適応的な敵対者からの部分的フィードバックによる、オンライン予測適合のための新しい学習手法を提案します。これは、真のラベルが構築した予測集合の内側にあるときにのみ明らかにされる、より困難な設定です。具体的には、各候補予測集合をアームとして扱うことで、オンライン予測適合を敵対的バンディット問題として定式化します。敵対的バンディットに関する既存のアルゴリズムに基づき、我々の手法は、学習者の後悔（regret）との結び付きを明示的に確立することで、長期的なカバレッジ保証を達成します。最後に、独立同分布（i.i.d.）および非i.i.d.の双方の設定において、提案手法の有効性を実験的に示します。すなわち、予測集合の大きさを妥当な範囲に保ちつつ、誤覆い率（miscoverage rate）を適切に制御できることを示します。