JJUG ナイトセミナー 機械学習・自然言語処理のおはなしを聞きにいった

雑なまとめですが一応公開します.速記なので内容の正確性は保証できません.スライドを見ると良いと思います.

Javaでカジュアルに機械学習

機械学習を始める前に知っておきたいこと

機械学習とは,経験(データ)によって賢くなるアルゴリズムの研究.分類・識別,パターンマイニング・アソシエーションルール,予測・回帰,クラスタリングなどができる.これらは正解があってモデルを作っていく教師あり学習と,正解がない教師なし学習に分類できるそうです.

入力データとしては原則として数値列しか扱えないため,非構造データはそのままでは扱えない.そういった場合はそのデータを表現するなにがしかの「特徴量」を抽出することによって機械学習を実現している.得られた結果が正しいかどうかについて確かめる方法として,k分割交差検証や適合率,再現率,相関係数,決定係数などを用いるものがある.また線形分離という,データを一本の線を轢くことによってデータを分類する方法もある.

Javaで機械学習

機械学習アルゴリズムのテストはかなり辛く,時間・空間効率の良い実装はさらに難しい.したがって車輪の再発名はなるべく避け既存のライブラリをなるべく使うようにした方がよい.Javaで機械学習を用いたアドホック分析はだいぶ辛いので,そういったことであればPythonを使うと良いとのこと.

Javaで使える機械学習ライブラリのなかで発表者がおすすめなものがliblinear-java.線形分類・回帰可能な問題へ特化している. Wekaは多種多様な機械学習アルゴリズムが提供されているため最初に触るには向いているらしい.MLib(Spark)は分散処理フレームワークSpark上での利用を前提としていて,アドホック分析の環境としてもScalaを用いて利用できる.MahoutはHadoop上の機械学習ライブラリ.Sparkのほうが出てきてから若干オワコン感があるらしい.SAMOAはStomなどの分散ストリーミングフレームワーク上で利用できる機械学習ライブラリだが最近開発があまり活発ではない?Jubatusはリアルタイム性が要求されるときに用いると良い.h2oはディープラーニングをJavaでやりたいときに使うことになるそうです.

UCI Machine Learnigというところで色々なデータが提供されている.だいたいがCSVファイルで提供されている.そのなかでもIrisというのは機械学習の世界でのHello worldにあたるくらい常識的なデータセットらしいです.

Wekaの入力形式はCSVの先頭にちょっとおまけがついているものだが,CSVLoaderというクラスがあるので問題はない.k分割交差検証を実施するweka.classifiers.Evaluation,ロジスティック回帰による分類はweka.classifiers.functions.Logisticあたりを用いる.実際のコードはGitHubにあがっている.

SparkとMLlibのはなし

機械学習でモデルの制度を高めたいがデータが増えると計算量やIO量が増えるし,そのデータをどこに置いておくのかという点が問題で,かつ従来の機械学習ライブラリは,単一のマシンで計算を行うことが前提としてつくられていた.したがって計算処理の効率は単一のマシンの性能に制約されていた.Hadoopはオープンソースの大規模分散処理基盤で特別な聞きを用いずコモディティなサーバ機器を複数束ねてクラスタを形成して,並列分散処理を可能にするものだそうです.

HDFSは複数のスレーブを束ね,大きなファイルシステムに見せる仕組み,故障することが前提の設計.MapReduceは大規模分散処理向けのフレームワークでこちらも故障が前提.これらを連携させることにより真価を発揮する.HadoopとMahoutの登場で機械学習はある側面でスケーラブルになったそうな.MapReduceを前提としていると反復処理の回数を増やすほど,モデルが作られるまでのレイテンシが大きくなる.Hadoopはスループットを最大にすることを目的にしているため,ジョブが多段になったときにもオーバーヘッドが問題となっていく.

Apache Sparkとはスループットとレイテンシの両方が必要な問題領域にアプローチするために開発されたOSSのインメモリ分散処理基盤.HadoopはMapReduceという単一の処理パラダイムであるが,RDDという異なる処理モデルがとられている.

HadoopはMapとReduceでジョブを構成している.SparkはRDDで処理をしたデータをチェーンでつなげた全体を単一ジョブとして構成する. Sparkの目標の一つはコアとなる分散処理エンジンを中心に据え,それを活用するためのライブラリを充実させることで,そのひとつがMLlibになる.Scala/Java/Pythonでコードを書ける.

自然言語処理のはなし

このあたりで動画あがってるのに気付いたのでメモしてない

感想

ElasticSarchとKibanaとMLlibあたり面白そうなので、それらを使って何か作ってみようと思いました

ラムダ計算について調べた(前編)

関数プログラミングとその背景にある数学的なお話を理解する上でラムダ計算の知識が必要そうなので,確認していきます. というかなんかよくよく調べていくと,「計算機科学の理論としては常識」とか書いてあったりするので,あせって基礎をさらいました. まずは型なしのラムダ計算まで. 間違ったところがあったらご指摘頂けると嬉しいです.

ラムダ計算とは何か?

Wikipediaによるとラムダ計算とは次のようなものとされています.

ラムダ計算(lambda calculus)は、計算模型のひとつで、計算の実行を関数への引数の評価(evaluation)と適用(apply)としてモデル化・抽象化した計算体系である。ラムダ算法とも言う。

ラムダ計算では,関数をラムダ抽象を使って記述します. たとえば f(x)=2x+1 なる関数は f=λx.2x+1 というように書きます. こうすることにより,関数を返す関数などを定義することができるようになります. また名前をつけずに値のように関数を取り扱えるようになりました.

たとえば, g(x,y)=x+2y+1 は g=λx.(λy.x+2y+1) といったように 2変数関数は,1変数を返す関数として定義することができます.このような変換をカリー化(currying)とよびます. また関数を値として受け取ったり,返したりする関数のことを高階関数(higher-order function)とよびます.

関数に値を適用したい場合はラムダ抽象の後ろに値を書けば良いです. たとえば f(x)=2x+1 に x=2 を適用するときは ((λx.2x+1)2) と書きます. これを関数適用といいます.

またλx.x+y についてx は束縛されているといい y は自由であるといいます.

型なしラムダ計算(lambda calculus)

ラムダ式の構文

型なしラムダ計算の抽象構文は e::=x|λx.e|e1e2 のように定義されます. 単純にいうとラムダ式は,変数か,ラムダ抽象か,関数適用から構成されるということです.

ラムダ計算の実行

ラムダ計算の実行はα-変換,β-簡約,η-変換の3つの操作に抽象化できます.

  • α-変換(α-conversion)
    • λx.M→αλy.M[x:=y]
    • 束縛変数の名前はMの中に自由なyがなければ置き換えられる:λx.f⇒λy.f[x→y]
  • β-簡約(β-reduction)
    • (λx.M)N→βM[x:=N]
    • 関数適用そのものを指す:λx.fy⇒f[x→y]
  • η-変換(η-conversion)
    • λx.Mx→ηM
    • 関数の外延性を表す:λx.fx⇒λy.f

ラムダによるデータの表現

自然数

以下のように自然数をラムダ式で表せる.このようなラムダ式をチャーチ数(Church Number)とよびます.

  • 0 を λs.λz.z
  • 1 を λs.λz.sz
  • 2 を λs.λz.s(sz)

これは足し算を plus=λg1.λg2.λs.λz.g2sg1z を定義して, plus 1 2 などを計算してみると納得がいくと思います

論理値

論理値 true は λt,λf.t ,false は λt.λf.f とすると, if e1 then e2 else e3 を e1e2e3 としてうまい具合にif-elseの構造を表せる. これは if true then e1 else e2 = true e1 e2 = (λt.λf.t)e2e3 →(λt.e2)e3→e2 かつ if false then e1 else e2 = false e1 e2 = (λt.λf.f)e2e3 →(λf.g)e3→e3 となることから納得がいくと思います.

その他 この資料 が結構良い感じにまとまっています

他クラスに依存しないテストを支える仕組み:スタブ・モック・スパイ

手元にはあったが長らく積んでいたJUnit実践入門の11章:テストダブルの章を読んでまとめを書きました.実際のところMockitoってなんだかいままでよく分からない存在だったけど,手をつけてみるとかなりお手軽&便利なものでした.学習コストもそれほど高くないので,何となく敬遠していたり,テストってどう書けば良いのかよくわかっていない私のような人がいたら是非,Mockitoを使ったテストコードを実際に書いてみることをお勧めします.

テスト対象クラスが依存するクラス・モジュール問題

理想的なユニットテストは,依存するすべてのクラスや外部システムを使用したもの  
* なぜなら,実際に動くコードはそういう状況で動くのだから
* しかし依存する本物のオブジェクトを常に使用できるとは限らないし,ユニットテストで扱いにくいオブジェクトもある
* このようなときにテストしやすいようにリファクタリングしたり,本物のオブジェクトの代役となるオブジェクトに置き換えてテストを行うという手法が用いられる

テスタビリティを高めるリファクタリング

  • JavaのDateの精度はミリ秒であるため次のコードは,テストに成功したり失敗したりする
  • 乱数を使ったコードは当然ながらテストが書きにくい
  • このようにインスタンス生成のタイミングや環境に依存してしまう部分が含まれるコードのテストは難しい

インスタンス生成の部分を抽出してファクトリメソッドを作ると,ここをOverrideして振る舞いを変えることができ,依存度を下げることができる

今回の例に対してはやや過剰な実装とはなるが,振る舞いの複雑なメソッドをオブジェクトに切り出し,委譲を使って差し替え可能にするという方法もある

テストダブル:スタブ/モック/スパイ

  • テスト対象となるクラスが他クラスに依存していないケースはほとんどない
  • 依存しているクラスもまた他のクラスに依存している
  • この状態でテストを行うメリットは実行時に近い状態でテストができること
  • デメリットはテスト対象以外の問題を原因としてテストが失敗する可能性があること
  • このとき依存しているオブジェクトの代役(スタブ・モック)を使うことをテストダブルという

スタブ

  • スタブとは依存するクラスやモジュールとして代用できる仮のクラス・モジュール
  • 以下のようなときに用いられる
    • 依存オブジェクトが予想できない振る舞いを持つとき
    • 依存オブジェクトのクラスがまだ存在しないとき
    • 依存オブジェクトの実行コストが高く,簡単に利用できない
    • 依存オブジェクトが実行環境に強く依存している
  • 例えば乱数を用いるようなクラスのテストは,依存オブジェクトRandomが予想できない振る舞いを持つためスタブを使うと良い
  • コード的には次のようなものになる

モック

  • スタブと同様にテスト対象が依存するクラスやモジュールの代用として使用されるもの
  • スタブはメソッドの返り値を予想可能な値にすることにより、依存クラス・モジュールが正しく利用できているか確かめるもの
  • モックはメソッドが正しく呼び出されているかを検証するもの

スパイ

  • 基本的にテストはメソッドへの入力に対して出力を検証する
  • 従ってvoid型のメソッドの検証はやりにくい
  • そこでロガーに書き込まれた内容を検証に使うスパイという手法がある
  • 基本的にはロガーのロギング機構にStringBufferへのappendの処理を追加して,検証時にtoStringして文字列比較するという単純なもの

Mockitoでスタブ・モックを作る

  • mockitoが適当に使える状況にしておく
  • Mock.mock(モックを作りたい対象のクラス)でモックが作れる
  • `where(モックのインスタンス.メソッド()).thenReturn(期待する返り値)Pで振る舞いを持たせられる
  • その他,コードを見ればきっと分かる!
  • 基本的にmockitoの使い方自体は簡単だけれど,そもそもスタブ・モックとは何かを理解できていないところがmockitoを使う上での最大の壁になると感じた
  • 現に本を読んで自分はちゃんとスタブ・モックがなにかを理解できていなかったので反省した

Scalaのクエスチョンマーク3つは「Predef.???」

つい数日まえについにScalaでいろいろ書き始めました. コップ本のクラス定義の仕方とかそのあたりを適当に流し読みして, とりあえずいろいろ書いて分かんないところ読もうという方針のもと,コードを書いていくことにしました. わりと順調に進んで,型付きパターンマッチや, 変位指定アノテーションあたりなどちょくちょく分からないところをコップ本とググってでてきたページで解決してきました.

しかしながら,いろいろ調べものして出てきたScalaのコードにdef hoge = ???なる記述が…。とりあえずコップ本の索引を見てみるも載っておらず,?は記号なのでググっても引っかからない.「scala クエスチョンマーク」「scala 記号」で検索してもダメで,twitterでぼやいたところ,その正体がPredef.???だということを教えていただきました(ありがとうございました).

例えばdef hoge = ???としておくとコンパイルは通りますが,実行時にNotImplementedErrorをスローするという挙動をするもののようです.これはScala2.10から追加されたもののようで,追加に向けてForumでいろいろ議論がされていたようです.

すこしでも検索に引っかかりやすくなるようまとめてみました.
正確な話は公式のDocumentやソースコードを見て頂けると良いかと.

ちっと「???」はググって解決しにくいよなぁ…と,思いました(小並感).

以下最近調べたScalaまわりのことまとめ

型付きパターンマッチ

objがIdentifier[_]型のときマッチされ,値を以下の例だとthatという名前で扱える.別にthatじゃなくても良い.

全てのオブジェクトに実装されている##メソッドの実態

## は基底クラス(Any)に定義されているハッシュ値の取得メソッド

override def hashCode: Int = 31 * id.##

変位指定アノテーション:非変・反変・共変

[T]: 非変(nonvariant) => 指定した型変数のみを受け入れる
[-T]: 反変(contravariant) => 指定した型変数のスーパークラスを受け入れる
[+T]: 共変(covariant) => 指定した型変数のサブクラスを受け入れる

この場合,Indentifierトレイトの型変数には,Tとそのサブクラスを受け入れることができる.

Bridge Pattern

参考リンク

機能と実装の違い

ある数列[1,3,2,5,4]をソートしたいとします.このときソートの方法は何通りかあります.このとき「ソートをする」ということが機能にあたります.そして「ソートをする方法」,たとえばクイックソートやマージソートなどが実装にあたります.クラスを拡張しようとするときには,具体的には「機能の拡張」と「実装の拡張」のいずれかであることが多いです.

Bridge Patternが必要になる状況例

TECSCOREにわかりやすい例が載っていたので,それに添ってBridgeパターンが必要になるシチュエーションを見てみます.ソート機能を持つ抽象クラスSoterに対して,実装クラスQuickSorterBubbleSorterを以下のように作成したとします.機能はSoter,実装はQuickSorter, BubbleSorterに分離されていることに注意します.

現状のコードに新しい「実装」を増やすことは容易いです.単にSoterをextendsした実装クラスを書けば良いだけだからです.しかしながら新しい「機能」を増やすためにはどうしたら良いでしょうか.ためしにソートに加え,それにかかった時間を表示する機能を追加したい場合を考えてみます.するとコードは以下のようになります.

ソートの実装自体は先ほど実装してあるQucickSort, BubbleSortクラスを使いたいとします.しかしながらよくよく考えてみるとTimeSorterにそれらの実装を与えることができません(Java1.7以下での話?).そこで残念ながらそれらのTimeSorterに対応した実装クラスQuickTimeSorterBubbleTimeSorterを書かなければなりません.図で表すと以下のような具合になります.

l-1

このような状況に上手く対処するためにBridge Patternが用いられます.

Bridge Pattern

Bridge Patternでは実装の部分を別の階層に切り離すことによって,これまでに見てきた例のような問題を解決します.まずはコード例を見てみます.

このように機能を実現するための方法がSortImpl委譲されているため,実装の追加はもちろん,機能の追加は容易になります.まとめとしてBridge Patternのクラス図を示しておきます.

l-2

時間経過に伴って機能が拡張されていくバージョンアップの過程と,実装タイプのバリエーションを豊富に広げる品揃えの充実具合を,別個に分けて,整理して管理できる(GoFの23のデザインパターンを,Javaで活用するための一覧表より)

Java8での機能と実装の追加について考えてみた.

この部分については個人的に思いついた内容なので,実際に良い方法なのか微妙なところですが,とりあえず書いておきます.Java8ではインターフェースがデフォルト実装を持てるようになったため,先の例ででてきたSorterを抽象クラスではなくインターフェースとして定義しておけば,「実装の拡張」はもちろん,「機能の拡張」もすっきりおこなえるかなと思いました.ソートにかかる時間を表示するtimeSort機能を追加したあとのクラス的にはこんな具合になると思います.

l-3

現時点でこの方法が抱えている問題は,Sorterが抽象クラスではなくインターフェースになったので状態(プロパティ)を持てなくなってしまったという点だと考えていますが,どうでしょうか.

Strategy Pattern

状況・文脈(context)によって動的に振る舞いを変えたいときの定石がStrategy Patternです.
たとえば各OS向けに文字列を出力するTextPrinterクラスがあるとします.
ところが各OS標準で用いられる改行コードはことなるのでその部分についての振る舞いをOSによって変えなければなりません.
以下はこういう状況のときにありがちなコード例です.

往々にしてif文の嵐になります.そこで改行コード出力のふるまいだけを抜き出して,オブジェクトとして扱ってしまおうというのがStrategy Patternになります(言い過ぎ?).どの環境下でのふるまいも共通して「改行コードを出力する」という責務を持っているのでインターフェースを決めておくと便利です.今インターフェースCompositorを定義し,その後に各々の環境に応じた実装をしていくと良いです.

このようにスッキリしました.今やったことを抽象化したStrategy Patternのクラス図は以下のようになります.

l-4

【参考:GoF本での定義】アルゴリズムの集合を定義し、各アルゴリズムをカプセル化して、それらを交換可能にする。
Strategyパターンを利用することで、アルゴリズムを、それを利用するクライアントからは
独立に変更することができるようになる。

アルゴリズム実装のための専用オブジェクトを複数作っておき,その中から使うものだけを動的に選んで実行する。
ある程度複雑なアルゴリズムになると,ふつうのプログラマであれば,その部分を切り出して集約するだろう。また,他のアルゴリズムに置き変わった時に備えて,互換性も持たせておくだろう。なので,あまり新規性を感じないパターンに思えるかもしれない。とはいえ,アルゴリズムの交換可能性を増すために,共通の基底(または共通のインタフェース)を持たせているという点は注目。(GoFの23のデザインパターンを,Javaで活用するための一覧表より

Bridge PatternとStrategy Patternの違い

よくわからなかったので,GoF本の適用可能性の欄を参照しました.

  • Bridge Pattern(構造に関するパターン)
    • 抽出されたクラスとその実装を永続的に結合することを避けたい場合.
    • 抽出されたクラスとその実装の両方を,サブクラスの追加により拡張可能にすべき場合
    • 抽出されたクラスの実装における変更が,クライアントに影響を与えるべきではない場合
    • 複数オブジェクトの間で実装を共有したい場合
  • Strategy Pattern(振る舞いに関するパターン)
    • 関連する多くのクラスが振る舞いのみ異なっている場合
    • 複数の異なるアルゴリズムを必要とする場合.
    • アルゴリズムが,クライアントが知るべきではないデータを利用している場合.
    • クラスが多くの振る舞いを定義しており,これらがオペレーション内で複数の条件文として現れている場合.

ここから察するに,Bridge Patternは継承より委譲を使うことにより,インターフェースとその実装の結合を弱め,「機能」と「実装」を柔軟に拡張できる構造を作りたいときに使うパターン.そしてStrategy Patternは状況に応じ振る舞いが変わるような状況下でその振る舞いの部分を切り出し,クラスの肥大化・複雑化を避けたり,あるいはクラスと振る舞いの結合を弱めるために使われるのではないかと思いました.間違いがあったらご指摘いただけるとありがたいです.

参考リンク

Singletonパターンの罠

インスタンスが一個しか存在しないクラスを書くためのパターンがSingleton Patternです.登場するのはSingletonクラスひとつのみで以下のようなクラス図になります.

L

結城本には以下のような感じでサンプルコードが掲載されていました.

Double-checked locking 問題

参考ページ

概要

Fooクラスのインスタンスがただ一つだけするようにSingletonパターンを用いて以下のようなコードを書いたとします.

もし2つのスレッドが同時にgetHelper()を呼んだ場合,同時にインスタンスを生成しようとして,片方が完全に初期化されないままのインスタンスの参照を持ってしまうようなことが起こり得ます.これを防ぐためには,コストは大きいですが同期を取ってあげればよく,以下のようなコードに変更すれば良いです(from wikipedia).

よくよく考えてみるとsynchronizeが必要なのはgetHelper()内の最初のif文のみです.そこでDouble-checked lockingというイディオムが考えられました(from wikipedia).

Initialization-on-demand holder idiom

Double-checked lockingによりsynchronizedにより初回に正しくインタスタンス生成されたあとは同期を取らずにすみます.理論的には申し分ないのですが,これはJavaプラットフォームのメモリー・モデルが原因で,期待通りの動作が必ずしも保証されません.Javaではシングルトン実装のアンチパターンとされています.そこでInitialization-on-demand holder idiomというものが推奨されています(from wikipedi).

Template Method Pattern

だいたいの処理の流れが共通しているとき,それをテンプレートとしてスーパークラスに記述して,個々の具体的処理のみをサブクラスに記述するというパターンがTemplate Method Patternです.

このパターンに登場するクラスは主に2つあります.ひとつは,ひな形となるAbstractClassで,ここにはテンプレート内で行う個々の処理を抽象メソッドです.もうひとつは,それらを使った一連の処理の流れを実装したメソッドです.個々の処理はサブクラスで実装するためにprotectedかpublic修飾子を,それらを使った一連の流れを定義したメソッドは全サブクラスで共通化(テンプレート化)させたいのでfinal修飾子を付けます.クラス図は以下のような具合になります.

l

実際にファイルになにかを保存するための一連の流れを想定した例を以下のように書いてみました.

まとめ

  • Template Method Patternはabstract classの有用な使い方のひとつで,「似たような複数の処理の流れ」から共通の性質を見つけ出し,テンプレート化することにより,「似たような複数の処理の流れ」の数が増えたときでも,読みやすいコードが書けるのではないかと思った.
  • ただその「似たような複数の処理の流れ」の共通の性質をしっかりと見抜いて,良いテンプレートを作らないとかえって変更が難しいコードになってしまう危険性も持っているのではないかと思いました.
  • 事例で学ぶデザインパターン 第3回 Template Methodパターン