2012-12-14

AROW を Ruby で実装してみた

Machine Learning Advent Calendar 2012 の 14 日目の記事になります。気まぐれでこのカレンダー登録してみたものの、この日に至るまでの数々の記事のガチな高レベルさに登録してしまったことをかなり後悔している @komiya_atsushi です。

この記事では、オンライン学習アルゴリズムの AROW を Ruby で実装した (& gem として公開した) という、どこにでもよくある話を書いています。主に機械学習に馴染みのない or 取り組み始めたばかりの(自分を含めた)エンジニア向けの記事となっています。

AROW とオンライン学習

まずはじめに、この記事で取り上げている AROW とその前提となる知識について軽く説明していきます。

AROW (Adaptive Regularization of Weight Vectors) というのは、「オンライン学習」ができる「教師あり」の「クラス分類(二値分類)」アルゴリズムです。ではこの AROW を使って何ができるのか? というと、例えば「海賊船からかっぱらってきた金貨のようなものを、事前に明らかになっている数十枚のコインの真贋の情報をもとに、その体積と重さから真贋を見分ける」ことができるようになります。

AROW は 2009 年に提案されたアルゴリズムであるものの、後からよりよい手法が幾つか提案されているので state of the art な手法ではないですが、言い換えれば安定して使える「枯れた技術」として使うには十分ではないでしょうか。

オンライン学習

「オンライン学習」については、今回の Advent Calendar でも記事を書かれている kisa12012 さんの オンライン学習による線形識別器 などがありますので、詳しく知りたい方はこちらをご参照いただくのがいいかと思います。ここではざっくりな概要の説明に留めるとして、クラス分類での説明を簡単(雑?)にすると「次々と与えられるデータの『特徴』とそのデータに対するクラスを示す『ラベル』(Yes / No みたいなもの)をもとに、それらをラベルに従って分類してくれるモデルを作る・更新する(=学習する)」となるでしょう。

オンライン学習の特徴としては、以下に示すものがあります。

  • 大量のデータをもとにモデルを作る必要があっても、全データを同時にすべて取り扱う必要がない(主記憶装置にやさしい)。
  • モデルの更新に利用したデータを不要となれば破棄することもできる(二次記憶装置にやさしい)。
  • 1回1回のモデルの更新にかかる計算量が小さい(演算装置にやさしい)。

教師あり学習

次に「教師あり学習」について。教師あり学習というのは「正解の状態が明らかになっているデータ(訓練データ)をもとにモデルを作成する」学習になります。具体例でいうと今回取り上げている「クラス分類」がそれにあたります。対する用語として「教師なし学習」がありますが、こちらは「クラスタリング」などが例に挙げられます。

クラス分類

最後は「クラス分類」について。これは「データの『特徴』とそのデータに対するクラスを示す『ラベル』(Yes / No みたいなもの)をもとに、それらをラベルに従って分類してくれるモデルを作る・更新する。またラベルが未知のデータを予測して分類してくれる」お仕事と表現できるかと思います。

AROW の論文を読んでみる

続いて、AROW のアルゴリズムを実装する観点で、AROW の 論文 を読んでいきましょう。…とは言え、私自身、数式がそれなりにふんだんに使われた論文をすらすらと読めるほど数学リテラシーが高いわけではないので、重要な部分だけをピックアップして軽く説明します。

AROW を実装するに当たって一番重要なのは、p.4 のページ上にある Fig.1 です。(下図参照)

ここにある式を頑張って実装すればいいわけです。Σ が summation としてではなく共分散行列を表す変数として使われていることと、ベクトル x が列ベクトルであることに注意をすれば比較的容易に数式を読み解けると思います。

実際にこのコア部分を Ruby で実装すると、高々 50 行弱のコードになります。とってもシンプルですね! 1

なお既存の他言語での実装を見てみると、Σ の更新式が、論文中の (9) 式ではなく、(8) 式をもとにした実装がほとんどになっているようです。tsubosaka 先生の Java 実装 や C++ 実装の AROWPP などなど。なぜみんな (8) 式を利用しているのか理由が分からなかったのと、(9) 式の方がより効率よく計算できて精度も向上するようなので、今回は (9) 式での実装をしました。 2

gem 'arow'

今回は上記実装をもとに gem 化したものを RubyGems.org で公開 しています。ソースコードは github.com/komiya-atsushi/arow にて公開しています。突貫工事的に gem 化したので、テストケースはないしマニュアルはないし README からして適当と粗が目立ちますが、カジュアルに使えるクラス分類器を自分自身が欲していたので、(お仕事が落ち着いたら)もうちょっと使いやすくできるようにメンテナンスをしていく予定です。

利用例がないのもアレなので、先に挙げた Code IQ の問題に対する適用例を示します… としたかったのですが、12/14 現在、まだ挑戦者受付中とのことらしいので念の為にしばらくはコード公開を控えておきます。また後日で。 3

2012.12.21 追記:公開しました。

おわりに・感想

久々に数式たっぷりな論文を読んで、改めて己の数学力の低さを悔やみました。数学力を鍛え直したい…

この Machine Learning Advent Calendar の企画を開催してくださいました @naoya_t さん、ありがとうございました!


1 : 今回の実装では、μ (@means) と Σ (@covariances) は時間・空間計算量を減らすために行列の対角要素をとったもので表現しています。既存の各種実装をみても、いずれもこの対角要素を利用する方式をとっているようです。
2 : 理由を御存知の方がいらしたら是非、教えていただけると幸いです。
3 : Advent Calendar に登録した当初は 12/14 時点で受付終了している予定でしたが、終了が延長されてしまったため、このタイミングでは公開できず、と。ぐぬぬ…
10:13No comments

2012-11-29

Play framework (1.2.5) のアプリで Twitter4J を利用する

難しい手順ではないのだけれど、ちょっとはまったことがあったので未来の自分のためにメモを残しておきます。

手順

  1. $ play new で Play framework のアプリを作成する
  2. ./conf/dependencies.yml に Twitter4J を利用する旨を記述する
  3. $ play dependencies で依存ライブラリを ./lib に配置する
  4. $ play eclipsify で Eclipse 上で開発可能な状態にする
  5. javaee-api-5.0-x.jar をビルドパスから取り除く

「2. ./conf/dependencies.yml に Twitter4J を利用する旨を記述する」について

以下のように、Twitter4J に対する依存を記述すれば OK。Twitter4J の jar ファイルをダウンロードして特定ディレクトリに配置… みたいなことをする必要はありません。

# Application dependencies

require:
    - play
    - org.twitter4j -> twitter4j-core [3.0,)

「5. javaee-api-5.0-x.jar をビルドパスから取り除く」について

これをし忘れてちょっとはまりました。

Twitter4J を dependencies.yml に記述して $ play dependencies を実行すると、twitter4j-code-3.0.x.jar とともに javaee-api-5.0-x.jar というファイルも ./lib のディレクトリに配置されることになります。この jar ファイルをビルドパスに含めたまま Play アプリを起動してページアクセスすると、以下のエラーが発生することがあります。

play.exceptions.UnexpectedException: Unexpected Error
 at play.Invoker$Invocation.onException(Invoker.java:244)
 at play.Invoker$Invocation.run(Invoker.java:286)
 at Invocation.HTTP Request(Play!)
Caused by: java.lang.NoSuchMethodError: javax.persistence.EntityManager.setProperty(Ljava/lang/String;Ljava/lang/Object;)V
 at play.db.jpa.JPAPlugin.startTx(JPAPlugin.java:375)
 at play.db.jpa.JPAPlugin.beforeInvocation(JPAPlugin.java:345)
 at play.plugins.PluginCollection.beforeInvocation(PluginCollection.java:473)
 at play.Invoker$Invocation.before(Invoker.java:217)
 at play.Invoker$Invocation.run(Invoker.java:277)
 ... 1 more

どうやら javaee-api-5.0-x.jar に含まれる javax.persistence.EntityManager クラスの定義が Play が参照しているそれとかち合ってしまうようなので、思い切って javaee の方をビルドパスから除去してあげることで解消できます。

14:56No comments

2012-11-17

UTF-8 エンコードされた絵文字を MySQL / JDBC で取り扱うには?

2013.06.08 追記:JDBC 接続文字列で characterEncoding / connectionCollation を指定すると思った通りの挙動をしてくれないようなので、別の方法 (多分これが正しい方法) を記載しました。

Unicode における、こんな 感じの絵文字、いわゆる Unicode の 追加面 の文字、Java で言えばサロゲートペアでの表現が必要となる文字を、JDBC 経由で UTF-8 エンコーディングして MySQL のテーブル・カラムに格納しようとすると、以下の例外が発生することがあります。

Caused by: java.sql.SQLException: Incorrect string value: '\xF0\x9F\x98\x81 h...' for column 'col_name' at row 1
    at com.mysql.jdbc.SQLError.createSQLException(SQLError.java:1074)
    at com.mysql.jdbc.MysqlIO.checkErrorPacket(MysqlIO.java:4096)
    at com.mysql.jdbc.MysqlIO.checkErrorPacket(MysqlIO.java:4028)
    at com.mysql.jdbc.MysqlIO.sendCommand(MysqlIO.java:2490)
    at com.mysql.jdbc.MysqlIO.sqlQueryDirect(MysqlIO.java:2651)
    at com.mysql.jdbc.ConnectionImpl.execSQL(ConnectionImpl.java:2734)
    at com.mysql.jdbc.PreparedStatement.executeInternal(PreparedStatement.java:2155)
    at com.mysql.jdbc.PreparedStatement.executeUpdate(PreparedStatement.java:2458)
    at com.mysql.jdbc.PreparedStatement.executeUpdate(PreparedStatement.java:2375)
    at com.mysql.jdbc.PreparedStatement.executeUpdate(PreparedStatement.java:2359)

Twitter API 叩いて得たツイートを MySQL に入れて蓄積したい、みたいなことをしようとして、毎回このスタックトレースと格闘しているので、対応方法を忘れないようにメモしておきます。

確認した環境は以下のとおり。

  • MySQL 5.5.25a
  • MySQL Connector/J 5.1.22
  • Java 1.7.0_07-b10

すべきこと

  • 強く推奨される対処方法
    1. my.cnf (Windows の場合は my.ini) の [mysqld] セクションで character-set-server に utf8mb4 を設定する
    2. 既存のデータベース / テーブル / カラムの CHARSET を確認する
  • いかんともし難い理由により my.cnf を変更できない場合の代替手段
    1. データベース / テーブルの CHARSET に utf8mb4 を指定する
    2. Java のプログラムから具体的な SQL を発行する前に SET NAMES utf8mb4 を発行する

ざっくりとまとめると上記のとおり、2 つの手段があります。以下でそれぞれ説明します。

強く推奨される対処方法

my.cnf (my.ini) を変更することができるならば、こちらの手段での対処を強くおすすめします。こちらの方法であれば、Java プログラム側は特別な対処をする必要がありません (JDBC 接続文字列での characterEncoding や connectionCollation の設定も不要です)。

1. my.cnf の [mysqld] セクションで character-set-server に utf8mb4 を設定する

以下のように、character-set-server の値を utf8mb4 に書き換えるだけです。

(略)

# SERVER SECTION
# ----------------------------------------------------------------------
#
# The following options will be read by the MySQL Server. Make sure that
# you have installed the server correctly (see above) so it reads this 
# file.
#
# server_type=3
[mysqld]

(略)

# The default character set that will be used when a new schema or table is
# created and no character set is defined
character-set-server=utf8mb4  # ← ここを utf8mb4 にする

2. 既存のテーブル / カラムの CHARSET を確認す

続いて、すでに存在するテーブルやカラムの CHARSET を以下のクエリで、テーブルごとに確認します。

SHOW CREATE TABLE テーブル名

このクエリを実行した結果、たとえば、

CREATE TABLE `tbl_name` (
  `col_name` varchar(8) CHARACTER SET utf8 DEFAULT NULL
) ENGINE=InnoDB DEFAUTL CHARSET=utf8bm4;

このような結果が得られた場合は、tbl_name CHARSET は utf8mb4 だけれども、col_name は utf8 であることが分かります。このテーブルのカラムをすべて utf8mb4 の CHARSET にしたい場合は、

ALTER TABLE tbl_name CONVERT TO CHARACTER SET utf8mb4;

というクエリを発行します。この確認 (と CHARSET 変更) を、追加面の文字が格納される可能性のあるすべてのテーブルに対して実施します (確認が面倒どうであれば、すべてのテーブルに対して無差別に ALTER TABLE ~ してしまってもいいかもしれませんね)。

いかんともし難い理由により my.cnf を変更できない場合の代替手段

こちらは my.cnf を変更出来ない場合の対処方法です。理由は後述しますが、こちらの対応方法はあまりおすすめできません。

1. データベース / テーブルの CHARSET に utf8mb4 を指定する

この対応方法はまず、データベース or テーブルで文字列を取り扱う際の CHARSET に utf8mb4 を指定することから始まります。

データベース全体の CHARSET を設定するのであれば、CREATE DATABASE でデータベースを作成する際に以下のように指定するとよいでしょう。

CREATE DATABASE
    db_name
  DEFAULT CHARSET
    utf8mb4;

また、テーブルを作成するときに、テーブル単位 or カラム単位で CHARSET を指定することもできます。追加面の文字が入るテーブル / カラムのみ変更したい場合は、こちらの指定がよいでしょう。

/* テーブル単位で指定する場合 */
CREATE TABLE tbl_name (
  col_name VARCHAR(100)
) ENGINE 
    InnoDB
  CHARSET
    utf8mb4;

/* カラム単位で指定する場合 */
CREATE TABLE tbl_name (
  col_name VARCHAR(100) CHARSET utf8mb4
);

2. Java のプログラムから具体的な SQL を発行する前に SET NAMES utf8mb4 を発行する

続いて Java プログラム側の話になります。

INSERT / UPDATE などの具体的な SQL を発行する前に、「コネクション単位で」SET NAMES utf8mb4 のクエリを発行するようにします。つまり以下のプログラムのように、java.sql.Connection オブジェクトを取得した直後に java.sql.PreparedStatement オブジェクトなどを利用して SET NAMES utf8mb4 を発行するようにします。

try (Connection conn = 
         DriverManager.getConnection("jdbc:mysql://localhost/dbname?user=u&password=p")) {
    try (PreparedStatement pstmt = conn.prepareStatement("SET NAMES utf8mb4");
         ResultSet rset = pstmt.executeQuery()) {
    }

    // この後に具体的な SQL を発行する...
}

SET NAMES utf8mb4 の発行結果はコネクションをまたいで引き継がれるわけではないので、コネクションを取得し直す度に毎回 発行し直す必要があります (逆を言えば、同一のコネクション内であれば、再発行する必要はありません)。

この対応方法がおすすめ出来ない理由

MySQL Connector/J のマニュアル 22.3.5.4. Using Character Sets and Unicode を読み進めて見ると分かりますが、

上記のキャプチャのように、「SET NAMES を JDBC のコネクション上で発行すること自体すべきでない」と明記されています。 加えて O/R マッパーを利用する場合、java.sql.Connection オブジェクトの管理が O/R マッパー任せとなるので、いつ SET NAMES utf8mb4 を発行すればよいか、そのタイミングを図るのが非常に難しくなります。

特別な理由がない限りは、my.cnf の設定を変更する方法を利用し、「どうしても my.cnf は触れない/触りたくないんだ…!」というときのみ、こちらの利用をするとよいかと思います。

2013.06.08 削除:以下の対処は不要で、文字数分の大きさの VARCHAR カラムをすれば十分でした。

2. Unicode 追加面 が格納される可能性のある VARCHAR のカラムを、文字数の4倍に設定する

Unicode 追加面の文字を VARCHAR のカラムに格納すると、同文字1文字あたり VARCHAR 4 文字分を消費するようです。そのため、例えば 100 文字格納できるカラムが合った場合に、すべての文字が Unicode 追加面の文字である 100 文字の文字列を格納することを想定して、VARCHAR のカラムの文字数を 400 に設定する必要があります。

つまり、

CREATE TABLE tbl_name (
  col_name VARCHAR(100)
)
のようなテーブルがあったとして、col_name のカラムに実際に 100 文字格納したいんだけど、Unicode 追加面の文字が混じる可能性があるのであれば、
CREATE TABLE tbl_name (
  col_name VARCHAR(400)
)
のようにしましょう、ということです。

2013.06.08 削除:この対処も不要で、特に接続文字列に何かを付け加える必要はありません。

3. JDBC の接続文字列で characterEncoding / connectionCollation を指定する

MySQL のサーバ側の設定などは上記までで、残すは JDBC 周りとなります。JDBC 周りの設定に手を入れない限りは、最初に示したスタックトレースとおさらばすることはできません。

JDBC 周りの設定内容は以下のとおりです。

  • characterEncoding ... UTF-8
  • connectionCollation ... utf8mb4_general_ci

JDBC の接続文字列での指定例は以下になります

jdbc:mysql://host:3306/db_name?characterEncoding=UTF-8&connectionCollation=utf8mb4_general_ci

以上。

15:271 comment

2012-09-30

第3回 データ構造と情報検索と言語処理勉強会 #DSIRNLP でトークしてきました

2012/9/30(日)に開催された 第3回 データ構造と情報検索と言語処理勉強会 DSIRNLP で、最近(個人的に)注目の圧縮ライブラリ、LZ4 に関してトークしてきました。

LT という時間枠でしたので、テーマを絞って LZ4 の速さの秘密について話しましたが、秘密が盛りだくさんで話し切れず。時間をオーバーしてご迷惑をおかけしてしまいました。すみません…

発表資料は以下になります。

私の発表はアレですが、LZ4 を知らない方が結構多い集まりでしたので、今回の発表を機に、もっと利用が広まるといいなあと思っています。

以下、個人的な反省点です。

  • LT で 90 ページ超とか無理があり過ぎるのでやめよう。
  • もっと簡潔に話そう。
  • テーマを絞り込もう。
  • いい加減、発表直前まで資料作成をするのはやめよう。

18:14No comments

2012-08-29

フロント Web サーバで SSL デコードされた HTTPS リクエストを正しくリダイレクトする Play アプリを作る

Play 的に正しいと思われる解決方法が明らかになったのでメモ。Play framework 1.2.5 が対象です。また、フロントの Web サーバは nginx を想定しています。

リバースプロキシと SSL

Play framework を使って開発された Web アプリケーションを本番環境で運用する場合、Play アプリの AP サーバを直接外部に対して公開するのではなく、Apache や Nginx などの Web サーバを前方に立てて、その Web サーバからの HTTP リクエスト(リバースプロキシ)として、Play アプリの AP サーバに HTTP リクエストが到達するようなサーバ構成を取ることが一般的と思われます。

Play に限った話ではありませんが、このようなサーバ構成において SSL (HTTPS) による通信をサポートするとなると、フロントの Web サーバで SSL をデコードし、Web サーバと AP サーバの間を HTTP プロトコルで通信をすることがきっと多いことでしょう。

Play framework でのリダイレクトと HTTPS に関わる問題

ところで、Play framework の play.mvc.Controller クラス (MVC アーキテクチャでいうところのコントローラに相当するもの) には、HTTP ステータスコード 301/302 によりリダイレクトを行う Controller.redirect() メソッドが実装されています。このメソッドを使って redirect("Users.list"); とすると、次のような HTTP レスポンスがクライアントに返却され、その結果、http://localhost:9000/Users/list の URL へのリダイレクトが行われることになります。

HTTP/1.1 302 Found
Server: nginx/1.2.2
Date: Mon, 27 Aug 2012 16:30:14 GMT
Content-Type: text/plain; charset=utf-8
Content-Length: 0
Connection: close
Location: http://localhost:9000/Users/list
Cache-Control: no-cache

この Controller.redirect() によるリダイレクトですが、前述したリバースプロキシかつフロントの Web サーバで SSL デコードをする構成で行うと、リダイレクト先の URL が https で始まる URL ではなく、http で始まる URL となってしまいます。これにより、Web アプリケーションを利用している最中のリダイレクトにより、思いがけず HTTPS から HTTP に切り替わってしまうという悩ましい問題が発生し得ることになります。この問題は、Play アプリとフロントの Web サーバとの間のやりとりが HTTP ベースで行われていることによります。

問題の解決方法

この問題を解決する方法として、

  • フロント Web サーバの設定と Play アプリの application.conf の設定を変更する
  • Controller.redirect() メソッドを呼び出す直前で、request.isSecure = Boolean.TRUE とする
などの方法があります。後者の手段は、フロント Web サーバの設定を変更できない残念な状況の最終手段として残しておくとして、Play 的には前者の手段での対応がおすすめされているようです。そういうわけで、前者の方法について以下説明していきます。

application.conf の設定を変更する

リダイレクト先の URL を生成する Play framework の当該処理の実装を見てみるとわかりますが、スキームを http にするか https にするかの判断は、play.mvc.Http クラスの Http#parseXForwarded() メソッド と Http#isRequestSecure() メソッド の処理結果が強く関係してきます。特に、後者のメソッドが実行されて true を返すような処理となる場合に、リダイレクト先 URL のスキームが https となるので、つまりはそのような望ましい結果となるように条件を揃えてあげればいいことになります。

同式を true にするために変更すべき application.conf の設定は、以下の2つになります。

  • XForwardedSupport=all を追記する ... これにより、Play アプリに渡される HTTP リクエストのヘッダに X-Forwarded-For フィールドが存在すれば、無条件に Http#isRequestSecure() が実行されるようになります。
  • XForwardedProto=https とする ... これを設定することにより、X-Forwarded-Proto フィールドや X-Forwarded-Ssl フィールドの値によらず、X-Forwarded-For フィールドが定義された状況下での Play アプリに対するリクエストを HTTPS でリクエストされたものとして扱うようになります。Web アプリ全体を HTTPS で提供する場合に適した設定となります。
このあたりの設定は実は Play のドキュメント にも書かれています(私は、この内容から今回の目的に対する解決策を汲み取ることができませんでした…)。

nginx.conf の設定を変更する

nginx.conf の設定は簡単で、リバースプロキシの設定において proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for; を仕込んであげれば OK です。

解決方法は以上となります。もっとこと細かに HTTP / HTTPS を制御したい、としても、基本は play.mvc.Http クラスの、特に前述した2つのメソッドの実装を眺めれば解決するものと思います。

1:43No comments

2012-08-17

2つの Date オブジェクトで表される期間を Iterator オブジェクトで列挙できるようにしたい。

業務システムとかを開発していると、たまにこの手の処理がしたくなるのですが、

Date date = new Date();
for (int i = 0; i < 10; i++) {
  Calendar cal = Calendar.getInstance();
  cal.setTime(date);
  cal.add(Calendar.HOUR, 1);
  date = cal.getTime();

  // ここに date オブジェクトを利用した処理が書かれる...
}
こんなコードを書きたくない人向けの Iterator / Iterable クラスがこちらになります。


1:54No comments