Scala

Scala用の機械学習関係ライブラリ関係を調べてみる

 
Scala Advent Calendar 2013の一環として記事を書いてます.内容としてはScala Advent Calendar 2011の記事(Scalaは機械学習に使えるかな?)の続きみたいなものかな・・・.

まずScalaからJava系のライブラリ各種を呼び出す場合ですが,Scala Days 2013のトーク : Scalable and Flexible Machine Learning With Scala (http://parleys.com/p/51c2e0f3e4b0ed877035684f)や,関係のスライド Scalable and Flexible Machine Learning With Scala @ LinkedInあたりをまず見てみます.
 
要するにMapReduceの処理にどうやって持っていくかという話になるのですが(暴論),紹介されているScalding(Github: https://github.com/twitter/scalding)などのように,ScalaでDSLの実装をして,裏ではJavaライブラリやScalaで書かれた部分に頑張ってもらう,と.ScalaでDSLという話はScalaスケーラブルプログラミングにも出てくる程度には普通の話だと思うので,まぁ普通に嬉しいですね,ということになります.
 
自前で実装するという話をもう少し見ていくと,メソッドを演算子のような形で使うことで(この表現は怪しい?)普通に自作クラス間での計算式を賭けるようになるので,機械学習で使うような計算(線形代数: ベクトル,行列, 確率統計: 分布からのサンプルその他)を実装していくという方向になります.2年前に調べたときはScalalaという線形代数(Linear Algebra, LA)のライブラリ開発がされていましたが,今はbreezeというプロジェクトになりました.

Github: https://github.com/scalanlp/breeze

ScalaNLPというNLP(自然言語処理; 人間が読み書きや話しに使う言語で書かれた文書や,文書の集まり(コーパス)をコンピュータで処理すること. ibisforestさんより)のための開発の一環でしょうか.

Breeze is a library for numerical processing, machine learning, and natural language processing. Its primary focus is on being generic, clean, and powerful without sacrificing (much) efficiency.

 
Scalalaの時代はそこまでドキュメントが整理されていなかったですが,最近ではMatlabやPythonでのNumpy/Scipyと比較してどうこう・・・Breeze Linear Algebra · scalanlp/breeze Wiki · GitHubというページが整備されていて,普通の行列計算やベクトル計算をそのまま書き写すことが一応出来るでしょうか.

なぜ一応と言っているかというと,Pythonでいうndarrayの機能が全てないようなんですね.全て無いこと自体は欠点ではないですが,平たく言うと多次元配列をそんなに上手く扱えないようので,そのあたりが本当にMatlabやNumpy/Scipyからの書き写しが出来るのか疑問に思っています.というかできなかったんだよ.

val c = DenseMatrix.zeros[Double](n,m) 
c(::, 2) 

このようにそれっぽく要素アクセス出来るので,たぶんちゃんと調べたらもう少し使い方分かるような気がするのですが.上の対応表ページで紹介されているSpecial “reduction” functions.とか面白いのですけどね.肝心の性能ですが

Breeze uses netlib-java for its core linear algebra routines. This includes all the cubic time operations, matrix-matrix and matrix-vector multiplication. Special efforts are taken to ensure that arrays are not copied.

ということらしいです.僕は詳しいことは分からないので,そのうち実験したいです.DenseMatrixと他のMatrixの違いとか.

breeze自体は上に書いた通り,自然言語処理関係の一部分で開発されているようなので,線形代数計算以外にもパッケージがあります.機械学習関係(breeze-learn)や可視化関係(breeze-viz)があります.一番ドキュメントが整理されているのは線形代数関係(UserGuide: https://github.com/scalanlp/breeze/wiki/UserGuide)だと思いますが.ホームページ上ではEpicというパーサ(文を区切ります)を作ってるっぽいですが,正体は謎です.

ただ,ScalaDocで吐き出されているAPIページを見てみると,breeze.classify(分類器), breeze.corpora(コーポラ), breeze.data(データ関係,おそらくファイルとか読み込んだりする用), breeze.inference, breeze.stat, breeze.optimize(推論,確率統計関係,最適化関係)とかいろいろあるんですよね.まぁ開発中なんでしょ,きっと.

ちょっと試したい場合,build.sbtにライブラリ依存を書いて使って見て下さい.

scalaVersion := "2.10.2"

libraryDependencies ++= Seq(
  "org.scalanlp" % "breeze_2.10" % "0.5.2",
  "org.scalanlp" % "breeze-viz_2.10" % "0.5.2"
)

resolvers ++= Seq(
  "Sonatype Snapshots" at "https://oss.sonatype.org/content/repositories/snapshots/",
  "Sonatype Releases" at "https://oss.sonatype.org/content/repositories/releases/"
)



さて,もう少し別の方向にDSLが発展した(と言っていいのか,ちょっと自信がないですが)ものにOptiMLという開発中のものがあります(Stanford PPL).これは全体的にもっと大きなフレームワークの一部だと思いますが,機械学習用のDSLを目指しているように見えます.

OptiML is a domain-specific language for machine learning written in Scala. This project primarily explores how scalable data and task parallelism can be implicitly extracted out of high level abstractions such as vectors, matrices, factor graphs, decision trees, and neural networks.


現在はアルファ版(OptiML — Welcome)で遊ぶことができます.結構容量あります.Scalaで書かれているものを.degファイルで書かれたものにコンパイルして実行します.大きなフレームワークってどういう話かというと,OpenCLやCUDA使ったり,C++と絡ませたり,そういうことです.全然Scalaで完結してないじゃん・・・.

それはともかく,サンプルとしてGDA(って何?), ロジスティック回帰,ナイーブベイズ,RBM,kNNのscalaファイルが入ってます.余計な部分を省いてちょっと見てみます.

val x = readMatrix(args(0))
val y = readVector(args(1)).t

val theta = DenseVector.zeros(x.numCols)
// gradient descent with logistic function
val alpha = 1.0
val w = untilconverged(theta, maxIter = 30) { cur =>
  val gradient = sum((0::x.numRows) { i =>
    x(i)*(y(i) - sigmoid(cur *:* x(i)))
  })
  val z = cur + gradient*alpha
  z
}

ってまぁ上のbreezeみたいな計算,中で書いてます.普通だった.んでoptimlの中身に上のbreezeのコアで使われているっぽいですがnetlib-java使ってるようです.あらあら.もう少しの中身はExampleページをどうぞ(Example: OptiML — Examples).実際中身でどんなことしてるか,よくわかりませんでした.


と,ここまで順番にbreezeとOptiMLを見て見ましたけど(書いてないですが,breeze.linalg使って一応ナイーブベイズまで書いたんだよ…),正直なところ例えばMatlabからScalaに,PythonからScalaにと,移行してくるほどかというと,全然そうでもないですね.また来年に期待しましょう.もう少し真面目に,ドキュメント/API読んでみようかなぁ.

Parabola Journal

酔っぱらいながらアプリオリアルゴリズムを書いてみた

 
Aprioriアルゴリズム:ここでは頻出アイテム集合だけを発見する.「アプリオリアルゴリズム」で検索して上に出てきた2つのページをリンクします.
~アプリオリアルゴリズム・極大頻出アイテム集合~
データマイニング
酔っ払ってるし,よく分からん型作ってるね.あとItemMax決め打ちかよ.
 

object Main {
  def main(args: Array[String]): Unit = {
    val set = Mining.apriori("database.txt", 3)		
    println(set)
  }
}

object Mining {
  import scala.io.Source
  type LDB = List[Set[Int]]
  type SDB = Set[Set[Int]]
  val ItemMax = 9
  def apriori(filename: String, th: Int): SDB = {
    val lines = Source.fromFile(filename).getLines.toList
    val database = lines.map{_.split(" ").toList.map(_.toInt).toSet}

    // Calculate all occurrences of 
    val size1 = (1 to ItemMax).toList.
    map(Set(_)).filter( i => count(database, i) >= th)

    // Generate candidates of length k+1 from those of length k
    def growth(k: Int, Sk: LDB): (LDB, LDB) = {
      val candidates = collection.mutable.ListBuffer[Set[Int]]()
      for (S1 < - Sk) {
        for (S2 <- Sk if S1 != S2
             && (S1 ++ S2).size == k+1
             && !candidates.contains(S1 ++ S2)) {
              candidates.append(S1 ++ S2)
        }
      }
      val frequentCandidates = candidates.filter( count(database, _) >= th)
      (candidates.toList, frequentCandidates.toList)
    }

    def _apriori(k: Int, C: LDB, S: LDB): LDB = {
      if (C.isEmpty) return S
      else {
        val (nC, nS) = growth(k, S)
        return S ++ _apriori(k+1, nC, nS)
      }
    }

    // Calculate until no such candidates are generated
    val frequentItemsets = _apriori(1, size1, size1)
    frequentItemsets.toSet
  }

  def count(db: List[Set[Int]], itemset: Set[Int]): Int = {
    db.filter( itemset.subsetOf(_) ).length
  }
}

database.txtの中身は以下のとおり.
1 2 5 6 7 9
2 3 4 5
1 2 7 8 9
1 7 9
2 3 7 9

たぶん動いた気がする(震え声)

Scala

ScalaのPriorityQueue

 
Scala 2.9.1.
 

object Main {
  type Pair = (Int, Int)
  // Comparing the second element of 2-tuple
  object MyTupleOrdering extends Ordering[Pair] {
    def compare(a: Pair, b: Pair) = - (a._2 compare b._2)
  }
  def main(args: Array[String]) = {
    import scala.collection.mutable.PriorityQueue

    val pq = PriorityQueue[Pair]()(MyTupleOrdering)
    val _list = List[Pair]( (1, 2), (2, 1), (3, 5), (5, 7) )
    for (v < - _list) pq += v

    while (!pq.isEmpty) {
      val top = pq.dequeue
      println("->(%d,%d)".format(top._1, top._2))
    }
  }
}


 
出力
cocomoff[10:20午前]% scala Sample.scala 
->(2,1)
->(1,2)
->(3,5)
->(5,7)


 
何をやろうとしてたんだっけ?
 

Scala

Project Eulerの22問目

 
特に工夫しなかった…




// @cocomoff
// 2013-02-20

object Main {
def main(args: Array[String]) {
import scala.io.Source
val strL = Source.fromFile(“names.txt”).getLines.toList.mkString

// 名前切り出し
val list = strL.split(“,”).map( v => v.slice(1, v.length-1) ).toList

// 文字列でソート
val slist = list.sort((e1, e2) => (e1 compareTo e2) < 0)

// 文字列を名前に変換する関数
def str2value(str: String): Int = str.map( v => v.toChar.toInt – ‘A’ + 1).sum

// コスト
val scorelist = for ((str, i) <- slist.zipWithIndex) yield { (i+1) * str2value(str) }
println(scorelist.sum)
}
[/scala]それよりも大きい数を扱うような問題を全部ScalaのBigIntに逃げてるのがもう少し工夫した方がいい気がしてきた.

Scala

[scala][advent]Scalaは機械学習に使えるかな? #scalaadvent2011

これはScala Advent Calendar jp 2011の20日目の記事です.今日は12月20日,企画も終盤.ここではScalaと機械学習について書きます.機械学習をあまり知らない人たちのために,そちらの解説も入れておきました.

機械学習について簡単に

詳しい説明は朱鷺の杜に譲るとして,簡単に言うと,私たち人が普通に行なっている「学習」というものを情報屋さん的に扱った学問領域のことです.「情報の中から,有益そうな知識を獲得していく過程」をコンピュータで実現させることを目指してます.実際には,数値・文字・画像・音声などのデータの中から,規則性とか知識とかを発見して役に立てよう〜としています.

こういう領域でデータを扱うには,データをベクトルにして行列とか使ってどうたら…ってやるわけです.なぜかというと,数値はもちろん,画像とか音声というのは全部コンピュータの中ではベクトルで書けてしまうからです.ですので機械学習の処理をどうにかしようと思うと,線形代数のライブラリがあれば,最悪なんとかなるということになります.ですがこの記事ではScalaにおける線形代数のライブラリについては全然調べませんでした,ごめんなさい.この記事の最後に少しだけ補足しました.

個人的にScala+機械学習に期待したいこと

機械学習の話でこっちのデータ使って学習(ここの学習はプログラムを調整する,ぐらいの意味です)して,こっちのデータ使ってテストしてみようってことをやります.このとき,ある集合S=\{data_1,data_2,\dots\}に対して1つずつ○○をして…って計算したり,処理したりするので,こういう処理って地味にfilter/foldLeft/Mapあたりと相性がいいと僕は勝手に思っています.またある集合Sを分割して処理するので,並列処理なんかも相性がいい場合が多いです.

6日目の id: j5ik2o さんのパラレルコレクションの性能測定 – じゅんいち☆かとうの技術日誌 のように,新しめのScalaではパラレルコレクションが使えるってこともありますし,Actorなどもありますので,純粋に最近良く使われているPython+numpy/scipy+matplotlib+scikits.learnみたいなセットよりも高速な処理系が書けるのでは,と期待してます.

またPythonと比べると,型の情報が使えるのは大きいですね.計算の途中でこの途中式はベクトルだから…とか行列だから…とかちゃんと分かりますし(笑)

使ってる環境,ライブラリなど一覧

深い線形代数の知識を使わずに,機械学習で遊ぶにはJavaさんの力を借りるのがいいですね(偏見).Java界隈にはWekaという機械学習/データマイニングの機能をたくさーん実装してまとめてライブラリにしちゃったよ(´∀`)ってライブラリ(本当はGUIツールですが…)があります.せっかくなのでそれを借りてきましょう.

Weka 3 – Data Mining with Open Source Machine Learning Software in Java
Wekaの日本語情報@weka-jp.info

公式サイトからweka-3.6.6.zipをダウンロードしてきて,中に入ってるはずのweka.jarを作業ディレクトリのlibとかに置いておきます.sbtで管理出来るならどこでもいいです.僕はこんな感じでやってます.zipを解凍したらdataってディレクトリもあるので,一緒にコピーしておきます.遊ぶため.

~/ (作業ディレクトリのルート) 
 ├ target - sbtに管理してもらう
 ├ lib - weka.jar
 ├ data - wekaのdataファイル(.arff)を置いた
 └ Main.scala - 今回遊んでたソースファイル(笑)

遊んでみたこと

weka.jarとweka用のデータファイルである.arffファイルの詰め合わせ,dataディレクトリをコピーしてきたので,普通にJavaからwekaを使うように遊べるはずです.実際に遊んでみます.

import weka.associations._
import weka.core._
import java.io._

object Main extends App{

  override def main(args: Array[String]){

    // Arffファイルを読んで扱える形にする                                                                                
    val reader = new FileReader("data/supermarket.arff")
    val instances = new Instances(reader)

    // 相関ルール発見の初期設定                                                                                          
    val apriori = new Apriori()
    apriori.setDelta(0.1)
    apriori.setNumRules(20)

    // 発見                                                                                                              
    apriori.buildAssociations(instances)
    println(apriori)
  }
}

出力結果
Best rules found:

 1. biscuits=t frozen foods=t party snack foods=t fruit=t vegetables=t total=high 510 ==> bread and cake=t 478    conf:(0.94)
 2. biscuits=t frozen foods=t cheese=t fruit=t total=high 495 ==> bread and cake=t 463    conf:(0.94)
 3. biscuits=t cheese=t fruit=t vegetables=t total=high 513 ==> bread and cake=t 479    conf:(0.93)
 4. baking needs=t biscuits=t party snack foods=t fruit=t total=high 557 ==> bread and cake=t 520    conf:(0.93)
 5. baking needs=t cheese=t fruit=t vegetables=t total=high 519 ==> bread and cake=t 483    conf:(0.93)

もっとたくさん出力されます.上のソースで試しているのは相関ルール分析というデータマイニングの手法です.そんなに難しい手法でもないのでネット上の解説記事を読めばよく分かるのですが,購買履歴が収まったテーブルが与えられたとき,どんな商品の組がよく買われているとか,どんな購買の癖が現れるかを発見する手法です.

例えば上の出力結果の1番を見てみると「ビスケットとフローズンフード(って何だ?)と,パーティースナック菓子とフルーツと野菜を買ってトータルがhigh(なんだこれ)なとき(条件),パンとケーキも買う(矢印の右側)」っていう謎のルールになっていて(これを相関ルールと呼ぶ),その信頼度は0.94ぐらいだよ〜と言ってます.

もう少し詳しい説明はここにありました.
アソシエーション分析 - @IT情報マネジメント用語事典

もう少しだけ

さすがにこれだけだとタイトルに対して釣りになっているような気がしてきたので,もう少しだけ書こうと思います.上ではJavaのライブラリWekaを使っています.せっかくなのでJavaのライブラリ的な話をもう少し,あとScalaオンリーの話も少しだけやります.

まずJavaの話ですが,Wekaは速度はよく知らないですが,GUIとしてもギリギリ普通に使える設計になっていると僕は思っています.なんだかんだで機械学習のある程度確立されているようなアルゴリズムはたぶん全部実装されています.ですので,ちょっと機械学習の手法を使いたいという場面で問題になることはあんまりないのでは…と思ってます(だからあまりScalaネイティブを真面目に調べなかった).また同じくJava関係ではMahoutと呼ばれるパッケージ(パッケージ群?)があります.このあたりもScalaから使えると過ごそうだな…と.おそらく使えます.いやぁ,Scalaは幸せだなぁ.コードが書きやすいし短めだしライブラリも豊かだなぁ(この際,ネイティブかどうかは捨てる)

Apache Mahout: Scalable machine learning and data mining
Apache Mahout の紹介
機械学習/MacでMahoutを使う – とうごろうぃき

Scalaオンリーだと,一応Scalaで書かれている機械学習ライブラリがあります.あまり多くのアルゴリズムは準備されていないようですが….今回は試していないのであまりわかりません.内部ではscalalaという線形代数ライブラリを使ってます.
scala-recog – A machine learning library in Scala – Google Project Hosting

そういえばPythonには集合知プログラミングという悪名高い本(機械学習関係)があるのですが,それをScalaで書いちゃう〜ってのをやっている方も見つけました.こう見るとScalaも全然イケますね!(お前は何を言っているんだ)
Scalaで集合知プログラミング まとめ – Reinvention of the Wheel

集合知プログラミング
Toby Segaran
オライリージャパン
売り上げランキング: 97234

おわりに

本当はもう少し準備して書くつもりもあったのですが,直前に体調を崩してしまったので残念な感じになりました.もう少しScalaネイティブの環境が整ってきてもいいかなぁーというか,あると思ったのですが,いざ調べてみるとあまり見当たらなかったですね.残念…(´・ω・`)

機械学習について知ってみたい方は,以前僕が書いた記事もあります.(宣伝)
[まとめ] 機械学習/データマイニングに興味がある人が読むといいかも?な本をまとめた

なんだかんだで長文になりましたね.申し訳ないです.

オマケ: Scalaで線形代数ライブラリ?

真面目に線形代数を使っていろんなことがやりたい場合は,真面目にライブラリを探すか,Javaの数値計算用ライブラリを借りてくることになると思います.Scalaの話を言うと,一応scalalaというライブラリはありました.tensorが実装されているようなので,注目ですね.

scalala – Scala Linear Algebra library – Google Project Hosting
scalala/Scalala – GitHub

要注目と思います.一応Python系よりも高速になる可能性があると僕は思っているので,注目したいです.ベンチマークとかもすればよかったかしらね.Tensorの処理系が用意されているのは珍しいと思いました.実際にgit cloneしてきて使ってみると,僕の手元のscala 2.9.1+sbt 0.11ですごく長い時間コンパイルしてJavaのheap errorが出ました.設定が悪いな….

本当におしまい.せっかくWekaのことを書いたので,今年中に決定木アルゴリズムについて書きます.Scala版.たぶん.今日書けなかったのは大人の事情です.ごめんなさい.

決定木 – Wikipedia