PythonとGo言語でSlackからTogglとスプレッドシートを操作するbotを作った

機械学習に全然関係ないです

togglという時間を計測したり分析してくれるサービスがありますね
最近勉強時間を測って振り返ってみようと思い使っているが、スマホやブラウザから操作すると大抵タイマーをストップするのを忘れて作業時間が43時間になったりすることがよくある

正直タイマーのスタートやストップのために一々スマホアプリやwebブラウザを開くのは面倒で困る。
という訳でいつもよく見るslackやtwitterから操作すれば面倒に感じないのでは?と思い勉強の息抜きも兼ねてtogglのタイマーを操作してくれるslackbotを作ることにした。すでにそういうものがある?まあ・・・うん・・・・

最初はpythonで作ったけど後からgo言語でも作った
以下を参考にした

Real Time Messaging APIで秘書botを作ってみる - adish intelligence
golang で始める Slack bot 開発 - at kaneshin
GitHub - toggl/toggl_api_docs: Documentation for the Toggl API

やっていることは、特定のキーワードに反応して対応する操作を行い、メッセージを返すといったもの
例えばstartと入力すればtogglのタイマーをスタートする、add desc hogeと打てばそのtogglのタイムエントリーにhogeという説明文を追加するとか
個人のtogglのAPIトークンを使って操作するので同チャンネル内の他の人からは操作できないように、メッセージの送信者のメールアドレスを確認して特定のユーザーなら操作を行うといったものにしておいた

f:id:Owatank:20180128143706p:plain f:id:Owatank:20180128143316p:plain

それとは別に計測した時間をgoogleスプレッドシートに書き込んでくれる機能も盛り込んだ
用意しておいたスプレッドシートから対応する日付の行を持ってきていい感じに出力してシートを更新したりする

f:id:Owatank:20180128144313p:plain

コードはここ(追記: Goの方パターン諸々綺麗に直しといた)
Go言語のほう
Pythonのほう

開発は全然したことないから関数名、パターンだったり例外処理だったりと雑なのだ
Pythonをここ最近触っていたせいか初めてgoを触ったせいなのか色々とギャップがひどかった。Pythonのが色々とゴリ押しで書けるところがあるからか...

期待値と分散(離散値の場合)について

青いイルカの深層学習の本やスパース性に基づく機械学習の本でも、損失関数の説明あたりで平均期待二乗誤差といった誤差の期待値を最小化する式が出てくる

なんとなく雰囲気で読んでいて、いつも期待値が得体の知れないもののように感じて詰まってしまっていた。
適当に調べると期待値は ある関数f(x)の確率分布p(x)の下での平均値をf(x)の期待値と呼ぶ とか書かれていた。
参考(12-3. 確率変数の期待値 | 統計学の時間 | 統計WEB)

悩むのは 確率分布p(x)の下での平均値 というところ。確率ってP(X=a)というのは何%でX=aが起きるかを示しているものだからそれ自体が平均っぽいものじゃないのか?と考えていた。

スパース性に基づく機械学習でも期待値で詰まっているところがあるし、悩みっぱなしは良くないと思い、「プログラミングのための確率統計」という本を読むことにした

読み進めて期待値について自分なりにイメージを掴んだのでメモメモ

機械学習において nクラス分類 というのは、データの特徴という入力を渡し結果として分類の結果(nクラスのうちの一つ)を受けとるといったものを考える。ソフトマックス関数でいえば最も確率が高いもののクラスを選ぶ

これは{ \displaystyle X}を入力、{ \displaystyle Y}を結果としたら { \displaystyle Y = f(X)} みたいに数式で表せるはず

でも現実にはノイズの混入を避けることができずXの測定値が同じでも、得られるYの測定値は異なるということが起こってしまう。 { \displaystyle Y = f(X) + b }な感じかな?

{ \displaystyle Y = f(X)}、つまりX=aなら必ずY=bが出るよみたいに確定して言えないならせめてX=aのときは何%くらいでY=bが出るとは言えないだろうか?

こういった表現は条件付き確率{ \displaystyle P(Y=b|X=a)}で表すことができる

ところで新年明けましたね。くじ引きをしたのではないでしょうか。ということで次のようなくじ引きをする

100円、500円、1000円のいずれかを払うと1回引けるくじがある。それぞれのくじの内容は

  • 100円くじ : 80%で50円、15%で100円、5%で300円もらえる
  • 500円くじ : 60%で250円、25%で500円、15%で1500円もらえる
  • 1000円くじ : 35%で500円、45%で1000円、20%で3000円もらえる

500円くじに挑戦したときいくらぐらいもらえるだろうか
これは条件付き確率{ \displaystyle P(Y=もらえる金額|X=500円くじを引く)}となる

確率ではもちろん「60%で250円、25%で500円、15%で1500円もらえる」と言うことができるがそうじゃない。そういった揺らぐ値ではなく揺らがない具体的な値としての答えが欲しい。例えばこのくじ引けば大体5000兆円儲かるよみたいな
そんな役割を果たす具体的な値のことを期待値と呼ぶそうだ

確率分布p(x)は揺らぐからこそ平均としてこんな値が出る、といった一目でわかる値が欲しいんだな
ちなみに期待値は平均みたいにn個の値を合計してnで割るということはしていないので平均値と期待値は違うもの、でいいのかな

次に期待値と呼ぶのはいいけどどうやってその値を求めるか
確率は起こりうる事象を全て足した結果は1にならないといけない

例えば全ての出る目の確率が等しい6面サイコロだったら
(1がでる確率)+(2が出る確率)+...+(6がでる確率) = 1

ここで
{ \displaystyle P(Y=250|X=500) + P(Y=500,X=500) + P(Y=1500,X=500) = 1}
としよう

どのくじを引くかは任意で、くじの種類によってもらえる金額は変わってくるけどくじの内容の確率が変化するということはないので独立とする

図で表すとこう
f:id:Owatank:20180123105522p:plain

面積1の正方形の中に確率の値を面積とした領域がある感じ

同時確率は
{ \displaystyle P(Y,X) = P(Y|X)P(X) }

独立なときは{ \displaystyle P(Y,X) = P(Y)P(X) }としていいので{ \displaystyle P(X)=1}とすると、結局は{ \displaystyle Y}がいくらでるかの確率(周辺確率)で考えることになる

次に上の画像の各領域において、いくらもらえるかの値段を高さで表現する
f:id:Owatank:20180123105959p:plain

デコボコしている。このデコボコを均一にして綺麗な直方体のようにしたとき、面積はYがとりうる全ての確率P(Y)になるから、その時の高さが{ \displaystyle Y}がいくらでるかの平均にならないだろうか。

f:id:Owatank:20180123112414p:plain

その高さはどう計算するかというとこの体積を雪だと思えば雪が少ないとこに分けてあげて均一にするだけ、それはそれぞれの体積を足した結果と変わらないはず
体積自体を増やしたり減らしたりすることはしてない


つまり

{ \displaystyle E [Y ] = 250\ast P(Y=250,X=500) + 500\ast P(Y=500,X=500) + 1500\ast P(Y=1500,X=500) }

こうすれば期待値(体積)を求められる。ちなみにYの期待値を{ \displaystyle E [Y ] } で表した。結果は
{ \displaystyle E [Y ] = 250\ast 0.6 + 500\ast 0.25 + 1500\ast 0.15 = 500 }

平均として500円もらえるっぽい
「0.6%で250円、0.25%で500円,0.15%で1500円もらえるよ」よりも「期待値として500円貰えるから損はしないよ」と言われる方が参加する人は増えるかな

「期待値として500円貰えるから損はしないよ」と言われてやってみよっかな〜〜〜、って思ったときあくまで期待値だし、期待値が出たら損をしないだけ。
{ \displaystyle Y}がいくらでるかは揺らぐ値だから期待値が必ずでるとは限らない。そこで期待値ではない値{ \displaystyle y}が出た時、それが期待値からどれくらい離れているか計算して、外れた時のリスクはどれくらいかといったものを調べてから挑戦したい気持ちもある

かなり離れていたら損をしたときのショックはでかいし、離れていなければダメージはそこそこ少ないし・・・まあいいか・・とか対策を練ってから挑みたい

この距離は期待値を{ \displaystyle \mu }、くじを引いた時の実際の金額を{ \displaystyle y }とすれば距離は{ \displaystyle | \ y - \mu \ | }でいいはずなんだけど、絶対値をだと場合分けしないといけなかったり微分できない点があったり不便らしい。そのため{ \displaystyle ( \ y - \mu \ )^{2} }といった2乗の形、自乗誤差と呼ばれるものを使う

二乗しているため期待値{ \displaystyle \mu }から離れるほど値は大きくなるのが特徴
{ \displaystyle y }は必ずこういった値が出る、というものではなく揺らぐ値なので{ \displaystyle ( \ y - \mu \ )^{2} }揺らぐ値になってしまう。ダメじゃん

この期待値からの外れ具合を表す値の揺らがない値、つまり外れ具合を表す値の期待値が欲しいので

{ \displaystyle V[Y] = E [( \ y - \mu \ )^{2}] }

を計算すれば外れ具合を表す値の期待値が得られる。
そしてこの{ \displaystyle V[Y] }のことを分散と呼ぶ。分布の散り具合・・かっこいい・・・
分散は値が大きければ散らばっている、値が小さければ散らばり具合が少ないといったことを示してくれる

さっそく計算して求める
{ \displaystyle V[Y] = (250-500)\ast (250-500)+(500-500)\ast (500-500)+(1500-500)\ast (1500-500) = 1062500 }

うーん・・・値が大きいってことは散らばっているということだけど、どれくらい散らばっているのかわからない・・・

距離がそもそも{ \displaystyle ( \ y - \mu \ ) }、単位として{ \displaystyle m }だとしたら、二乗しているということは分散は{ \displaystyle m^{2} }長さの二乗を表していることになる。単位が違うから比較が難しい。
なら平方根を取れば{ \displaystyle m }に直せるじゃん。取ってみよう

{ \displaystyle \sqrt{V [ Y ] } = \sqrt{1062500} = 1030.7764064 }

分散の平方根を取ったものを標準偏差と呼ぶ。期待値は{ \displaystyle \mu = 500 }だから悪くはないのかな?

最後に500円くじを500回試行したときの1回ごとの累積和をプロットしてみた
ソースはここ
github.com

横軸は試行回数、縦軸はその時の所持金額とする。
まず500回試行して250円、500円、1500円がどれくらい出たかというと

f:id:Owatank:20180123120519p:plain

だいたい事前に設定した「60%で250円、25%で500円、15%で1500円もらえる」に従っているので良しとする。

3人がくじに挑戦したとしてそれぞれの累積の結果は

f:id:Owatank:20180123120651p:plain

f:id:Owatank:20180123120711p:plain

f:id:Owatank:20180123120726p:plain

赤の線が期待値を表し、赤の点線が期待値±標準偏差を表す。この点線内に点が集中していないことから分布がひどく散らばっているのがわかる。
最初の人はかなり勝っているのに対し、三番目の人はかなりボロ負けしている。
二番目の結果を見る限り、最初は負け続けていても途中から利益が出ているのを見ると、負け続けても諦めなければ勝てるといった気持ちも大切なのかなとか思う。ギャンブル試行だ・・・

大事なことは期待値、分散、標準偏差は揺らがない値で確率分布における目安のような役割を果たす値ということ。

参考文献(Kindle版もあるよ)

プログラミングのための確率統計
プログラミングのための確率統計
プログラミングのための確率統計

スパース性に基づく機械学習のわからないとこのメモ

タイトル通りL1ノルムとか正則化あたりを理解しようと思ったので「スパース性に基づく機械学習」という本を読んでる
わからないというより日本語が理解できないところがいくつかあったのでメモとして残して、理解できた部分はここでまとめることにする。
わからないとこは箇条書きする

未解決のとこでわかる人いれば助けてほしい・・・・・・・

第1章

スパース性というのは「まばら」を意味する単語
この本だとn次元のベクトル{ \displaystyle \vec{x} }が非ゼロの成分がごく一部しかなくて、それ以外の成分が0なものとかを指す
{ \displaystyle \vec{x} = (1,1,1,0,0,...,0)^{T} }
こんな感じ

スパース性の考えが機械学習にどう役立つか?というのを「ひよこのオスとメスの分類」で考える
ひよこのオスとメスを仕分けするバイトがあるとして、どう仕分けするか。クチバシとか足とか全身をくまなく調べて仕分けする方法を取った時、全身を見るのでかなり時間がかからないだろうか。
実際に仕事としてやっている人たちはどうやら肛門や羽といった一部分のみを調べて仕分けしているそう。
これは全身、「すべての特徴」を見るのではなく「ある一部分の特徴」にのみに注目するだけで仕分けができるということを意味している。スパース性の考えとしては一部分(非ゼロ)ということになる。

また「すべての特徴」がひよこのオスとメスの分類に関係あるとしたら沢山のひよこの「すべての特徴」をくまなく調べないといけないが、「ある一部分の特徴」のみが関係あるとしたら、少数のひよこからその関係を調べるだけで済む。

こんな感じでスパース性は「計算量」の節約の他に「統計に必要なサンプル数」といった統計的な問題を良い方向に持っていってくれることができる。

ここで「ある一部分の特徴」のみが関係しているはずと仮定を立てたとして、「ある一部分の特徴」がどこなのかはわかっていない状況なのでその特徴は自分たちで探さないといけないというのも重要

  • ページ2の「スパース性の拡張のもう一つの例として行列の低ランク性が~」の部分 --- 解決

    d行T列の行列を推定する問題で行列のランクが{ \displaystyle r}であるということは、T個の学習課題に共通する{ \displaystyle r}個の要因が存在することを意味する

省略したけど大体ここら辺が理解できなかった

まず特異値というのは、これは行列Aを相似変換して対角行列の形にしたとき、その対角成分が非ゼロな値のものを特異値と呼ぶっぽい
そして相似変換された元の行列Aのランクはこの特異値の数と一致する性質があるとのこと。

$$ A = \begin{pmatrix} a_1 & a_2 & a_3 \\ a_4 & a_5 & a_6 \\ a_7 & a_8 & a_9 \end{pmatrix} $$

行列Aが(3,3)行列だったとして、第3列目が第1列目の3倍、つまり{ \displaystyle a_7 = 3a_1, a_8 = 3a_2, a_9 = 3a_3 }といった関係だったとしたら、3次元のうち一つの次元は残りの次元で表現できるということを意味する。
基底でいえば線型独立ではないって言えるということかな
スパース性でいえば、3次元の「すべての特徴」を見る必要はなくなったといえる

ここミスってる気がするから修正する

第2章

  • ページ4の「例示することが容易でも、ルールとして言い表すことが難しい事柄が多数存在する」 --- 疑問

MNISTみたいな手書き数字の分類で言えば、例示で「手書き数字の0と9の区別」を説明するのは簡単だけど、ルールで説明するには「基準としての手書き数字0と9」を定義しなければ説明できないが、基準を定義するにはほぼ無限にあるサンプルが必要であり困難ということであってる?

  • ページ5,6の相対エントロピーやロジスティック損失の導出 --- 未解決

イルカの方の深層学習で導出したような気がするのでそっちを復習してまとめるはず

この本では予測や分類を「入力ベクトル{ \displaystyle \boldsymbol{x} }が与えられたもとで、どの程度よくラベル{ \displaystyle y }を予測(分類)できるか」という観点で評価する。データから学習して、分類などを行いたいデータの背後にある未知の確率分布{ \displaystyle P(\boldsymbol{x},y) }に関する期待値を求める

でもこの期待値は未知の確率分布{ \displaystyle P(\boldsymbol{x},y) }に関する期待値だから直接評価はできないため、訓練データから{ \displaystyle P(\boldsymbol{x},y) }ある程度近似するということ。

統計学の授業で「日本人の20歳の平均身長」を求めたいとき全ての20歳の日本人のデータを集めるのはほぼ無理というか難しいから、例えばいくつかの大学に協力してもらったりして有限の人数、いくつかの20歳の日本人のデータを集めて「日本人の20歳の平均身長」を近似するという話に似ている気がする

そのため訓練データから期待誤差を近似したもの、最小化をすることを経験誤差経験誤差最小化と呼ぶ
深層学習でよく定義する訓練誤差とかはこっちを指してるんだな

深層学習の本で入力と重み{ \displaystyle \boldsymbol{w} }とバイアス{ \displaystyle b}を用いた { \displaystyle f(\boldsymbol{x}) = \boldsymbol{x}^{T} \boldsymbol{w} + b }といった曲線の式をよく見る。この曲線に従ってラベル{ \displaystyle y}を予測したりヌンヌン...
誤差を最小にするというのは訓練データでいえば{ \displaystyle f(\boldsymbol{x}) = \boldsymbol{x}^{T} \boldsymbol{w} + b }という曲線による予測が訓練データがもつ答え{ \displaystyle y}と大体一致して欲しいということ

f:id:Owatank:20171228125452j:plain

曲線の形をグニャグニャ変えていけばいつかは大体一致する曲線になっていくはず。{ \displaystyle \boldsymbol{w} }{ \displaystyle b}の値を変えていくと形は変わるので、最小化するとは最適な{ \displaystyle  \hat{ \boldsymbol{w}} }{ \displaystyle \hat{b} }を見つけること。

f:id:Owatank:20171228132907p:plain

最小化を達成するための{ \displaystyle  (\hat{ \boldsymbol{w}},\hat{b}) }定量と呼び、ハットをつけて区別するらしい

ある行列
{ \displaystyle \boldsymbol{X} = ( \boldsymbol{x_1}, ... , \boldsymbol{x_n} ) }
のランクが{ \displaystyle d+1}以上であれば、一意に解{ \displaystyle  (\hat{ \boldsymbol{w}},\hat{b}) }が定まる

ここが「?」となった。伝えたいことはランクが{ \displaystyle d+1}以上ということは解決したいことがらは{ \displaystyle d+1}次元で表現できるということ。3次元なら2次元で表現することは難しいから論外(というか自己符号化器の話になる?)として、{ \displaystyle d+1}以上なら次元が多くても、求めたい{ \displaystyle  (\hat{ \boldsymbol{w}},\hat{b}) }は定まるということかな。

訓練誤差が小さい値になったからといって近似したい期待誤差が小さいとは限らないことがある。こういう状況は取ってきた一部、訓練データにかなり適合してしまっているとかが考えられる。適合しすぎて期待誤差が大きくなってしまう現象を過剰適合、オーバーフィッティングと呼ぶ。過適合ってやつだ
訓練誤差が小さくなって、期待誤差もそこそこ小さくなることを汎化するという。よく汎化性能って単語見ますね

過適合を防ぎ、汎化性能を上げるにはモデルを制約し、誤差への当てはまりを抑えることが大事になってくる。モデルを制約する方法としては

  1. 多項式などの独立な基底関数の和として関数{ \displaystyle f }を表現し、その基底関数の数を小さく抑える
  2. 関数{ \displaystyle f }の何らかのノルムを抑える

む、難しい単語で書かれてる・・・・。今までの知識を振り絞って考えると1つ目は要するに「次元数を抑えろ」ということだと思う。基底関数でエッッと混乱したけど、曲線を表す多項式は行列で表すとき、極端な話単位ベクトルで構成される基底で分解して表現できるはず。基底関数の数を小さく抑えるというのはこの基底の要素である基底ベクトルの本数を減らすということ。基底ベクトルの本数が減るんだから次元数も当然減る。

近似したい曲線が3次式のする。この曲線を3次式以上で表現しようと考えると、できないことはないが近似したい曲線と形は離れていくかもしれない。それは汎化性能が落ちてしまうことになる。

2つ目は次元数を固定したときの係数(推定量){ \displaystyle \boldsymbol{w} }のとり方の制限かな。実数範囲から係数の値を選べるとしてある次数の係数はめっちゃ大きくとって別の係数は小さくとって・・・とバラ付きすぎるのは問題。実数のある値より大きい値は取らないみたいな制約を決めて{ \displaystyle  \hat{ \boldsymbol{w}} }を選ぶ方法をとるということ。

  • ページ12~14の平均期待二乗誤差 --- 未解決

ここ完全に頭追いつかなかった。
まず推定量{ \displaystyle \boldsymbol{w} }期待二乗誤差の訓練データに関する期待値
{ \displaystyle \bar{L}(\boldsymbol{w}) = E_T E_{\boldsymbol{x},y} (y-\hat{\boldsymbol{w}}^{T}\boldsymbol{\phi}(x))^{2})}と定義する

また次数pのとき { \displaystyle \boldsymbol{\phi} = (1,x^{1}, ... , x^{p})^{T} , \boldsymbol{w} = (w_0,w_1, ... ,w_p)^{T} }

このとき平均期待二乗誤差は
f:id:Owatank:20180101161043p:plain

(二乗が抜けていたので赤で修正)この導出が全然わからん・・・。第一行目でおそらく二乗の中身を \[ (( \hat{\boldsymbol{w}}^{T} + \bar{\boldsymbol{w}}^{T} - \bar{\boldsymbol{w}}^{T} + {\boldsymbol{w}^{\ast}}^{T} - {\boldsymbol{w}^{\ast}}^{T} )\boldsymbol{\phi}(x) - y )^{2} \]
こんな感じにして変換しているとは思うけど第二行目の変換で悩んでしまった。

※追記( 12/29 )

{ \displaystyle E_{T_r} }は推定量{ \displaystyle \hat{\boldsymbol{w}} }を見つけるために使った訓練データ(標本)からの期待値

{ \displaystyle \bar{\boldsymbol{w}} }は推定量{ \displaystyle \hat{\boldsymbol{w}} }の訓練データに関する期待値らしく{ \displaystyle \bar{\boldsymbol{w}} = E_{T_r}\hat{\boldsymbol{w}} }と定義している


最適性条件というのは
\[ E [ \boldsymbol{\phi}(x)(\boldsymbol{w}^{\ast} \boldsymbol{\phi}(x) - y) ] = 0 \]

{ \displaystyle \boldsymbol{w}^{\ast} }は全てに当てはまる理想のパラメータだから、{ \displaystyle (\boldsymbol{w}^{\ast} \boldsymbol{\phi}(x) - y) }のところが0にならないといけないということなはず

平均二乗誤差に存在する{ \displaystyle {\sum}_x }は計量行列と呼び以下のように定義される

\[ {\sum}_x = E [ \boldsymbol{\phi}(x) \boldsymbol{\phi}^{T}(x)] \]

この計量に基づく距離を

\[ || \boldsymbol{w} - \boldsymbol{w}^{\prime}||_{\sum{x}} = \sqrt{ (\boldsymbol{w} - \boldsymbol{w}^{\prime})^{T} {\sum{x}} (\boldsymbol{w} - \boldsymbol{w}^{\prime})} \]

と定義しているそうだ


ちなみに最後の行の第一項は期待値{ \displaystyle \bar{\boldsymbol{w}} }のまわりでの推定量{ \displaystyle \hat{\boldsymbol{w}} }の揺らぎを定量化する項、ばらけ具合ということで分散になって、第二項は期待二乗誤差{ \displaystyle L(\boldsymbol{w}) }を最小化するパラメータ{ \displaystyle \boldsymbol{w}^{\ast} }と推定量の期待値{ \displaystyle \bar{\boldsymbol{w}} }の距離の2乗でありバイアス(近似誤差)定量化する項になる
近似して求めたいのは期待二乗誤差を最小化する理想のパラメータ{ \displaystyle \boldsymbol{w}^{\ast} }であり{ \displaystyle \bar{\boldsymbol{w}}=\boldsymbol{w}^{\ast} }になれば推定量{ \displaystyle \hat{\boldsymbol{w}} }は不偏推定量(訓練データ(標本)から求めた期待値が母集団の期待値と一致)になるのはわかる。

最適性条件などを使って平均期待二乗誤差を導出しているらしい。まとめておく

  • ページ18の制約付き最小化問題と罰則項付き最小化問題の等価性 --- 未解決


    ヤバイ

    文がわからなかっただけなので後回しかも

※追記(1/1)
ラグランジュの未定乗数法のことという神の声を頂いた

第3章

{ \displaystyle \boldsymbol{y}= \boldsymbol{x}^{T} \boldsymbol{w}}を満たすようなパラメータ(ベクトル){ \displaystyle \boldsymbol{w} }を決めるとき、ベクトルの非ゼロ要素は少ない方がいい。

例として電車を考える。目的地まで電車で移動したいとき、同じ料金、同じ時間で到着するなら乗り換え({ \displaystyle \boldsymbol{w} }の非ゼロ要素として見る)は少ない方が嬉しくないだろうか。自分は乗り換えが苦手なので少ない方が助かる。

なので推定量{ \displaystyle \hat{\boldsymbol{w}} }を見つけるときの条件として新たに非ゼロ要素は k個 以下という制約を加えてあげればより良い{ \displaystyle \hat{\boldsymbol{w}} }を見つけることができると書いてあった。すごい。

しかし残念ながらこのような制約を加えた最適化問題の計算は現実的に困難であるそうだ。ええ・・・。
理由としては{ \displaystyle \boldsymbol{y}= \boldsymbol{x}^{T} \boldsymbol{w}}を満たすような{ \displaystyle \boldsymbol{w} }の組をしらみ潰しというかブルートフォース?とも言えるのだろうか、調べなくてはいけないから。次元数が増えれば増えるほど調べないといけない組の数は多くなってしまう。

困ってしまった。そこでL1ノルム正則化と呼ばれる手法が役に立つ。
ベクトル{ \displaystyle \boldsymbol{w} }のL1ノルムはベクトルの要素ごとの絶対値の線形和として

{ \displaystyle {\| \boldsymbol{w} \|} (l_1)  = \sum_{j=0}^d | w_i |}

で表される。
ベクトル{ \displaystyle \boldsymbol{w} }の非ゼロ要素の数が多いほど、L1ノルムの値も大きくなる。非ゼロの数が1、2、と増えていくのとは別でL1ノルムの値は要素の値によって比例して大きくなることに注意。

このL1ノルムと呼ばれるものを使って非ゼロ要素が少なくて、求めたい要件を満たすような{ \displaystyle \boldsymbol{w} }を見つける。最適化問題としては

{ \displaystyle minimize(\boldsymbol{w})  \,\, \,\, \hat{L}(\boldsymbol{w}) \,\, (  \,\, {\| \boldsymbol{w} \|} (l_1) \leq C  \,\,) }

あるいは

{ \displaystyle minimize(\boldsymbol{w})  \,\, \,\, \hat{L}(\boldsymbol{w}) \,\, + \lambda \| \boldsymbol{w} \| (l_1) }

と表される。また条件として{ \displaystyle C > 0 ,  \lambda > 0}

L1ノルムは{ \displaystyle  y = x^{2} }みたいな形をしているから任意の d次元ベクトル{ \displaystyle \boldsymbol{w} }のL1ノルムは凸関数になる

f:id:Owatank:20180102143841p:plain

なので最適化問題

{ \displaystyle minimize(\boldsymbol{w})  \,\, \,\, \hat{L}(\boldsymbol{w}) \,\, + \lambda \| \boldsymbol{w} \| (l_1) }

{ \displaystyle \hat{L}(\boldsymbol{w}) }が凸関数なら、凸最適化問題になると書いてあった。凸関数同士を合わせたものが凸関数になるという証明がなかったけど自明なのかな?

1次元ベクトル{ \displaystyle \boldsymbol{w} }のL1ノルムは

n = 100
x = np.linspace(-1, 1, n)

f = np.abs(x)
plt.plot(x,f,"r-")
plt.show() 

f:id:Owatank:20180102153358p:plain

こんな感じの直線で引けるけど、本に書いてあるL1ノルムの図形はひし形みたいなグラフになっている。ナンデダヨヾ(`Д´)ノ
よく読んだらひし形はL1ノルムの等高線を表していると書いてあった。
等高線は小学校のときに地形の等高線しか引いた記憶しかないけど、ここでは d次元ベクトル{ \displaystyle \boldsymbol{w} }のL1ノルムの値を高さとしたグラフが等高線となる。書いてみる

等高線を書くには方眼、meshgridが必要なので用意する

n = 30
x = np.linspace(-1, 1, n)
y = np.linspace(-1, 1, n)

xx,yy = np.meshgrid(x, y)

変数xxyyが方眼、グリッド線になってくれる。

次に描写したいL1ノルムの方程式を用意する。2次元のグラフとして表示したいので2次元ベクトル{ \displaystyle \boldsymbol{w} = (w1,w2)^{T} }として
{ \displaystyle f(w1,w2) = |w1| + |w2| }のようなL1ノルムの値を高さとして持つ { \displaystyle f(w1,w2) }を作る。
ここでは x軸をw1、y軸をw2として作ることにする。

meshgridで作ったxxyyは変数を見る限りこんな感じになってるはず
f:id:Owatank:20180102161104p:plain f:id:Owatank:20180102161001p:plain f:id:Owatank:20180102160844p:plain

上の水色と緑の線は5本だけど、プログラムとしてはn = 30とn本で指定される
{ \displaystyle f(w1,w2) }はこの [-1,1]区間の全ての点、組の結果を計算して作る

f = np.abs(xx)+np.abs(yy)

plt.contour(xx,yy,f)
plt.xlim(-1,1)
plt.ylim(-1,1)
plt.gca()
plt.show()

f:id:Owatank:20180102164853p:plain

ひし形になってくれた。 n の値を変えるとよりひし形っぽくなるのも確認できた。
等高線っぽさを見たいので別のメソッドで出力してみると

from mpl_toolkits.mplot3d import Axes3D
fig = plt.figure(figsize=(10,6))
ax = Axes3D(fig)
ax.contourf3D(xx,yy,f)

f:id:Owatank:20180102165031p:plain

いい感じに等高線っぽくなった

このことからL2ノルムでよく見る楕円の形はあるベクトルの要素からできるL2ノルムの等高線、楕円を図示していたということかな。

線形代数のまとめ その3(行列式について)

その2の続き

その2で写像って何だ?というとこから基底や逆行列についてメモした
最後で独立の意味って何だろう?とか任意のある行列に逆行列が存在するかの判定任意でとった基底の組が基底としての条件を満たしているかの判断はどうすればいいんだろうという疑問が浮かんで終わった。続きをメモする。

ところで線形代数の授業を受けた人なら行列の他にも行列式というのを見たことがあるというか解かされたことがあるんじゃないだろうか

$$ \begin{bmatrix} 1 & 9 & 3 \\ 7 & 5 & 3 \\ 3 & 1 & 5 \end{bmatrix} $$

こんな形のやつ。自分は思考を停止して余因子展開したり2次の行列式なんかに関してはもう{ \displaystyle (ad-bc)}して終わりッッって感じに解いていた。

前回で行列は写像、基底の移り先を教えてくれるものという見方をした。2次元空間において基底の組{ \displaystyle ( \vec{e_1} , \vec{e_2} )} (単位ベクトル { \displaystyle \vec{e_1} = (1,0)^{T} , \vec{e_2} = (0,1)^{T} })をとったとき
正方行列AとB
$$ A = \begin{pmatrix} 1.5 & 0 \\ 0 & 0.5 \end{pmatrix} B = \begin{pmatrix} 1 & -0.7 \\ -0.3 & 0.6 \end{pmatrix} $$
この2つの行列による写像はそれぞれ以下のようになる。
f:id:Owatank:20171223155552p:plain
元の基底ベクトルたちがそれぞれビヨーンと伸びたり縮んだり、方向自体変わったりした。

ここで線形空間ではベクトルの長さという概念はないが、この写像される前と後の基底ベクトルから成る四角形の面積を求めてみる。
ちなみに長さや角度の概念がある線形空間内積空間と呼ぶそうだ

f:id:Owatank:20171223160036p:plain
上の画像のように、{ \displaystyle S}{ \displaystyle S_A}{ \displaystyle S_B}を求めたい。
{ \displaystyle S}を単位ベクトルからできる四角形の面積、横=1{ \displaystyle ( \vec{e_1})}、縦=1{ \displaystyle ( \vec{e_2})}として{ \displaystyle S = 1}とする。
{ \displaystyle S_A}{ \displaystyle ( \vec{e_1})}が1.5倍、{ \displaystyle ( \vec{e_2})}が0.5倍拡大されたものだから、
{ \displaystyle S_A = \vec{e_1^{\prime}} \times \vec{e_2^{\prime}} = 1.5 \times 0.5 = 0.75 }となる。0.75倍ということは写像前より小さくなった。

{ \displaystyle S_B}は本には0.39倍と書いてあったがどうやって求めたんだ・・・・と悩んだが調べたら外積で求めることができるそうだ。電磁気学の授業でよく教授が右ねじ〜^^と言いながら親指をグルグルさせていたのをよく覚えている。

{ \displaystyle \vec{e_1^{\prime \prime}} = (1,-0.7)^{T} }{ \displaystyle \vec{e_2^{\prime \prime}} = (-0.3,0.6)^{T} }が成す外積{ \displaystyle S_B}
{ \displaystyle S_B = \vec{e_1^{\prime \prime}} \times \vec{e_2^{\prime \prime}} = 1 \ast 0.6 - (-0.7) \ast (-0.3) = 0.6 - 0.21 = 0.39 }
{ \displaystyle S_B}は 0.39倍とこっちも小さくなった。

ここで、

自分は思考を停止して余因子展開したり2次の行列式なんかに関してはもう{ \displaystyle (ad-bc)}して終わりッッって感じに解いていた。

この{ \displaystyle (ad-bc)}を見て欲しい。行列AとBが都合よく2次行列だしせっかくなので行列式とやらを求めてみる。2次行列の要素を
$$ \begin{pmatrix} a & b \\ c & d \end{pmatrix}$$
とする。このときAとBの行列式
$$ detA = \begin{bmatrix} 1.5 & 0 \\ 0 & 0.5 \end{bmatrix} = 1.5 \ast 0.5 - 0 \ast 0 = 0.75 $$
$$ detB = \begin{bmatrix} 1 & -0.7 \\ -0.3 & 0.6 \end{bmatrix} = 1 \ast 0.6 - (-0.7) \ast (-0.3) = 0.39 $$

!?

行列式の値 detA、detBと面積の値{ \displaystyle S_A}{ \displaystyle S_B}が一致している・・・しかもBの行列式は心なしか外積と計算式が似ている・・・・・・・・

というわけでこの本では上で求めた面積の拡大率のことを行列式とよぶ。(3次なら体積拡大率とも言える)
授業や試験に出た2次の行列式の問題はつまり四角形の面積の拡大率を計算させられていたということか・・・
イケてる小学生は行列式で平行四辺形の面積を求めるのかもしれん

ちなみに行列式正方行列に対してだけ定義されるものなため正方行列じゃないものに関しては行列式は考えないそうだ

行列式は行列の要素によっては計算結果から負の値が出ることも考えられる。負の面積拡大率って何だろう?という問いに関しては面積を求めたい図形が裏返しになる、イメージだそうだ。外積では「向き」という考えがあったしそんな感じかな。

f:id:Owatank:20171223165307p:plain

写像する前の画像(平面)は写像した後だと反転している(ステッキとか)。「面積自体は拡大したけど写像していた向きと同じ向きに拡大されたわけではない」ということを示したい時とかだと負の値を見れば一発でわかるね便利だね

行列式には以下のような性質がある
* { \displaystyle detI = 1}
* { \displaystyle detAB = det(A)det(B) }

一つ目は単位行列{ \displaystyle I }が「写像しても何も変化しない」行列なので、つまり元の面積を1倍すると考えると納得できる。
二つ目は行列Bで拡大して次に行列Aで拡大した拡大率{ \displaystyle det(AB)}{ \displaystyle detB}倍して{ \displaystyle detA}倍したと同じということ。

行列式が面積拡大率ということなら行列式が0になるというのは何を意味するだろう?面積が0倍・・・?
上にある単位ベクトルが基底のときの行列式({ \displaystyle S})は1だった。これを何かしらの行列で写像して、その結果の拡大率が0ということは元々あった面積がぺちゃんこになってしまったということ

f:id:Owatank:20171223170701p:plain

こんな感じだ。元々の面積というよりは基底ベクトルからできていた平面がほぼ点にしか見えないような平面へと写像されるイメージ
またはこんな風に写像されてしまったかもしれない
f:id:Owatank:20171223171035p:plain
面積が0ということは平面が作れないということ。写像した後の基底ベクトルが同じ向きを向いてしまったら、平面は作ることができない。

そんなこんなで(2次元空間において)行列式が二つの基底ベクトルが成す面積拡大率を表すもので、行列式の計算結果が0になってしまうことはその時の基底ベクトルが同じ向きを向いているか、1本しかない、などの状況が考えられる。

こんな状況になる基底は基底としての条件を満たさないということだった。

f:id:Owatank:20171219121642p:plain

上の画像のようになってしまう基底ベクトルでは基底は作れなかった。つまり

行列式を求めることで移された基底の組が基底の条件を満たすかどうかの判定ができる!!!!!

行列式スゲー

次に{ \displaystyle detAB = det(A)det(B) }の性質を使って{ \displaystyle det(AA^{-1}) = det(A)det(A^{-1}) }がどうなるか考える。
逆行列の定義から{ \displaystyle AA^{-1} = I }となるので、左辺は{ \displaystyle det(AA^{-1}) = det(I) = 1 }となるはず。
そうなると右辺も1にならないといけない。{ \displaystyle detA^{-1} }{ \displaystyle detA }の値の逆数であれば両辺は成立する。

{ \displaystyle det(A^{-1}) = \frac{1}{det(A)} }という関係式が得られる。

このとき面積拡大率が0、{ \displaystyle detA }が0の時この関係式が成り立たないことがわかる。
成り立たないってことは { \displaystyle A^{-1} }が存在しないって言ってもおかしくない。

ん?

ちょっと待てよ・・・ということは

行列式を求めることでその行列に逆行列が存在するかどうかも判定できる!!!

行列式スゲー!!!!!!!!!!

また逆行列が存在するかを行列式から求めることができる→行列式正方行列にしか定義されない→逆行列は正方行列でなければ存在しないという前回の単射全射あたりがより納得できる

まとめると、n次正方行列Aがあって{ \displaystyle detA = 0}のとき * そのときのn本の基底ベクトルから成る基底の組は、いずれかのベクトルが他のベクトルで表現できるような独立でない、またはn本より少ない状態にある。 * 逆行列が存在しない

ということがわかった。

逆に{ \displaystyle detA = 0}じゃないなら、そのn次正方行列Aは正則行列ということが言えるのがわかった。

n次のときで証明してない?買おう

長くなったので余因子展開とか別の行列式の性質はまた今度

そういえば外積の求め方と行列式の計算方法は何か関係があるんだろうか?どっちから派生したとかかな

線形代数のまとめ その2(写像について)

その1の続き

その1では線形代数の授業で雰囲気で覚えていた線形空間や基底についてメモった

小学校や中学校で方眼紙を使ったことがあると思うが、一つの四角のマスが長さ 1cm を表しているとして

f:id:Owatank:20171220104030p:plain

この方眼紙においては、一つの四角のマスの横({ \displaystyle \vec{e_1}})と縦({ \displaystyle \vec{e_2}})があるベクトル { \displaystyle \vec{v}} に行くための基準となってくれる。

上の画像にあるベクトル { \displaystyle \vec{v}} への行き先は基準を使って

{ \displaystyle \vec{v} = 3\vec{e_1} + 2\vec{e_2}}

と書き表せる

基準となる1組のベクトルのことが基底だった。ここでは方眼紙の縦と横を表せればいいので基底の組は({ \displaystyle \vec{e_1}},{ \displaystyle \vec{e_2}})であり、組の要素である{ \displaystyle \vec{e_1}}とかが基底ベクトルだった。

{ \displaystyle \vec{v} = 3\vec{e_1} + 2\vec{e_2}}のような{ \displaystyle \vec{v}}もベクトルの足し合わせでできたベクトルなので、もちろん足し算と定数倍はできる。

今回は授業でよく聞いたけどイメージが湧かない写像をメモする

ある行列 A があるとする
$$ A = \begin{pmatrix} 2 & 1 \\ 1 & 3 \end{pmatrix} $$

写像というのは{ \displaystyle \boldsymbol{y} = A \boldsymbol{x}}のようにベクトル{ \displaystyle \boldsymbol{x}}を行列Aで別のベクトル{ \displaystyle \boldsymbol{y}}に移すこと
(m,n)行列Aのとき、その行列は n次元空間のものを m次元空間に移す写像を表す

試しにベクトル{ \displaystyle \vec{v} = 3\vec{e_1} + 2\vec{e_2}}を上の(2,2)行列Aで写像してみることにする
{ \displaystyle \boldsymbol{x}}の部分が{ \displaystyle \vec{v}}に変わるので計算式は以下のようになる
$$ \boldsymbol{y} = \begin{pmatrix} 2 & 1 \\ 1 & 3 \end{pmatrix} \begin{pmatrix} 3 \\ 2 \end{pmatrix} $$

{ \displaystyle \boldsymbol{y}}はこのとき { \displaystyle (8,9)^{T}}になる。
途中式を書いて基底がどうなったかを確認する。そもそも{ \displaystyle (3,2)^{T}}{ \displaystyle \vec{v} = 3\vec{e_1} + 2\vec{e_2}}を表したものだから
$$ \begin{pmatrix} 3 \\ 2 \end{pmatrix} = 3\begin{pmatrix} 1 \\ 0 \end{pmatrix} + 2\begin{pmatrix} 0 \\ 1 \end{pmatrix}$$

{ \displaystyle \boldsymbol{y} = A \boldsymbol{x}}を変形すると
$$ \boldsymbol{y} = \begin{pmatrix} 2 & 1 \\ 1 & 3 \end{pmatrix} \begin{pmatrix} 3\begin{pmatrix} 1 \\ 0 \end{pmatrix} + 2\begin{pmatrix} 0 \\ 1 \end{pmatrix} \end{pmatrix} $$

分配法則(定数は前に持ってくる)から
$$ \boldsymbol{y} = 3 \begin{pmatrix} 2 & 1 \\ 1 & 3 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} + 2 \begin{pmatrix} 2 & 1 \\ 1 & 3 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix} $$

$$ \boldsymbol{y} = 3 \begin{pmatrix} 2 \\ 1 \end{pmatrix} + 2 \begin{pmatrix} 1 \\ 3 \end{pmatrix} $$ $$ = \begin{pmatrix} 6 \\ 3 \end{pmatrix} + \begin{pmatrix} 2 \\ 6 \end{pmatrix} = \begin{pmatrix} 8 \\ 9 \end{pmatrix} $$

分配法則で計算したけど最終的な答えは{ \displaystyle (8,9)^{T}}と一致したから問題なし。大事なのは基底を表している部分
$$ \boldsymbol{y} = 3 \begin{pmatrix} 2 \\ 1 \end{pmatrix} + 2 \begin{pmatrix} 1 \\ 3 \end{pmatrix} $$
最初の基底と変わっている。同じじゃない
定数は無視して、{ \displaystyle \vec{e_1} = (1,0)^{T}}{ \displaystyle \vec{e_1^{\prime}} = (2,1)^{T}}に、{ \displaystyle \vec{e_2} = (0,1)^{T}}{ \displaystyle \vec{e_2^{\prime}} = (1,3)^{T}}になってる

元の基底をプロットすると
f:id:Owatank:20171220151118p:plain こんな感じ

{ \displaystyle \boldsymbol{y} = A \boldsymbol{x}}をした後の基底をプロットすると

f:id:Owatank:20171220150923p:plain

元の行き先{ \displaystyle \vec{v}}はかなり遠くに移された。
上のことから行列Aは元の基底の移り先を表しているとも言える。(Aの第一列が{ \displaystyle \vec{e_1^{\prime}}}、第二列目が{ \displaystyle \vec{e_2^{\prime}}}に対応している)

人間、一度は故郷を離れることがあると思う。

たまに故郷に戻りたくなったりしないだろうか

つまり{ \displaystyle \boldsymbol{y} = A \boldsymbol{x}}として移った{ \displaystyle \boldsymbol{y}}から{ \displaystyle \boldsymbol{x}}に戻りたいということ。これも同じように何かしらの行列Pで写像して基底の移り先を教えてあげればいいはず
よく聞いた逆行列というのがこれで、ある正方行列((n,n)行列ということ)Aに対してその逆写像に対応する行列をAの逆行列という

その1のときに基底の表し方が1通りでいけない理由はこの逆行列のことを考えると、2通りあったらどっちへ戻ればいいかわかんなくなって困るというのがわかる

じゃあ正方行列でないといけない理由は?

(2,3)行列Aでの写像を考える。これは3次元のものを2次元空間に写像する。
3次元という立体のような空間で表されるものを2次元という平面の空間に移したら立体らしさの情報が欠落してしまう。
f:id:Owatank:20171220160022p:plain
上の画像でいうなら黄緑の面とオレンジの面に存在するベクトルをそれぞれ{ \displaystyle \vec{a}}{ \displaystyle \vec{b}}また({ \displaystyle \vec{a} ≠ \vec{b}})とする。画像の写像先を見ると同じ x = p という同じ移り先にいることになっている。これは「2通りあったらどっちへ戻ればいいかわかんなくなって困る」という状態になってしまった。
基底という言葉を使えば立体らしさを表してくれる基底の組の中にある基底ベクトルの情報が写像によって失われてしまう感じかな

(3,2)行列のように2次元のものを3次元の空間に写像したらどうなるか
前者の場合と違って次元が増えるので情報が欠落することはない
f:id:Owatank:20171212160305p:plain
でも移り先の3次元空間に存在する全てのベクトルをカバーできていないのがわかる。赤の平面以外の場所に存在するベクトルの戻り先が存在しないのでこれはこれで困ってしまった。

図で(2,3)行列のような場合はこんな感じになる
f:id:Owatank:20171220163038p:plain
移り先 f(x) の 3 から x へ戻るとき、この 3 は 2 か 4 どちらから移ってきたかわからず困る。こういう状況を全射

(3,2)行列の場合は
f:id:Owatank:20171220163306p:plain
移り先から戻り先は1対1対応だけど、 f(x) の中にある i や 10 に対応するものが戻り先にはないケース。こういう状況を単射

逆行列で嬉しい場合は1対1対応で、移り先のベクトルに対して唯一の戻り先があること
f:id:Owatank:20171220163502p:plain
単射であり、全射。二つ合わせて全単射という

雑だけど(m,n)行列において m < n でも m > n の場合でも困ることがわかった。そのため(n,n)という正方行列のがいいことになる。
正方行列でもその1でメモした基底の条件を満たすような正方行列じゃないといけないことに注意する
正方行列で写像した基底の移り先が実はどの基底ベクトルも同じ方向を向いていたとかだったらどっかしら情報が欠落して元に戻れなくて困る。すなわち逆行列が存在しない。正方行列で逆行列が存在する行列を正則行列と呼ぶ。


まとめるとして
* (m,n)行列による写像は移すベクトルの基底の移り先を示す、または n次元空間のものを m次元空間へと写像する。
* 写像した先から元に戻るためには写像した行列が正則行列であれば元に戻れる。

逆行列が存在するかどうかにも基底は関わっているし、基底がめちゃめちゃ重要なのがわかる。

でも逆行列が存在するとか、任意でとった基底の組が基底としての条件を満たしているとかはどうやって判断するのだろうか。

謎は深まるばかり

線形代数のまとめ その1(線形空間、基底とか)

プログラミングのための線形代数という本で線形代数の復習をしている。4章あたりまで読んだので振り返りとしてメモを残すことにする。

よく変数で配列だったりタプルだったりを使うことがある。これは複数の数値や文字列の集まりを一つのものとして見る。物理や線形代数だったりの勉強をしているとそれらはベクトルと呼ばれてる。
f:id:Owatank:20171219101249p:plain
こんなやつ。大学だと矢印じゃなくて太字で書くものしか見ない...

ベクトルでは同じ次元(上で言うとnの値)のもの同士なら足し算(引き算)と定数倍ができる。
例えばこんなベクトルがあるとして
3人の現在の身長 = (1.5m,1.8m,1.7m)
3人の2年前の身長 = (1.4m,1.6m,1.5m)

3人の2年前から伸びた分の身長を求めたいとする。これは現在の身長から2年前の身長を引いて残ったものが伸びた分になるから

3人の2年前から伸びた分の身長 = 3人の現在の身長 - 3人の2年前の身長
= (1.5m - 1.4m , 1.8m - 1.6m , 1.7m - 1.5m)
= (0.1m , 0.2m ,0.2m)

3人の2年前から伸びた分の身長= (0.1m , 0.2m ,0.2m)となる。

定数倍は
3人の現在の身長を3倍したもの = 3*(3人の現在の身長)と表せることができて

3人の現在の身長を3倍したもの = 3*(3人の現在の身長)
= 3*(1.5m,1.8m,1.7m)
= (3*1.5m,3*1.8m,3*1.7m)
= (4.5m,5.4m,5.1m)

ベクトルを構成している各要素を c倍 すればいい

掛け算や割り算もできそうじゃんって思うけど、できない
3人の現在の身長(cm表記) = (150cm,180cm,170cm) 3人の2年前の身長(cm表記) = (140cm,160cm,150cm) 先ほどのベクトルをcm表記で表したものを用意する。

この2つから3人の2年前から伸びた分の身長(cm表記)3人の現在の身長を3倍したもの(cm表記)を求めると

3人の2年前から伸びた分の身長(cm表記) = 3人の現在の身長(cm表記) - 3人の2年前の身長(cm表記)
= (150m - 140cm , 180cm - 160cm , 170m - 150cm)
= (10cm , 20cm , 20cm)
3人の現在の身長を3倍したもの(cm表記) = 3*(3人の現在の身長(cm表記))
= 3*(150cm,180cm,170cm)
= (3*150cm,3*180cm,3*170cm)
= (450cm,540cm,510cm)

表記は違うけど、求めたいものの意味合い(数値)は同じ

(3人の現在の身長)x(3人の2年前の身長)(3人の現在の身長(cm表記))x(3人の2年前の身長(cm表記))は同じになるか考える

(3人の現在の身長)x(3人の2年前の身長)
=(1.5*1.4, 1.8*1.6, 1.7*1.5)
=(2.1m, 2.88m, 2.55m)
(3人の現在の身長(cm表記))x(3人の2年前の身長(cm表記))
=(150*140, 180*160, 170*150)
=(21000, 28800, 25500)  //m表記に直すと
=(21m, 28.8m, 25.5m)

足し算や定数倍は同じものだったのに掛け算は全く別物になってしまった。
こんな風に掛け算と割り算はcmをmに直すといった座標系と呼ばれるものを変更するとxy = zx'y' ≠ z'という感じになってしまうからできない。というよりは成立するかわからないからできない。

元に戻って「足し算(引き算)」と「定数倍」が定義された世界のことを線形空間またはベクトル空間と呼ぶ。
ベクトルというのは以下のように矢印のようなもので表すことができる。(x軸とy軸で構成する2次元空間とする)
f:id:Owatank:20171219105321p:plain
これは { \displaystyle \vec{v} } という場所にはx座標に3歩進んで、y座標に2歩進むことで到着できる を表す

ちょっと待ってほしい。この方眼紙のような目盛りって誰が用意したのだ

もしこの目盛りがなくなったとして、こんな状況を考える
f:id:Owatank:20171219112038p:plain 誰かに { \displaystyle \vec{v} } の地点までお使いして欲しいとき、行き方はどうやって教えればいいだろう
目盛りがないと3コマ目のようにどの方向にどんな歩幅で3歩、2歩進めばいいか悩んでしまう。

目盛りがないなら、自分で作ればいいじゃん!ということで基準(目盛り)となるベクトル { \displaystyle
\vec{e_1},...,\vec{e_n}
}を定める。

基準を決めてしまえば、それを使って { \displaystyle \vec{v} } への行き先を「{ \displaystyle \vec{e_i}}の方向に3歩、{ \displaystyle \vec{e_j}}の方向に2歩進む」と伝えることができる。

f:id:Owatank:20171219113911p:plain

ベクトルは足し算、定数倍できることはわかったから{ \displaystyle \vec{v} = 3\vec{e_i} + 2\vec{e_j}}と書ける。
つまり{ \displaystyle \vec{v}}{ \displaystyle \vec{e_i}}{ \displaystyle \vec{e_j}}という基準の組み合わせで表現できるということ。

「基準となる1組のベクトル」を基底、「各基準で何歩進むか」を座標と呼ぶ。
上の例だと「基底{ \displaystyle (\vec{e_i},\vec{e_j})}に関して、ベクトル{ \displaystyle \vec{v}}の座標は{ \displaystyle \vec{v}=(3,2)^{T}}
ここでは基底は{ \displaystyle (\vec{e_i},\vec{e_j})}の組であり、各要素{ \displaystyle \vec{e_i}}{ \displaystyle \vec{e_j}}のことを基底ベクトルという。

基底という目盛りを自分で作れることがわかったけど、基底{ \displaystyle \vec{e_1},...,\vec{e_n} }を作るにも条件がある。

  • (今考えている線形空間内の)どのベクトル{ \displaystyle \vec{v}}でも { \displaystyle \vec{v} = x_1 \vec{e_1} + ... + x_n \vec{e_n}}という形で表せること(x1,...,xnは任意の数)

  • その表し方は一通りであること

一つ目は特定のベクトルだけ表せる基底なんて基底と言えない。二つ目は表し方が一通りでないと、異なる座標{ \displaystyle \boldsymbol{x}=(x1,...,xn)^{T}}{ \displaystyle \boldsymbol{y}=(y1,...,yn)^{T}}が与えられたときそれが違うもの同士か同じものが2通りの書き方をされているか困ってしまうことがあるから

2次元空間において以下のようなものが基底として取れる
f:id:Owatank:20171219121200p:plain
2本の基底ベクトルが「独立した方向」を向いていること
この独立という単語がいまいち難しいかもしれないけど、後々大事になってくる

以下のようなものは基底として取れない悪い例
f:id:Owatank:20171219121642p:plain

  • 左は1本の基底ベクトルでは無理ということ
    2次元空間なのに1本の基底ベクトルでは(x軸、y軸としたら)片方の軸しか表すことが出来ないから。これは基底の条件である
    どのベクトル{ \displaystyle \vec{v}}でも { \displaystyle \vec{v} = x_1 \vec{e_1} + ... + x_n \vec{e_n}}という形で表せることという条件を破ってしまう

  • 真ん中は2次元空間において3本(以上)の基底ベクトルは余分ということ
    { \displaystyle \vec{e_k}}という基底ベクトルは{ \displaystyle \vec{e_i}}{ \displaystyle \vec{e_j}}で表すことができるから必要ない。(基底の組として要素にする必要がない)

  • 右は2本の基底ベクトルが同じ方向ではダメということ
    { \displaystyle \vec{e_i}}を c倍 すれば{ \displaystyle \vec{e_j}}になるから{ \displaystyle \vec{e_j}}は余分
    結局1本の基底ベクトルだけということになる。これは基底の条件の一つ目を破ってしまうのでダメ

数学的な表現では

{ \displaystyle u_1 \vec{e_1} + ... + u_n \vec{e_n} = \vec{0}} ならば { \displaystyle u_1 = ... = u_n = 0 }

与えられたベクトル{ \displaystyle \vec{e_1},...,\vec{e_n} }に対して、任意の数{ \displaystyle u_1 , ... , u_n }を用意してできるベクトル
{ \displaystyle u_1 \vec{e_1} + ... + u_n \vec{e_n} }{ \displaystyle \vec{e_1},...,\vec{e_n} }線型結合をよぶ
複数のベクトルを n倍 だったり m倍 して足したり引いたりしたものをその複数のベクトルの線型結合というんだな

これらの条件から基底は「{ \displaystyle \vec{e_1},...,\vec{e_n} }の線型結合で任意のベクトル{ \displaystyle \vec{v}}が表現できて、その表し方が一通り(唯一)であるとき、{ \displaystyle (\vec{e_1},...,\vec{e_n}) }を基底と呼ぶ」

おまけで次元数は基底ベクトルの本数から定義されるので
次元 = 基底ベクトルの本数 = 座標の成分数 と定義される。

長くなったのでここまで

チコノフ(Tikhonov)正則化について

お久しぶりです。

最近プログラミングのための線形代数という本で線形代数のやり直しをしている。基底のイメージが掴みやすくて読んでいて楽しい

第二章の最後あたりにチコノフ正則化というものについて書いてあったので試してみることにした
コードはいつも通りここ(リンクを修正)

github.com

線形代数をやったことある人は以下の数式をよく見かけるはず
f:id:Owatank:20171212154859p:plain
(y,xはベクトル、Aは行列)

何をしているかというと(m,n)行列Aでn次元のベクトルxをm次元のベクトルyへと写像している
写像という言葉がイメージを掴みにくいけれど、m=3,n=2(m>n) に設定するとして

2次元空間で表されるベクトルxという平面を3次元空間に移す(写像する)とき、その空間でベクトルxはどのように表現されるかということ、であってるはず

f:id:Owatank:20171212160305p:plain

図で表すとこうなる。y=Axから元の2次元平面にある点xは写像した結果3次元空間ではyというベクトルで表される。図から写像した赤い平面以外の場所にある点(zとする)へと移れるxは存在しないことがわかる。こういう場合は単射というそうだ。

もちろん逆の場合m=2,n=3(m<n)も考えられる。3次元ベクトルで表されるxが2次元空間へ写像したときどう表現されるかということ。3次元情報を2次元情報で表すのは無理があるのでいくつか情報は削られてしまう。マリオがペーパーマリオになってしまう感じだ。

なので写像するときにはn次元からn次元への写像が基本的に嬉しい。n次元ベクトルxを回転したり引き延ばしたりする写像Aで写した時のn次元ベクトルyとか考えやすい。

n次元からn次元への写像において y = Ax とすると、yからxに戻すときは逆行列 inv_A を用いれば元に戻れる。 f:id:Owatank:20171212161825p:plain

このことから写像する行列Aには逆行列が存在しないといけないこともわかる。(行列Aは正則行列でなくてはならないということ)
逆行列が存在しないということはn次元空間を作るためのn本の基底が存在しない(n-1本だったりとか)ということで上の3次元情報を2次元情報で表現するといった状況になっていることになる。

世の中はひねくれているので正則行列ではあるけどほぼ逆行列に近い行列Aというのも存在する。
立方体をほぼ平面にするくらいぺちゃんこにしてしまう行列Aとかそんな感じ。このとき逆行列は元の立方体に戻す行列だからぺちゃんこな立方体を物凄く拡大して戻す逆行列 inv_A となる。

ここで元の立方体にノイズ(立方体の箱に黒い点のような落書きをしておくイメージ)を乗せて上のようなほぼ逆行列に近い行列Aでぺちゃんこにして、 inv_A で元に戻した時、ノイズも物凄く拡大されてしまう(黒い点のような落書きがかなり引き伸ばされたりしているイメージ)問題が発生すると本に書いてあった。

試してみることに
元の画像は以下のカニさん f:id:Owatank:20171212162928p:plain

画像を多少ぼかす行列Aを用意する
f:id:Owatank:20171212163027p:plain
単位行列の対角成分周りをぼやぼやした感じ(0.13とか0.6とか値を小さく)調整した。

y = Ax としたときのyの結果はこうなった
f:id:Owatank:20171212163245p:plain

全体的に暗くなった感じもあるけどちょっとぼやけてるのがわかる。
このyにノイズを乗せる(y+noise)
f:id:Owatank:20171212163402p:plain

Aの逆行列をかけて元に戻す( x = inv_A(y+noise) )

f:id:Owatank:20171212163815p:plain

かなりザリザリした結果になった。ノイズが引き伸ばされたのはわかる。
ちなみに逆行列自体はこんな感じだった
f:id:Owatank:20171212163911p:plain
なんかロマンチックだ

このノイズが引き伸ばされるのをなんとかしようというのがチコノフ正則化で、ざっくりいうと Ax と y+noise の距離(|| Ax - y ||)とか正則項を適用したりして、いい感じになるxを決めるぽかった。 数式で表すとこうなる
f:id:Owatank:20171212165419p:plain

右辺のyを除いた行列の結果は以下のようになった(α=0.03)
f:id:Owatank:20171212165921p:plain
逆行列 inv_A を表したものを太くした感じに見える

これをノイズありのyにかけるとこうなる
f:id:Owatank:20171212170052p:plain

ちょっとノイズが減ったのがわかる。でも完璧にとはいかなかった。αを0.5とかに変えたりすると元の画像xではなくどちらかというとぼかし行列を加えたyに近くなった。
この原因はなんだろう。逆問題あたりをもっと調べるとわかってくるのだろうか。