SECCON 2017 Online CTF writeup

SECCON2017のオンライン予選に参加したのでそのwriteupです。結果は700ptで321位。頑張らねば・・・。

Vigenere3d (crypto 100)

$ python Vigenere3d.py SECCON{**************************} **************
POR4dnyTLHBfwbxAAZhe}}ocZR3Cxcftw9

出力結果が上の暗号文になるような平文を探せという問題。まずタイトルからヴィジュネル暗号を使っていると分かります。 平文の一部が分かっているので、それと暗号文の情報から鍵を計算するスクリプトを書きました。

実行すると、鍵の一部が分かります。

$ ./search_key.py 
plain:  SECCON{**************************}
key:    _KP2Za_**************************a
crypt:  POR4dnyTLHBfwbxAAZhe}}ocZR3Cxcftw9

鍵長は14ですが、ここで与えられた暗号化スクリプトの15行目をみると、鍵の8~14文字目は1~7文字目を反転したものであると分かるので、鍵は以下のようになります。

key: _KP2Za__aZ2PK_

鍵が割り出せたので、暗号文と鍵の情報から平文を計算するスクリプトを書きます。

実行すればflagが出ます。

$ ./decrypt.py 
POR4dnyTLHBfwbxAAZhe}}ocZR3Cxcftw9
_KP2Za__aZ2PK__KP2Za__aZ2PK__KP2Za
SECCON{Welc0me_to_SECCON_CTF_2017}

flag:

SECCON{Welc0me_to_SECCON_CTF_2017}

Run Me! (programming 100)

単純に実行すればflagが出そうですが、実際は再帰が深すぎてうまくいきません。みるからにフィボナッチ数列のプログラムなので、再帰を使わない方法で実装します。

実行すればflagが出ます。

$ ./Run_Me2.py 
SECCON{65076140832331717667772761541872}

flag:

SECCON{65076140832331717667772761541872}

putchar music (programming 100)

見やすく整形し、コンパイルが通るように書き直します。

$ gcc ./putchar_music2.c -lm
$ ./a.out > output.wav
$ aplay output.wav

あの有名な曲が流れてきます。

flag:

SECCON{STAR_WARS}

SHA-1 is dead (crypto 100)

SHA-1が衝突する2つのファイルを探す問題。条件として2つのファイルは2017KiB以上2018KiB以下である必要があります。SHA-1は既にGoogleなどによって衝突が発見されており、同じハッシュ値を持った内容の異なるファイルが公開されています。SHA-1の仕組み上、この2つのファイルの末尾に同じデータを追加してもこれらのハッシュ値は変わらないので、それを使っていい感じにファイルサイズを調整します。

$ ./sha-1_is_dead.py 
SHA-1 hash
file1: 108fa3cd125fbf1b14f05fef51fca3a0a12f1c97
file2: 108fa3cd125fbf1b14f05fef51fca3a0a12f1c97
$ ls
file1           sha-1_is_dead.py    shattered-2.pdf
file2           shattered-1.pdf
$

出来たファイルをsubmitしてflagを得ます。

flag:

SECCON{SHA-1_1995-2017?}

Log Search (web 100)

WebサーバのアクセスログをElastic searchで検索できるサービスが与えられます。検索窓にSQLインジェクションXSSなど試してもSomething wrong... X(というメッセージが出てくるだけで対策されているっぽいので、適当にflagで検索してステータスが200になっているログを探してアクセスしたらflagが出てきました。

http://logsearch.pwn.seccon.jp//flag-b5SFKDJicSJdf6R5Dvaf2Tx5r4jWzJTX.txt

flag:

SECCON{N0SQL_1njection_for_Elasticsearch!}

おそらくもっとちゃんとした解き方があると思いますが想定解が分かりません。

JPEG file (binary 100)

壊れたjpegファイルが与えられます。ファイル中のどこか1bit修正すれば表示できるようになるらしいです。試しにGIMPで開こうとすると以下のメッセージが出ました。

Corrupt JPEG data: premature end of data segment Unsupported marker type 0xfc

よって画像ファイル中から0xfcとなっている箇所を探して修正すれば良いと分かります。JPEGでは、0xffの後にマーカータイプが来るので、0xfffcを探します。

$ hexdump -C problem.jpeg | grep 'ff fc'
$

ところが上のコマンドを実行しても何も出てきませんでした。調べたところ、hexdumpの出力がちょうど0xffと0xfcの間で改行が入っていることが原因でした。次のスクリプトを実行してファイルを修正します。

ちゃんと画像が表示されてflagをゲット出来ました。

f:id:tuz358:20171211225607p:plain

flag:

SECCON{jp3g_study}

Thank you for playing!

flag:

SECCON{We have done all the challenges. Enjoy last 12 hours. Thank you!}

pwn解いていない&100点問題しか解いてないので来年までに強くなってもっと高い点数を取れるようにしたいです。

Pythonでニューラルネットを実装する

「Pythonで多層パーセプトロンを実装する」では、多層パーセプトロンによってXOR関数を近似しましたが、重みや閾値などのパラメータは自分で決めていました。そこで今回は誤差逆伝播法を使ったニューラルネットワークを実装することでパラメータを自動で学習させてみます。

パーセプトロンとの違い

パーセプトロンニューラルネットワークも脳の神経細胞が行う情報処理の仕組みを模倣したものであることは同じですが、ニューラルネットワークには以下のようなパーセプトロンとは異なる特徴があります。

特徴

  • 出力が2値でない
  • 活性化関数がステップ関数でない
  • 損失関数

活性化関数

パーセプトロンでは、ニューロンが発火するかどうかは閾値 \textstyle \thetaによって決められ、出力される値は \textstyle 0 \textstyle 1のどちらかでした。しかしニューラルネットワークでは活性化関数というものを導入することでより複雑な発火の表現ができるようになっています。つまり活性化関数はニューロンがどのように発火するかを決めている関数といえます。活性化関数には種類があり、代表的なものでは以下の3種類があります。

シグモイド関数

 f(x) = \dfrac{1}{1 + \exp(-x)}

ReLU関数

 {\displaystyle  f(x) = \left\{ \begin{array}{1} x  \hspace{1em} ( x > 0 ) \\ 0 \hspace{1em} ( x \leqq 0 ) \end{array} \right.  }

tanh

 f(x) = \tanh(x)

シグモイド関数やReLUは微分計算が簡単であることから広く使われています。tanhはRNNやLSTMなどの再帰ニューラルネットによく使われます。

損失関数

損失関数とは、ニューラルネットワークの出力が正解データからどれだけ離れているか(誤差)を計算する関数です。一般的に回帰問題では2乗和誤差、分類問題ではクロスエントロピー誤差が用いられます。

2乗和誤差

 E = \displaystyle \frac{1}{2} \sum_{i} (y_i-t_i)^2

クロスエントロピー誤差

 E = \displaystyle - \sum_{i} t_i \log y_i

ニューラルネットワークの順伝播

ニューラルネットを実装するにあたり、まず順伝播の計算式を導出します。今回は以下のような構造のネットワークを考えます。

順伝播の流れを分かりやすくするために活性化関数( \textstyle \sigma)を明示的に書きました。 \textstyle x_iは入力信号、 \textstyle w_{ij}は重み、 \textstyle y_iは出力信号を表しています。 \textstyle b_iはバイアスと呼ばれるもので、入力信号 \textstyle x_iと重み \textstyle w_{ij}をかけたものにこのバイアスを加えることで前回のエントリでいう閾値 \textstyle \thetaと同じ役割を果たします。図では、バイアス項を加える処理を、入力 \textstyle 1 \textstyle b_iをかけるという処理で表しています。以上のことを踏まえると、まず活性化関数の手前までの計算は次のように表せます。

 y_1 = x_1 w_{11} + x_2 w_{21} + b_1
 y_2 = x_1 w_{12} + x_2 w_{22} + b_2

バイアス項が加わっただけで後はパーセプトロンの計算と変わりありません。 また、上の式はベクトルと行列を用いて一つの式にまとめることが出来ます。

 \displaystyle \begin{pmatrix} y_1 \quad y_2 \end{pmatrix} = \begin{pmatrix} x_1 \quad x_2 \end{pmatrix} \begin{pmatrix} w_{11} \quad w_{12} \\\ w_{21} \quad w_{22} \end{pmatrix} + \begin{pmatrix} b_1 \quad b_2 \end{pmatrix}

ベクトルや行列を使って表すことで、プログラムに落とし込むときに線形代数のライブラリを活用でき、さらに一つの式にまとめることで入力や出力の数がどんなに多くなっても一層分の順伝播の計算は一回の計算で行えるようになります。ここで、

 \boldsymbol{Y} = \begin{pmatrix} y_1 \quad y_2 \end{pmatrix},\quad \boldsymbol{X} = \begin{pmatrix} x_1 \quad x_2 \end{pmatrix},\quad  \boldsymbol{W} = \begin{pmatrix} w_{11} \quad w_{12} \\\ w_{21} \quad w_{22} \end{pmatrix},\quad  \boldsymbol{B} = \begin{pmatrix} b_1 \quad b_2 \end{pmatrix}

とすれば、上の式は

 \boldsymbol{Y} = \boldsymbol{X} \cdot \boldsymbol{W} + \boldsymbol{B}

と非常に簡単な式になります。この計算は線形変換と呼ばれます。よって活性化関数を含めたこのニューラルネットワーク全体の順伝播の式は、

 \boldsymbol{o} = \sigma \begin{pmatrix} \boldsymbol{Y} \end{pmatrix} = \sigma \begin{pmatrix} \boldsymbol{X} \cdot \boldsymbol{W} + \boldsymbol{B} \end{pmatrix}

となります。さらに学習時には上の出力が損失関数に入力として与えられ、例えば2乗誤差を使う場合、

 \displaystyle E = \frac{1}{2}\sum_{i}(o_i - t_i)^2

が誤差 \textstyle Eとして出てきます。そしてこの誤差 \textstyle Eから各パラメータ(重みやバイアスなど)に対する微分を効率的に計算するアルゴリズムが次に説明する誤差逆伝播法です。

誤差逆伝播

ニューラルネットワークを学習させるにあたり、ニューラルネットワークが出力した誤差をもとに各パラメータをどれだけ修正するかを求める必要があります。この修正量は「あるパラメータを一定量変化させたときの誤差の変化量」と言い換えることができ、それは誤差に対する各パラメータの微分で表せます。この微分値を効率良く計算するアルゴリズム誤差逆伝播法で、その原理の基本は連鎖律によって説明できます。

では上の順伝播計算で得た誤差から、学習すべきパラメータの誤差に対する微分を求めてみます。誤差逆伝播法では、出力層から逆順に誤差が伝播していくため、今回のネットワーク構造の場合は損失関数 -> 活性化関数 -> 線形変換の順に誤差が伝わっていきます。

損失関数の逆伝播

損失関数では学習するパラメータはありませんが後ろの層に誤差を伝えるため、 \textstyle \frac{\partial E}{\partial y}を計算する必要があります。今回は損失関数に2乗和誤差を用いるので \textstyle \frac{\partial E}{\partial y}は以下のようにして求められます。

 \begin{eqnarray*} \dfrac{\partial E}{\partial y} &=& \displaystyle \dfrac{\partial}{\partial y} \begin{pmatrix} \dfrac{1}{2} \sum_{i}(y_i - t_i)^{2} \end{pmatrix} \\\ \\\ &=& 2 \cdot \dfrac{1}{2} \sum_{i}(y_i - t_i) \cdot (y_i - t_i)' \\\ \\\ &=& \sum_{i}(y_i - t_i) \end{eqnarray*}

これと順伝播の式を合わせて損失関数をPythonで書いてみます。

活性化関数の逆伝播

活性化関数についても同様に、学習すべきパラメータは無いので単純に誤差を入力信号で微分して後ろの層へ伝播させるだけです。今回はシグモイド関数とReLUを使います。まずシグモイド関数微分してみると、

 \begin{eqnarray*} \dfrac{d}{dx}f(x) &=& \dfrac{ -(1 + \exp(-x))' }{ (1 + \exp(-x))^{2} } \\\ \\\ &=& \dfrac{ \exp(-x) }{ (1 + \exp(-x))^{2} } \\\ \\\ &=& \dfrac{ 1 }{ 1 + \exp(-x) } \dfrac{ \exp(-x) }{ 1 + \exp(-x) } \\\ \\\ &=& \dfrac{ 1 }{ 1 + \exp(-x) } \dfrac{ 1 + \exp(-x) -1}{ 1 + \exp(-x) } \\\ \\\ &=& \dfrac{ 1 }{ 1 + \exp(-x) } \begin{pmatrix} 1 - \dfrac{ 1 }{ 1 + \exp(-x) } \end{pmatrix} \end{eqnarray*}

まとめると、

 \dfrac{d}{dx}f(x) = f(x) (1 - f(x))

導関数シグモイド関数自身で表せます。これは重要な性質で、微分の計算をするときに順伝播で求めた値を再利用できるということです。Pythonによるシグモイド関数の実装は以下のようになります。

次にReLUの逆伝播を考えます。ReLUの微分はとても簡単です。

 { \dfrac{d}{dx}f(x) = \left\{ \begin{array}{1} 1  \hspace{1em} ( x > 0 ) \\ 0 \hspace{1em} ( x \leqq 0 ) \end{array} \right.  }

Pythonでの実装はこちらのリポジトリが参考になりました。

線形変換の逆伝播

線形変換では、重み \textstyle w_{ij}とバイアス \textstyle b_{i}の2つの学習パラメータがあります。そのため \tfrac{\partial E}{\partial \boldsymbol{W}},  \tfrac{\partial E}{\partial \boldsymbol{B}}を求めます。当然後ろの層へ誤差を伝えるために \tfrac{\partial E}{\partial \boldsymbol{X}}も求めます。

また、微分の計算を分かりやすくするために、図のように線形変換を計算グラフで表します。

上の図は式  \textstyle y_1 = x_1 w_{11} + x_2 w_{21} + b_1 を表しています。さらに、上の式の計算途中の中間値を以下のように保存しておきます。

 z_1 = x_1 w_{11} , \quad z_2 = x_2 w_{21} , \quad z_3 = z_1 + z_2

まず例として、出力から逆にたどって誤差に対する x_1成分の微分を計算します。すると \tfrac{\partial E}{\partial x_1}は連鎖律を用いて、

 \dfrac{\partial E}{\partial x_1} = \dfrac{\partial E}{\partial z_3} \dfrac{\partial z_3}{\partial z_1} \dfrac{\partial z_1}{\partial x_1}

と書けます。ここで、加算の部分は前の層から伝わってきた誤差をそのまま次の層に渡し、乗算の部分は入力信号をひっくり返したものを伝播させるので、

 \dfrac{\partial E}{\partial x_1} = \dfrac{\partial E}{\partial y_1} w_{11}

となります。他の成分も同様に誤差に対する微分を求めると、

 \dfrac{\partial E}{\partial x_2} = \dfrac{\partial E}{\partial z_3} \dfrac{\partial z_3}{\partial z_2} \dfrac{\partial z_2}{\partial x_2} = \dfrac{\partial E}{\partial y_1} w_{21}

 \dfrac{\partial E}{\partial w_{11}} = \dfrac{\partial E}{\partial z_3} \dfrac{\partial z_3}{\partial z_1} \dfrac{\partial z_1}{\partial w_{11}} = \dfrac{\partial E}{\partial y_1} x_1

 \dfrac{\partial E}{\partial w_{21}} = \dfrac{\partial E}{\partial z_3} \dfrac{\partial z_3}{\partial z_2} \dfrac{\partial z_2}{\partial w_{21}} = \dfrac{\partial E}{\partial y_1} x_2

 \dfrac{\partial E}{\partial b_1 } = \dfrac{\partial E}{\partial y_1}

となります。

また、上の計算グラフは式  \textstyle y_2 = x_1 w_{12} + x_2 w_{22} + b_2 を表しており、計算途中の値は以下のように保存します。

 z_4 = x_1 w_{12} , \quad z_5 = x_2 w_{22} , \quad z_6 = z_4 + z_5

これも先ほどと同様に誤差に対する各成分の微分を求めると、

 \dfrac{\partial E}{\partial x_1} = \dfrac{\partial E}{\partial z_6} \dfrac{\partial z_6}{\partial z_4} \dfrac{\partial z_4}{\partial x_1} = \dfrac{\partial E}{\partial y_2} w_{12}

 \dfrac{\partial E}{\partial x_2} = \dfrac{\partial E}{\partial z_6} \dfrac{\partial z_6}{\partial z_5} \dfrac{\partial z_5}{\partial x_5} = \dfrac{\partial E}{\partial y_2} w_{22}

 \dfrac{\partial E}{\partial w_{12}} = \dfrac{\partial E}{\partial z_6} \dfrac{\partial z_6}{\partial z_4} \dfrac{\partial z_4}{\partial w_{12}} = \dfrac{\partial E}{\partial y_2} x_1

 \dfrac{\partial E}{\partial w_{22}} = \dfrac{\partial E}{\partial z_6} \dfrac{\partial z_6}{\partial z_5} \dfrac{\partial z_5}{\partial w_{22}} = \dfrac{\partial E}{\partial y_2} x_2

 \dfrac{\partial E}{\partial b_2 } = \dfrac{\partial E}{\partial y_2}

これで誤差に対する全ての成分の微分が計算出来たのでそれらをまとめます。

 \begin{eqnarray*} \dfrac{\partial E}{\partial \boldsymbol{X} } &=& \begin{pmatrix} \dfrac{\partial E}{\partial x_1} \quad \dfrac{\partial E}{\partial x_2} \end{pmatrix} \\\ &=& \begin{pmatrix} \dfrac{\partial E}{\partial y_1} w_{11} +  \dfrac{\partial E}{\partial y_2} w_{12} \quad \dfrac{\partial E}{\partial y_1} w_{21} + \dfrac{\partial E}{\partial y_2} w_{22} \end{pmatrix} \\\ &=& \begin{pmatrix} \dfrac{\partial E}{\partial y_1} \quad \dfrac{\partial E}{\partial y_2} \end{pmatrix} \cdot \begin{pmatrix} w_{11} \quad w_{21} \\\ w_{12} \quad w_{22} \end{pmatrix} \\\ &=& \dfrac{\partial E}{\partial \boldsymbol{Y}} \cdot \boldsymbol{W}^T \end{eqnarray*}

 \begin{eqnarray*} \dfrac{\partial E}{\partial \boldsymbol{W} } &=& \begin{pmatrix} \dfrac{\partial E}{\partial w_{11}} \quad \dfrac{\partial E}{\partial w_{21}} \\\ \dfrac{\partial E}{\partial w_{12}} \quad \dfrac{\partial E}{\partial w_{22}} \end{pmatrix} \\\ &=& \begin{pmatrix} \dfrac{\partial E}{\partial y_1} x_1 \quad \dfrac{\partial E}{\partial y_1} x_2 \\\ \dfrac{\partial E}{\partial y_2} x_1 \quad \dfrac{\partial E}{\partial y_2} x_2 \end{pmatrix} \\\ &=& \begin{pmatrix} x_1 \\\ x_2 \end{pmatrix} \cdot \begin{pmatrix} \dfrac{\partial E}{\partial y_1} \quad \dfrac{\partial E}{\partial y_2} \end{pmatrix} \\\ &=& \boldsymbol{X}^T \cdot \dfrac{\partial E}{\partial \boldsymbol{Y}} \end{eqnarray*}  \dfrac{\partial E}{\partial \boldsymbol{B} } = \begin{pmatrix} \dfrac{\partial E}{\partial b_1} \quad \dfrac{\partial E}{\partial b_2} \end{pmatrix} = \begin{pmatrix} \dfrac{\partial E}{\partial y_1} \quad \dfrac{\partial E}{\partial y_2} \end{pmatrix} = \dfrac{\partial E}{\partial \boldsymbol{Y}}

すなわち、

 \dfrac{\partial E}{\partial \boldsymbol{W} } =  \boldsymbol{X}^T \cdot \dfrac{\partial E}{\partial \boldsymbol{Y}}

 \dfrac{\partial E}{\partial \boldsymbol{X} } = \dfrac{\partial E}{\partial \boldsymbol{Y}} \cdot \boldsymbol{W}^T

 \dfrac{\partial E}{\partial \boldsymbol{B} } = \dfrac{\partial E}{\partial \boldsymbol{Y}}

したがってPythonでの実装は次のようになります。

勾配法

誤差逆伝播法によって各パラメータをどれだけ修正すれば良いか分かったので、次は実際にパラメータを調整してニューラルネットワークを学習させていきますが、その際に勾配法というアルゴリズムを使ってパラメータの値を更新していきます。勾配法(この場合は勾配降下法)では、損失関数の出力を最小にするために損失関数の勾配を活用します。具体的には、損失関数の勾配が小さくなる方へ進むことで損失関数の最小値を探します。式で表すと以下のようになります。

パラメータの更新式

 \boldsymbol{W_{new}} = \boldsymbol{W_{old} } - \eta \dfrac{\partial E}{\partial \boldsymbol{W_{old}}}

 \boldsymbol{B_{new}} = \boldsymbol{B_{old} } - \eta \dfrac{\partial E}{\partial \boldsymbol{B_{old}}}

上が重みパラメータ、下がバイアスパラメータの更新を行う式です。式中の \textstyle \etaは学習率というもので、誤差逆伝播法で得た修正量をどれだけ反映するか(どれだけパラメータを更新するか)を調整する係数です。Pythonで実装すると、以下のようになります。

今回実装するネットワークでは学習パラメータが存在するのは線形変換の部分のみなのでシグモイド関数やReLUでは何もしません。

実装

実装するのに必要な式が一通り表せたので、いよいよPythonニューラルネットを実装します。今回もXOR関数を学習させてみます。まず以下のようにニューラルネットを訓練するクラスを書きました。

nnetモジュールには今までに書いた線形変換や活性化関数などのクラスがまとめてあります。また、上の訓練クラスを使ってXORの学習を行うコードスニペットの一例を以下にのせます。

さらに、学習したモデルを使って推論を行うスクリプトを作成しました。

上のコードでニューラルネットワークを訓練した結果、以下のようにXOR関数をうまく学習できました。

$ ./xor_predict.py ./xor_sample_weight.pkl
in: [ 0.  0.]  ->  out: 0 (0.00486784050737)
in: [ 0.  1.]  ->  out: 1 (0.997805826021)
in: [ 1.  0.]  ->  out: 1 (0.997805828447)
in: [ 1.  1.]  ->  out: 0 (0.00486784050737)
$

今回作ったプログラムは以下のリポジトリに置いてあります。 github.com

PythonでグローバルIPアドレスを取得する

最近グローバルIPアドレスを調べることが多くなったのでまとめておくことにする。

DynDNS

dyn.com

DynDNSは、ダイナミックDNSのサービスです。自分のグローバルIPアドレスを知りたい場合はここにアクセスします。返ってくる結果には余分な文字列が含まれるので少しだけ追加の処理を行う必要があります。

>>> import urllib2 as u
>>> url = 'http://checkip.dyndns.com/'
>>> res = u.urlopen(url)
>>> html = res.read()
>>> html
'<html><head><title>Current IP Check</title></head><body>Current IP Address: xxx.xxx.xxx.xxx</body></html>\r\n'
>>> html.split(':')[1].strip().rstrip('</body></html>\r\n')
'xxx.xxx.xxx.xxx'
>>> 

ieServer.Net

www.ieserver.net

ieServer.NetもDynDNSと同様にダイナミックDNSを提供してくれるサービスで、無料で利用することが出来ます。http://ipcheck.ieserver.net/にアクセスすると自分のグローバルIPアドレスを教えてもらえます。

>>> import requests
>>> url = 'http://ipcheck.ieserver.net/'
>>> res = requests.get(url)
>>> res.text
u'xxx.xxx.xxx.xxx\n'
>>> str(res.text.rstrip('\n'))
'xxx.xxx.xxx.xxx'
>>>

IP address information

http://inet-ip.info/

このWebサイトは接続してきたクライアントのIPアドレス、ホスト名や国名などの情報を表示してくれます。URLの末尾にipを付加するとIPアドレスのみが取得でき、jsonを付加するとIPアドレス以外の情報も含めた様々な情報をjson形式で取得できます。

>>> import requests
>>> res = requests.get('http://inet-ip.info/ip')
>>> res.text
u'xxx.xxx.xxx.xxx'
>>>

ifconfig.io

http://ifconfig.io/

こちらもグローバルIPアドレスやその他のネットワーク情報を出力してくれるWebサイトです。ただし、純粋にIPアドレスの文字列のみを返して欲しい場合はUser-Agentにcurlを設定してあげる必要があります。

>>> import requests
>>> headers = {'User-Agent': 'curl'}
>>> res = requests.get('http://ifconfig.io/', headers=headers)
>>> res.text
u'xxx.xxx.xxx.xxx\n'
>>> str(res.text.rstrip('\n'))
'xxx.xxx.xxx.xxx'
>>>

その他

ipify.org

>>> import requests
>>> res = requests.get('http://api.ipify.org/')
>>> res.text
u'xxx.xxx.xxx.xxx'
>>>

ident.me

>>> import requests
>>> res = requests.get('http://ident.me')
>>> res.text
u'xxx.xxx.xxx.xxx'
>>>

icanhazip.com

>>> import requests
>>> res = requests.get('http://icanhazip.com')
>>> res.text
u'xxx.xxx.xxx.xxx\n'
>>>

trackip.net

>>> import requests
>>> res = requests.get('http://www.trackip.net/ip')
>>> res.text
u'xxx.xxx.xxx.xxx'
>>>

dnsomatic.com

>>> import requests
>>> res = requests.get('http://myip.dnsomatic.com')
>>> res.text
u'xxx.xxx.xxx.xxx'
>>> 

ちなみにグローバルIPアドレスをプログラムから利用したりしない場合はわざわざPythonスクリプトにしなくてもcurlとか使った方が速いです。

Pythonで多層パーセプトロンを実装する

多層パーセプトロン(multilayer perceptron)は、任意の関数を近似できるアルゴリズムです。ニューラルネットワークディープラーニングアルゴリズムを理解する前段階として、今回はこの多層パーセプトロンPythonで実装してみます。

多層パーセプトロンとは

多層パーセプトロンの前にまず単純なパーセプトロンについて理解しておく必要があります。 パーセプトロンは脳の神経細胞(ニューロン)をモデルとして作られています。

f:id:tuz358:20170628205802j:plain

上に神経細胞の模式図を示しました。神経細胞は情報の伝達や処理を行うための細胞で、以下のような性質を持ちます。

  • 多入力・多出力 : 複数の神経細胞から入力信号を受け、複数の神経細胞へ出力信号を送る。
  • 情報の重み : 神経細胞間の結合強度によって情報が伝達される度合い(重み)が変わる。
  • 発火 : 他の神経細胞から受け取った信号の総和がある閾値を超えると発火状態になり、信号を他の神経細胞に伝達する。

これらの性質を考慮して作られたモデルがパーセプトロンです。

f:id:tuz358:20170629162401j:plain

上図のように、入力信号を x、出力信号を y神経細胞同士の結合の度合いを wで表します。また、発火する際の閾値 \thetaとします。入力信号 xを受け取ると、パーセプトロンはその信号に重み wを掛け、その値が閾値 \thetaを超えた場合に 1を出力し、そうでなければ 0を出力します。式で表すと、

 {\displaystyle  y = \left\{ \begin{array}{1} 1  \hspace{1em} ( wx > \theta ) \\ 0 \hspace{1em} ( wx \leqq \theta ) \end{array} \right.  }

入力信号が 2つ以上の場合は、複数の入力信号の総和を計算し、閾値 \thetaと比較します。

 {\displaystyle  y = \left\{ \begin{array}{1}  1 \hspace{1em} \left( \displaystyle \sum_{i=1}^{n} w_i x_i > \theta \right) \\ 0 \hspace{1em} \left( \displaystyle \sum_{i=1}^{n} w_i x_i \leqq \theta \right) \end{array} \right.  }

パーセプトロンには、後述しますが直線(線形関数)しか近似できないという問題点があります。そこで直線だけでなく任意の関数を近似できるよう考案されたのが多層パーセプトロンです。多層パーセプトロンとは、入力層と出力層を含めて層の深さが 3以上のネットワークを指します。

f:id:tuz358:20170629170654j:plain

左から入力層、隠れ層、出力層となります。隠れ層を増やすことで表現力が増し、より複雑な関数を近似できます。

パーセプトロンの実装

試しにパーセプトロンにAND演算の機能を持たせてみましょう。AND演算の真理値表を以下に示します。

入力 A 入力 B 出力 C
0 0 0
0 1 0
1 0 0
1 1 1

この表から、AND演算をパーセプトロンで実現するには 2つの信号を受け取って 1つの信号を出力するようなパーセプトロンを用意すればいいことが分かります(下図)。

f:id:tuz358:20170629171633j:plain

ただし、 (1,1)という信号を受け取ったとき 1、それ以外の信号の組み合わせを受け取ったとき 0を出力するような重 w_A w_B閾値 \thetaパーセプトロンに設定してあげる必要があります。これらのパラメータは当てずっぽうで決めてもいいのですが、AND演算のグラフを使うとそれらのパラメータの設定を直感的に行えます。

f:id:tuz358:20170629173549j:plain

横軸は入力 A、縦軸は入力 Bです。また、出力 C 1の点は赤色、 0の点は青で表しています。このとき、青と赤の点を分離する直線を引けられればAND演算を実現できます。例えば、次の直線

 B = -A + 1.2

はそのような条件を満たしています。

f:id:tuz358:20170629182603j:plain

この直線の式を変形すると、

 A + B - 1.2 = 0

入力A、Bの係数は 1なので、この直線は入力A、Bにそれぞれ 1の重みを掛けて足し合わせた値が閾値 1.2を超えたかどうかを識別する関数を表していることが分かります。よってパーセプトロンがこの関数を近似するために設定すべきパラメータは、

 w_A = 1 \\ w_B = 1 \\ \theta = 1.2

となります。ではAND演算をPythonで実装してみます。

>>> def AND(A, B):
...     W_a = 1
...     W_b = 1
...     theta = 1.2
...     out = W_a * A + W_b * B
...     y = 1 if out > theta else 0
...     return y
... 
>>>

入力信号を与えてやると、

>>> AND(0, 0)
0
>>> AND(0, 1)
0
>>> AND(1, 0)
0
>>> AND(1, 1)
1
>>>

パーセプトロンでAND演算を実装できました。

多層パーセプトロンの実装

同じようにXOR演算をパーセプトロンで実装してみましょう。真理値表は以下の通りです。

入力 A 入力 B 出力 C
0 0 0
0 1 1
1 0 1
1 1 0

AND演算と同様にグラフを書くと、

f:id:tuz358:20170629180749j:plain

赤と青の点を一つの直線で分類できるでしょうか?XOR演算は、どのようなパラメータを与えても直線では分類出来ません(線形分離不可能)。パーセプトロンで近似できるのは線形の関数のみなので、非線形の関数も近似できる新たな仕組みが必要です。そこで先程説明した多層パーセプトロンを使います。

f:id:tuz358:20170629182149j:plain

多層パーセプトロンを使えば上図のような曲線を近似させることが可能です。ただ、直線であれば重みや閾値を決めるのは簡単でも非線形のものではグラフを見てもパラメータを設定するのは困難です。そこでどうするかですが、結論を言ってしまうと既にパラメータが分かっているパーセプトロン(関数)を組み合わせるという方法があります。XORの場合は、

 XOR\left(A,B\right) = AND\left(OR\left(A,B\right),\ NAND\left(A,B\right)\right)

と表せることを利用します。OR演算やNAND演算は線形分離可能なのでAND演算と同じ方法でパラメータを決められます。これをパーセプトロンで表現すると、

f:id:tuz358:20170629191358j:plain

OR演算やNAND演算のパラメータの求め方はAND演算のときと同じなので省略しました。OR演算とNAND演算もそれぞれPythonで実装してみます。

>>> def OR(A, B):
...     W_a = 0.5
...     W_b = 0.5
...     theta = 0.4
...     out = W_a * A + W_b * B
...     y = 1 if out > theta else 0
...     return y
... 
>>> OR(0, 0), OR(0, 1), OR(1, 0), OR(1, 1)
(0, 1, 1, 1)
>>>
>>> def NAND(A, B):
...     W_a = -1.0
...     W_b = -1.0
...     theta = -1.2
...     out = W_a * A + W_b * B
...     y = 1 if out > theta else 0
...     return y
... 
>>> NAND(0, 0), NAND(0, 1), NAND(1, 0), NAND(1, 1)
(1, 1, 1, 0)
>>>

パラメータを変えるだけで様々な機能を持たせられることが分かります。OR演算とNAND演算を呼び出した後にAND演算を呼び出せばいいので、XOR演算のコードは次のようになります。

>>> def XOR(A, B):
...     h1 = OR(A, B)
...     h2 = NAND(A, B)
...     y = AND(h1, h2)
...     return y
... 
>>> XOR(0, 0), XOR(0, 1), XOR(1, 0), XOR(1, 1)
(0, 1, 1, 0)
>>>

多層パーセプトロンを使って表現力を上げることでXOR演算を実装できました。