筆者が躓いた所

線形代数の本を開くと、行列は実は線形写像と等価ですとか、ユニタリ変換がどうのこうのとか言った話を良く目にします。はて、それらを使ってどんな面白い計算が出来るのでしょうか。

応用例1 : システムの安定性評価

問題設定

システム（ビルの空調システムや火力発電所を想像して頂けると良いです）を安定に運用できる条件を考えます。

時刻が $t\to t+1$ になる時、内部状態が時刻 $t$ のパラメータの線形結合に変化するとします。

例えば、空調システムにおいて、$2$ つの状態

$x:設定温度からの偏差(現在の室温-目標温度)$
$y:空調機の出力(クーラーの強さ)$

として、

$$x_{t+1}=0.9x_t-0.2y_t$$

$$y_{t+1}=0.4x_t+0.8y_t$$

といった具合です。この場合、係数がシステム固有の情報を表しており、係数をいい感じに設定することで $x_t\approx 0$ を保ちたいな〜そのうえで $|y_t|$ 小さいと良いなぁ〜などと思うわけです。

ひとまず。

システムが安定、つまり暴走しない事を保証する上で、以下の事を保証する必要があります。

システム運用中に、設定温度からの偏差や空調機の出力が際限なく上昇するといった、状態の歯止めのきかない変化が起きない。

また、システムを安定に運用できる範囲内で、効率を最大化したいです。なので、システムにはこちらが設定できるパラメータ $\theta$ が存在するとします。

つまり我々の興味は、システムが安定な $\theta$ の範囲です。

定式化例

時刻 $t$ におけるシステムの状態を ${\mathbf{x}}_t$ で表し、システムをパラメータ $\theta$ を用いて行列$A(\theta )$ で表す。この時、

$${\mathbf{x}}_{t+1}=A(\theta ){\mathbf{x}}_t$$

$${\mathbf{x}}_t=A^t(\theta ){\mathbf{x}}_0$$

である。

システムが安定であることは次で定式化される。

$${\mathbf{x}}_0が有界\Rightarrow {\mathbf{x}}_tが有界$$

ここで、$A(\theta )$ が対角化可能であるならば、${\mathbf{x}}_t$ は次の表示を持つ。

$${\mathbf{x}}_t=P(\theta )\left(\begin{array}{ccc}{\lambda }_1(\theta {)}^t& & 0\\ & \ddots & \\ 0& & {\lambda }_n(\theta {)}^t\end{array}\right)P(\theta {)}^{-1}{\mathbf{x}}_0$$

今任意の ${\mathbf{x}}_0$ を考えており、$P^{-1}(\theta )$ は正則行列なので、結局

$$システムが安定\iff |{\lambda }_i(\theta )|\le 1(\forall i)$$

である。

応用例2: 行列の分解

問題設定

$C$ を $n\times m$ 行列とします。

$$C\mathbf{x}$$

の計算を高速化したいです。 ここで、$C$ は一般とは限りません。お好きに（くだらなくならない程度に）性質を付加して構いません。

定式化例

$$r:=\text{rank}(C)$$

とする。ここで、行列 $A:n\times r,B:r\times m$ であって、
$C=AB$
を満たすものが存在する。

$$r\ll n,m$$

ならば、

$$C\mathbf{x}=AB\mathbf{x}$$

とすることで計算が高速化される。

計算量は $nm$ から $r(n+m)$ になる。例えば $n,m=1000,r=4$ の時, $125$ 倍速になる。

感想

世の中の多くの物は行列でかけます。なので、その行列について詳しいと嬉しいというメリットがあると思います。

空調の話について、システムが暴走しないでほしいという我々のふわっとした要求が、ある数値 $\lambda$ を用いて $|\lambda |\le 1$ というとても簡単な条件で出てきます。これならばチェックも簡単でマニュアル化等できますし、のちの応用でも使える気がします。　　
なお、 $|\lambda |<1$ を条件とすることで、 なんと $x_t,y_t\to 0$ を保証できます。つまり、設定温度への収束を保証しつつ将来的な消費電力 $=0$ まで保証できるわけで、これはちょっとアガります。

$\text{rank}$ の話について、これは機械学習で良く起こると言われており、計算資源に難がある研究環境で特に頻繁に実用されています。

筆者が躓いた所

私たちは $\mathbb{R}$ や $\mathbb{C}$ の世界の問題を解きたいのであって、それより一般化した話はちょっと、怖いです。

応用例: 動的計画法（マルコフ決定過程文脈）によるゲームAI

問題設定

ゲームAIを作ることを考えます。

ゲームとして、ブロック崩しやテトリス、ルービックキューブを考えます（抽象的に言うと、マルコフ性を持つ $1$ 人プレイゲームを仮定していますが、深く考える必要はないです）。

特定のゲームを選ぶと、状態集合 $S$, 行動集合 $A$, 即時報酬関数 $R:(S,A)\to \mathbb{R}$, 遷移確率関数 $p:(S,A,S)\to [0,1]$, 割引率 $\gamma \in [0,1)$ が既知あるいは設定できるパラメータとして手に入ります（詳しくは説明しません、諸々の定数と思っていただければ良いです。また、$\sup |R|<\infty$）

行動価値関数 $q:(S,A)\to \mathbb{R}$ を定義します。

この時、次の命題が成立します:

$q$ についての方程式(ベルマン最適方程式)

$$q(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s,a)\underset{a^{\prime }}{\max }q(s^{\prime },a^{\prime })$$

を満たす $q$ を （存在するならば）$q^{\ast }$ と置く。
ここで、各盤面 $s\in S$ について

$$\arg \underset{a}{\max }{q}^{\ast }(s,a)$$

を達成する行動 $a$ を選択する戦略は最適戦略の１つである。つまり、即時報酬関数によって定義される、ゲーム全体を通した収益を最大化する戦略である。

つまり、我々の興味は、$p,S,A$ が与えられ、かつ $R,\gamma$ を定義した時、ベルマン方程式を満たすような関数 $q^{\ast }$ を求める事です。$q^{\ast }$ が一度求まれば命題の戦略を取ることで文字通り最適なプレイが実現され、それは時に人のプレイを凌駕するでしょう。

なお、このアプローチによるゲーム解析を動的計画法と呼びます。

定式化例

距離空間から出てくる著名な定理の１つに、バナッハの不動点定理というものがある。

バナッハの不動点定理（縮小写像の原理）
$(X,d)$ を完備距離空間とし、$f:X\to X$ を $X$ から $X$ 自身への縮小写像とする。この時、次の $2$ つの命題が成立する:

1. $f(x^{\ast })=x^{\ast }$ を満たす $x^{\ast }\in X$ がただ $1$ つ存在する
2. $X$ 内の任意の初期点 $x_0\in X$ を選び、漸化式 $x_{n+1}=f(x_n)$ によって点列 $\{x_n\}$ を定義すると、この点列は $n\to \infty$ のとき不動点 $x^{\ast }$ に収束する

今回、ベルマン作用素 $T$ を

$$(Tq)(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s,a)\underset{a^{\prime }}{\max }q(s^{\prime },a^{\prime })$$

とすると、 $T$ は一様ノルムに置いて縮小写像であり、かつ $T{q}^{\ast }=q^{\ast }$ を満たす。よって、

$$q_{n+1}=T{q}_n$$

と更新していくことで $q^{\ast }$ が求まる。なお、収束の速度は指数的である。

感想

$q^{\ast }$ が満たすべき方程式が手に入ったと思ったら、それを漸化式とみなして更新を繰り返すだけで $q^{\ast }$ が求まってしまいました。あっけないものです。

まぁ、実際の（面白みがある）ゲームでは $|S|>10^{20}$ とか $|S|>10^{73}$ とかになってしまって、計算回らないんですけどね。

ともかく。$q$、 つまり ${\mathbb{R}}^n$ や ${\mathbb{R}}^{\infty }$で記述された方程式の問題が、抽象化を推し進める分野から出た結果によって鮮やかに解かれたわけです。

また、今回 $q$ は引数がせいぜい可算無限ですが、ゲームの設定によっては $q$ は引数に実数を取りえます。これは行動空間や状態空間が非加算無限であれば良く、例えば車の自動運転などでは実数として扱うのが自然でしょう。

そして、その場合でも大筋は変わりません。これは成功裏に「関数同士の距離」や「関数の収束」を考えている事になり、これらの拡張を踏まえると集合と位相・関数解析のような抽象化した議論を経るのが自然です。

筆者が躓いた所

私たちは $\mathbb{R}$ や $\mathbb{C}$ の世界の問題を解きたいのであって、それより一般化した話はちょっと、怖いです。

応用例: 情報理論における誤り訂正符号

ある通信局から別の通信局に $01$ 列を送る事を考えます。

通信の過程で、ノイズが入ってしまいます。具体的には、各文字について、確率 $p$ で反転してしまいます。

ここで、送りたい文字列に追加で誤り訂正のための符号を追加することで、誤りに強くする方法を考察します。

単純なものとして、繰り返し符号化を紹介します。例えば

$$110101$$

を送りたい時、

$$111111000111000111$$

を送るという取り決めを考えます（空白は見やすさのためで、実際に送られる文字列にはありません）。

文字列を復元する側はこう考えれば良いです:前から３文字ずつ見ていく。 $0,1$ で多い方を採用する。

前回の例で言えば、

$$110111001011100100$$

が届いたならば、

$$111111000111000000\to 110100$$

と復元することになります。

文字ごとの誤り率は $3p^2-2p^3$ です。 $p\ll 1$ , 例えば $p=0.05$ ならば $0.00725$ となり、送る文字列長が短い間は実用的になるでしょう。

ここまではちょっとした算数パズルのようですね。

ここからは、より効率的な符号を考えたいです。

符号の誤り訂正能力が $t_0\in \mathbb{N}$ であることを次で定義します:

符号に発生したノイズが $t_0$ 個以下である時、元の符号を正しく復元できる。なお、個数には訂正の為に追加した bit に発生したものを含む。

我々が求めたいのは、元々送りたい 01 列の長さに対して割合が小さい bit 数で、かつ誤り訂正能力が高い符号です。さらに、要求する誤り訂正能力に対応して付加する訂正 bit を少なく出来ると理想的です。

ただし、簡略化のため以下の仮定を入れます:

• 送りたい $01$ 文字列の長さは全て等しい
• 付加する誤り訂正 bit の個数も全て等しい

議論の文脈がないのでアレなんですが、結構自然な仮定です。

定式化例

ここで、 $BCH$ 符号を導入する。

概要:

$GF(2^m)$ の原始元を $\alpha$ とし、$d$ を $n=2^m-1$ 以下の任意の正整数、$d=2t+1$ を満たす $t$ を導入する。この時、生成多項式を次のように定義する:

$$g(x):=\alpha ,{\alpha }^3,{\alpha }^5,\dots ,{\alpha }^{d-1}をすべて根に持つような、{\mathbb{F}}_2上の多項式の中で次数が最小のもの。$$

この時、 $g(x)$ により生成される巡回符号（という、別で定義される符号）を BCH符号と呼ぶ。

性能:

全体の符号長 = $2^m-1$
元々送りたかった01列長 $\ge$ $2^m-1-mt$
誤り訂正能力 $t_0\ge t$

つまり、誤り訂正能力 $t_0$ を持つ符号化方を、追加 bit 数 $\approx$ $t_0{\log }_2(元の文字列長)$ 程度で得られる。

感想

長さ $N$ の $01$ 列を送りたい時、最初の「３個繰り返し符号」は訂正能力=1を得るために $2N$ の追加 bit を付加していました。

しかし、代数学の力を借りた $BCH$ 符号では、 ${\log }_{2}N$ の追加 bit でこれを実現しています。つまり、オーダーレベルでの削減に成功しているわけです。

おまけに $BCH$ 符号は誤り訂正能力を簡単に調整可能ですので、遥かに実用性が高いでしょう。

元々は $01$ 列を効率的に送りたかったというだけなのに、こういった議論が突然出てくるのだから驚きます。