Hatena::ブログ(Diary)

総合的な学習のお時間 RSSフィード

2013-12-15

[]Scalaアプリケーションを配布する 08:00 Scalaアプリケーションを配布するを含むブックマーク

Scalaのコードをコンパイルすると.classファイルができるが、これをjavaコマンドで実行するとNoClassDefFoundErrorになる。


$ cat Test.scala
object Test {
  def main(args: Array[String]){
    println("Hello, World!")
  }
}
$ fsc Test.scala
$ java Test
Exception in thread "main" java.lang.NoClassDefFoundError: scala/Predef$
	at Test$.main(Test.scala:3)
	at Test.main(Test.scala)
Caused by: java.lang.ClassNotFoundException: scala.Predef$
	at java.net.URLClassLoader$1.run(URLClassLoader.java:366)
	at java.net.URLClassLoader$1.run(URLClassLoader.java:355)
	at java.security.AccessController.doPrivileged(Native Method)
	at java.net.URLClassLoader.findClass(URLClassLoader.java:354)
	at java.lang.ClassLoader.loadClass(ClassLoader.java:424)
	at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:308)
	at java.lang.ClassLoader.loadClass(ClassLoader.java:357)
	... 2 more
$ 

実行にはscala-library.jar(その他 scala-swing.jar などのライブラリも必要に応じて)が必要。


自分の環境ではScalaはhomebrewでインストールしているので、これらのjarは /usr/local/Cellar/scala/2.10.3/libexec/lib/ にあった。


$ SCALALIB=/usr/local/Cellar/scala/2.10.3/libexec/lib 
$ ls $SCALALIB
akka-actors.jar			scala-actors.jar		scala-reflect.jar
diffutils.jar			scala-compiler.jar		scala-swing.jar
jline.jar			scala-library.jar		scalap.jar
scala-actors-migration.jar	scala-partest.jar		typesafe-config.jar
$ java -classpath .:$SCALALIB/scala-library.jar Test
Hello, World!
$ 

Scalaで作ったアプリケーションを他の人に渡すときは、scala-library.jarを同梱して、クラスパスを設定して起動するスクリプトを付けることになるだろう。


scala-library.jarの配布ライセンスは、Scala Licenseを付けておけば良い?

http://www.scala-lang.org/old/node/401 (2008年の情報)

トラックバック - http://d.hatena.ne.jp/tomerun/20131215

2013-09-22

[] Java7にキャッチアップ 01:21  Java7にキャッチアップを含むブックマーク

TopCoderやAtCoderでもJava7が使えるようになったことだし、止まっている知識をアップデートする。

Java7の新機能について、気になるものをこのあたりから拾ってきて試した。

http://www.oracle.com/technetwork/java/javase/jdk7-relnotes-418459.html


Binary Literals

2進数リテラル。先頭に0b(または0B)を付ける。

    int one  = 0b00000001;
    int two  = 0b00000010;
    int four = 0b00000100;
    int FF   = 0b11111111;
    System.out.println(Integer.toBinaryString(FF ^ (one | two | four)));

出力

11111000

Underscores in Numeric Literals

数値リテラルの中にアンダースコアを含ませることができる。

    System.out.println(123_456_789);
    System.out.println(3.141_592_653_589_793);

Strings in switch Statements

switch文でStringが使えるようになった。

    switch (args[0]) {
    case "-n":
      int n = Integer.parseInt(args[1]);
      break;
    case "-h":
      System.out.println("usage: hogehoge");
      break;
    case "-v":
      System.out.println("version 3.14");
      break;
    default:
      break;
    }

if-then-elseより速いらしい


try-with-resources, AutoCloseable

try-catch-finallyを使わずにリソース自動解放

    try (Scanner sc = new Scanner(System.in)) {
      System.out.println(sc.nextInt());
    }

tryの中にはAutoCloseableインターフェースを実装したクラスを指定する。


Type Inference for Generic Instance Creation

ジェネリックなクラスの初期化でコンストラクタに型パラメータを指定しなくて良くなる

    ArrayList<Integer> list = new ArrayList<>();
    HashMap<String, Integer> map = new HashMap<>();

java.nio.fileパッケージ

http://docs.oracle.com/javase/7/docs/api/java/nio/file/package-summary.html

FilesクラスとかPathクラスとか、ファイル操作まわりに便利なライブラリが追加されている。

    FileSystem fileSystem = FileSystems.getDefault();
    Path src = fileSystem.getPath("./tmp.txt");
    Path dst = fileSystem.getPath("./copyTo.txt");
    try {
      Files.copy(src, dst);
      Files.delete(src);
      for (String line : Files.readAllLines(dst, Charset.forName("UTF-8"))) {
        System.out.println(line);
      }
    } catch (IOException e) {
      System.err.println(e);
    }

Objectsクラス

http://docs.oracle.com/javase/7/docs/api/java/util/Objects.html

小物関数群。

    int hash = Objects.hash("string", 42, 3.14);
    String str = "hoge";
    String nullStr = null;
    Objects.equals(str, nullStr);
    System.out.println(Objects.toString(nullStr, "this object is NULL!!!!"));

BitSet

http://docs.oracle.com/javase/7/docs/api/java/util/BitSet.html

微妙にメソッドが追加されていた。

    BitSet bitset = BitSet.valueOf(new long[] { 0xFFFF_FFFF_FFFF_FFFFL, 0x1234_5678_9ABC_DEF0L });
    for (int i = bitset.previousSetBit(bitset.size()); i >= 0; i = bitset.previousSetBit(i - 1)) {
      System.out.println(i);
    }
    byte[] bytes = bitset.toByteArray();

Integer#compare

http://docs.oracle.com/javase/7/docs/api/java/lang/Integer.html#compare%28int,%20int%29

自分で比較コードを書かなくて良くなった。

Longなどでも同じ。Doubleには前からあった

    Integer.compare(0, 0);
    Long.compare(Long.MAX_VALUE, Long.MIN_VALUE);
トラックバック - http://d.hatena.ne.jp/tomerun/20130922

2012-12-22

[]文字コードの自動判別を機械学習23:54 文字コードの自動判別を機械学習でを含むブックマーク


これはMachine Learning Advent Calendar2012の22日目の記事です。


まえがき


「アルゴリズム使って実世界の問題を解決できるの面白いナー」とPRML読んだりしているのですが、

研究や仕事で機械学習を使っているわけでもなく、自分の中では純粋に趣味・老後の楽しみ的な位置づけになっています。

しかしせっかく勉強しているのだから何かに使おうと、「有名データを利用するのも面白くないし、良いネタはないか」

と探していたら、以前こんなことを言っていたのを思い出しました。


文字コードの自動判別を機械学習使ってやる、って誰かがやってそうだけど検索しても出てこない

https://twitter.com/tomerun/status/9729721761

というわけで試しにやってみます。

この記事の中で使ったコードはここに置いています。 https://github.com/tomerun/MachineLearning

コメントなどあまり付いてないけどご勘弁を


※エンコーディングなんて規則は全部分かってるのだから、精度に関しては機械学習とか持ち出さずともヒューリスティックに判定する方が良いに決まってます。

この記事は、機械学習の手法を使ってみた例でしかないことに注意。


データの準備


データには、「日本語バランス文」の上位1000個を使います。


ダウンロードしてきたデータについて、次の前処理をやります。

  • 形態素がスペースで区切られているので、スペースを全て除去
  • 元はWikipediaから取られた文なので、脚注を表す「^ 」が先頭に付いているものがある。これを取り除く
  • 2箇所、nbspが紛れ込んでいるので除去
  • 1箇所、Shift_JISやEUC-JPにマッピングできない文字であるホリゾンタルバー(U+2015)があるので半角ハイフンに置き換え
  • 深圳」の「圳」がShift_JISにマッピングできないのでカタカナに置き換え
  • 英数や記号が全て全角になっているので、文ごとに1/2の確率で半角に変換

続いて、1000個の文をそれぞれ、UTF-8、UTF-16LE、Shift_JIS、EUC-JPの4通りのバイト列に変換します。

ランダムに500文を選んで、500文*4エンコーディングの2000個のバイト列を訓練データ、残りの2000個のバイト列をテストデータとします。


各バイト列を、0〜255の値がそのバイト列中にどのくらいの割合で出現するかを要素とする256次元ベクトルとします。

ベクトルの要素の値が小数だといろいろ面倒なので、割合の値を10倍した整数(小数点以下切り上げ)で扱います。

たとえば、あるバイト列が {1,2,1,3} だった場合、出現割合は1が0.5、2と3が0.25なので、ベクトルは {0, 5, 3, 3, 0, ... } になります。


データの様子


それぞれのエンコーディングについて、バイトごとの値の分布がどのようになっているかのHeat mapを描きました。


f:id:tomerun:20121222205133p:image


f:id:tomerun:20121222205134p:image


f:id:tomerun:20121222205132p:image


f:id:tomerun:20121222205131p:image


確かに傾向が出てますね。

バイトの値の割合を特徴量にするだけで分類できそうだと期待できます。


分類


ナイーブベイズ

以前実装していたナイーブベイズに入れてみます。

ゼロ頻度問題を避けるためのpseudocountは、適当に0.1で(パラメタいろいろ変えてみても結果にはっきりした変化はなかった)。


コード抜粋

NaiveBayesClassifier<Sentence> naiveBayes = new NaiveBayesClassifier<Sentence>(0.1);
naiveBayes.train(Arrays.asList(trainingSet));
int correct = 0;
for (Sentence testData : testSet) {
	int expect = testData.label();
	int actual = naiveBayes.classify(testData);
	if (expect == actual) {
		++correct;
	}
}
System.out.println("correct:" + correct);
System.out.println("wrong:" + (testSet.length - correct));

乱数を変えて5回実行するとこうなりました。


$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1977
wrong:23
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1972
wrong:28
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1984
wrong:16
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1976
wrong:24
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1984
wrong:16

平均正解率98.93%でした。


Random Forest

次はRandom Forestに入れてみます。

実装は以前独自にやっていたものです(なのでたぶんけっこう遅い)。


// RandomForest(決定木の数, 1つの決定木で使う特徴量の数, 1つの決定木の分岐数)
RandomForest<Sentence> randomForest = new RandomForest<Sentence>(500, 6, 300);
randomForest.train(Arrays.asList(trainingSet));
int correct = 0;
for (Sentence testData : testSet) {
	int expect = testData.label();
	int actual = randomForest.classify(testData);
	if (expect == actual) {
		++correct;
	}
}
System.out.println("correct:" + correct);
System.out.println("wrong:" + (testSet.length - correct));

これも5回実行するとこうなりました。


$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1980
wrong:20
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1990
wrong:10
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1989
wrong:11
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1993
wrong:7
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1984
wrong:16

平均正解率99.36%。はっきりとNaiveBayesよりも良い結果が出ています。

ただし、パラメタはいろいろ試行錯誤して一番良くなるように決めたものです。

  • 決定木の数は一定以上増やしても計算時間がかかるばかりで結果は良くならない
  • 1つの決定木で使う素性数を増やしすぎるとかえって悪くなる
  • 分岐数は、Wikipediaなどでは識別問題の場合は1が推奨と書かれているけど、この問題については大幅に増やした方が断然良かった

(参考)nkf

比較対象として、nkfに推定させてみました。

どうもnkfでUTF-16が判定できないみたいなので、1000文*3エンコーディングの3000個のテストデータについて試しています。


$ ls UTF-8/*.dat | xargs nkf -g | grep -E "UTF-8$" | wc -l
     997
$ ls EUC-JP/*.dat | xargs nkf -g | grep -E "EUC-JP$" | wc -l
     997
$ ls Shift_JIS/*.dat | xargs nkf -g | grep -E "Shift_JIS$" | wc -l
     997

正解率99.7%でした。

テストデータの中には5文字くらいの極端に短い文も含まれているので、さすがにこのくらいが限界だと思います。


おわりに


けして高度な手法を使っているわけではないものの、それなりに満足のいく精度が出ました。

テストデータは平均40文字くらいとそう長くない文章だったのでどうだろうと思っていたのですが、エンコーディングごとのパターンがはっきりしているため良く分類できているのでしょう。


元データは人手によって一度整理されているものではあるけれども、現実世界のデータを扱うにはやはり前処理でいろいろとやらないといけないことが出てきますね。なかなか面倒


今回は単純にバイト値の出現頻度だけを使いました(これ、bag of featuresと呼ぶのかな??)が、エンコーディングについての一般的知識から、バイトの順序に意味があるはずなので、隣り合う値の組(byte 2-gram)を考慮に入れるようにすると精度上がるかもしれません。

ただしそれをやるなら、たぶん計算量がすごく大きくなるのでなにか工夫しないといけないと思いますが。


宣伝


Competitive Programming Advent CalendarでKaggleの紹介を書きました。こちらもよろしく

http://topcoder.g.hatena.ne.jp/tomerun/20121221/1356017174

トラックバック - http://d.hatena.ne.jp/tomerun/20121222