外書輪講I(第9回)

[場所1E503（月曜日5限）]

HPに行く

今回はMiniature 5, 16, 10を行いました。

Miniature 5

誤り訂正符号の話です。

用語の説明をしておきます。

$S$ をアルファベットといい、$S^n$ の元をワード(語)としておきます。

このとき、$C$ が符号であるとは、$C\subset S^n$ とワードの部分集合とします。

線形符号の場合は、線形部分空間です。

$u,v$ をワードとして、
$u=u_1u_2\cdots u_n$ かつ $v=v_1v_2\cdots v_n$ としておきます。

$d(u,v)=\#\{i|u_i\neq v_i\}$ をハミング距離と言います。

つまり、2つのワードに含まれるアルファベットのうち、違っているものの数

ということです。

よって任意の2つのワードの最大距離は $n$ となります。

$\forall u\in S^n$ に対して、$d(u,v)\le t$ となる$v\in C$ が高々1つ存在するとき、

$C$ は $t$ 個の誤りを直す ($C$ corrects $t$ errors) と言います。

よって、$t$ 個の誤りを直すとすると、$u\in C$ であれば、$d(v,u)\le t$ となる

$v\in C$ は存在しないということになります。

また、$d(C)=\min\{d(u,v)|u,v\in C,u\neq v\}$ とします。

ここで、$C$ が誤りを $t$ 個直すことと、$d(C)\ge 2t+1$ であることは同値です。
これは簡単なのですが、学生にやってもらおうと思っています。

感想ですが、このMiniature 5は、それほど難しくないと思うのですが、
他のものと比べると、学生にとっては少し難しいようです。

Miniature 16

は、少し先の章ですが、やってもらいました。

$I$ を閉 $0,1$ 区間とします。

$\{0,1\}^n\subset I^n$ とします。

この左は、$0,1$ の長さ $n$ の列を表します。

その列に応じた $I^n\subset {\mathbb R}^n$ の中の頂点の位置です。

例えば、列が $0,1,1,0,1,1$ なら、頂点 $(0,1,1,0,1,1)$ を表します。

また、超空間とは、${\mathbb R}^n$ の中で、1次元方程式

$a_1x_1+\cdots +a_nx_n=b$  を満たす点集合 $(x_1,\cdots, x_n)$ のことを指し、
$(a_1,\cdots, a_n)\neq (0,\cdots, 0)$ と仮定します。

主張は以下です。

定理

いくつかの超空間 $h_1,\cdots, h_m$ は、すべて ${\mathbb R}^d$ の原点を通らない
とする。さらに、この超空間の和集合は、頂点 $\{0,1\}^d\subset I^d$ のうちで、原点を除いたもの全てを通るとします。 このとき、$m\ge d$ である。

例えば、$d=2$の場合 なら、$(0,1),(1,0),(1,1)$ は同一直線上に乗らないので
この3点を通るような $1$ 本の直線は存在しないというのは、感覚としては当然です。

また、2本なら、$x_1=1$ と、$x_2=1$ があれば大丈夫です。
$x_1=0$, $x_1=1$ は、1本が原点を通るのでだめです。

一般にも、$x_1=1$, $x_2=1$, $x_3=1,\cdots, x_d=1$ として

$d$ 本で覆えるというのは分かります。

それが最小だというのがこの主張となります。

もし、$m<d$ であるとします。

$h_1,\cdots, h_m$ をその町空間とします。

その一次式を

$a_{11}x_1+\cdots +a_{1n}x_d=1, \cdots, a_{m1}x_1+\cdots+a_{md}=1$

とします。ここで、定数項はゼロではないので、その数で割っているため、定数項
は1として良いことになります。

このとき、$f(x_1,\cdots, x_d)=\prod_{j=1}^{m}(1-(a_{j1}x_1+\cdots+a_{jd}x_d))-\prod_{j=1}^d(1-x_j)$

のようにおきます。この関数のおき方がエクセレントです。

このとき、$f$ は、$I^d$ の頂点 $\{0,1\}^d$ においては、全て $0$ になります。

$(0,\cdots,0)$ の場合は、$1-1=0$ で、それ以外の頂点の場合は、$0-0=0$

となり、どちらにしても $0$ になります。

いま、$\{0,1\}^d$ 上の実数値関数全体を $V$ とします。

$V$ は有限次元ですので、ここから線形代数の活躍となります。

${\mathbb R}^d$ 上の関数を $V$ の関数だと思うとき、

このとき、$\varphi:C({\mathbb R}^d,{\mathbb R})\to V$ という

線形写像ができていることに注意しましょう。
ここで、$C({\mathbb R}^d,{\mathbb R})$ は、${\mathbb R}^d$ から ${\mathbb R}$ への連続関数全体とします。

$f$ を $V$ の元としたとき、$0$ に写ります。

また、$x^2_i$ と $x_i$ は $V$ では同じ関数となってしまいます。

つまり、$x_i^2-x_i$ はこの写像 $\varphi$ の核(カーネル)になります。

ですので、$V$ において、(${\mathbb R}^d$ における)多項式関数の

各単項式 ($cx^{i_1}_1\cdots x^{i_d}_d$ という形の項)は、$V$ の元としては、
2次の因子はなくてもよい、つまり $i_1,\cdots, i_d$ は高々 $1$ としてよいことになります。

つまり、多項式関数を $\varphi$ によって $V$ に写したものは、
$V$ の元として、$S\subset \{1,2,\cdots,d\}$ が $S=\{l_1,\cdots, l_p\}$ であるとき、
$c_Sx_{l_1}\cdots x_{l_p}$ のような項の一次結合で書けることになります。

ここで、$c_S\in {\mathbb R}$ です。
今、$x_S=x_{l_1}\cdots x_{l_p}$ と書きましょう。

以下、$\chi=\{x_S|S\subset \{1,2,\cdots, d\}\}$ が一次独立であることを示します。

もしそうだとすると、$m<d$ であるから、$f(x_1,\cdots, x_d)$ は、
$\pm x_1\cdots,x_d$ が次数最大の項で、 $V$ においてもそうです。

ということは、$V$ 上で $f=0$ であることから、この項が
他の $x_S$ の一次結合で書けなければなりません。
これはこれらの単項式が一次独立であることから矛盾します。

よって、$\chi$ が一次独立であることを示せばよいことになります。

$$\sum_{S\subset \{1,2,\cdots, d\}}\alpha_Sx_S=0\ \ \ \ (\ast)$$

とします。

今、$S\subset \{1,2,\cdots, d\}$ に対して、$x_S$ を代入します。
そうすると、$S$ の部分集合 $S’\subset S$ に対しても、$x_{S’}$ の項が残ります。
ですので、マトクセクの本文では、$\alpha_S\neq 0$ となる(包含関係において)

極小の $S$ をとって代入すればよいと言っています。

この辺もスマートな証明ですね。

それか、$|S|=1$ となるもの頂点をまず代入してそのような $S$ に
対して $\alpha_S=0$ になる。

次に、$|S|=2$ となるものを代入してそのような $S$ に対して $\alpha_S=0$ となる。

という具合にしたから順番にやっていってもよいと思います。
が、マトウセクの方がやはりスマートですね。

Miniature 10

は、グラフ理論と計算量についての話です。

グラフ理論とは、頂点と辺のある組み合わせ論的対象です。

ネットワークを抽象化したものということもできます。
この本でももうすでに何回か出てきました。
計算量は、計算機科学の分野の用語です。

最初の問題は、グラフの中に、いったいいくつの三角形、つまり、

周期３のサイクルが存在するか？という問題です。

グラフの頂点に $1$ から $n$ の番号をつけておきます。

グラフのサイクルとは、頂点 $i$ から出発して、それが辺で $j$ とつながっている。

また、$j$ が頂点 $k$ と辺でつながっている、さらに、$k$ が辺で $i$ とつながっている

という状態のことをいいます。

グラフの隣接行列 $A$ を以下のように定義します。

つまり、

$i\neq j$ であり、頂点 $i,j$ をつなぐ辺が存在したとき $a_{ij}=1$ 

で、

それ以外は $a_{ij}=0$ 

となる行列 $A=(a_{ij})$ です。

このとき、このグラフの頂点 $i,j,k$ の間に三角形が存在するかどうかは、

$A$ と $A^2$ の間の $(i,j)$ 成分がどちらもゼロではないことに同値となります。

これはちょっと考えれば分かります。

次の問題は、三角形が存在するかどうか検出するために、どれほどの
時間がかかるか？ということです。
それは、計算量というもので測ることができます。

つまり、$A,A^2$ が計算できればよいですが、

与えられているのは、$A$ ですから、$A^2$ がどれほどの時間で計算できるか
ということにかかってきます。

計算量とは、ある計算 $X(n)$ をするのに、

ある基準の計算を何回用いたか数えたものをいます。

その回数を $n$ によって表した時に、その回数のオーダーを考えるのです。

ここでは、計算量を測るのにラージオーというオーダーを使います。
(ラージオーについては以前書いたので、こちらを参照してください。)

ある計算をするのに、$n^3$ 位の

多項式オーダーである場合、つまり、$3n^3+2n+1$ 回かかっても、

$2n^3+n^2$ 回かかっても、全て、そのトップの次数の多項式をとることで、

$O(n^3)$ のようにかきます。

$O$ の中は、多項式とも限りません。

例えば、$n$ 番目のフィボナッチ数を計算するのに、足し算で計算すれば、

$O(n)$ のオーダーで計算できますが、掛け算を用いれば、$O(\log n)$ の計算量
でできることになります。(Miniature 1)

話を元に戻しましょう。

ここで、行列算の計算量を考えます。

行列 $A=(a_{ij})$, $B=(b_{ij})$ の積を考えるとき、

(ここで簡単のため、正方行列としておきます)、基準となる操作は、
掛け算です。行列を計算するのに足し算も使うのですが、足し算の回数は数えません。

その理由は、掛け算に比べて足し算はその桁に関しておよそ線形回くらいの操作で

大丈夫だが、掛け算は、2乗のオーダーくらいの計算回数がかかります。

例えば、0から9までの九九、0から9までの足し算をそれぞれ計算回数1回と
カウントすることにします。
このとき、$n$ 桁の数を２つ足すことと、２つかけることでは、
小学校の筆算を思い出してもらえばわかる通り、
前者は線形のオーダーつまり、$O(n)$ であるのに対し、後者は、$O(n^2)$ となります。
ですので、足し算の計算量は、掛け算にしてみれば、無視できるレベルだという
ことがわかります。

なので、計算回数の基準を掛け算にしてしまって、足し算をカウントしないという

ことにしてもよいわけです。

そうすると、(かけ算1回を1としてカウントした計算量で)
$n\times n$ の行列の掛け算の計算量は、それぞれの

成分ごとに $n$ 回の掛け算がありますので、全部計算するのに、
$n^3$ 回となるのです。

元の話に戻ります。本当に行列の掛け算を計算するのにをするのに、

$n^3$ 回かかるのでしょうか？

実は、2つの行列をかける計算量は、$O(n^3)$ より真に小さくすることができます。

Strassen のアルゴリズムというのがあります。(マトウセクの本文にもあります。)
$2\times 2$ 行列の積を計算するのに、本来８回かけ算をする必要がありますが、
かかることになりますが、実は７回でいけるのです。
下記の文献参照。

ですので、$4\times 4$ 行列を積を計算するのには、それを応用することで

$7\times 7=49$ 回の計算量で計算できます。本当なら64回必要です。

一般に、$n=2^k\times 2^k$ 行列の積を計算するのには、$7^k$ 回の計算量 

で充分となります。

つまり、$7^k=7^{\log_2{n}}=n^{\log_27}$ で、

$\log_27$ は大体2.8くらいですので、

$O(n^{2.807})$ の計算量ということになります。

これにより、$n^3$ より少し改善されたことになります。

このシュトラッセンの方法が最初の3より小さいアルゴリズムのようです。

このようにさらによい計算方法が今では考えられており、
現在知られている最小のオーダーは、この本では、Coppersmith-Winograd による、$O(n^{2.376})$ と書いてあります。
現在この競争がどれほど進展しているんでしょうか？

予想として、このオーダーが2でいけるのではないかと信じられているようです。

参考文献

• Strassen, Volker, Gaussian Elimination is not Optimal, Numer. Math. 13, p. 354-356, 1969
• D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions. J. Symbolic Comput. 9 (1990), no. 3, 251–280