はじめに

これは、LLM の生成テキストに電子透かしを入れる手法について書かれた論文です。
ICML2023 のベストペーパーの一つに挙げられています。

生成AIで作られた画像やテキストがネット上に氾濫していますが、生成AIモデルがこれらのデータを学習すると、そのモデルが生成するデータの品質が劣化したり[1]、多様性を失ったりする[2]ことが報告されています。
これらを回避するには、学習データに生成AIで作られたものを除外する必要がありますが、電子透かしはその有効な手段となり得るかもしれません。

電子透かし

電子透かしというと、お札の透かしのように、LLM が生成するテキストに何か「余分なデータ（＝透かし）」を入れ込むようなイメージが浮かびますが、この論文の手法はそうではありません。奇抜な発想で「透かし」を入れ込みます。それを説明しましょう。

LLM は次の単語（実際は「トークン」）を生成する際に、トークン確率ベクトル$\boldsymbol{p}=(p_1,\dots,p_N)$を参照します。ここで、$N$は語彙数（トークンの異なり数）で、$p_k$ は次トークンとして $k$ 番目のトークンを出力する確率です。つまり、LLMは、この確率を見て次トークンを出力します。もっとも単純な場合は、最大確率を与えるトークンを選ぶでしょう。この戦略では、決定的・再現性のある出力が得られます。

もっと多様な出力になるようにするには、トークン確率ベクトル $\boldsymbol{p}$ の要素のトップ$P$ の中からランダムに出力トークンを選んだり、あるいは、確率があるしきい値以上になる要素を選んで、その中からランダムに出力トークンを選んだりします（これらは、いわゆる Top P や Temperature といったChatGPTのハイパーパラメータの設定を行うことにより実現します）。

さて、次トークンの出力候補である$N$個のトークンを、たとえばランダムに半分に分割して、一方をレッドリスト、もう一方をグリーンリストと呼ぶことにしましょう。そして、次トークンの出力は必ずグリーンリストから選択するようにするとどうでなるしょうか。LLMが生成するテキストは、グリーンリストのトークンのみを使って作られることになります。実は、これが「電子透かし」になるのです。だって、こんな仕組みを知らない人間が作ったテキストは、レッドリストからのトークンが半分で、グリーンリストからのトークンが半分になるでしょう。それに対して LLM が生成するテキストはグリーンリストのトークンしか使わないのですから、一目瞭然です。

そんなことして大丈夫なの？

皆さんの中には語彙を半分にしてLLMが生成するテキストの品質を保てるの？と心配される方がいるかもしれません。けれども、私たちが使っている単語には類義語がたくさんあります。ある概念を意味する単語はこの1個しかない、というのはかなり稀なことです。ですから、語彙を半分にしてもそんなにテキストの品質が落ちることはないでしょう（あなたはすべての単語を知っていて、いつもそれらの単語をくまなく使っていますか？）。だって、Top P や Temperature の設定を行なえば、必ずしも確率が最大の単語を出力するわけではないので、この状況（使用できる語彙が半分になる状況）とさして変わりません。

それから、語彙をレッドリストとグリーンリストに分ける作業は、毎回のトークン出力時に行います。再現性を保つため（再現性が保てなければ電子透かしの確認のしようがない！）、現在のトークンを乱数の種にして、乱数を作り、それに基づいてレッドリストとグリーンリストに分割します。

どうやって電子透かしを検出するの？

さて、こうして生成したテキストの電子透かしを検出するにはどうしたらよいでしょうか？これは、先にも書いたように、テキスト中に「不自然に」グリーンリストのトークンばかりが並んでいたら、これは人間が書いたものではないと疑うことができます。でも、この「不自然に」というのは、人間が見れば感じるかもしれませんが、コンピュータはどうやってその「不自然さ」を判断すれば良いのでしょうか。何らかの客観的な基準が必要です。

そこで登場するのが、伝統的な統計手法である「検定」です。「検定」のスキームはこうです。まず、証明したいこと（ここでは、「このテキストには電子透かしがある」あるいは「このテキストは LLM が生成したものである」というのが証明したいことです）を否定するような仮説を立てます（この場合は「このテキストは LLM が生成したものではない」、あるいは「このテキストはレッドリストの存在を知らない人間が書いたものである」）。この仮説を「帰無仮説」といい、$H_0$で表します（先に示した「証明したいこと」を「対立仮説」といい、$H_1$で表します）。次に、帰無仮説に基づいて、今手元にあるテキストが作られる確率を求めます。「レッドリストの存在を知らない人間が書いた場合、このテキストが生成される確率は〇〇だ」とった具合です。この確率〇〇を$p$値といいます。

$p$値があまりにも小さい場合はどう考えたらよいのでしょうか？たとえば、帰無仮説の下で、このテキストが生成される確率は1% ($p=0.01$) だとしたら？
おそらく、その場合は、帰無仮説が正しくないと考えるのが自然でしょう。そこで、ある基準になる確率（これを有意確率といい、$\alpha$で表します）を定め、この確率を下回ったら帰無仮説を棄却する（つまり対立仮説を採択する）という戦略をとります。$\alpha$は、0.05 や 0.01 に設定するのが普通です。

p値はどのようにして計算するの？

この論文に書いてある帰無仮説$H_0$を以下に示します。

$H_0:$テキストシーケンスは、レッドリストのルールを全く知らない状態で生成される。

この帰無仮説の下で、テキストシーケンスが得られる確率（$p$値）を求めましょう。
いま、テキストシーケンスの長さを $T$ 、テキストシーケンスを構成するトークンを $s_1,\cdots,s_T$とします。帰無仮説 $H_0$ の下で、$s_1$が得られる確率 $p$（これは $p$ 値の $p$ とは違うことに注意してください）はいくらでしょうか？

グリーンリストに含まれるトークンはトークン全体の半分ですから、当然 $p=1/2$ です。したがってテキストシーケンス全体がグリーンリストのトークンからできている場合、このテキストシーケンスが得られる確率は $p^T=(1/2)^T$ です。テキストシーケンス長 $T$ が10であれば、この値は $(1/2)^{10}=1/1024=0.000977$ になります。すごく小さい値ですね。もし、有意確率 $\alpha$ を $0.05$ に設定した場合、$p < \alpha$ になるので、帰無仮説 $H_0$ は棄却されます。つまり、このテキストシーケンスは LLM が生成したものだと判定されるのです。

余談ですが、何かを行ったときに起こる結果が2つしかない試行（たとえば、コインを投げて表が出れば勝ち、裏が出たら負けといった試行）のことを「ベルヌーイ試行」といいます。このテキストシーケンスは、その構成要素であるトークンがレッドリストに含まれるか、グリーンリストに含まれるか、まさに２つに一つなので、ベルヌーイ試行と考えることができます。

では、LLM が生成したテキストを人が修正したらどうなるでしょう？テキストシーケンスにはレッドリストのトークンが混ざるかもしれません。そこで、長さ $T$ のテキストシーケンスにグリーンリストのトークンが $|s|_G$ 個含まれる場合の帰無仮説 $H_0$ の下でのテキスト生成確率 $P(X=|s|_G)$ を計算してみましょう。この場合のテキスト生成確率は二項分布に従います。二項分布とは、ベルヌーイ試行を $T$ 回行って、成功する（この場合は、グリーンリストのトークンが出現する）回数が従う確率分布です。したがって、

$$P(X=|s|_G) = \dbinom{T}{|s|_G} p^{|s|_G} (1 - p)^{T-|s|_G} \quad・・・\quad(1) $$

ここで、$\dbinom{T}{|s|_G}$ は $T$ 個のトークン列中からグリーンリストのトークンが占める $|s|_G$ 個の位置を決める組み合わせの数で、$p^{|s|_G}$ はグリーンリストのトークンが $|s|_G$ 個出現する確率、$(1 - p)^{T-|s|_G}$ はレッドリストのトークンが $T-|s|_G$ 個出現する確率です。

検出しきい値 z

この論文では、検出しきい値 $z$ なる変数を使って電子透かしの検出を行っています。検出しきい値の説明に入る前に、前節に登場した二項分布の性質についてここでまとめておきます。導出などの詳細は、たとえばこのサイトを参照してください。まず、二項分布の平均値 $\mu$、分散 $\sigma^2$ は次のようになります。

\begin{align}
\mu &= Tp \quad・・・\quad(2)  \\ \sigma^2 &= Tp(1-p) \quad・・・\quad(3) 
\end{align}

また、二項分布は、トークンシーケンス長 $T$ が長く、かつ $np \gg 1$ のとき、以下のように正規分布で近似できます。

$$P(X=|s|_G) = \frac{1}{\sqrt{2\pi\sigma^2}}\exp{\left(-\frac{(|s|_G-\mu)^2}{2\sigma^2}\right)} \quad・・・\quad(4)$$

さて、準備が整ったので検出しきい値の説明を行います。いま、

$$ z = \frac{|s|_G - \mu}{\sigma} \quad・・・\quad(5) $$

とします。これは、Z得点（あるいは、$z$値、$z$スコア）と呼ばれるもので、(4)式で与えられる正規分布を平均が $0$、標準偏差が $1$ になるように変換します。下図に示すように、Z得点を指定すると $\alpha$ の値が一意に決まるので、電子透かしの検定の基準として有意水準 $\alpha$ の代わりZ得点を用いることができます。そして、この論文ではこれを検出しきい値$z$と呼んでいます。

Fig.1 検出しきい値

$z=4$ にすると $\alpha=3.17\times10^{-5}$ になります。かなり小さい値です（前述したように、普通は $\alpha=0.05$ あるいは $\alpha=0.01$ とします）。この論文ではこの $z=4$ を電子透かしの検定の基準にしています。

何トークンあれば検出できる？

ここまでの話では、LLM はグリーンリストのトークンしか出力しないはずだから、レッドリストのトークンに出くわしたら、それは人間が作成したものだと判定していいでしょう。そこで、何トークンあれば電子透かしを検出できるかを計算してみましょう。ここでも、検出しきい値は$z=4$ $(\alpha=3.17\times10^{-5})$を使うものとします。考え方はこうです。

(5)式に(2)式、(3)式を代入すると

$$ z = \frac{|s|_G - Tp}{\sqrt{Tp(1-p)}} \quad・・・\quad(6) $$

となります。いま、語彙全体をレッドリストとグリーンリストにランダムに2分割しているので、$p=1/2$です。これを(6)式に代入すると

$$ z = \frac{2(|s|_G - T/2)}{\sqrt{T}} \quad・・・\quad(7) $$

となります。これが、論文の(2)式です。この式の意味は、トークンシーケンス長 $T$ のテキストに $|s|_G$ 個のグリーンリストからのトークンを検出したときの検出しきい値は左辺で与えられる $z$ だということです。ということは、左辺の $z$ に $4$ を代入し、右辺にある $|s|_G$ に $T$ を代入すれば（つまり、すべてのトークンはグリーンリストからのトークンであるとすれば）、検出しきい値 $z=4$ の下で電子透かしが検出できるトークンシーケンス長 $T$ を求めることができます。

では、計算をしてみましょう。(7)式に $z=4$、$|s|_G=T$ を代入すると、$T=4^2=16$ となります。したがって、最低16トークンあれば電子透かしを検出できることになります。

この電子透かし、問題あり！

これまで述べてきた電子透かしには重大な問題があります。それは、全語彙をレッドリストとグリーンリストに（ランダムに）分割して、グリーンリストからしか次トークンを出力しないというルールです（論文ではこれを "hard watermark" つまり「硬い電子透かし」と呼んでいます）。これを論文に記載された例で説明しましょう。

オバマ大統領は知っていますね？彼の名前は "Barack Obama" です。いま、米国の大統領に関するレポートを依頼された LLM が第44代大統領であるオバマ元大統領について "Barack" というファーストネームまで出力したとしましょう。そして、次の出力候補のトークンリストを参照すると、なんと "Obama" というラストネームがレッドリストに入っているではないですか！いくら語彙数は多く、類義語はいくらでもあるといっても、"Obama" に代わる語はさすがにありません。

問題は、一律にレッドリストとグリーンリストに分割して次トークン候補をグリーンリストに限定するところにあります。このバラク・オバマの例のように、言葉には決定的なもの（「バラク」に続く「オバマ」）とそうでないもの（代替可能なもの）があります。そこで、決定的なもの（往々にして頻出頻度が少ない語）はレッドリストのトークンであっても選ばれるようにし、代替可能な語（往々にして頻出頻度が高い語）はグリーンリストの方が選ばれやすくするという改善策を提案しています。論文ではこれを、先ほどの「硬い電子透かし」に対して「柔軟な電子透かし」（"soft watermark"）と呼んでいます。

エントロピー

「決定的な語」や「代替可能な語」といっても、コンピュータにそれを分かってもらうには、何か具体的な指標が必要です。その指標としてこの論文が扱っているのがエントロピーです。エントロピーは、物理学や情報理論で使われる重要な概念で、システムの乱雑さや不確定さ（予測の困難さ）を表す指標として用いられます。情報理論で使われるエントロピーを情報エントロピーと呼び、$H$ で表します。情報エントロピーは、メッセージやデータの中に含まれる情報の量や予測の困難さを表す指標として用いられ、ある事象 $k$ が起こる確率 $p_k$ とその事象の情報量 $-\log_2{p_k}$ の積を足し合わせたもの（すなわち、平均情報量）で表されます。数式で書くとこうなります。

$$ H(\boldsymbol{p}) = -\sum_{k=1}^{N}p_k \log_2{p_k}\quad・・・\quad(8)$$

ここで、$\boldsymbol{p}=(p_1,\cdots,p_N)$ です。

「決定的な語」のエントロピーはどうなるでしょうか？$N$個あるトークンの候補の中で、先ほどの"バラク・オバマ"の例のように、"バラク"に続く語は"オバマ"だけです。したがって、(8)式の和の中の"オバマ"に対応する $p_k$ のみが$1$で、あとは全部ゼロです。したがって、$\log_2{1}=0$ を考慮すると、$H=0$ になります。

では、「代替可能な語」のエントロピーはどうでしょうか？ここでは、「どんな単語を選んでも構わない」という極端な場合でエントロピーを評価してみましょう。その場合、各単語が選ばれる確率は $p_k=1/N$ なので、エントロピーは

$$H(\boldsymbol{p}) = -\sum_{k=1}^N \frac{1}{N}\log_2{\frac{1}{N}}=\log_2{N}$$

となります。したがって、情報エントロピーの値がとる範囲は

$$ 0 \le H \le \log_2{N}$$

となり、より「決定的な語」ほどエントロピーは低く、$H = 0$ の場合は完全に決定的になり、ある一つの単語が選ばれます。一方、より「代替可能な語」ほどエントロピーは高く、$H = \log_2{N}$ の場合、完全にランダムに単語が選ばれます。

このように、エントロピーという概念を用いれば、コンピュータに、どれが「決定的な語」でどれが「代替可能な語」かを伝えることができます。ただし、この論文では、(8)式で与えられる情報エントロピーは使っていません。その代わり、次単語予測（次トークン予測）で用いる離散確率ベクトル $\boldsymbol{p}$ と相性の良いスパイク・エントロピーというものを考案して使っています。

スパイク・エントロピー

離散確率ベクトル$\boldsymbol{p}$とスカラー $\zeta$ が与えられたとき、係数 $\zeta$ を持つ $\boldsymbol{p}$ のスパイク・エントロピーを次のように定義します（論文では、$\zeta$ ではなく $z$ という変数名を使っていますが、検出しきい値 $z$ との混乱を招く恐れがあるので、ここでは $\zeta$ という変数名にしています）。

$$S(\boldsymbol{p}, \zeta) = \sum_{k=1}^{N}{\frac{p_k}{1+\zeta p_k}}\quad・・・\quad(9)$$

情報エントロピーのときのように、「決定的な語」や「代替可能な語」のスパイク・エントロピーの値を見積もっておきましょう。

まず、「決定的な語」の場合ですが、ある $p_k$ のみ $1$ で、他はすべて $0$ でした。したがって、(9)式は

$$ S(\boldsymbol{p}=(0, \cdots, 1, \cdots, 0), \zeta) = \frac{1}{1+\zeta}$$

となります。

次に、「代替可能な語」ですが、ここでも「どんな単語を選んでも構わない（すべての $p_k$ は等確率）」という極端な場合でエントロピーを評価してみます。(9)式に $p_k = 1/N$ を代入すると

$$ S(\boldsymbol{p}=(1/N, \cdots, 1/N), \zeta) = \sum_{k=1}^N \frac{1/N}{1+\zeta/N} = \frac{1}{1+\zeta/N} = \frac{N}{N+\zeta}$$

となります。
したがって、スパイク・エントロピーの範囲は

$$ \frac{1}{1+\zeta}\le S(\boldsymbol{p}, \zeta) \le \frac{N}{N+\zeta}\quad\cdots\quad(10)$$

となります。語彙数 $N$ を $10,000$ として、(10)式で与えられるスパイク・エントロピーの上下限を係数 $\zeta$ のスケールを変えながらプロットしたものを下図に示します。

Fig.2 スパイク・エントロピーの係数ζ依存性

図の左端は $0 \le \zeta \le 1.0$ の範囲、中央は $0 \le \zeta \le 2.0$ の範囲、そして右端は $0 \le \zeta \le 10000$ の範囲でスパイク・エントロピーの上下限を描いたものです。$\zeta$ が $0$ のとき、上下限はともに $1$ で、$\zeta$ の増加に伴って上下限ともに単調に減少しますが、$\zeta$ の小さい領域では上限はほぼ $1$ で（図の左と中央）、$\zeta$ のスパンが語彙数 $N$ の大きさになると、上限が $\zeta$ の増加とともに単調減少し、下限はほぼ $0$ になっているのが分かります（図の右）。

離散確率ベクトルのシミュレーション

スパイク・エントロピーの性質を調べるため、シミュレーションを行ないます。その際、離散確率ベクトル $\boldsymbol{p}$ が必要になります。離散確率ベクトル $\boldsymbol{p}$ は、次単語予測（次トークン予測）で用いる確率ベクトルです。このベクトルの第 $k$ 成分は、$k$ 番目の語彙が生成される確率です。
さて、シミュレーションを行なうために、「代替可能な語」が生成されるエントロピーの高い状態から、「決定的な語」が生成されるエントロピーの低い状態に連続的に移るような離散確率ベクトル $\boldsymbol{p}$ を作りたいと思います。そこで、このような要請を満たす確率分布の一つとして対数正規分布を取り上げたいと思います。対数正規分布の確率密度関数を以下に示します。

$$
f(x) = \frac{1}{\sqrt{2\pi\sigma^2}x} \exp{\left( -\frac{(\ln{x} - \mu)^2}{2\sigma^2} \right)}
\quad・・・\quad(11)
$$

下図は、平均 $\mu = 0$ とし、$\sigma = 0.125, 0.25, 0.5, 1, 1.5, 2, 5, 10$ に対する対数正規分布の確率密度関数を描いたものです。

Fig.3 対数正規分布の確率密度関数

標準偏差 $\sigma$ が大きくなるにつれて、左右対称な分布から次第に右に裾野を引く歪んだ分布に変形し、最終的には原点に針のようなピークを持つ分布になります。

下図は、上図に対する標準偏差 $\sigma$ を使って対数正規乱数を $N=100$ 個発生させて、離散確率ベクトル $\boldsymbol{p}$ を生成したものです。横軸は語彙番号 $k=1,\cdots,N$ で、縦軸はその語彙が次単語で生成される確率 $p_k$ です。

Fig.4 対数正規分布から生成した離散確率ベクトル

標準偏差 $\sigma$ が大きくなるにつれて、離散ベクトルは一様乱数からいくつかのスパイク状のピークを持つ乱数に変わり、しかも、そのスパイク状のピークの数が減少し、$\sigma = 10$ ではたった一本のスパイク状のピークしかなくなっています。これは、 $\sigma$ の増大に伴って「代替可能な語」が生成されるエントロピーの高い状態から、「決定的な語」が生成されるエントロピーの低い状態に連続的に移行していることを意味しています。実際、図のタイトルに示したスパイク・エントロピー $S(\boldsymbol{p},N)$ の値は$\sigma$ の増大に伴って減少しています。

スパイク・エントロピーの解釈

論文のP.4右段の Definition 4.1 の最後の方に次のような記述があります。

For large $z$, the value of $\frac{p_k}{1+z p_k} \approx 1/z$ when $p_k > 1/z$ and $\approx 0$ for $p_k < 1/z$. For this reason, one can interpret the spike entropy as a softened measure of the number of entries in $\boldsymbol{p}$ greater than $1/z$.

和訳すると、

大きな $z$ に対して、$p_k$ の値は、$p_k$ が $1/\zeta$ より大きい場合には $1/\zeta$ に近く、$p_k$ が $1/\zeta$ 未満の場合にはほぼ $0$ に近づきます。このため、スパイクエントロピーは、$\boldsymbol{p}$ のエントリ数が $1/\zeta$ より大きいものの数の和らげられた尺度と解釈できます。

ということです（論文表記の $z$ を $\zeta$ と読み替えています）。これを実際に確かめてみましょう。
(9)式より

$$
\begin{eqnarray}
S(\boldsymbol{p}, \zeta)
&=& \sum_{k=1}^{N}{\frac{p_k}{1+\zeta p_k}} \\
&=& \sum_{p_k < \frac{1}{\zeta}}{\frac{p_k}{1+\zeta p_k}} + \sum_{p_k > \frac{1}{\zeta}}{\frac{p_k}{1+\zeta p_k}} \\
&\approx& \sum_{p_k < \frac{1}{\zeta}} 0 + \sum_{p_k > \frac{1}{\zeta}}\frac{1}{\zeta} = \frac{1}{\zeta} \sum_{p_k > \frac{1}{\zeta}} \\
&=& \frac{1}{\zeta} \left[ \boldsymbol{p} のエントリ数が 1/\zeta より大きいものの数 \right] \\
\end{eqnarray}
$$

となるので、$\boldsymbol{p}$ のエントリ数が $1/\zeta$ より大きいものの数は、$\zeta S(\boldsymbol{p}, \zeta)$ となります。

何を言っているかというと、スパイク・エントロピーに $\zeta$ を掛けたものは、離散確率ベクトル $\boldsymbol{p}$ の要素のなかで $1/\zeta$ より大きい要素の数を表しているということを言っているのです。言い換えると、スパイク・エントロピーに $\zeta$ を掛けたものは、スパイク状のピークの本数を表しているということです。ここで、スパイク状のピークとは、$p_k > 1/\zeta$ であるような $p_k$ のことです。これを実際に確かめたのが下図です。

Fig.5 スパイク・エントロピーのζ依存性

この図は、離散確率ベクトル $\boldsymbol{p}$ （標準偏差 $\sigma$ を変えながら生成した $N=10,000$ 個の対数正規乱数）を用いて、シミュレーションを行なったものです。横軸は離散確率ベクトル $\boldsymbol{p}$ の要素のうち $1/\zeta$ より大きかった $p_k$ の数を数えたもので、縦軸（予測）はスパイク・エントロピーに $\zeta$ を掛けた $\zeta S(\boldsymbol{p},\zeta)$ です。ここでは、$\zeta = N \hspace{3pt}(= 10,000)$ としました。つまり、$p_k > 1/N$ をスパイク状のピークと定義したのです。図中の青い点は様々な標準偏差 $\sigma$ に対するシミュレーション結果で（各点に付けた数字は $\sigma$ の値）、赤色の破線は、対角線、つまり、スパイク状のピークの予測値と実際の数が一致するラインです。この図から、スパイク・エントロピーに $\zeta$ を掛けたものは、スパイク状のピークの本数を表しているという論文の主張は概ね正しいと言えそうです。

柔軟な電子透かし (soft watermark)

さて、道具が揃ったので、いよいよ柔軟な電子透かしの議論に入っていきます。

LLM は次の単語（実際は「トークン」）を生成する際に、トークン確率ベクトル $\boldsymbol{p}=(p_1,\dots,p_N)$ を参照します。

これは、この記事の冒頭で述べたことです。では、そのトークン確率ベクトル $\boldsymbol{p}=(p_1,\dots,p_N)$ はどうやって作成しているのでしょう。下図は LLM の内部で離散確率ベクトルの生成過程を描いたものです。

Fig6 ロジットベクトルと離散確率ベクトル

現トークン $\boldsymbol{u}^{(t)}$ はトランスフォーマーによって潜在ベクトル $\boldsymbol{h}^{(t)}$ に変換され、全結合ネットワーク $W_e$ によってロジットベクトル $\boldsymbol{l}^{(t)}$ に変換され、それを Softmax 関数で正規化して最終的に離散確率ベクトル $\boldsymbol{p}^{(t)}$ が得られます。ここで、ロジットベクトル $\boldsymbol{l}^{(t)}$ は、次トークンとしてどれが相応しいかを表すスコアのようなものです。ロジットベクトル $\boldsymbol{l}^{(t)}$ の $k$成分は、次式で離散確率ベクトル $\boldsymbol{p}^{(t)}$ の $k$成分に変換されます。

$$
p_k^{(t)} = \frac{\exp{\left( l_k^{(t)} \right)}}{\sum_{i=1}^{N} \exp{\left( l_i^{(t)} \right)}}
\quad・・・\quad(12)
$$

硬い電子透かし (hard watermark) はレッドリストからの次トークン出力を禁止していましたが、柔軟な電子透かし (soft watermark) は禁止する代わりに、グリーンリストに属するトークンのロジットに、一律に正の定数 $\delta$ を加えてトークン出力確率 $p_k$ に下駄を履かせるのです。すなわち、

$$
\hat{p}_k^{(t)} =
\begin{cases}
\frac{\exp{\left( l_k^{(t)} + \delta \right)}}{\sum _{i \in R}\exp{\left( l_i^{(t)} \right)} + \sum _{i \in G}\exp{\left( l_i^{(t)} + \delta \right)}}, \quad k \in G \\
\frac{\exp{\left( l_k^{(t)} \right)}}{\sum _{i \in R}\exp{\left( l_i^{(t)} \right)} + \sum _{i \in G}\exp{\left( l_i^{(t)} + \delta \right)}}, \quad k \in R
\end{cases}
\quad・・・\quad(13)
$$

とします。こうすることによって、拮抗する $p_k$ において（すなわち高エントロピーの場合）は、グリーンリストのトークンを出やすくし、逆に、突出する $p_k$ があれば（すなわち低エントロピーの場合）、$\delta$ を適切に設定することにより、レッドリストでも選択されるようになります。

うまいこと考えましたね！でも、こうやって生成したテキストに電子透かしが入っているか、どうやって検証するのでしょう？硬い電子透かし (hard watermark) の場合はトークンがレッドリスト由来のものかグリーンリスト由来のものかはベルヌーイ試行なので、二項分布を使って比較的簡単に検定することができました。しかし、この柔軟な電子透かし (soft watermark) は一筋縄ではいかない気がします。どうやって検定に持ち込むのか？次節でそれを解説していきます。

Theorem 4.2

論文のP.4の右段の後半にこんな記述があります。

Theorem 4.2. Consider watermarked text sequences of $T$ tokens. Each sequence is produced by sequentially sampling a raw probability vector $\boldsymbol{p}(t)$ from the language model, sampling a random green list of size $\gamma N$, and boosting the green list logits by $\delta$ using Equation 4 before sampling each token. Define $\alpha = \exp{(\delta)}$, and let $|s|G$ denote the number of green list tokens in sequence s. If a randomly generated watermarked sequence has average spike entropy at least $S^*$, i.e.,
$$
\frac{1}{T}\sum_{t=1}^{T}{S \left( \boldsymbol{p}^{(t)}, \frac{(1-\gamma)(\alpha-1)}{1+(\alpha-1)\gamma} \right)} \geq S^{\ast},
$$
then the number of green list tokens in the sequence has expected value at least
$$
\mathbb{E}|s|_G \geq \frac{\gamma\alpha T}{1+(\alpha-1)\gamma}S^{\ast},
$$
Furthermore, the number of green list tokens has variance at most
$$
\mathrm{Var}|s|_G \leq T \frac{\gamma\alpha S^{\ast}}{1-(\alpha-1)\gamma} \left( 1-\frac{\gamma\alpha S^{\ast}}{1-(\alpha-1)\gamma} \right).
$$

数式説明の部分を和訳すると、

無作為に生成された電子透かしシーケンスが、少なくとも$S^{\ast}$の平均スパイクエントロピーを持つ場合、すなわち、
$$
\frac{1}{T}\sum_{t=1}^{T}{S \left( \boldsymbol{p}^{(t)}, \frac{(1-\gamma)(\alpha-1)}{1+(\alpha-1)\gamma} \right)} \geq S^{\ast}
\quad・・・\quad (14)
$$
の場合、グリーンリストのトークン数の期待値は
$$
\mathbb{E}|s|_G \geq \frac{\gamma\alpha T}{1+(\alpha-1)\gamma}S^{\ast}
\quad・・・\quad (15)
$$
で与えられる。さらに、グリーンリストのトークン数の分散は次式で与えられる。
$$
\mathrm{Var}|s|_G \leq T \frac{\gamma\alpha S^{\ast}}{1-(\alpha-1)\gamma} \left( 1-\frac{\gamma\alpha S^{\ast}}{1-(\alpha-1)\gamma} \right)
\quad・・・\quad (16)
$$

となっています。これは、(14)式で定義した平均スパイクエントロピーの下限 $S^*$ を使うと、長さ $T$ のトークンシーケンス中にあるグリーンリスト由来のトークンの期待値（平均値）と分散が、それぞれ(15)式と(16)式で推定できるよ、と言っているのです。
「検出しきい値 $z$」の節で説明したように、平均値と分散がわかれば検出しきい値 $z$ を求めることができ、事前に設定した有意水準 $\alpha$ の下でテキストが LLM が出力したものかどうかを判定できます。なお、(14)式～(16)式の導出は、論文の「F.Proof of Theorem 4.2」(p.21)に詳しく書いてあります。

観測すべきトークン列の長さ

では、論文 P.5 の「4.1. Sensitivity of the watermark test」に沿って、電子透かしを検出するために観測すべきトークン列の長さ $T$ を見積もっていきましょう。そもそも(5)式は観測した $T$ 個のトークン列に、グリーンリストからのトークンが $|s|_Z$ 個入っている場合の $z$スコアを与える式でした。ですから、観測した $T$ 個のトークン列すべてがグリーンリストのトークンである場合のトークン数 $T$ を $z=4$ という基準のもとで求めれば、電子透かしを検出できる最小のトークン数を求めることができます。

(5)式に $z = 4, |s|_G = T$ を代入すると、$ 4 = \frac{T - \mu}{\sigma}$ となり、さらに $\sigma$ に $\sqrt{\mathrm{Var}|s|_G}$ を、$\mu$ に $\mathbb{E}|s|_G$ を代入すると

$$
4 = \frac{T - \mathbb{E}|s|_G}{\sqrt{\mathrm{Var} |s|_G}}
\quad・・・\quad(17)
$$

となります。ここで、(17)式に $ \mathrm{Var}|s|_G$ として(16)式の上限である $T\frac{\gamma\alpha S^{\ast}}{1 + (\alpha - 1) \gamma} \left( 1 - \frac{\gamma\alpha S^{\ast}}{1 + (\alpha - 1) \gamma} \right)$を、$ \mathbb{E}|s|_G $ として(15)式の下限 $\frac{\gamma\alpha T}{1 + (\alpha - 1) \gamma} S^{\ast}$ を代入すると、

$$
\begin{eqnarray}
4 &=& \frac{T - \frac{\gamma\alpha T}{1 + (\alpha - 1)\gamma} S^{\ast}}
{\sqrt{T\frac{\gamma\alpha S^{\ast}}{1 + (\alpha - 1)\gamma}\left( 1 - \frac{\gamma\alpha S^{\ast}}{1 + (\alpha - 1) \gamma} \right)}} \\
&=& \sqrt{T} \frac{1 - \frac{\gamma \alpha}{1 + (\alpha - 1) \gamma} S^{\ast}}
{\sqrt{\frac{\gamma\alpha S^{\ast}}{1 + (\alpha - 1) \gamma} \left( 1 - \frac{\gamma\alpha S^{\ast}}{1 + (\alpha - 1) \gamma} \right)}} \\
&=& \sqrt{T} \sqrt{\frac{1 - \frac{\gamma \alpha}{1 + (\alpha-1) \gamma} S^{\ast}}
{\frac{\gamma\alpha S^{\ast}}{1 + (\alpha - 1) \gamma}}} \\
&=& \sqrt{T} \sqrt{\frac{1 + (\alpha - 1) \gamma - \gamma \alpha S^{\ast}}
{\gamma \alpha S^{\ast}}}
\quad・・・\quad(18)
\end{eqnarray}
$$

となりますが、これを $T$ について解けば、

$$
T = \frac{16 \gamma \alpha S^{\ast}}{1 + (\alpha - 1) \gamma - \gamma \alpha S^{\ast}}
\quad・・・\quad(19)
$$

を得ます。

論文にしたがって $\gamma = 0.5, \delta = 2.0, \alpha = \exp(\delta) = 7.389$ として、(19)式から $T$ を求めます。しかし、$S^{\ast}$の値がわかりません。そこで、$T$ の $S^{\ast}$ 依存性をシミュレーションしてみます。以下にシミュレーションのコードを示します。

コード 1

# 電子透かしを検出できる最小のトークン数 T を求める
import matplotlib.pyplot as plt
import numpy as np
import math

# (19)式から T を計算する関数
def get_T(z, gamma,  alpha, S):
  T = z**2 * gamma * alpha * S / (1 + (alpha - 1) * gamma - gamma * alpha * S)
  return T

z = 4
gamma = 0.5
delta = 2.0
alpha = math.exp(delta)

# T の S* 依存性をプロット
Ss = np.linspace(1/(1+z),1.1,100)
Ts = get_T(z, gamma,  alpha, Ss)

plt.plot(Ss, Ts, label="T")
plt.plot([1/(1+z),1.1],[128,128],linestyle="dashed", label="T=128 line")

# 簡易的に T(S*)=128 を解いて S* を求める
S_prev, T_prev = -1., -1.
for S, T in zip(Ss, Ts):
  if T < 128.:
    S_prev, T_prev = S, T
  if T > 128.:
    plt.plot([S_prev,S_prev],[T_prev,0.],linestyle="dashed", label=f"S*={S_prev:.2f} at T=128")
    break

plt.xlabel('S*')
plt.ylabel('T')
plt.title(f'S* dependence of T at γ={gamma}, δ={delta}')
plt.legend()
plt.show()

実行結果は下図のようになりました。

Fig.7 トークン長 $T$ の $S^{\ast}$ 依存性

Fig.7 を見ると、$S^{\ast} \approx 1.0$ のとき $T = 128$ となり、論文とほぼ一致しました（論文では $T = 128.2$）。ということで、論文では $S^{\ast} = 1$ として計算しているものと思われます。では、この $128.2$ という数値は何を表しているのでしょうか？もちろん、「電子透かしを検出するために観測すべきグリーンリストのトークン列の長さ」であることは間違いないのですが、この数値の役割は何でしょうか？

「硬い電子透かし」(hard watermark) の場合、検出しきい値 $z$ を計算する(5)式の平均値 $\mu$ に $Tp$ を用いました（(6)式参照）。なぜならば、出力されるグリーンリストのトークン数は2項分布に従うからです。2項分布の平均値 $\mu$ は $Tp = 200 \times 1/2 = 100$ でした。では「柔軟な電子透かし」(soft watermark) の場合はどうでしょうか？グリーンリストのトークンのロジットには下駄を履かせていますから、もはや2項分布にはなりません。実は、$S^{\ast} = 1$ として(19)式を計算して得られた $T = 128.2$ が「柔軟な電子透かし」におけるグリーンリストのトークン数の平均値 $\mu$ になるのです。それを理解するには $S^{\ast} = 1$ の意味について考えなければなりません。離散確率ベクトル $\boldsymbol{p}$ が、一様乱数ベクトルかの如く突出した成分がない場合（Fig.4 左上参照）、スパイク・エントロピーはその最大値である 1 になります（Fig.2 参照）。これは、次トークンに語彙中の何が来るかわからない状態を表しています（高エントロピー状態）。まさしくベルヌーイ試行の様相を呈しています。ただ、ベルヌーイ試行と違うのは、グリーンリストのトークンのロジットに下駄を履かせたことにより、トークンが選ばれる確率 $p$ に偏りがあるということです。その偏りを加味してグリーンリストのトークン数を計算するのが $S^{\ast} = 1$ とした(19)式でした。したがって、以後、「柔軟な電子透かし」で検出しきい値 $z$ を求める(5)式を使う場合には、$\mu = 128.2$ とします（２項分布の場合が 100 だったので、当然ながらそれよりは多いですね）。

シミュレーションによる理論の検証（Type Ⅱエラー解析）

論文 P.5 左段後半部分に以下のような記述があります。

Theoretical bound. Our generations have an average spike entropy per sample of $S = 0.807$ over $\sim 500$ generations. Theorem 4.2 says that the expected number of green list tokens per generation is at least $142.2$. Indeed, the empirical average is $159.5$. For sequences with entropy equal to the mean ($S = 0.807$) we get $\sigma \le 6.41$ tokens, and $98.6\%$ sensitivity ($1.4\%$ type-II error rate), using a standard Gaussian approximation for the green list count.

この記述は、定理4.2 (Theorem 4.2) の限界について述べています。シミュレーション（論文には500個のテキストを生成したという記述がみられます）を行ない、その結果に基いて平均スパイク・エントロピーを計算し、それを(15)式および(16)式の $S^{\ast}$ に代入して、シーケンス中のグリーンリスト・トークン数の期待値（ $\mathbb{E}|s|_G$ ）とその分散（ $\mathrm{Var}|s|_G$ ）を求め、感度を評価しています。ここでいう「感度」とは、LLMが生成したテキストに対して電子透かしの検出テストを行なった際、陽性（検出に成功）に判定されるテキストの割合（True Positive ratio: 真陽性率）のことです。

では、実際に計算をして論文に書いてある結果を確かめてみましょう。シミュレーションの結果、平均スパイク・エントロピーは $S=0.807$ になったと書いてあるので、$S^{\ast} = 0.807, \gamma =0.5, \alpha = \exp{2.0} = 7.389$ を(15)式に代入します。すると $\mathbb{E}|s|_G = 142.2$ となり、論文に書いてある通りの結果となりました。

次に分散ですが、(16)式から $\mathrm{Var}|s|_G = 41.11$ となり、$\sigma = \sqrt{\mathrm{Var}|s|_G} = 6.41$ が得られました。これも論文に書いてある通りです。得られた $\mathbb{E}|s|_G = 142.2, \sigma = 6.41$ 、そして前節で求めた $S^{*} = 1$ のときの電子透かし検出のための最低トークン長 $T = 128.2$ を平均値 $\mu$ とみなして(5)式に代入すると、検出しきい値 $z = 2.177$ が得られました。この検出しきい値に対するタイプⅡのエラー率（False Negative ratio: 偽陰性率）を計算すると $1.47\%$ となり、小数点１桁目までは論文に一致しました。

なお、タイプⅡのエラーとは、対立仮説が実際には真であるのに帰無仮説を採用してしまうエラーのことです。この論文の帰無仮説は「$H_0$: このテキストは、レッドリストのルールを全く知らない人間が作成したものである」で、対立仮説は「$H_1$: このテキストは LLM が生成したものである」です。ということは、先ほど書いたタイプⅡのエラーは、「このテキストは LLM が生成したものであるのに、人間が作成したと判定してしまう」エラーです。そのエラー率が $1.47\%$ であったということです。これは高いのでしょうか、低いのでしょうか？200件のテキスト中、3件は誤って判定される（この場合、見過ごされる）という勘定になりますから、適用領域によっては問題となることがあるかもしれません。これを著者らは「定理4.2 (Theorem 4.2) の限界」としているのです。

論文には

If we use the true empirical mean of 159.5 rather than the theoretical bound, we get a $5.3 \times 10^7$ type-II error rate, a realistic approximation but not a rigorous lower bound.

と書かれており、シミュレーションで得られたグリーンリストの平均トークン長は $159.5$ で、これを使ってタイプⅡのエラー率を計算すると $5.3 \times 10^7$ になったということです。実際に計算して確かめたところ、検出しきい値は $z = 4.883$ で、タイプⅡのエラー率は $5.2 \times 10^7$ となり、論文の値とほぼ一致しました。これは、約200万件のテキストを検出ソフトにかけて 1 件見過ごすという実用面では現実的な精度です。ただし、シミュレーション結果の平均スパイク・エントロピー $S$ は、厳密な下限ではないということに注意する必要があるということです。

参考文献

[1]Self-Consuming Generative Models Go MAD. https://arxiv.org/abs/2307.01850
[2]The Curse of Recursion: Training on Generated Data Makes Models Forget. https://arxiv.org/abs/2305.17493