2017/07/21 ~ 2017/07/26

Kagisys

Kagisys | Aizu Online Judge

n本の認証キーとm回の認証試行がある
m回のループを回して各回で扉を開錠可能かどうか判定すればよい
扉の状態を保存するためにループの外側に変数openedがある

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  int n, m;
  cin >> n;
  vector<string> u(n);
  rep (i, n) cin >> u[i];

  cin >> m;
  vector<string> t(m);
  rep (i, m) cin >> t[i];

  vector<bool> ut(m);
  bool opened = false;

  rep (i, m) {
    bool solved = false;

    rep (j, n) {
      if (t[i] == u[j]) {
        if (opened) {
          cout << "Closed by " << t[i] << endl;
          opened = false;
          solved = true;
        }
        else {
          cout << "Opened by " << t[i] << endl;
          opened = true;
          solved = true;
        }
        break;
      }
    }

    if (!solved) cout << "Unknown " << t[i] << endl;
  }

  return 0;
}

便利なgensim.models.word2vec

• loggingの設定を書けば学習の進捗状況をレポートしてくれる
• 単語の表層形を返すgeneratorを書けば全データをメモリに載せなくても学習可能

rare-technologies.com

gensim.models.word2vec with generator

学習時にgeneratorを渡していた場合，__next__()が重いとworkersの値が2以上であっても
1スレッドしか学習が行われない現象が発生する．

gensimの並列化ではmasterが常にgeneratorからデータを取得し，各サブプロセス(workers個存在)のうち
空いているプロセスに投入する仕組みになっているために起きる現象の模様．

generatorの中でfor文を書いたりすると起きるので注意が必要．

github.com

2017/07/19 ~ 2017/07/20

税率変更

税率変更 | Aizu Online Judge

• 以下のように1つのループで税込み価格を探索しようとしたが失敗した

for (int p1=1; p1<s; p1++) {
  int p2 = s-p1;
}

• 税抜き価格で全探索する

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  int x, y, s;
  while (cin >> x >> y >> s, x && y && s) {
    int ans = 0;

    for (int o1=1; o1<s; o1++) {
      for (int o2=1; o2<s; o2++) {

        int p1 = o1 * (100+x) / 100.0;
        int p2 = o2 * (100+x) / 100.0;

        if (p1+p2 != s) continue;

        int n1 = o1 * (100+y) / 100;
        int n2 = o2 * (100+y) / 100;

        ans = max(ans, n1+n2);

      }
    }

    cout << ans << endl;
  }
  return 0;
}

Amida, the City of Miracle

Amida, the City of Miracle | Aizu Online Judge

あみだくじの枝を高さでソートする
始点を選び，辿っていく
[解説](http://www.deqnotes.net/acmicpc/p0102/)をみてmultisetを使った

イテレータにはドット演算子ではアクセスできない
アロー演算子を使う必要がある
C++よくわかっていないので原因はあとで調べる

pair v = it.second; // ダメ
pair v = it->second;
pair v = (*it).second;

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

typedef multimap< int, pair<int, int> > HL;

int main() {
  int n, m, ans;
  int h, p, q;

  while (cin >> n >> m >> ans, n && m && ans) {
    set<int> hs;
    multimap<int, pair<int, int>> hl;

    rep (i, m) {
      cin >> h >> p >> q;
      hs.insert(h);
      hl.insert(make_pair(h, make_pair(p, q)));
    }

    for (set<int>::reverse_iterator sit=hs.rbegin(); sit!=hs.rend(); sit++) {
      int hhead = *sit;

      for (multimap<int, pair<int, int>>::iterator it = hl.lower_bound(hhead); it != hl.upper_bound(hhead); it++) {
        pair<int, int> v = it->second;
        if (v.first == ans) {
          ans = v.second;
          break;
        }
        else if (v.second == ans ) {
          ans = v.first;
          break;
        }
      }
    }

    cout << ans << endl;
  }
  return 0;
}

幸運の操作者

Luck Manipulator | Aizu Online Judge

10000+1 (0回目+10000回の試行) の乱数生成結果を先に作る
あとは作った乱数とYを照合する
計算はもっとサボれる (毎回10000回乱数生成をする必要はない) が，
一番楽な実装でも十分間に合いそうだったのでこのまま

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int solve(int n, int a, int b, int c, int x, vector<int> &y, vector<int> &z) {
  int head = 0;
  rep (t, 10000+1) {
    if (y[head] == z[t]) head++;
    if (head == n) return t;
  }
  return -1;
}

int main() {
  int n, a, b, c, x;
  vector<int> y;
  vector<int> z(10000);

  while(cin >> n >> a >> b >> c >> x, n) {
    y.resize(n); z[0] = x;
    rep (i, n) cin >> y[i];

    for (int i=1; i<=10000; i++) z[i] = (a*z[i-1] + b) % c;
    cout << solve(n, a, b, c, x, y, z) << endl;
  }
  return 0;
}

2017-07-05 ~ 2017-07-18

Dynetのインストール

gccはlinuxbrewで入れたものを使う

% which gcc
gcc (Homebrew gcc 5.3.0) 5.3.0
Copyright (C) 2015 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Eigen3をインストール
brew install eigen

glibcのバージョン
brew install glibc
> glibc: stable 2.19
> The GNU C Library

リポジトリをクローン

git clone https://github.com/clab/dynet.git

ビルドの準備

cd dynet
mkdir build
cd build
cmake .. -DEIGEN3_INCLUDE_DIR=$HOME/.linuxbrew/include/eigen3/ -DPYTHON=`which python``

ビルド

make -j20
<||

実行確認
>|sh|
./examples/train_xor  # 動いた

c++までは動作を確認した．

• • -

Pythonライブラリインストール

cd python
python setup.py install

実行

python
>> import dynet
# ImportError: /lib64/libc.so.6: version `GLIBC_2.14' not found (required by ./_dynet.so)

残念
あとで頑張る

考えられる原因

• glibcの特定のバージョンがないとインストールできない
• brewで入れたlibc.soを参照できていない

連続する整数の和

Sum of Consecutive Integers | Aizu Online Judge

整数Nがあたえられる．
２つ以上の連続する整数の組み合わせのうち，
和がN（1<=N<=1000）に等しくなるものの数を求める．

1. 連続する整数，つまり初項1，等差1の等差数列の部分列
2. 2点（左右）が定まれば良いので，全探索できる

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int sum (int l, int r) {
  return (r*(r+1)-l*(l-1)) / 2;
}

int main() {
  int n;
  while (cin >> n, n) {
    int l, r;
    int ans = 0;
    for (int l=1; l<=n; l++) {
      for (int r=l+1; r<=n; r++) {
        int ret = sum(l, r);
        /* if (ret == n) cout << l << ", " << r << "= " << ret << endl; */
        if (ret == n) ans++;
      }
    }
    cout << ans << endl;
  }
  return 0;
}

Keitai Message

Keitai Message | Aizu Online Judge

つらいやるだけ問題．
1. ヘッドを用意して順次更新
2. 0が入力されたら出力にpushしてヘッドを初期化

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;


class Keyboard {
  public:
    string input, output;
    vector<vector<char>> keyboard;
    string make_output();

    Keyboard(string input) : input(input) {
      // IMPORTANT: vector<vector<char>> keyboard;
      // これをここでやってしまうとメンバ変数とは違う
      // 形で初期化が行われてしまい外部から参照できなくなる
      keyboard.resize(10);

      keyboard[0] = vector<char>({'A'});
      keyboard[1] = vector<char>({'.', ',', '!', '?', ' '});
      keyboard[2] = vector<char>({'a', 'b', 'c'});
      keyboard[3] = vector<char>({'d', 'e', 'f'});
      keyboard[4] = vector<char>({'g', 'h', 'i'});
      keyboard[5] = vector<char>({'j', 'k', 'l'});
      keyboard[6] = vector<char>({'m', 'n', 'o'});
      keyboard[7] = vector<char>({'p', 'q', 'r', 's'});
      keyboard[8] = vector<char>({'t', 'u', 'v'});
      keyboard[9] = vector<char>({'w', 'x', 'y', 'z'});
    }

};

string Keyboard::make_output() {
  int curr;
  int prev = -1;
  int freq =  0;
  output = "";

  rep (i, input.size()) {
    curr = (int)input[i] - 48; // ascii code

    // 一緒 or 初め
    if (curr == prev || prev == -1) freq++;

    // 入力確定
    if (curr == 0) {
      if (prev != -1) {
        freq--;
        int qindex = keyboard[prev].size();
        /* cout << "i, j: " << prev << "," << freq % qindex << endl; */
        /* cout << keyboard[prev][freq%qindex] << endl; */
        output += keyboard[prev][freq%qindex];
      }

      // 初期化
      prev = -1;
      freq = 0;
    }
    else prev = curr;
  }

  return output;
}

int main() {
  int n;
  string s;
  cin >> n;

  rep (i, n) {
    cin >> s;
    Keyboard k = Keyboard(s);
    cout << k.make_output() << endl;
  }

  return 0;
}

お姫様のギャンブル

Princess's Gamble | Aizu Online Judge

実際にシミュレーションをする．
分母に0が来ることがあるので0除算の恐れがある．
場合分けを行えば良い．

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  int n, m, f;
  while (cin >> n >> m >> f, n) {
    vector<int> x(n);
    rep (i, n) cin >> x[i];

    float sum = 0;
    rep (i, n) sum += 100.0*x[i];

    float ret = sum - ((float)f/100) * sum;

    int ans = ret / x[m-1];
    cout << (ans > 0 ? ans : 0) << endl;
  }

  return 0;
}

C++で文字列を数値にする

c_strでconst char*に変換するといける
普通はどうするものなのかよくわかっていない
（そもそも文字列->数値な変換が発生すること自体がダメ？）

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  string a = "53";
  int i = atoi(a.c_str());
  cout << i << endl;
  return 0;
}

github.com

Long Short-Term Memory Over Tree Structures

• 論文: https://arxiv.org/abs/1503.04881
• 実装: https://github.com/pfnet/chainer/blob/master/chainer/functions/activation/slstm.py (in chainer)

概要

LSTMの木構造への一般化を考える．

背景

LSTMは線形な系列を入力に受け取る，非常に成果をあげているニューラルネットワークである．
しかし，いくつかのケースでは入力が線形ではなく，なんらかの構造を持っていた方が良さそうなケースというものもある．
代表的なものにstanford nlpの[sentiment treebank](https://nlp.stanford.edu/sentiment/)がある．
これは文を構文解析し，構文木が入力として与えて文の極性を予測するタスクである．
葉ノード（単語に相当する）と内部ノード（フレーズに相当する）に対して極性が人手（？）でアノテーションされている．
[Socher et al.](https://nlp.stanford.edu/~socherr/EMNLP2013_RNTN.pd://nlp.stanford.edu/~socherr/EMNLP2013_RNTN.pdf)はRecursive Neural Network(RvNN)・RNTNNを用いてこのタスクを解いた．

RvNNは内部に再帰構造を持っており，木を入力とすることができる一方で，木の深さが深くなると勾配消失が起きてうまく学習できない問題がある．
これは通常のRNNにも見られる問題であり，LSTMはメモリブロックという概念を導入することでこの問題に対処した．
この成果を活かし，RvNNにもLSTMのメモリブロック構造を導入し，より深い構文木が入力されても学習可能なS-LSTM(Structured-LSTM)を提案した．

手法

モデル全体は以下の図のようになっている．

また，各ノードに注目すると以下の図のようになっている．

LSTMと非常によく似た構造であり，差分としてはS-LSTMには忘却ゲートが2つ存在する．
ちなみに，忘却ゲートが2つと言っているが，これは入力される木が2分木であると仮定しているからそうなっているだけであり，n分木の場合は忘却ゲートがn個になる．
著者曰く

> Extension of teh model to handle more children is rather straightforward

である．
ちなみに，なぜ入力が2分木なのかというと，sentiment treebankのデータ構造が2分木であり，Socher et al.と同じ条件で実験しているからである．

入力・セル・重み・入力ゲート・忘却ゲート・出力ゲートについて詳しく見ていく．

忘却ゲートとセル，および重みが2つあることがわかる．
学習はSocher et al.と同じように行う．ロス関数は2通り考えられている．

1. ノードごとの予測のクロスエントロピーの総和
1. ルートノードの予測のクロスエントロピー

実験

sentiment treebankを用いて評価実験を行なった．
比較対象はSocher et al.のRvNNとRNTN,，あとNaive BayesとSVM．
RvNNは通常のRecursive Neural NetworkでRNTNはRecursive Neural Tensor Network．
RNTNはテンソルを用いたRvNNの一般化(?)モデルであるらしい．Socher et al.を読んでください．

MODEL	ROOTS	PHRASES
NB	41.0	67.2
SVM	40.7	64.3
RvNN	43.2	79.0
RNTN	45.7	80.7
S-LSTM	48.0	81.9

S-LSTMが一番良い性能を発揮した．
S-LSTMはRNTNと比較すると学習にかかる時間が短い点もアピールされている（論文を読んでください）．

ここからが面白い点だが，著者らはsentiment treebankのアノテーションはあまり現実のデータに則していないことを指摘している．
というのも，sentiment treebankは木のすべてのノードに対してアノテーションを行なっているが，現実のデータにフレーズ単位のアノテーションが付与されているとは考えにくい．
そのため，フレーズ単位のアノテーションが得られていない以下の2つの設定で追加実験をを行なった．

• (a)ルートノードにのみアノテーションが付与されている
• (b) 葉ノードとルートノードにアノテーションが付与されている)

おそらく以下のようなデータが与えられている（赤色がアノテーションされていることを示す）．

MODEL	ROOTS
(a) RNTN	29.1
(a) S--LSTM	29.1
(b) RNTN	34.9
(b) S--LSTM	44.1

同じ条件下ではRNTNよりも良い予測性能を発揮していることがわかる．

議論の腰を折りかねない疑問として「本当に入力に構造があった方が良いのか？」というものがある．
通常のLSTMも暗黙的に構造のようなものを学習していて，入力データには明示的な構造は必要ないのではないかという意見も起きうる．
そこで，データに対して特殊な制約を加えて，それらのデータを学習に使った場合と木構造を入力とした場合の予測性能も比較している．

LSTM--LRとLSTM--RRという2つの特殊なデータは，本来木構造を持っていた入力データの枝を張り替えて，構造を壊したものである．
LRは文中の1番左の単語の左側にルートノードを張り，RRは1番右の単語の右側にルートノードを張っていることを示している．

MODEL	ROOTS
(a) S--LSTM--LR	40.2
(a) S--LSTM--RR	40.3
(a) S--LSTM	43.5
(b) S--LSTM--LR	43.1
(b) S--LSTM--RR	44.2
(b) S--LSTM	44.1

LRとLLはほぼ同じ性能，もともとの木構造を入力としたものがそれより良い性能を発揮していることがわかる．
この結果から，著者は少なくともいくつかのタスクにおいては入力データの木構造は予測性能に影響を与えると結論付けた．

Research and reviews in question answering system

走り書きです．

• conference CIMTA 2013
• Sanjay and Vaishali

概要

QAのサーベイ． QAは現在のクエリを投入したら適合文書のリストが渡されて，そこから正確な情報をクエリ投入者が探すというパラダイムを超える可能性を持っている．

QAシステムは時間をかけて大変進歩してきたが，まだ幾つかの挑戦的な課題を残している．

1. 自然文の質問を理解すること
2. 質問タイプの分類
3. 適切なクエリ化
4. 曖昧性解消
5. 意味的類似語の検出

6. identification of temporal relationship in complex questions

7. QAシステムの３つのステップ

8. 質問解析
   • パージング
   • 質問分類
   • クエリ構築
9. 文書解析
   • 候補抽出
   • 解答特定

10. 解答解析

    • 解答候補のランク付け

11. QAシステムの分類

12. Linguistic Approach

    • tokenization and parsing
      • 異なる分野では異なる文法が必要になるなど，可搬性に乏しい
      • 適切なKBを作るのは時間がかかる
    • knowledge information is organized in the form of production rules, logics, frames, templates(triple relations), ontologies and semantic networks

13. Statistical Approach

    • 近年の爆発的な情報の増加を背景に発展してきたアプローチ
    • 大規模，不均質なデータをうまく扱うことができる
    • 特定のクエリ言語に依存しないし，自然言語でクエリをかける
    • 言語に依存しないし新しいドメインにも適応しやすいが，語彙的に意味のあるフレーズなどに弱い

14. Pattern Matching Approach

Ling

データベースに問い合わせるための自然言語インターフェース

自然言語文をクエリにする

• BASEBALL
• LUNAR

DIALOG

• ELIZA
• GUS

これらの手法では，データを構造化データベースに格納するため，解答能力に制約がある．

これらの制約を許容して，構造化データベースから得られる情報をもとに推論を行うタイプの質問応答システムが現れた．

STARTはWEBを知識源としている．経験則的な情報を用いてWeb上の情報を知識ベースに格納する．

Rule

Auarc，Carqは経験則にもとづいて質問文中から質問のタイプを分類する語彙的，意味的なヒントを探す．

• who, what, which, where,...
• others

Statistical

Answer finding task（クエリに対応する解答を統計的に探す）に使ってみたところ，パフォーマンスはデータセットの語彙数に依存することがわかった．

IBMが作った質問応答システムでは，Okapi（BM25?）とTREC-9のQAコーパスを使ったクエリの拡張の２つを採用していた．

Statistical methodでは，クエリと文書，もしくは一文との類似度をどのように計算するかがキモになっていて，キーワードの類似度やクエリや文書の長さ，出現単語の語順の類似など，様々な尺度が考えられ適用されている．

Pattern Matching

「Where was Cricket World Cup 2012 held ?」という質問に対して，「where was held ?」というテンプレートをマッチさせる（同時に，解答タイプが「場所」であることも予め定義しておく），というアプローチを取るものたち．

現在の質問応答システムの多くは上記のようなパターンをテキストから自動的に学習することが多い（言語学的な知識やオントロジー，言語資源（WordNetなど）を用いる複雑な手法は採用されない傾向がある）．

あまり複雑な質問に応答することはできない（パターンが膨大になる）ため，小-中規模の比較的簡単かつ限られた質問をされるような場面で使いやすい．

Surface Pattern based

大量の正規表現を使って解答を抽出する．

正規表現を大量に作成するのは非常に手間のかかる作業であるが，それらによって抽出される解答は非常に精度が高い．

得られた解答の信頼度を定量的に示すためにsurface patternを用いる手法もある．それらは高精度かつ低再現度である．

Template based

slotを埋めていくアプローチ．slotを埋めるタイプの質問応答は音声系の研究で多いと指導教官に教えてもらった記憶がある．

新しいデータが入ってきたとき，新しいテンプレートを作らなくてはそのデータに対応することができない．

Summary

linguistic approachは限定的なドメインをスコープに持つときにきわめて良いパフォーマンスを発揮する． 知識ベースを人でで作るのは分野の専門家が必要であり，手間もかかる． 最近の研究では，Webを知識源とすることによって知識ベースを強化したりオープンドメイン質問応答をしようという試みがある．

Statistical approachは充分な語彙数の大規模なデータ（= データ間が比較可能）が得られているときに良いパフォーマンスを発揮する． Statisticalなアプローチを取るときには，充分な訓練データがなければいけないが，一度適切に学習することができれば複雑な質問に対しても良い解答を生成することができる．

Pattern based approachは言語学的な分析をする代わりにテキストの特徴的な表現を活用する．Pattern basedな手法はその「浅さ」（表面情報しか加味しない点）ゆえに失敗することもあるが，Webをデータ源として活用するための効率的なテクニックでもある．Pattern basedな手法は，言語学的な情報への依存を減少させるだけでなく，不均質なデータをうまく扱える．だが，しばしばこの手法は意味的におかしい解釈や判断を行うことがある）（「浅さ」ゆえに）．

これらの基本的なアプローチは，単体ではそれぞれに異なる制約がある．これらの手法を組み合わせることでより精度，再現率の良いシステムを構築する試みもあり，ASQAやIBM Watsonなどが有名．

結び

QAシステムを実装するにあたって，どの技術を用いるべきかは想定される問題のタイプにきわめて強く依存している． 複数のアプローチのハイブリッドが良い結果を出しているが，以前として基本的な手法の研究も重要であり続けるだろう．

Python文法詳解メモ

www.oreilly.co.jp

Python文法詳解という本がある． 読むととてもためになる．自分がおおと思ったものをメモしている．

気になったら実際に読んでみると良いと思います．上記のリンクはオライリーの商品詳解ページを指していますが，このリンクを経由して本書を購入することで私に金銭的な利益が発生することはないので安心してください．

適当な値を要素に持つ配列を作る

こうしてた

[1 for _ in range(N)]

こうできる

[1] * N

罠があります（前者で作るのかな）． 後者の書き方でリストを作ると実行時間が劇的に短い．なんでかは考えてみてください．

qiita.com

算術演算

これは

a ** b % c

こっちのほうが高速

pow(a, b, c)

powって第三引数取れたんですね...

リストの展開

def spam(ham, egg):
    return (ham, egg)

a = [1, 2]
spam(*a)

辞書の展開

def spam(ham, egg):
    return (ham, egg)

a = {'ham': 1, 'egg': 2}
spam(**a)

ちなみに辞書を展開して変数にする(?)ので，キーは文字列でなければなりません(1 = 2みたいなことになってしまう)．

要素の分解

a, b, *c = list(range(10))

右辺の要素の数が足りないとき，cは空のリストになる(ただし，a, bは値がないといけないので，以下はエラーになる．

a, b, *c = list(range(1))

#=> Traceback (most recent call last):
#     File "<stdin>", line 1, in <module>
#     ValueError: not enough values to unpack (expected at least 2, got 1)

shallow copyとdeep copy

>>> a = [1,2,3]
>>> b = a
>>> a.append(1)
>>> a
[1, 2, 3, 1]
>>> b
[1, 2, 3, 1]

>>> 
>>> a = [1,2,3]
>>> b = a.copy()
>>> a.append(1)
>>> b
[1, 2, 3]
>>> a
[1, 2, 3, 1]

よく見ると新しくオブジェクト作ってるやつ

>>> a = 1
>>> b = a
>>> a += 1
>>> b
1

list.extend(iterable)

>>> a = [1,2,3]
>>> a.extend([1,2,3])
>>> a
[1, 2, 3, 1, 2, 3]
>>> a.extend('spam')
>>> a
[1, 2, 3, 1, 2, 3, 's', 'p', 'a', 'm']
>>> 

リストの末尾にイテラブルオブジェクトのすべての要素を追加する．

list.sort(key=int)

>>> a = ['1', '10', '2', 3]
>>> a.sort(key=int)
>>> a
['1', '2', 3, '10']

なにこれすごい．

str.center(w)

>>> 'a'.center(10)
'    a     '
>>> 'a'.center(10, '*')
'****a*****'
>>>

プログラミング演習でつかえそう(内輪ネタ)．

辞書内包

>>> {x+y:1 for x in 'abc'
             for y in '123'}
{'a3': 1, 'c2': 1, 'c1': 1, 'c3': 1, 'a2': 1, 'b3': 1, 'b2': 1, 'a1': 1, 'b1': 1}
>>>

集合内包

{i for i in range(10)}
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
>>> 

set(i for i in range(10))って書いてた．

そういえば，set([i for i in range(10)])って書かなくて良いのも最近知りました．

例外の送出

raise ValueError('不正な値です')

print('不正な値です')ってやってた．

関数アノテーション

>>> def spam(ham: "ハムの枚数") -> int:
...     return ham
>>> spam(2)

きちんと書くとIDEが良い感じにしてくれるらしい（伝聞）．

ラムダ式

>>> f = lambda x, y, z: 1
>>> f(1, 2, 3)
1
>>>

続パタの前向き・後ろ向きアルゴリズムについてのメモ

8章で解説されている前向きアルゴリズムに関するメモです． 私が勉強していてつまずいたところを，本文に即する形で補足します．

---

求めたいのは，サイコロの目の系列 が得られる確率 です．

この確率は潜在変数を用いて

と表すことができます．

\begin{align} \sum_{ \mathbf{s} } \end{align}

は一見普通の和に見えますが，実は

\begin{align} \sum_{ \mathbf{s} } = \sum_{s_1} \sum_{s_2} \sum_{s_3} \dots \sum_{s_n } \end{align}

という恐ろしい形の和です．

\begin{align} P( \mathbf{x}, \mathbf{s}) = \Pi_{ \mathbf{s} } a(s_{t-1}, s_{t}) b(s_t, x_t) \end{align}

この同時確率から $ \mathbf{x} $ のみに関する確率を得るためには，上で述べた恐ろしい $ \mathbf{s} $ に関する周辺化を行う必要があり， $ s_n $ の $ n $ が大きくなると現実的ではありません（$ O(2nc^{n}) $ になります）．

ここで，

\begin{align} P( \mathbf{x}, s_t = w_i ) \end{align}

について考えてみましょう．

\begin{align} P( \mathbf{x}, s_t = w_i ) &= P( x_1 x_2 \dots x_t, s_t = w_i ) P( x_{t+1} x_{t+2} \dots x_{n} | x_1 x_2 \dots x_t, s_t = w_i) \\ &= P(x_1 x_2 \dots x_t, s_t = w_i ) P( x_{t+1} x_{t+2} \dots x{n} | s_t = w_i ) \end{align}

最後の式で，２つ目の確率の条件の部分から $ x_1 x_2 \dots x_t $ が消えていることに気づくと思います．

この消去は条件付き独立の定義によって行われています．

問題文の条件に従ってグラフィカルモデルを書いてみると， $ x_n $ は $ x_1 \dots x_{n-1} $ の値とは独立であることがわかります．

ここで，

\begin{align} \alpha_t (i) = P(x_1 x_2 \dots x_t, s_t = w_i) \end{align}

とします．

$ \alpha_n (i) $ を $ \alpha_{n-1} (i) $を用いて表すことができないか考えてみます．

(唐突感がありますが， $ t = n-1 $とおいて考えてみたらこうなりました)

\begin{align} \alpha_n (i) = \left[ \sum_{j=1}^{c} \alpha_{n-1} (j) a(s_{n-1}, s_n) \right] b(s_{n}, x_{n}) \end{align}

ただし．$ t = 1 $のときは $ \alpha_{1} (i) = \rho_i b(w_i, x_1) $ とします．

得られた確率をよく見ると， $ \alpha_{n} (i) $ は $ P( \mathbf{x}, s_t = w_i ) $であることに気づきます．

つまり，これを $ i $ について周辺化すれば求めたい確率 $ P( \mathbf{x} ) $ を得ることができます．

よって，

\begin{align} P( \mathbf{x} ) = \sum_{i = 1}^c \alpha_{n} (i) \end{align}

となります．

おつかれさまでした．