ストリーミングアルゴリズム(streaming algorithm)とは、長いデータの列を先頭から 1 回だけ読み、データ全体よりはるかに小さい記憶で、列についての量を計算または近似するアルゴリズムである。値の頻度 $m_i$ から決まる量が典型で、$k-1$ 個の数え札を使う Misra–Gries のアルゴリズムは、$m/k$ 回より多く現れる値をすべて残し、頻度を誤差 $m/k$ 以内で表す。値ごとに 4 つずつ独立な符号を割り当てて和の 2 乗をとると、2 次のモーメント $\sum_i m_i^2$ を対数の程度の記憶で近似できる。一方、相異なる値の個数を決定的に正確に求めるには、値の種類の数と同じビット数の記憶が要る。
前提知識: 期待値の線形性, Chebyshevの不等式, Hoeffdingの不等式, 有限体
ストリーミングアルゴリズム(streaming algorithm)とは、長いデータの列を先頭から 1 回だけ読み、データ全体よりはるかに小さい記憶しか使わずに、列についての量を計算または近似するアルゴリズムである。読んだデータは記憶に残せないので、後から見直すことはできない。通信の記録、検索の問い合わせ、センサーの観測のように、全部を保存するには大きすぎる列を扱う計算の模型である。
扱う量の典型は、各値の出現回数(頻度)から決まるものである。値の種類が $n$ 個、列の長さが $m$ のとき、頻度を全部数えれば正確に答えられるが、$n$ 個の数え札が要る。ストリーミングアルゴリズムでは、記憶を $\log n$ や $\log m$ の多項式程度に抑えることを目指す。そのために、答えを近似で許したり、乱数を使ったりする。
この記事では、ストリーミングアルゴリズムと頻度のモーメントを定義し、3 つの結果を証明する。$k-1$ 個の数え札で頻出する値をすべて拾う Misra–Gries のアルゴリズム、乱数の符号を使って 2 次のモーメント $F_2=\sum_i m_i^2$ を $O(\log n+\log m)$ ビットの程度で近似する Alon–Matias–Szegedy のアルゴリズム、そして相異なる値の個数を決定的に正確に求めるには $n$ ビットが要るという下界である。
$n\ge1$ について $[n]:=\{1,\dots,n\}$ とおく。
$[n]$ の元の有限列 $A=(a_1,\dots,a_m)$ を ストリーム という。値 $i\in[n]$ の 頻度 を $m_i:=\lvert\{j:a_j=i\}\rvert$ とし、$k\ge0$ について
$$
F_k:=\sum_{i=1}^n m_i^k
$$
を $A$ の $k$ 次の 頻度のモーメント という。ただし $F_0$ では $0^0:=0$ と読み、$F_0$ は列に現れる相異なる値の個数である。$F_1=m$ は列の長さである。
状態の集合は $n$ と、列の長さの上限 $m$ に応じて選んでよい。記憶がデータを 1 回読むことしか許されないので、状態 $s_A$ は、その後に続く列に答えるために $A$ について覚えておくべきことすべてを含まなければならない。下界の証明(thm-sa-lower)はこの点を使う。
長さ $F_1=m$ は、2 進法の数え札 1 つで $\lceil\log_2(m+1)\rceil$ ビットで正確に求まる。最大値 $\max_j a_j$ も、それまでの最大値を $\lceil\log_2(n+1)\rceil$ ビットで覚えれば求まる。一方、相異なる値の個数 $F_0$ を正確に求めるには、どの値がすでに現れたかを覚える必要があり、thm-sa-lower のとおり $n$ ビット要る。
$k\ge2$ とする。$m/k$ 回より多く現れる値は $k-1$ 個以下しかない($k$ 個あれば頻度の合計が $m$ を超える)。次のアルゴリズムは、それらをすべて記憶の中に残す。
記憶は、値と正の整数(数え札)の組を $k-1$ 個以下持つ集合 $T$ で、初めは空とする。値 $a$ を読むたびに次をする。
減算の段は、「$a$ と $T$ の $k-1$ 個の値」という相異なる $k$ 個の値の出現を 1 つずつ消す操作である。Misra と Gries は、相異なる $k$ 個の出現を消せなくなるまで消すと、$m/k$ 回より多く現れる値だけは必ず残ることを示し、このアルゴリズムを得た(MG82 §3 の Theorem 1 とアルゴリズム (3)、p. 147)。次の定理は、残る数え札が頻度を誤差 $m/k$ 以内で表すことまで述べる。
長さ $m$ のストリームを読み終えたとき、すべての $i\in[n]$ について
$$
m_i-\frac mk\le\hat m_i\le m_i
$$
である。とくに $m_i>m/k$ となる値 $i$ はすべて $T$ に残る。記憶は $O\bigl(k(\log n+\log m)\bigr)$ ビットである。
減算の段の回数を $D$、読み終えたときの数え札の合計を $\Sigma:=\sum_i\hat m_i$ とする。
段 1($\hat m_i\le m_i$)。値 $i$ の数え札が増えるのは $i$ を読んだときだけで、1 回に $1$ だけ増える。よって $\hat m_i$ は $i$ を読んだ回数 $m_i$ を超えない。
段 2($D\le m/k$)。読むたびに数え札の合計がどう変わるかを見る。手順 1・2 では合計が $1$ 増える。減算の段では $T$ の $k-1$ 個の数え札が $1$ ずつ減るので合計は $k-1$ 減る。読んだ回数は全部で $m$ なので、
$$
\Sigma=(m-D)-(k-1)D=m-kD
$$
である。$\Sigma\ge0$ から $D\le m/k$ である。
段 3($m_i-\hat m_i\le D$)。値 $i$ について、それまでに $i$ を読んだ回数から $i$ の数え札(組がなければ $0$)を引いた差 $e_i$ を考える。手順 1・2 で読んだ値が $i$ なら $e_i$ は変わらず、$i$ でなければ $i$ の数え札も読んだ回数も変わらない。減算の段で $e_i$ が増えるのは、読んだ値 $a$ が $i$ のとき(読んだ回数だけが $1$ 増える)か、$i$ の組が $T$ にあるとき(数え札が $1$ 減る)で、減算の段では $a$ は $T$ にないので、この 2 つは同時には起こらない。よって 1 回の減算の段で $e_i$ は高々 $1$ しか増えず、読み終えたとき $m_i-\hat m_i=e_i\le D\le m/k$ である。
段 4(記憶)。$T$ は $k-1$ 個以下の組で、各組は値($\lceil\log_2 n\rceil+1$ ビット以下)と $m$ 以下の数え札($\lceil\log_2(m+1)\rceil$ ビット)からなる。$\square$
thm-sa-mg は「頻出する値は必ず残る」ことを保証するが、残った値が本当に頻出するとは限らない(ex-sa-mgrun)。列をもう 1 回読めるなら、残った $k-1$ 個以下の値の頻度を正確に数え直して確かめられる(MG82 §1 は $k=2$ の場合をこの 2 回読む形で述べている)。
$F_2=\sum_im_i^2$ は頻度の偏りを測る量である。すべての値が 1 回ずつなら $F_2=m$、1 つの値だけなら $F_2=m^2$ になる。Alon・Matias・Szegedy は、値ごとに無作為な符号 $\sigma_i\in\{1,-1\}$ を割り当て、和 $Z=\sum_i\sigma_im_i$ を 1 つの数え札で保つ方法を与えた。$Z$ は $a_j$ を読むたびに $\sigma_{a_j}$ を足せば求まる。符号を $n$ 個すべて覚えると記憶が $n$ ビットになるので、少ない乱数から作れる「4 つずつ独立な」符号を使う。
$d\ge1$ を $2^d\ge n$ となる整数とし、有限体 $\mathbb F_{2^d}$ の相異なる元 $x_1,\dots,x_n$ と、$\mathbb F_2$ 上の線形写像 $\lambda\colon\mathbb F_{2^d}\to\mathbb F_2$ で $0$ でないものを固定する。$c_0,c_1,c_2,c_3\in\mathbb F_{2^d}$ を独立に一様に選び、$h(x):=c_0+c_1x+c_2x^2+c_3x^3$、$\sigma_i:=(-1)^{\lambda(h(x_i))}$ とおく。このとき、相異なる $4$ 個以下のどの添字 $i_1,\dots,i_r$($r\le4$)についても、$(\sigma_{i_1},\dots,\sigma_{i_r})$ は $\{1,-1\}^r$ の上で一様に分布する。乱数は $4d$ ビットである。
写像 $\Phi\colon(c_0,c_1,c_2,c_3)\mapsto(h(x_{i_1}),\dots,h(x_{i_r}))$ は、$r\times4$ 行列 $(x_{i_s}^{\,t})_{s,t}$($1\le s\le r$、$0\le t\le3$)を掛ける $\mathbb F_{2^d}^4\to\mathbb F_{2^d}^r$ の線形写像である。その最初の $r$ 列は相異なる $x_{i_s}$ の Vandermonde 行列で可逆なので、$\Phi$ は全射である。全射な線形写像の各点の逆像は核の平行移動で、どれも同じ個数の元からなるので、$c$ が一様なら $(h(x_{i_1}),\dots,h(x_{i_r}))$ は $\mathbb F_{2^d}^r$ で一様、すなわち $r$ 個の値は独立で各々一様である。$\lambda$ は $0$ でない線形写像なので、$\lambda^{-1}(0)$ と $\lambda^{-1}(1)$ はどちらも $2^{d-1}$ 個の元からなり、一様な元の $\lambda$ の値は $0,1$ を確率 $1/2$ ずつとる。独立な確率変数の関数は独立なので、$\sigma_{i_1},\dots,\sigma_{i_r}$ は独立で、それぞれ $\pm1$ を確率 $1/2$ ずつとる。$\square$
$\sigma_1,\dots,\sigma_n$ を lem-sa-4wise の符号とし、$Z:=\sum_{i=1}^n\sigma_im_i$、$X:=Z^2$ とおく。
AMS99 Theorem 2.2(pp. 6–7)の主張で、符号の作り方を除き証明の筋も同書に従う(同書は 4 つずつ独立な符号を BCH 符号から作る)。
1:$E[\sigma_i]=0$、$\sigma_i^2=1$ で、lem-sa-4wise により相異なる $4$ 個以下の符号は独立である。$Z^2=\sum_{i,j}\sigma_i\sigma_jm_im_j$ の期待値では、$i\ne j$ の項は $E[\sigma_i]E[\sigma_j]=0$ なので
$$
E[X]=\sum_im_i^2=F_2
$$
である。$Z^4=\sum_{i,j,k,l}\sigma_i\sigma_j\sigma_k\sigma_lm_im_jm_km_l$ の期待値では、添字の中に奇数回だけ現れる値があればその符号の期待値 $0$ が因子になって消える。残るのは 4 つが同じ値の項 $\sum_im_i^4$ と、相異なる 2 つの値 $i< j$ が 2 回ずつ現れる項で、後者は 4 か所のうち $i$ が入る 2 か所の選び方 $\binom42=6$ 通りあるので
$$
E[X^2]=E[Z^4]=\sum_im_i^4+6\sum_{i< j}m_i^2m_j^2
$$
である。$F_2^2=\sum_im_i^4+2\sum_{i< j}m_i^2m_j^2$ から
$$
\mathrm{Var}(X)=E[X^2]-F_2^2=4\sum_{i< j}m_i^2m_j^2\le2F_2^2 .
$$
2:各 $Y_j$ は独立な $s_1$ 個の写しの平均なので、$E[Y_j]=F_2$、$\mathrm{Var}(Y_j)=\mathrm{Var}(X)/s_1\le2F_2^2/s_1$ である。Chebyshevの不等式 から
$$
P\bigl(\lvert Y_j-F_2\rvert>\lambda F_2\bigr)\le\frac{2F_2^2}{s_1\lambda^2F_2^2}\le\frac18
$$
である($F_2=0$ なら $X=0$ で常に正しい)。$Y_j$ が外れる事象の指示関数を $B_j$ とすると、$B_1,\dots,B_{s_2}$ は独立で $E[B_j]\le1/8$ である。中央値 $Y$ が外れるなら、$Y$ 以上の $Y_j$ と $Y$ 以下の $Y_j$ がそれぞれ半数以上あるので、外れた側にある $Y_j$ が半数以上ある。よって $\sum_jB_j\ge s_2/2$ で、Hoeffdingの不等式 から
$$
P\Bigl(\sum_jB_j\ge\frac{s_2}2\Bigr)\le P\Bigl(\sum_j(B_j-E[B_j])\ge\frac38s_2\Bigr)\le\exp\Bigl(-2s_2\Bigl(\frac38\Bigr)^2\Bigr)=e^{-9s_2/32}\le\varepsilon
$$
である。記憶は、$s_1s_2$ 個の写しのそれぞれについて乱数 $4d=O(\log n)$ ビットと、$\lvert Z\rvert\le m$ を保つ $O(\log m)$ ビットである。$s_1s_2=O(\lambda^{-2}\log(1/\varepsilon))$ なので主張の記憶になる。$\square$
中央値をとるのは、平均と Chebyshevの不等式 だけで失敗の確率 $\varepsilon$ を得ようとすると $s_1$ が $1/\varepsilon$ に比例して必要になるのに対し、中央値なら $\log(1/\varepsilon)$ に比例する回数で済むからである。
長さ $n+1$ 以下のすべてのストリームについて $F_0$ を正確に出力する決定的なストリーミングアルゴリズムは、状態を $2^n$ 個以上持つ。すなわち記憶は $n$ ビット以上である。
部分集合 $U\subset[n]$ について、$U$ の元を小さい順に並べたストリームを $A_U$ とする。状態が $2^n$ 個未満なら、鳩の巣原理 により、相異なる $U\ne U'$ で $s_{A_U}=s_{A_{U'}}$ となるものがある。出力は状態だけで決まるので、$\lvert U\rvert=F_0(A_U)=F_0(A_{U'})=\lvert U'\rvert$ である。$U\ne U'$ で大きさが同じなので、$i\in U\setminus U'$ がある。$A_U$ と $A_{U'}$ の後に $i$ を続けたストリームも、同じ状態から同じ更新をするので同じ状態になり、同じ値を出力する。しかし前者の $F_0$ は $\lvert U\rvert$、後者は $\lvert U'\rvert+1=\lvert U\rvert+1$ で異なり、矛盾する。$\square$
近似や乱数の一方だけでは、この下界は大きく下がらない。$F_0$ や $F_2$ を相対誤差 $0.1$ で近似する決定的なアルゴリズムも $\Omega(n)$ ビットを要し(AMS99 Proposition 3.7、p. 15)、$F_0$ や $F_2$ を正確に求める乱数を使うアルゴリズムも、誤りの確率が $1/2$ 未満の定数なら $\Omega(n)$ ビットを要する(同 Proposition 3.8、p. 16)。どちらもこの記事では証明しない。thm-sa-ams は、近似と乱数の両方を許したときに記憶が対数の程度まで下がることを示している。$F_0$ についても、近似と乱数を許せば、$c>2$ ごとに $O(\log n)$ ビットで、出力と $F_0$ の比が $1/c$ と $c$ の間に入らない確率を $2/c$ 以下にできる(AMS99 Proposition 2.3、p. 8)。
| 量と方法 | 保証 | 記憶(ビット) | 根拠 |
|---|---|---|---|
| 長さ $F_1=m$ | 正確 | $\lceil\log_2(m+1)\rceil$ | ex-sa-simple |
| Misra–Gries(数え札 $k-1$ 個) | $m_i-m/k\le\hat m_i\le m_i$ | $O(k(\log n+\log m))$ | thm-sa-mg |
| AMS の $X=Z^2$ | $E[X]=F_2$、$\mathrm{Var}(X)\le2F_2^2$ | $O(\log n+\log m)$ | thm-sa-ams |
| AMS の平均の中央値 | 相対誤差 $\lambda$ を超える確率 $\le\varepsilon$ | $O(\lambda^{-2}\log(1/\varepsilon)(\log n+\log m))$ | thm-sa-ams |
| $F_0$ を決定的に正確に | — | $\ge n$ | thm-sa-lower |
$k=3$(数え札 2 個)とし、ストリーム $1,2,1,3,1,4,2,1,5,1$($m=10$)を読む。$T$ は順に $\{1{:}1\}$、$\{1{:}1,2{:}1\}$、$\{1{:}2,2{:}1\}$、($3$ で減算)$\{1{:}1\}$、$\{1{:}2\}$、$\{1{:}2,4{:}1\}$、($2$ で減算)$\{1{:}1\}$、$\{1{:}2\}$、$\{1{:}2,5{:}1\}$、$\{1{:}3,5{:}1\}$ となる。減算の段は $D=2$ 回で、$\Sigma=4=10-3\cdot2$ である。$m_1=5>10/3$ の値 $1$ は $\hat m_1=3$ で残り、$5-10/3\le3\le5$ を満たす。$m_5=1$ の値 $5$ も残るが頻出ではない。
ストリーム $1,1,2,3,1$ では $(m_1,m_2,m_3)=(3,1,1)$、$F_2=11$ である。thm-sa-ams の 1 から $E[X]=11$、$\mathrm{Var}(X)=4(9+9+1)=76\le2\cdot11^2=242$ である。lem-sa-4wise を $n=7$($m_4=\dots=m_7=0$)、$d=3$、$\mathbb F_8=\mathbb F_2[t]/(t^3+t+1)$、$x_1,\dots,x_7$ を $\mathbb F_8$ の $0$ でない元、$\lambda$ を基底 $1,t,t^2$ に関する $1$ の係数として当て、乱数 $c\in\mathbb F_8^4$ の $4096$ 通りすべてで $X$ を計算すると、平均はちょうど $11$、分散はちょうど $76$ になる。
$\lambda=0.1$、$\varepsilon=0.01$ なら $s_1=1600$、$s_2=\lceil(32/9)\ln100\rceil=17$ で、写しは $27200$ 個である。$n=2^{20}$、$m=2^{30}$ とすると、写し 1 個は乱数 $4\cdot20=80$ ビットと $\lvert Z\rvert\le m$ を保つ $\lceil\log_2(2m+1)\rceil=32$ ビットで $112$ ビット、全体で $3{,}046{,}400$ ビットである。頻度を全部数えると $2^{20}\cdot31=32{,}505{,}856$ ビットなので、約 $1/10$ である。$n$ を $2^{40}$ に増やしても写し 1 個は $80$ ビット増えるだけである。
| 外す条件 | 例 | 成り立たなくなる結論 |
|---|---|---|
| 頻出は $m_i>m/k$(等号を含めない) | $k=2$、ストリーム $1,2$:$m_1=1=m/2$ だが、読み終えると $T$ は空 | thm-sa-mg の「必ず残る」を $m_i\ge m/k$ に広げた主張(不等式 $m_i-m/k\le\hat m_i$ は $0\le0$ で成り立つ) |
| 符号が 4 つずつ独立 | 2 つずつ独立なだけの符号(ex-sa-pairwise) | $\mathrm{Var}(X)\le2F_2^2$:$252>98$ になる |
| 値ごとに同じ符号を使う | 読むたびに新しい符号を引くと $E[Z^2]=m$(ストリーム $1,1,2,3,1$ で $5\ne11$) | $E[X]=F_2$ |
| 求める量が $F_0$ | $F_1=m$ は $\lceil\log_2(m+1)\rceil$ ビットで正確に求まる | thm-sa-lower の $n$ ビットの下界は量による |
$\tau_1,\tau_2,\tau_3$ を独立に $\pm1$ を確率 $1/2$ ずつとる符号とし、$\{1,2,3\}$ の空でない部分集合 $S$(7 個)ごとに $\sigma_S:=\prod_{i\in S}\tau_i$ とおく。$S\ne S'$ なら $\sigma_S\sigma_{S'}=\sigma_{S\triangle S'}$ の期待値は $0$ で、2 つずつは独立である。しかし $\sigma_{\{1\}}\sigma_{\{2\}}\sigma_{\{1,2\}}=1$ なので 3 つは独立でない。7 個の値が 1 回ずつ現れるストリーム($F_2=7$)では $Z=\sum_S\sigma_S=\prod_i(1+\tau_i)-1$ で、$Z=7$(確率 $1/8$)か $Z=-1$(確率 $7/8$)である。$E[Z^2]=(49+7)/8=7=F_2$ は成り立つが、$E[Z^4]=(2401+7)/8=301$ から $\mathrm{Var}(Z^2)=301-49=252>2F_2^2=98$ である。
| 誤り | 正しくは | なぜ |
|---|---|---|
| Misra–Gries で残った値はすべて頻出である | 頻出する値は必ず残るが、残った値が頻出とは限らない。もう 1 回読んで数え直す | ex-sa-mgrun の値 $5$ |
| 符号は乱数なら何でもよい | 値ごとに固定した、4 つずつ独立な符号を使う | 反例の表の 2・3 行目 |
| 平均の回数を増やせば失敗の確率も効率よく下がる | 分散と Chebyshevの不等式 だけで評価すると、平均の回数は $1/\varepsilon$ に比例する。中央値をとれば $\log(1/\varepsilon)$ | thm-sa-ams の証明 |
| 記憶の量は保つ数の個数である | 数え札の桁数と乱数のビット数も数える | def-sa-algo |
$F_k$($k\ge1$)は一般に $k$ と精度を固定すると $O(n^{1-1/k}(\log n+\log m))$ ビットで近似でき、$k\ge6$ では $n^{\Omega(1)}$ ビットが必要である(AMS99 Theorem 2.1・3.2、p. 3・p. 10。この記事では証明しない)。下界の証明では、2 人の間の通信量の下界(通信計算量)が使われる。ストリームの値に重みや削除を許す模型では、AMS の $Z$ は重みつきの和として同じように更新できる。データを 1 回だけ読むという制約は、要求に取り消せない応答をする オンラインアルゴリズム の制約と近い。乱数の使い方は 乱択アルゴリズム、少ない乱数から独立性を作る方法は ハッシュ関数 の普遍族と同じ考え方である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する