めいふの備忘ログ

やったことを忘れないように書きこのしておくのです。

StrategyパターンでNGramモデルの文生成器を作った時のおもいで（動作テストと反省会）

2.5.3 mavenプロジェクトの取り込みテスト

NGramプログラムを作成環境とは別の環境で使えるまでをテストした経緯について書いておきます。といっても、別のPCのeclipseで作成したmavenプロジェクトのpom.xmlを以下のように設定して、そのプロジェクトでNGramプログラムが動作することを確認しただけです。

 <!-- github上の NGramプログラムの maven リポジトリをセット -->  
  <repositories>
    <repository>
      <id>sentencegenerator</id>
      <url>https://raw.github.com/meihuno/sentencegenerator/mvn-repo2/</url>
      <snapshots>
   	<enabled>true</enabled>
   	<updatePolicy>always</updatePolicy>
      </snapshots>
    </repository>
  </repositories>
  
  <dependencies>
    
    <dependency>
      <groupId>nlp.sample</groupId>
      <artifactId>sentencegenerator</artifactId>
      <version>0.0.3</version>
    </dependency>

  <!-- 色々と省略 -->
  </dependencies>

サンプルコードはこちらになります。太宰治先生の「走れメロス」でNGramモデルを学習しています。

package sample.nlp.mytest.hello;

import nlp.sample.sentencegenerator.SentenceGenerator;
import nlp.sample.sentencegenerator.NGram;
import nlp.sample.sentencegenerator.CrossEntropy;

public class SampleTest {
　public static void main(String[] args) {
　　// TODO Auto-generated method stub
　　String dirname = "/home/sugihara/void/data/aozora_bunko/dazai_osamu";
    SentenceGenerator sg = new SentenceGenerator(NGram.retNGramModel(dirname, smoothingType));
    
　　// 文生成、文の長さは100形態素まで。確率値が最大の文頭の形態素からスタートする。
    // P(c|a,b)の確率値で次の形態素を選択する際に最大の確率値をとるcが選択される。
    System.out.println(sg.retRandomSentence(100, true, true));

　　// 文生成、文の長さは100形態素まで。確率値が最大の文頭の形態素からスタートする。
    // P(c|a,b)の確率値で次の形態素を選択する際にcの選択はランダム。
    System.out.println(sg.retRandomSentence(100, true, false));

　　// 文生成、文の長さは100形態素まで。文頭の形態素はランダムサンプル。
    // P(c|a,b)の確率値で次の形態素を選択する際にcの選択はランダム。
    System.out.println(sg.retRandomSentence(100, false, true));

    // Backoff smoothing の Cross entropy
    String smoothingType = "backoff";
    CrossEntropy.showCrossEntropy(dirname, smoothingType);
    
    // Laplase smoothing の Cross entorpy
    String smoothingType2 = "laplase";
    CrossEntropy.showCrossEntropy(dirname, smoothingType2);
  }
}

結果は以下です。ちゃんと動作しています。生成された文は、まあ、それなりですね。文と文のつなぎは今回のプログラムのスコープ範囲外です。また、BackoffスムージングのCrossEntropyのが、LaplaseスムージングのCrossEntropyより小さいのでほっと一安心です。

<S>メロスは激怒した時、突然、目の前に一隊の山賊が躍り出た。</S>
<S>メロスも覚悟したのか、ついに憐愍を垂れてくれ、と思ったか、二度、三日間だけ許して下さい。</S>
<S>太陽も既に真昼時です。</S>
CrossEntropy of Backoff is H(L,M) (-7.383126980350443) -H(L) (-1.4018975110973793) = 5.981229469253064
CrossEntropy of Laplase is H(L,M) (-11.642169315239284) -H(L) (-1.4018975110973793) = 10.240271804141905

3 反省会

ひととーりNGramのプログラムはできたのですが、色々ダメな部分もあったのでその備忘ログを残しておきます。以下の点が特にダメだったと思います。

  • 3gramまでを想定した実装になっており4gram以上のことは考えていなかった

演習問題のためのプログラムだと思って手を抜いてしまいましたが、後々のことを考えて拡張性を担保しておけばよかったです。

  • NGramの形態素列をデリミタで区切った文字列で表現してしまった

NGramの形態素列を"3@メロス:は:激怒"のように、単語列の長さと単語列の文字列をデリミタ（@と:で）区切って表現し、HashMapのキーなどに用いていたのですが、このキーの処理をデリミタ文字列を用いたsplitで行っていたので、テキスト中にデリミタの文字（@や:）が含まれていると正しく動作しないという問題がありました。かなりひどい悪手だと思われたので反省しているのです…。プロダクトでこんな設計ミスしたらかなり大事でございます。NGram形態素列はちゃんとクラスをきってオブジェクトで扱い、IDなどで管理したほうがよかったよ…。

まあ、NGramに基づく言語モデルのツールを使いたい場合は、素直にkylmを使うのが安心だと思いますし、勉強になります。ありがとう、Graham Neubig先生、Xuchen Yaoさん…。

www.phontron.com

さて、長々とNGramのプログラムを作って遊んでまいりましたが、ぼちぼち終わります（NGramには飽きてきたよ）。でも自然言語処理、面白いですね。今後も勉強を続けていきたいです。固有名詞抽出やゼロ代名詞解析ついてプログラム作って遊んでみたいと思います。また、機械学習手法、特に、Deep Learningもかじってみたいです。

そしていずれは、言語処理を利用して、楽しく小説や随筆が書けるツールを作ってみたいです。例えば、「文の芥川龍之介度判定器」、「テキストで記述されている内容が架空のものなのかリアルなのか判定器」、「テキストの人称視点ズレ検出器」などですね。役に立つのかわかりませんが、楽しくなってきました。うむ、明日もがんがろう。

StrategyパターンでNGramモデルの文生成器を作った時のおもいで（プログラム作成の一般的方法論 ドキュメンテーション/リリース の段）

2.4 仕様書の作成（ドキュメンテーション）

前回までの内容でNGramモデルのプログラムの設計と実装も終わり、Unit Testも通りました。ここからはプログラムの公開のために行った作業についての備忘ログを書いていきたいと思います。

自分が作ったプログラムを他の人に公開する際には、プログラムのドキュメントも合わせて公開します。ドキュメントには、クラスについてはその責務を、メソッドの引数、返り値などについて説明されているとよいでしょう。

ラピッドプロトタイピング時や研究用のプログラムなどは、作るのが精一杯で、ドキュメンテーションの必要性を感じないこともあるのですが、ドキュメントは忘れた時の備忘ログにもなりますし、後輩に研究を引き継ぎぐときにも役立つなど、色々とうれしいことがあります。ドキュメンテーションは優しさなのです。

eclipseでJavaプログラムを書いた場合には、Javadocでドキュメンテーションを行うのが楽です。JavaDocとドキュメンテーションの心得についてはこちらが勉強になりました。ありがとうございました。

qiita.com

Javadocの書き方については以下のサイトが参考になりました。ありがとうございました。

www.javadrive.jp

こちらのサイトも参考にいたしました。ありがとうございました。

promamo.com

eclipseのFile＞ExportでJavadocを選択すればソースコードのコメントを元にJavadocが生成されます。せっかく公開するのならドキュメンテーションは英語で行ったほうが良いのです。英語ですと世界中の人たちの眼にとまることになります。ですが、今回は日本語で記述しています。太宰治の走れメロスは日本語ですし、形態素解析はkuromojiの日本語解析なので、まあ、今回は、妥協したのです…。

なお、（後段の節で手順を書いていますが）今回のNGramのプログラムはgithubのほうにもアップしていて、そのdoc下にJavadocが格納されています。

https://github.com/meihuno/sentencegenerator

2.5 リリース（インテグレーション）

自分のプログラムが完成したらgitやsvnにcommitして他の人たちにソースコードを公開します。

複数のプログラムやモジュールで構成されるシステムやプロダクトの開発ですと、ここからそれらのプログラムやモジュール群を結合して、システムとして複数のモジュールが正しく協調動作しているかのチェックを行います。これを結合テストといいます。しかし、今回は言語処理の教科書の演習問題のプログラムなので、何かのシステムの一部というわけではないのです。

今回はNGramプログラムを以下の手順で公開したのでその手順を公開しておくことにします。

・githubのmavenリポジトリの設定（pom.xml）
・githubに maven プロジェクトをdeploy
・maven プロジェクトの他のプロジェクトへの取り込みテスト

2.5.1 githubでの maven リポジトリの設定（pom.xml）

NGramのプログラムは最初からeclipseのmavenプロジェクトとして作成していきました。このソースコードはgithubにcommitして、maven プロジェクトのリリース物をgithub上のmaven リポジトリに deloyしていきたいと思います。

まずは、pom.xmlに githubのmavenリポジトリの設定を行います「github maven」あたりで検索して検索結果に含まれたブログで参考にしたのは以下です。ありがとうございました。

m12i.hatenablog.com

注意点として、githubのユーザプロファイル周りの注意点はここを参考にしました。ありがとうございます。

yo1000.hateblo.jp

また、ワタクシの環境では、maven の setting.xmlには githubへのaccess tokenを設定しなければうまく設定できませんでした。その情報についてはこちらのサイトを参考にさせていただきました。

qiita.com

結局、ワタクシめの pom.xmlのmaven リポジトリの関連の設定は以下のようになっています（抜粋）。

<groupId>nlp.sample</groupId>
<artifactId>sentencegenerator</artifactId>
<version>0.0.3</version>
<packaging>jar</packaging>

<name>sentencegenerator</name>
<!-- github の リポジトリ の url をセット -->
<url>https://github.com/meihuno/sentencegenerator</url>
  
<properties>
  <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
  <!-- maven の setting.xmlにおける github関連要素名 をセット -->
  <github.global.server>github</github.global.server>  
</properties>

<!-- maven リポジトリ用の githubのブランチについて -->
<distributionManagement>
   <repository>
    <id>internal.repos</id>
    <name>Temporary Staging Repository</name>
    <url>file://${project.build.directory}/mvn-repo</url>
   </repository>
</distributionManagement>

<build>
  <plugins>
    <!-- JUnitなど他のplugin設定については省略しています -->

    <!-- maven delopy 用の設定 -->
  <plugin>
    <artifactId>maven-deploy-plugin</artifactId>
     <version>2.8.1</version>
      <configuration>
       <altDeploymentRepository>internal.repo::default::file://${project.build.directory}/mvn-repo</altDeploymentRepository>
      </configuration>
  </plugin>

   <!-- github用の設定 -->
   <plugin>
     <groupId>com.github.github</groupId>
     <artifactId>site-maven-plugin</artifactId>
     <version>0.12</version>
     <configuration>
      <!--  <merge>true</merge> -->
                
      <!-- Git コミットメッセージ -->
      <message>Maven artifacts for ${project.version}</message>
      <noJekyll>true</noJekyll>
      
      <server>github</server>
           
      <!-- distributionManagement の url と一致させる -->
      <outputDirectory>${project.build.directory}/mvn-repo</outputDirectory>
           
        <!-- リモートブランチ名 -->
       <branch>refs/heads/mvn-repo2</branch>
       
       <includes><include>**/*</include></includes>
           
       <repositoryName>sentencegenerator</repositoryName>
       
       <!-- Github リポジトリユーザー名 -->
       <repositoryOwner>meihuno</repositoryOwner>
           
     </configuration>
     <executions>
      <execution>
        <goals>
          <goal>site</goal>
        </goals>
       <phase>deploy</phase>
      </execution>
    </executions>
   </plugin>
 </plugins>
</build>

2.5.2 githubに maven プロジェクトをdeploy

まず NGgramのプログラムのソースコードをgithubにcommitします。

$ git init
$ git add .
$ git commit -m "modified pom.xml for adjusting repository url"
$ git remote add origin https://github.com/meihuno/sentencegenerator.git
$ git push -u origin master

なお、.gitignore に /target/を追加してjarファイルをcommitしないようにしたりしています。そして、remoteリポジトリに対してmaven deployします。この辺は参考にしたサイトさんの手順そのまんまです。

$ maven clean deploy

deployされたgithub上のmavenリポジトリはこちらです。リポジトリの名前がmvn-repo2というあたりに色々苦労の後が伺えてしまうのです。

GitHub - meihuno/sentencegenerator at mvn-repo2

maven で buildすると eclipse の JUnit4が通らなくなるのでmaven clean を行ってmaven の buildをリセットしたりと、色々とmaven様には苦労させられました。githubへもaccesstokenがないとうまくアクセスできたりできなかったり。maven！いいかげんにせんか！とシャウトすることもあったのです…。この辺は慣れなのでしょうか。

さて、最後に「maven プロジェクトの他のプロジェクトへの取り込みテスト」については新しい記事でログを残しておきたいと思います。反省会もそちらでいたします…

StrategyパターンでNGramモデルの文生成器を作った時のおもいで（プログラム作成の一般的方法論 実装/テスト の段）

2.2 実装（の準備）

今回のNGramモデルによる文生成プログラムは、テキストからNGramモデルを学習して文生成を行うためのクラス群、CrossEntoropyを計算する機能を提供するクラスとして設計されました。クラス設計が終わりましたし、今回の文生成プログラムは小難しいふるまいは特に考えないことにしますので、いよいよJavaの実装にとりかかっていきます（いきました）。

Javaプログラム実装はeclipseで行いました。emacsとは違い色々とお世話をしてくれるのです。publicメソッドをprivateメソッドに切り替えた際の問題をすぐに教えてくれますし、Unit Test用のJUnit(後述)もドキュメンテーション用のjavadoc（後述）もすんなり使えます。eclipseさんは世話焼き系IDEだそうです（世話焼き系IDE：eclipseたん - 虎塚）。

以下には、プログラムの実装とテストに先立って行ったeclipseの設定について備忘ログを残しておきます。

  • 今回のプログラムのリリースはmaven経由で行いたいので、今回のプログラムはmavenプロジェクトとして作成します。
  • その際、Javaで利用可能な形態素解析プログラムであるであるkuromoji を dependency に加えておきます。
  • Unit test JUnit4でテストを組むことにしたいので、eclipse上のプロジェクトのPropertiesからJava Bulid Path で Add Library ボタンを押して、JUnit4を追加します。以下を参考にしました。

https://teratail.com/questions/30524

  • maven でのテストもJUnit4を使いたいので、以下を参照に設定を行いました。

MavenでJUnit 4をテストするためのpom.xml - Qiita

  • アサーションライブラリ（Unitテスト時に期待結果と実際の結果の比較用のメソッドを提供してくれます）のhamcrestもmaven経由で入れてみました。junitとhamcrestについては問題含みだということが以下のような情報がネットで見つかりまして、色々と試行錯誤しました。

hamcrestとJUnitの依存関係メモ | Futurismo
http:// http://d.hatena.ne.jp/namutaka/20130708/1373246628
JUnit4.11にしたら、Hamcrestが無いってエラーが出たよ・・・ - Qiita
Use with Maven · junit-team/junit4 Wiki · GitHub

その結果、mavenのpom.xmlのテスト関係の箇所は以下のようになっています（2016/11/30でjunit 4.11で試しています）。

 <build>
   <plugins>
       <plugin>
	<!-- maven surfire plugin は mvn test 時に実行される pluginである-->
        <artifactId>maven-surefire-plugin</artifactId>
        <version>2.12.4</version>
        <executions>
          <execution>
            <id>default-test</id>
            <phase>test</phase>
            <goals>
              <goal>test</goal>
            </goals>
            <configuration>
              <junitArtifactName>junit:junit</junitArtifactName>
              <encoding>UTF-8</encoding>
              <inputEncoding>UTF-8</inputEncoding>
              <outputEncoding>UTF-8</outputEncoding>
              <argLine>-Dfile.encoding=UTF-8</argLine>
              <skipTests>false</skipTests>
            </configuration>
          </execution>
        </executions>
        <!-- mvn test 時にJunit4を実行-->
        <configuration>
          <junitArtifactName>junit:junit</junitArtifactName>
          <encoding>UTF-8</encoding>
          <inputEncoding>UTF-8</inputEncoding>
          <outputEncoding>UTF-8</outputEncoding>
          <argLine>-Dfile.encoding=UTF-8</argLine>
          <skipTests>false</skipTests>
        </configuration>
      </plugin>
  <!-- 他のbuild 用 pluginについては省略 -->
  </build>

  <dependencies>
    <dependency>
    	<groupId>org.atilika.kuromoji</groupId>
    	<artifactId>kuromoji</artifactId>
    	<version>0.7.7</version>
    </dependency>
    <!-- junit4.12では hamcrest-all と junit の組み合わせでよいようです -->
    <dependency>
    	<groupId>org.hamcrest</groupId>
    	<artifactId>hamcrest-all</artifactId>
    	<version>1.3</version>
    	<scope>test</scope>
    </dependency>
    <dependency>
    	<groupId>junit</groupId>
    	<artifactId>junit</artifactId>
    	<version>4.12</version>
    	<scope>test</scope>
    </dependency>
  </dependencies>

ともあれこれでJUnit4でUnitTestができるようになったので実装準備は完了です。実装とは、UnitTestなのです（なのでした）。

2.3 テスト（実装とデバッグ）

プログラムが期待通りに動くのかはテストされなければなりません。それはプロダクトでも、研究用コードでも変わりません。品質を満たさないプロダクトは市場には出せませんし、検証されていないプログラムでは論文は書けないのです。

また、Regression test (プログラムを修正変更した場合に過去に実施したテストを再度実施して結果に影響がないかを確認するテスト)は、今回のように教科書を読みながら試行錯誤しながら実装する場合に有効です。ワタクシも、各クラスのメソッドの期待動作についてUnit Testを書き、教科書を読みながらあーでもないこーでもないとプログラムを実装したのです。おかしなコードを書くと、テストが通らなくなるので、デバッガを起動してデバッグします。ブレークポイントをセットして、変数の中身を確認しながら何がおかしいのかの調査を繰り返しました。


f:id:meihuno_huno_san:20170114083236p:plain:w400
eclipseでのデバッグ風景。虫ボタンを押し、ブレイクポイントをセットし、停止時に変数を見るのです

JUnitでのUnitテストの書き方について解説しているサイトは数多あるのです。ワタクシはそのようなサイトを眺めて勉強しながらテストを書いていきました。テストクラスの直上に@付きのアノテーションを付与してテストの動作を定義します。@BeforeClassアノテーションはテストを行う前の準備のためのアノテーションです。@Testがテストメソッドになります。以下のサイト様が参考になりました。ありがとうございます。

Junitコードの書き方 - code snippets

テストクラスを Run As で JUnit Test を選択すれば、テストが実施されます。バーが緑なら全テストは成功、赤な場合はError/テスト失敗であることを表します。


f:id:meihuno_huno_san:20170114091257p:plain:w600

以下、BackOff Smoothingの実装をデバッグをしていてはまったポイントを備忘ログとして残しておきます。

頻度がゼロになる場合のGoodTuring推定値の補正値

頻度rの補正値の r^{*}計算には、頻度r+1の単語の総頻度数が必要になります。ごく少ない数の文でUnitテストを組んでいた時に、頻度1の単語列しかカウントできず、頻度2の単語列が得られず、rの補正値が計算できないというとほほな状況になりました。確率的言語モデルの教科書には、 N_{r}が得られない場合の補正値の計算方法が紹介されていました。ワタクシも以下の回帰直線を用いて N_{r}の補正値 S(N_{r})を計算しました（mとbの推定はさぼった）。

logS(N_{r}) = -m log r + b (m, bは定数)

文の生成確率の計算

文の生成確率を以下のように計算すると文生成確率の和が1になりません。

P(w_1,w_2,w_3,...,w_n) = P(w_1)P(w_2|w_1)P(w_3|w_1, w_2)...P(w_n|w_{n-1}, w_{n-2})

文生成確率の計算には条件付き確率の和で行います。3gramで行う場合は文頭はbigramになるが、文頭の記号 \verb|<| S \verb|>| を2つ準備するなりして文生成確率の和が1になるようにします。

P(w_1,w_2,w_3,...,w_n) = P(w_1|\verb|<| S \verb|>| )P(w_2|\verb|<| S \verb|>|, w_1)P(w_3|w_1, w_2)...P(w_n|w_{n-1}, w_{n-2})

今回の記事はまだ続くのです…

全てのメソッドのUnitTestがグリーンでしたら、実装は終了です。しかし、プログラム作成のお仕事はまだ残ってるのです（「StrategyパターンでNGramモデルの文生成器を作った時の思い出（プログラム作成の一般的方法論 ドキュメンテーション/リリース の段）」に続く）。

StrategyパターンでNGramモデルの文生成器を作った時のおもいで（プログラム作成の一般的方法論 設計の段）

2.プログラム作成の一般的な方法論

今回のNgramモデル作成Javaプログラムですが、企業や研究機関でのよくあるソフトウェアの書き方に則って作成してみました。すなわち、プログラム保守のしやすさや品質を維持するために、以下の作法に則ってプログラムを書いた次第です。

1. 設計
2. 実装
3. テスト
4. 仕様書の作成（ドキュメンテーション。普通は1と平行して行う）
5. リリース（インテグレーション）

RubyやPythonなどのスクリプト言語の使い手には「書きながら（設計やアルゴリズムを）考えてる！」という豪の者もいるそうなのですが、今回はJavaですし、設計図からプログラムを起こしたのでした。

2.1 設計

NGramモデルのあらましはわかりました（わかったことにしましょう）。「走れメロス」でNGramモデルを学習して、走れメロスっぽい文生を生成するを文生成器を作りたいと思います。では、どのようなポリシーでプログラムを作るべきなのでしょうか？

このポリシーを決定することがソフトウェアの設計のスタートです。ワタクシもこのポリシーに従ってソフトウェアが実現するべき機能（機能要件といいます）や性能的な特徴など（非機能要件といいます）を定め、ソフトウェアの静的な構造（どんなクラスで作るか）や振る舞い（オブジェクト間の呼び出しの手順）を決めていきます（今回はクラス設計までを行います）。

さて、今回はBack Off smoothing によるNGramモデルのプログラムを作成しますが、smoothing methodには他にも色々ありますし、NGramではない言語モデルもあります。将来的にはいろんな手法を試してみたい、と思うのです。そこで、ワタクシ、TINときたのです。「キン肉マンⅡ世」25巻（ゆでたまご著）、Page69で、戦況に応じて戦術（ストラテジー）を変えるBエボリューションズの２人のことを。

戦術（ストラテジー）パターンだ！と。

戦況に合わせてStrategyを選択するBエボリューションズのケビンとスカーフェイス（「キン肉マンⅡ世」25巻（ゆでたまご著）、Page69）

パターンとはデザインパターンのことです。過去のソフトウェア設計者が発見し編み出した設計ノウハウを蓄積し、名前をつけ、再利用しやすいように特定の規約に従ってカタログ化したものなのです（Wikipediaより）。

今回はStrategyパターンを採用します。Strategyパターンでは、様々なルールやアルゴリズムを、場合に応じて使い分けられるようにします。該当アルゴリズムの実装（この場合はモデルやスムージング手法）からアルゴリズムを個別に切り出します。色んなスムージング手法を試したい今回のような場合にぴったりです。

デザインパターンについては以下の本で勉強してみました。

オブジェクト指向のこころ（Alan Shalloway先生、James R.Trott先生著）
オブジェクト指向のこころ (SOFTWARE PATTERNS SERIES)

Ruby によるデザインパターン（Russ Olsen 先生著）
Rubyによるデザインパターン

StrategyパターンによるNGramモデル実装のためのクラス図も書いてみました。

NGramモデルは確率計算用のWordSequenceProbクラスを持ってはいますが、計算アルゴリズム自体はWordSequenceProbクラスにまかせています。スムージングの個別のアルゴリズムはWordSequenceProbクラスを継承したサブクラス内で行っています。新しいスムージング手法を試したい場合はWordSequenceProbクラスを継承したサブクラスを追加していけばよい、というわけです。

また、クラス図を書くとどのクラスがどのクラスに依存しているかなど言葉ではなく視覚でとらえることができます。クラス図をレビューすることで保守性の高いメンテナンスしやすいソフトウェアの構造に近づけていくこともできます。レビューはもちろん他の人にしてもらうのが一番ですが、ぼっちでもできます。

例えば、今回のクラス構造も最初はSentenceGeneratorクラスがFindFileを使用する形になっていましたが、ワタクシがクラス図をせっせと書いていると、NGramからもFindFileクラスを使用していることが白日の元にさらされたのでした。結果、テキストデータの読み込みはNGramにまかせて、SentenceGeneratorクラスからのFindFileクラスへと伸びていた依存の線はなくなったのでした。プログラムを書く時は最初にかるくでいいのでクラス図を書くと将来のめんどーごとを減らせるかもしれません。

さてさて、これでプログラムの設計ができあがったということにして、いよいよ実装です。記事は「StrategyパターンでNGramモデルの文生成器を作った時の思い出（プログラム作成の一般的方法論 実装/テストの段）」に続くのです。

なお、クラス図などのUML記述ツールはChangeVisionさんの [提供終了] 無償UMLモデリングツール astah* community を使わせてもらっています。astahは業界標準のUMLツールなんじゃないでしょうか。いつもお世話になっております。

StrategyパターンでNGramモデルの文生成器を作った時のおもいで（NGramモデルのあらまし）

前回のブログ更新から随分と日があいてしまいました。ワタクシのブログ更新の頻度は多分年一回とかそんなレベルなのではないでしょうか。何と生産力のないことでしょう（嘆き）。

さて、前回の記事では「JavaScript界のあらましをさらに勉強している」とか書きました。嘘ではなくてJavascriptは触っていて、Javascriptソースを処理して動作するJavascriptスクリプトを書いてみたけど、ソースを改行でsliceするfunctionを書いたらmerge-minify後にさっぱり動かない（注1）ことになって悲しみを知ったりとか色々あったのです。

しかし、今日はJavascriptではなくてJavaで書いたプログラムについて記事を書きたいと思います。JavascriptとJavaは全然違う言語だということはIT業界では常識云々ですが、そのへんの話は置いておいて以下の内容で記事を書いてみたいと思います。

「StrategyパターンでNGramモデルの文生成器を作った時のおもいで」

注１: merge-minify。javascriptソースコードから可読性のためのスペースや改行を除去してソースコードをまとめて軽量化すること。ページの応答速度が改善させる。改行を手がかりに処理していたので改行をとっぱらったらまるで動かなくなる。とほほ。

背景

ワタクシは自然言語処理という分野に興味を持ってお勉強をしてみたのです。自然言語処理は人間が書いたテキストをコンピュータで便利に処理するための技術です。例えば、キーボードの入力を漢字に変換するかな漢字変換とか、テキストを検索する検索システム（GoogleとかApache Solrとか）、商品レビューでお客さんが商品を褒めているのダメだししているのかの判定をしたりとか、医学論文などから人工知能が学習して医療診断する（IBMのシステムが有名です）などが自然言語処理の応用システムと言われています。

そのような応用システムを自然言語処理の基礎技術、例えば、テキストの「文」から「単語の区切りや品詞の判定」をする形態素解析ですとか、主語や述語といった文法的な構造の解析（文の構文解析といいます）といった技術が支えているのです。

ワタクシもこの自然言語処理に興味があったのです。例えば、小説執筆支援用「芥川龍之介パワー判定器」を作ってみたいのです。そこで、自然言語処理の教科書としてあちこちででおすすめされていた以下の２冊の本で勉強してみることにしました。

「Speech and Language Recognition 2nd editionand」（Daniel Jurafskey and James H. Martin 先生著、以下SLR本）
Speech and Language Processing: International Version: an Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition

「確率的言語モデル（北研二 先生著）」
言語と計算 (4) 確率的言語モデル

今日は、SLR本のSection4 N-Gramsの演習問題（4.1から4.8まで）を解いて3-gramを生成するプログラムを書いたでその時の備忘ログを残しておきます。より具体的には、3-Gramの言語モデルをStrategyパターンによって実装し、太宰治先生の「走れメロス」で学習したメロス文自動生成器を作りました。

以下、

1. NGramモデルとスムージング手法（Back off smoothing）のざっくりした説明
2. プログラム作成の作成手順（設計、実装、テスト、文書化、リリース）

の順に記事を書いていきたいと思います。

1. NGramモデルのざっくりした説明

1.1 NGramモデル概説

NGramモデルは、人間が文章を書いたり話したりするその過程を、「文字や単語はその直前のN個の文字（や単語）で依存して生成されている」という仮定に基づいて確率モデル化したものです。NGramモデルは検索システムの検索、入力補完、誤字の補正など広く自然言語処理システムに応用されているそうです。

以下の例文を考えてみましょう。声に出して読んでみます。

Nana eats an X. (確率的言語モデルの3.1 NGramモデル入門より)

なんとなく、Xはappleやorangeな気がしてきます。eatsに続く言葉は食べ物でしょうし、an の次の単語は母音スタートなのです。この「気がする」をどう計算機でモデル化したらよいか、NGramモデルでは、これを単語列の条件付き確率として表現します。単語列 "eats an"の次に単語Xが生じる確率 はP(X|eats, an)の値として表現します（とりあえずXの2つ前の単語列までを考えます）。

その確率値は、コーパスから単語列の頻度をカウントしてきて、P(apple|eats an) = C(eats an apple)/C(eats an)のように推定できます（Cはその単語列の頻度を表します）。テキストの"eats an apple"は、"eats an ant"よりもたくさん出現しそうですから、P(table | eat an) よりも P(apple|eats an)のほうが高くなりそうです。

NGramモデルでは、ある単語(または文字)の出現確率をその単語（文字）を含めたN個、N-1個前までの単語（文字）列の条件付き確率で表現します。N=3のトライグラムの場合は、2つ前にまでの単語列の条件つけで確率の値を計算します。P(w3|w1,w2)のようにです。単語列の生成確率はトライグラムの条件付き確率で以下のように表されます（ \verb|<|S \verb|>| は文頭を表す特別な記号です）。

P(w_1,w_2,w_3,...,w_n) = P(w_1|\verb|<| S \verb|>| )P(w_2|\verb|<| S \verb|>|, w_1)P(w_3|w_1, w_2)...P(w_n|w_{n-1}, w_{n-2})

Nの数字は大きくなればなるほど、計算と確率値の保持が大変になります。Nが大きいと、学習用テキスト中に長い文があった場合、文中の単語列の並びのパターンを全ての記憶していなければなりません。そこで、NGramモデルでは、言葉の生成は単語をN-1個前までだけ見て決めればよいという近似を採用することで、文中の単語列の並び全ての保持を回避しています。

しかし、NGramモデルにはまだ弱点があります。N-1個前のみを見るという豪快な近似は、それよりも前方の文脈に影響をモデルに組み込むことはできません（これは別のモデルで解決が試みられているそうです。Long Short Term Memory を利用した Recurent Neural Networkなどです）を顧慮できない、または、ゼロ頻度問題なる問題があります。

ゼロ頻度問題とは、学習データにない単語列がテキストに１つでも単語があると、単語列の生成確率が０になってしまうというものです。例えば、「走れメロス」を学習データとしてNGramモデルの確率値を推定した時に、単語列の頻度のみを用いて確率値を計算すると、P("メロスは感激した。")のような、走れメロスの本文にない文の生成確率を計算しようとして、そのような文の並びは走れメロスの本文中にはないので（頻度をカウントできないので）、確率値は０になってしまうのです。

このゼロ頻度問題（加えて学習コーパス中の低頻度な単語列の扱い）に対して、未知語の確率値がゼロにならないための様々なスムージング手法が提案されてきました。その１つがSLR本の4.7「Backoff」で取り上げられている「Katz's の Back Off smoothing」 です。

1.2 Katz's の Back Off smoothing

Backoff smoothing手法では以下のように確率値を補正します（以下は3gramの場合を示します）。


{ \begin{eqnarray} P(w_3|w_1,w_2) = \left\{ \begin{array}{ll} P^{*}(w_3|w_2, w_1) & (C(w_1,w_2,w_3) > 0 ) \\ \alpha(w_1,w_2) P(w_3|w_2) & (C(w_1,w_2) > 0) \\ P^{*}(w_3) & (Otherwise ) \ \end{array}\right. \end{eqnarray} }

スターのついている確率値は以下による補正値です。

P^{*}(w_3|w_1,w_2) = dC(w_1,w_2,w_3) C(w_1,w_2,w_3)/C(w_1,w_2)
dC(w_1,w_2,w_3) = C^{*}(w_1,w_2,w_3)/C(w_1,w_2,w_3)

C^{*}(w_1,w_2,w_3) は 単語列頻度の補正値であるGood Turing 推定値を用います。 w_1,w_2,w_3の出現数をr回とします。Good Turing 推定値は以下の数式で計算します。

r^{*} = (r+1)N_{r+1}/N_r

この N_rはr回出現したn(この場合3)単語列の総数です。3単語の頻度が頻度0の時は、（おそらくより頻度の高いであろう）2単語列による確率値を用いて代替します。dCをかけた確率値の和は1になりません。そのディスカウントした確率値をゼロ頻度時の確率値として貯金しておくのがBack Off smoothing 法のミソになります。 \alphaはディスカウント係数で貯金した確率値を分配する関数です。まず \alphaを与えるために便宜的に \betaという量を考えます。

\beta(w_1, w_2) = 1 - \sum_{w_3:C(w_1,w_2,w_3) > 0} \frac { dC(w_1,w_2,w_3) C(w_1,w_2,w_3)} { C(w_1,w_2) }

これは、 w_1,w_2によって与えられる条件付き確率値の合計1から w_1,w_2によるディスカウント係数分を引いたものです(ゼロ頻度用の貯金)。 \alphaという関数で、 w_1,w_2に対してこの貯金を w_1,w_2,w_3がゼロ（または低頻度）の場合に割り振っています。

\alpha(w_1,w_2) = \frac { \beta(w_1,w_2) } { \sum_{w3;C(w1,w2,w3)=0} P(w_3|w_1,w_2) }

以上がBackoffスムージング法の概要です。スムージング手法には他にも以下のようなものが色々とあります。

・線形補間法
・ワンカウント法
・カーリーネイスムージング方法

NGramモデルのプログラムについても、これら多様なスムージング手法の追加を想定した作りにしたいものです。また、言葉を生成する方法はNGramモデルだけではなくRecurent Neural Networkなどの他の方法もあります。NGramモデルと他のモデルの切り替えができたほうがよさそうです。このNGramのスムージング法がたくさんあるという事実が以下で述べるプログラムの書き方に影響を与えるのです。(次回、「StrategyパターンでNGramモデルの文生成器を作った時のおもいで（プログラム作成の一般的方法論 設計の段）」に続きます)

「Javascript の 絵本」のサンプルプログラムを OSX Yosemite で動かしたときのおもいで

　Javascirpt を仕事でさわる機会があったのですが、ワタクシは prototypeとかなにそれおいしいの？　みたいなすごい素人でした。お友達からも「ユーはJavascriptの基礎知識を薄い本で身につけるべき」と言われまして、そこで、ワタクシは応じたのです。

「一番（Javascriptの）薄い本を頼む！」と。

　それからJavascritpの入門書を検索してみると、Amazon.co.jp： JavaScriptの絵本: アンク: 本 がおすすめされていましたので買ってみました。

f:id:meihuno_huno_san:20150730074206p:plain

　今回はこの本でJavascriptの基礎知識を学んだ時の思い出を備忘ログとして残しておきます。具体的には「8章 Ajax の基礎」のミニ辞典のサンプルプログラム（諸藩では154ページから紹介されているやつです）の動かし方について記載するのです。プログラムの初心者にとっては、プログラム言語そのものよりもプログラムを動作させるための手順のことがわからず困ることがあるので、その辺りを中心にまとめておくことにします。

　さて、Ajax とはウェブサーバと非同期にXMLやJSONをやりとりするものだそーで、Google マップのような地図をマウスでぐりぐり操作するようなダイナミックなWebページに一役買っているそうなのです。サンプルプログラムでは、XMLhttpRequestオブジェクトを使ってWebサーバとの通信を行っています。

　このサンプルプログラムを動かす準備ですが、

１）クライアント側の html ファイル と サーバ側のperl スクリプトを準備します
２）Web サーバ を CGIを動作させる設定で動かす
３）html ファイル を公開用ディレクトリに、 perl スクリプトをCGI 用ディレクトリに配置
４）デバッグする

　の流れ進めています。

１）html ファイル と perl スクリプトを準備します

　「Javascriptの絵本」に書いてあるプログラムのソースを写本したのです。eclipse などの IDEでコードを書くとタイポなどを指摘してくれてよいそうですが、ワタクシはemacs でせっせと以下の2ファイルを写本いたしました。
　

　

２）Web サーバを動かす

　OSX でWeb サーバを動かすには xammp や MAMP といったアプリケーションをダウンロードして起動するという手がありますが、Yosemite には もともと apache の 2.4系 が入っているのでこちらを使います。

sudo apachectl start

　ブラウザから、http://localhost へアクセスして、"It works!" と表示されていればWeb サーバはとりあえず動いています。ただ、サンプルプログラムのdictionary.cgi は Web サーバ も CGIを動作させる設定でないと動きません。なので、/private/etc/apache2/httpd.conf の以下を確認します。#などでコメントアウトされていた場合は#をとって設定を有効にします。

LoadModule cgi_module libexec/apache2/mod_cgi.so が有効であること
AddHandler cgi-script .cgi が有効であること

CGI-Executablesの ExecCGIが有効

<Directory "/Library/WebServer/CGI-Executables">
    AllowOverride None
    Options ExecCGI
    Require all granted
</Directory>

　確認が済んだら、apachectl を restart させます。動作確認のために、以下のtmp.cgi を/Library/WebServer/CGI-Executablesに配置します。

#!/usr/bin/perl

print "Content-type: text/html;charset=UTF-8\n\n";
print "\n";
print "<html>\n";
print "<head>\n";
print "<title>テスト</title>\n";
print "</head>\n";
print "<body>\n";
print "これはCGIのテストです。\n";
print "</body>\n";
print "</html>\n";

　http://localhost/cgi-bin/tmp.cgiでアクセスした際に「これはCGIのテストです。」と表示されればWebサーバのCGIの設定はOKです。なお、tmp.cgi や dictionary.cgi には chmod コマンドで ファイルの実行許可を与えておきましょう（ワタクシはよく忘れるのです）。

３）html ファイル を公開用ディレクトリに、 perl スクリプトをCGI 用ディレクトリに配置する

/Library/WebServer/Documents/miniehon.html
/Library/WebServer/CGI-Executables/dictionary.cgi

とそれぞれ配置しておきます。

４）デバッグする

　上記の作業を完璧にこなせばサンプルプログラムは動作して、http://localhost/miniehon.html にアクセスすれば、それっぽいページが表示されているはずですが、写本がミスっていたりして、最初はうまく動かなかったのです。なので、ブラウザのデバッガーを利用してデバッグしたのです（ワタクシめはChromeを使っているので、以下、ブラウザはChromeです）。Chromeの画面で右クリック（トラックパッドの二本指クリック）するとメニューが表示されるので「要素を検証」を選択するのです。

f:id:meihuno_huno_san:20150730120651p:plain

すると、Chromeのデバッガが立ち上がります。

f:id:meihuno_huno_san:20150730121409p:plain

　ワタクシはまず、Consoleを表示させて、console.log(obj)でオブジェクトを表示させてみました。いろいろがんばってサンプルプログラムは無事に動いたのです。ふー、やれやれ。Chorme のデバッガーはよくできていて、ソースコードを見ながらObjectの内容の確認、ブレイクポイントの設定、クライアントとサーバとの通信状況の確認、メモリリーク調査などなど色々できるようなので、ワタクシもがんばって色々と使いこなしていきたいなあと思いました。

「Javascriptの絵本」の次は「Javascript本格入門」を読んでいます。

　Javascriptの絵本を読んで、Javascript界の概要とエッセンスは眺めることができたような気はしております。次のステップとして、今は
Amazon.co.jp： JavaScript本格入門 ～モダンスタイルによる基礎からAjax・ｊQueryまで: 山田 祥寛: 本 でJavascript界のあらましをさらに勉強しているところです。明日もがんばろう。

ikki fantasy の 技履歴表示ツールでマウスオーバー時のポップアップを作った時のおもいで

　以前 備忘ログに書いた ikki fantasy の 技履歴表示ツールの実装について、実装上の細かいテクニックについても 備忘ログとして残しておくのです。

本日の封殺予報（闘技大会の技履歴表示ツール）

https://young-ravine-2391.herokuapp.com/

ソースコードはこちら
https://github.com/meihuno/ikki_br_analysis

技の効果記述をポップアップで表示するようにしています。


　技履歴のテーブルにマウスカーソルをおくと技の効果がポップアップされるようになっています。これで相手チームのどの技がやばそうなのかを予習しておくことができるのです。敵を知り、己を知れば百戦危うからず、なのです。

f:id:meihuno_huno_san:20150729165938p:plain

　というか、ズバリ以下のアンギス様の「jQueryでツールチップ実装 その2」をそのまんま利用させてもらった次第なのです。ありがとうございました！

http://unguis.cre8or.jp/web/1934

特定のキーワードを含む技のテーブルに色をつけます。

　また、特定のキーワードを含む技履歴を調べたい、例えば、味方や対戦相手が「回復」を含む技を使ってきているかを調べたい場合、技履歴ツールで「回復」というキーワードを検索欄にいれて検索すると、技履歴のテーブルに色がつきます。

　色つきとポップアップ表示の手順としては、

１） 技効果のTable の td にはid = "sample"を与えておく
２）技履歴のTable内のtd の data-text 属性に技効果説明文をいれておきます
３）特定のキーワードを含む技が含まれている場合はtd の bgcolorを指定します

　のような処理を行っています。技効果説明文については 一揆wiki（Ikki Fantasy wiki） - スキル一覧 から技と効果説明文の対応を抽出して Hash につめておきます。

　以下のhtml は 「回復」で検索した場合のtableのtr、tdタグです。

<tr>
  <td>シュガー</td>
  <td>1</td>
  <td bgcolor="#ffc0cb" id="sample" data-text="冥土の歳墓@SP 消費 900 味方乱: (HP<u>回復</u>MHP*0.12?)+道連4を付加(重複可)*3">
　  グローム、冥土の歳墓、サニュイス
  </td>
  <!-- 以下省略 -->

　アンギス様のJavascript ソースを少しだけ改変し、tbタグのidがsampleでmouseenterした時にjavascript が動作するよう変更しています。これにて技履歴のTable にマウスをおくと技の効果が把握できるようになりました。

$("td#sample").on({
    'mouseenter':function(ev){
	var top = $(this).position().top;
	var left = $(this).position().left;
	//  以下省略

　なお、ツールのディレクトリ構成は 以下なのですが、css ファイルや javascript はbin/publicの下に配置されています。

bin/myapp.rb 他実行スクリプト
     /view
       - index.erb  (技履歴のTableを作成する)
       - layout.erb (レイアウト。こちらからjavasc)
     /public
        /css (css ファイルを配置)
        /js（javascriptファイル配置）
        /font (フォントの eot、ttf、svg、woffファイルなど)
lib/ （こちらにライブラリやユーティリティクラスを配置）
data/（ikki Fantasy 関連のデータ（Pstore で事前に保存したHashなど）を配置）
test/（第6回闘技大会専用のやっつけテストコード）
gogoikki.sh (ikki fantasy の更新結果から解析済みデータオブジェクトを作ったりします)

　これらの javascriptファイルやcssファイルは、諸々 bin/views下のlayout.erbにてincludeしておきました。技履歴のTable は ユーザからの クエリを受け取ってから作成しますので、index.erb 内にあらかじめinclude しておいても問題ないと思います。 

<html lang="ja">
 <head>
  <meata charset="urf-8">
  <title>本日の封殺予報</title>
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <link href="css/bootstrap.min.css" rel="stylesheet" media="screen">
  <link href="css/simple_sample.css" rel="stylesheet" type="text/css">
  <meta http-equiv="Content-Style-Type" content="text/css">
  <script src="https://ajax.googleapis.com/ajax/libs/jquery/1.10.2/jquery.min.js"></script>
  <script type="text/javascript" src="js/simple_sample.js"></script>
 </head>
<!-- 以下省略 -->

　CSS と Javascript でウェブのコンテンツがきびきび動くようになり、なんだか隠し味みたいだな、などと思いました。