極限における差分プライバシー付き言語生成と識別

arXiv stat.ML / 2026/4/10

💬 オピニオンSignals & Early TrendsIdeas & Deep AnalysisModels & Research

共有:

要点

本論文は、連続リリース（continual release）の設定の下で、Kleinberg と Mullainathan の「極限における言語生成（language generation in the limit）」モデルを差分プライバシー制約のもとで研究する。
任意の可算な言語の族について、定性的に実現可能性が損なわれない ε-差分プライベートな in-limit ジェネレータが存在することを示す。ただし、そのために必要なサンプル数は増加する。
目標とする言語の族が、無限の共通部分と有限の差分集合をもつ 2 つの言語を含む場合に、極限における ε-DP による言語識別が不可能であることを強く示す不可能性結果を証明する。
確率的（i.i.d. サンプリング）な変種では、著者らはプライベート識別が可能となる条件を特徴付ける。そこでは、識別可能性が敵対的（adversarial）な識別可能性と一致する一方、プライバシー制約のもとでは一致しないことを示す。
全体として、本研究は差分プライバシー下における「生成」と「識別」の間の新しい理論的相違を明らかにし、識別に関して敵対的レジームと確率的レジームの分離（separation）を含む。

Abstract

我々は、Kleinberg と Mullainathan [KM24] により最近導入されたモデルを、差分プライバシーの制約のもとで、極限における言語生成の研究を開始する。ここでは、継続的公開（continual release）モデルを考える。これは、生成器が、入力系列全体のプライバシーを保護しつつ、いずれは有効な文字列のストリームを出力しなければならないというものである。我々の最初の主結果は、可算な言語のコレクションに対しては、プライバシーは質的なコストを伴わない、という点である。すなわち、任意の可算なコレクションから極限で生成する

-差分プライベートなアルゴリズムを与える。これは、プライバシーによって学習可能性が不可能になる多くの学習設定と対照的である。しかし、プライバシーは量的なコストを課す。すなわち、サイズ k の有限なコレクションの中には、一様なプライベート生成に (k/) サンプルが必要なものがあるのに対し、非プライベートなら 1 サンプルで足りる。 続いて、より難しい問題である極限における言語識別に取り組む。ここでは、プライバシーが本質的な障壁を生み出すことを示す。具体的には、無限の共通部分と有限の差集合をもつ 2 つの言語を含むコレクションを、

-DP アルゴリズムが識別できないことを証明する。この条件は、識別に関する古典的な非プライベートの特徴付けよりもはるかに強い。次に、サンプル文字列が敵対者によって生成されるのではなく、分布から i.i.d.（独立同分布）にサンプリングされる確率的設定を考える。この場合、我々は、プライベート識別が可能であるのは、ちょうどそのコレクションが敵対モデルで識別可能であるときに限る、ことを示す。以上の結果により、生成と識別が異なる新たな次元が明らかになり、さらに識別においては、プライバシー制約によって敵対設定と確率的設定の間で分離が生じることが確立される。