2016-04-29

「詳解 Apache Spark」を共著で執筆しました (ので、みなさんぜひご購入ください!)

はじめに

昨年の秋ごろから、リクルートテクノロジーズの石川有さんらとともに共著で執筆していた「詳解 Apache Spark」 が遂に本日 4/29 に、技術評論社より発売となりました! なお、発売に先立って出版社および共著陣より献本させていただいた方々から、ありがたいことに書評や感想をいただいております。ぜひご購入の際の参考にしていただければと思います。

また、Amazon では Kindle 版も発売開始になった ようです。ですので、普段使いには物理書籍を、外出時には Kindle 版をご利用いただければと思います。

担当の「第 7 章 MLlib」について

書籍内ではあまり明確に謳ってはいないのですが、僕が担当した MLlib の章はデータ分析者だけではなく Web エンジニアを想定読者と考えています。仮に機械学習にあまり詳しくない方が読んだとしても、MLlib を利用するのに必要最低限の知識が獲得できつつ、MLlib を使ったアプリケーション開発ができるようになるであろう内容の構成としています。

章の前半では、RDD や DataFrame で表現されたデータに対して、MLlib の各機能 (特徴抽出や機械学習アルゴリズム、交差検証、評価メトリクスなど) を適用する説明に重点を置いた解説をしています。後半では、機械学習によって問題解決をするアプリケーションの開発イメージを掴むことを目的に、パブリックなデータセットを用いた具体例を提示しています。

紙面の都合もあり、機械学習の各種アルゴリズムの解説を事細かに網羅的に書くことは叶いませんでしたが、具体例で取り上げたアルゴリズムについては、そこそこ丁寧に説明をしました (したつもりです)。Spark 上で、より高度な機械学習の活用をしたいのであれば本書とあわせて、オライリー社の「Spark による実践データ解析」の書籍も読むのがいいでしょう。

また私の担当章以外も、GraphX や Spark Streaming など、MLlib の章以上に読み応えのある内容が盛りだくさんですので、このゴールデンウィークの勉強時間のお供にぜひ、本書をご購入いたければと思います。

おまけ

23:15No comments

2016-03-08

OS X で XGBoost & xgboost4j をビルドする手順 2016-03-07 版

追記: 2016-09-27 最新のビルド手順は こちら に記載しています。


いつのまにやら XGBoost のビルド手順が変更されていたので、メモしておきます (と言っても、 Installation guide に書いていることをほとんどそのまま日本語に直しただけですけどね)。

リポジトリの clone

手元に XGBoost の git リポジトリが存在しない場合は、以下のコマンドで submodule 含めて clone してしまいましょう。

git clone --recursive https://github.com/dmlc/xgboost

もし手元にリポジトリが存在する場合は、 git pull したのちに

git submodule init
git submodule update

として、submodule を手元に持ってきます。

XGBoost のビルド

clone したリポジトリに cd して、次の作業をします。

マルチスレッド非対応版で構わない場合

単に

cp make/minimum.mk ./config.mk
make -j4

とすれば OK です。

マルチスレッド対応版が欲しい場合

Installation guide 曰く、マルチスレッド (OpenMP) 対応した XGBoost をビルドするには、OpenMP-enabled なコンパイラである gcc-5.x.x が必要になるとのことです。なのでまず先に、 Homebrew で gcc をインストールしておきます (時間がかかるので、お茶でも飲んで待ちましょう)。

brew install gcc --without-multilib

なお、Homebrew で gcc-5.x.x をインストールしても gcc のコマンドが置き換わるわけではなく、 gcc-5 という名前でインストールされることに注意が必要です。そのため、Installation guide の手順をなぞっただけではマルチスレッド対応版の XGBoost をビルドすることはできません。

ここでは、Installation guide にある make/config.mk を単に cp する手順の代わりに、同ファイルで定義している CC および CXX をそれぞれ gcc-5, g++-5 に置き換えてコピーし、make する手順を紹介します。

cat make/config.mk | sed -e 's/# export CC = gcc/export CC = gcc-5/' | sed -e 's/# export CXX = g++/export CXX = g++-5/' >./config.mk
make -j4

xgboost4j のビルド

xgboost4j のビルドについては、以前の手順 よりハマりどころがなくなって楽になりました。詳しい手順は doc/jvm/index.md に書かれているとおりですが、ここでは次のように mvn package install して、ローカルの maven リポジトリにインストールしてしまいます (spark の依存が入っているため、最初の mvn install の実行でかなり時間がかかります。二杯目のお茶でも飲んで、待ちましょう)。

cd jvm-packages
./create_jni.sh
mvn package install

以上で xgboost4j のビルドは完了です。

1:16No comments

2016-02-09

エンジニアと機械学習、そして自分自身の振り返り ( #CROSS2016 に登壇しました)

2/5 (金) に開催された CROSS 2016 の「おーい、いそのー、エンジニアにとっての機械学習について考えようぜー!」というセッションにパネラーとして登壇してきました。セッションの内容はリンク先からの引用になりますが、

「機械学習は興味あるが、身に付けるためには何が必要?」
「機械学習を学ぶためにはいったい何からはじめればいい?」
「機械学習を身に付けたとして、その先のエンジニアとしてのキャリアはどうなる?」
と思ってる、そこのアナタ。
本セッションでは、機械学習や統計はもともと専門じゃないけど気がついたらバリバリ使ってた、そんなエンジニア連中が以下について語ります。
・エンジニアが機械学習を身に付けるために必要なこと
・どのように機械学習を学ぶのが効率的か
・エンジニアのキャリアパスとして考えた時、機械学習はどうなのか

というものでした。

当日は会場の音響の状況的に聞こえづらいところもあったかと思うので、僕がお話した内容(伝えたかったこと)+αをざっとまとめておきます。

エンジニアが機械学習を身に付けるには何が必要か?

まず最初は「エンジニアが機械学習を身に付けるために必要なこと」について議論しました。

そもそも、エンジニアにとって「機械学習を身に付ける」とはどういうことなのか、その点について共通認識がないままトピックが設定され議論をしていましたが、エンジニアと機械学習の関わり方には、主に以下の 2 つのタイプがあるんじゃないかと僕は考えています。

  • 機械学習を利用する人 :既存の機械学習のフレームワークやライブラリを用いる、またそれをアプリケーションに組み込んで利用する
  • 機械学習を実装する人 :既存の機械学習フレームワークなどには存在しない新しいアルゴリズムを実装する、もしくは特定のアプリケーションに最適化した形で既存のアルゴリズムを再実装する

前者のタイプであれば、機械学習の各種アルゴリズムがどのように動作するのか? というような、アルゴリズムに対するそこそこの理解が最低限必要になるかと思います。加えて、特徴エンジニアリング的な知識も必要になるかな… と、セッションを終えた後に議論を振り返っていて思ったのでした。

一方で後者のタイプであれば、機械学習アルゴリズムに対する深い理解が必要なのはもちろんのこと、アルゴリズムやデータ構造、時間・空間計算量などのある程度高水準なコンピューターサイエンスの知識、それと統計学の知識が必要になると考えています。また僕自身の経験から、微積や線形代数などの高校・大学レベルの数学の知識があると何かと助かるんじゃないかと思っています。その他には、英語力をつけておくと、最新の英語論文を読んでそれを実装したりもできていい感じです。

このトピックの僕の意見をまとめると、

  • 機械学習を利用する人:機械学習アルゴリズムに対する知識や特徴エンジニアリングの知識を身につけるべき
  • 機械学習を実装する人:上記に加えてコンピューターサイエンスや統計学、数学力、英語力を身につけるべき

となります。

機械学習を効率的に学習するにはどうしたらよいか?

次のトピックは「どのように機械学習を学ぶのが効率的か」でした。

これは僕自身の経験にもよるのですが、何よりも「仕事で機械学習を使わざるを得ない状況に身をおく」ことが一番効率的に機械学習を学べると実感しています。加えて言うと「機械学習の師匠」と呼べるような、理論面でも実活用面でも秀でた人物のそばで機械学習を利用する仕事ができるとベストだと思います(僕がいまいる会社がまさにそのような、理想的な状況にあるわけです)。

もちろん、そんな恵まれた状況に誰しもが巡り合えるわけではないことは重々承知していますが、本気で機械学習のお仕事をする覚悟があれば、転職をするのもありだと僕は考えています。ただし、転職をするにも多少なりとも機械学習の知識が必要になることもあるかと思います。そのような場合には、TokyoWebmining や TokyoR などの機械学習系の勉強会に顔を出したり、各種書籍の読書会に参加して発表するのが次善の策と言えるでしょう。

エンジニア+機械学習のキャリアパス

続いてのトピックは「エンジニアのキャリアパスとして考えた時、機械学習はどうなのか(機械学習を身につけることによって得られるリターンはいかほどか)」でした。

ここでいう「リターン」とは給与などのことを指すとして、現時点において機械学習を利用できるレベルのエンジニアの給与水準は、他の一般的なエンジニアの給与水準よりは幾分高いのではないかと推測しています。また、機械学習を実装できるレベルのエンジニアともなれば、相当な高水準の給与を得ているのではないでしょうか。

これは別に、機械学習の世界でだけ言えることではなくて、世間一般的に言えることなんじゃないかと思います。つまり、専門的かつ高度な技術・知識を持っていれば、給与水準は自ずと高くなるはずです。

ただその一方で、「機械学習を利用するエンジニア」の給与水準が今後も幾分高い水準を保てるかと言うと、僕は No だと考えています。現時点でも既に、Python 界隈は機械学習関連の機能が充実して使いやすくなってきているようですし、また Spark の MLlib が登場したことによって、一般的なエンジニアが機械学習を利用するまでのハードルが相当低くなっている = 技術コモディティ化が進んでいると思っています。この傾向は今後も継続して進んでいくものでしょうし、そうなるとただ単に「機械学習を扱える」だけのエンジニアの価値は並のエンジニアとさほど変わらなくなるでしょう。

また、機械学習が活用できるシチュエーションは、現実世界にはそう多くはない、ということにも注意が必要です。今は「人工知能」などのキーワードに引っ張られる形で機械学習も世間的に盛り上がっているようではありますが、この盛り上がりが落ち着いたときに、どれだけ「機械学習」が必要とされる仕事があるのか… というのを考えると、そう多くはないのでは? というのは想像に難くないかと思います。つまりは、機械学習を活用する仕事 = 需用が少なく、一方で供給 = 機械学習を扱えるエンジニアが多いと需給的には買い手市場となり、結果として給与水準が並のエンジニアとそう変わらない状況も生じるのではないかと思います。まあ、これはちょっと悲観的過ぎる推測でしたが…

そのため、機械学習を利用できるだけではなく、必要とあらば機械学習のアルゴリズムを実装できるぐらいのスキルがなければ中長期的にみて見合うリターンは見込めない、というのが僕の意見になります。というか、これは機械学習に限ったことじゃないですね… スペシャリスト的な働き方を目指すのであれば、それぐらいの覚悟がなければダメですよね。

機械学習を業務で扱う、その苦労

最後のトピックは「業務で大変だったこと、それをどう乗り越えたか」でした。

一般的にソフトウェア開発では、その品質を高めるために手動もしくは自動でのテストをするわけですが、機械学習においては知ってのとおり、手動や自動の議論以前に、そもそもテストを適用すること自体がそう簡単なことではありません。そのため、機械学習を組み込んだアプリケーションがあったとして、そのアプリケーションの実行結果がなんとも思わしくない結果が得られた場合、機械学習アルゴリズムにおける精度の制約なのか、それとも実装上の不具合なのかを切り分けることは困難な問題になります。

実際に僕も、この切り分けが困難な問題に何度も直面し、そのたびにつらみを感じてきました。そのため、今では機械学習の実装に対してできるかぎり自動テストを適用し、「実装上の不具合」を回避するように心がけるようにしています。

参考: 機械学習のテスト自動化コトハジメ #MLCT Machine Learning Casual Talks #1 // Speaker Deck

自分自身の振り返り

こんな感じで、当日のセッションでは識者ぶってお話をしてきました。でも今の僕は、「機械学習 黒帯」みたいなものを名乗るにはまだほど遠いところにいると思っています(「黒帯」とかただただ恥ずかしいだけだし、名乗りたいとは思っていません)。引き続き学習あるのみ、です。

そして、ふといままでの自分のキャリアを振り返ってきたときに、今となっては何の役に立たない残念な技術をいったいどれほど学習 = 貴重な時間を投資してきてしまったんだろうか… とも思いました。これまでの経験上、ソフトウェアエンジニアを続けている限りは「コンピューターサイエンス」を除いて廃れない技術はない、と僕は考えているので、機械学習もまたいつか廃れる日が来るのかもしれません。でもその日が来るまではしばらく、もうちょっと機械学習に投資してみようかな、と思っています。

2:391 comment

2016-01-15

弊社主催のイベント #SmartTechNight で、広告の配信最適化について喋りました

僕は最近こんなお仕事をしているんですよー、という意味をこめて喋りました。 機械学習だけが「アドテク」じゃない。最適化も重要なんだよ、という気持ちで。

よろしければ、こちらも合わせて御覧ください。

プレゼンテーションに盛り込む内容について、細かいことを言わない上司に恵まれているので、僕が担当している・していたお仕事の特に興味深そうなところをほぼすべてを余すことなくしたためた資料です。 遡ること 1 年半前、広告について何も知らなかった僕は必死の思いで関連文献を読み漁っていたわけですが、当時にこれくらい充実した資料があれば、もっと楽して開発できたのになあ、と資料を作りながら思ったのでした。 ですので、この資料が他の誰かの助けになれば幸いです。

そして、こういう話題であーでもないこーでもないと盛り上がれる仲間が欲しいです! 応募は こちら からお気軽に☆ 応募するのはまだちょっと踏ん切りが付かないけど、広告システムやその分析について議論してみたい! という方がいましたら僕宛にコンタクトください。

今日の反省点:Space cats や Shibe のネタスライドは受けがよくない。

0:094 comments

2015-12-12

Spark/MLlib 向けに、評価メトリクスとして Logarithmic loss (LogLoss) を利用する Evaluator を実装してみた

ロジスティック回帰を使って確率を予測したいときに「評価メトリクスとして使いたいのは AUC (areaUnderROC) じゃなくて Logarithmic loss (LogLoss) なんだよ!」と常々思っているのですが、現在の MLlib には二値分類 (BinaryClassificationEvaluator) 、多クラス分類 (MulticlassClassificationEvaluator)、回帰 (RegressionEvaluator) 用の Evaluator 実装しか用意されていなかったので、ついカッとなって実装してしまった次第です。

これくらいの機能は標準で取り揃えていてもいいんじゃないかと思うんだけどなあ…

16:54No comments

2015-11-08

xgboost4j より数千倍速く predict できる Pure Java な XGBoost 互換の予測器を作ってみた

TL;DR

XGBoost で構築した予測モデルを Java から利用したい、それも特徴ベクトルが一つ一つ、任意のタイミングで与えられるような オンライン環境下 で リアルタイムな予測 を実現するために利用したい、という目的を叶えるためのモジュールを作りました。

(XGBoost の凄さとか XGBoost そのものの使い方とか GBDT/GBRT の解説は本エントリにはありませんので、そのような情報を求めている方は他のブログエントリを読まれることをおすすめします。)

xgboost4j という選択肢

Java から XGBoost を利用しようとすると、XGBoostをJavaのwrapperを使用して実行する - TASK NOTES にあるように、DMLC が提供している xgboost4j を利用する手段がすでに存在しています。ただ、この xgboost4j をオンライン予測に適用する場合、下記に挙げるようないくつかの懸念があります。

  • XGBoost の Java wrapper でしかないので、オンライン予測の目的で利用をするにはインタフェースがちょっと使いづらい
    • 大量の特徴ベクトルを入力して一括予測するようなバッチ処理に適したインタフェースになっている
  • LIBSVM フォーマットじゃないデータを入力するのに手間がかかる
    • 特に疎な特徴ベクトルを DMatrix で表現するのが面倒
  • JNI 由来のオーバーヘッドが気になる
    • 予測処理などが C++ で書かれているので高速処理が期待できる一方で、特徴ベクトルを一つ一つ与えて予測させる場合、ネイティブコードの呼び出しにかかるオーバーヘッドが全体のパフォーマンスに大きな影響を与えそう
  • どこの Maven repository にもアップロードされていないので、自前で mvn install する必要がある
    • OS X で開発をしている場合、ネイティブライブラリをビルドするのも一苦労 (参考)

Pure Java での予測を実現する

そういうわけで、

  • 速度性能がオンラインでの利用に耐えうる水準で
  • そこそこ使いやすいインタフェースで
  • ネイティブコードを必要としない (= Pure Java な)

XGBoost 互換な予測器を作って jCenter で公開しました。

使い方

README.md にもサンプルコード込みで使い方を書いていますので、合わせてご参照ください。

なお、タイトルでも「予測器」と明言しているとおり、学習 (training) 機能については割りきって一切実装をしていません (モデルの構築をオンラインですることは流石にないと思うので)。 そのため学習データを用意し、XGBoost を CLI で直接実行、もしくは Python や R のラッパーを経由するなどして別途モデルの構築を事前に済ませておく必要があります。

学習済みのモデルが用意できたら、そのモデルを new Predictor("/path/to/model-file") としてロードします。 予測をするには Predictor#predict() のメソッドを呼び出します。

予測の際の入力となる特徴ベクトルは、FVec インタフェースのオブジェクトとして表現する必要があります。 基本はお手持ちのデータの形式に合わせて FVec インタフェースを実装したクラスを用意していただくことになりますが、配列や Map でデータが表現されている場合には、以下のユーティリティメソッドを利用することができます。

  • double の配列で表現された密な特徴ベクトルで → FVec.Transformer#fromArray() で FVec オブジェクトに変換できます
  • 特徴量のインデックスと値の対を表現した Map オブジェクト → FVec.Transformer#fromMap() で FVec オブジェクトに変換できます

また GBDT/GBRT のモデルを特徴ベクトルの変換に利用することを目的に、(分類・回帰の結果を出力するのではなく) GBDT/GBRT の各ツリーにおいて辿り着いたリーフのノード番号を出力する Predictor#predictLeaf() メソッドも用意されています。

ベンチマーク

元々このモジュールを作った動機の一つとして、オンライン利用に耐えうる速度性能で予測をしたい、という目的があったので xgboost4j と合わせてベンチマークをとってみました。 ベンチマーク計測の詳細は こちら のプログラムにあるとおりです。

機能 xgboost-predictor xgboost4j 性能比
モデルの読み込み 49017.60 ops/s 39669.36 ops/s 1.24
単一の特徴ベクトルでの予測 6016955.46 ops/s 1018.01 ops/s 5910.48
複数の特徴ベクトルの予測 44985.71 ops/s 5.04 ops/s 8931.47
リーフノードの出力 11115853.34 ops/s 1076.54 ops/s 10325.53

結果は上記のとおり、

  • 予測処理は 1ms 以下で処理できている
  • xgboost4j と比較して約 6,000 倍近い速度性能がでている (要は xgboost4j よりも十分速い)

となります。Pure Java にしただけで xgboost4j との性能差がこんなに出るものなのか… とちょっと不思議ではありますが、今回のベンチマークの計測に利用したテストデータは人工的に生成されたものなので、その影響があるのかもしれません。 そのため、実世界のデータを与えた場合にはまた違った結果になる可能性がありますのでご注意ください。

制限

現時点の xgboost-predictor は、モデルとしては “gbtree” のみをサポートしています。また目的関数は “binary” および “multi” のみのサポートとなります。 (“gblinear” や他の目的関数のサポートについては、必要そうであれば対応する予定です。)

21:095 comments

2015-10-29

XGBoost の Java wrapper を OS X でビルドするときに気をつけるべきたった二つのこと

追記: 2016-09-27 最新のビルド手順は こちら に記載しています。


なんで Java から XGBoost を扱いたいのかはさておき、概ね XGBoostをJavaのwrapperを使用して実行する - TASK NOTES こちらのサイトの解説どおりではあるのですが、OS X で素直に java/create_wrap.sh を叩いてビルドしようとすると

$ ./create_wrap.sh
build java wrapper
clang-omp++ -Wall -O3 -msse2  -Wno-unknown-pragmas -funroll-loops -fopenmp -fPIC -fPIC -shared -o java/libxgboostjavawrapper.so java/xgboost4j_wrapper.cpp wrapper/xgboost_wrapper.cpp updater.o gbm.o io.o subtree/rabit/lib/librabit.a dmlc_simple.o -pthread -lm  -I/Library/Java/JavaVirtualMachines/jdk1.8.0_66.jdk/Contents/Home/include -I/Library/Java/JavaVirtualMachines/jdk1.8.0_66.jdk/Contents/Home/include/linux -I./java
In file included from java/xgboost4j_wrapper.cpp:15:
/Library/Java/JavaVirtualMachines/jdk1.8.0_66.jdk/Contents/Home/include/jni.h:45:10: fatal error: 'jni_md.h' file not found
#include "jni_md.h"
         ^

みたいなエラーが出てしまうはずです。

この問題の対処法は実に簡単で、xgboost リポジトリのトップディレクトリ配下にある Makefile の 8行目を

before: export JAVAINCFLAGS = -I${JAVA_HOME}/include -I${JAVA_HOME}/include/linux -I./java
after : export JAVAINCFLAGS = -I${JAVA_HOME}/include -I${JAVA_HOME}/include/darwin -I./java

と書き換えるだけ、です。

続いて、java/xgboost4j ディレクトリ配下で mvn package コマンドを実行して jar ファイルを生成しようとしてみると、今度は

-------------------------------------------------------
 T E S T S
-------------------------------------------------------
Running org.dmlc.xgboost4j.BoosterTest
Oct 29, 2015 2:51:55 AM org.dmlc.xgboost4j.DMatrix <clinit>
SEVERE: load native library failed.
Oct 29, 2015 2:51:55 AM org.dmlc.xgboost4j.DMatrix <clinit>
SEVERE: java.io.FileNotFoundException: File /lib/libxgboostjavawrapper.dylib was not found inside JAR.
Tests run: 1, Failures: 0, Errors: 1, Skipped: 0, Time elapsed: 0.121 sec <<< FAILURE!
testBoosterBasic(org.dmlc.xgboost4j.BoosterTest)  Time elapsed: 0.063 sec  <<< ERROR!
java.lang.UnsatisfiedLinkError: org.dmlc.xgboost4j.wrapper.XgboostJNI.XGDMatrixCreateFromFile(Ljava/lang/String;I[J)I
        at org.dmlc.xgboost4j.wrapper.XgboostJNI.XGDMatrixCreateFromFile(Native Method)
        at org.dmlc.xgboost4j.DMatrix.<init>(DMatrix.java:62)
        at org.dmlc.xgboost4j.BoosterTest.testBoosterBasic(BoosterTest.java:75)
        at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
        ...

と、test フェーズでこけてしまうかと思います。これは native ライブラリの拡張子が .so となってしまっているのが原因なので、これは create_wrap.sh の 12 行目 の移動先ファイル名を明示的に libxgboostjavawrapper.dylib と指定するか、もしくはすでに移動先にある native ライブラリの拡張子を .so から .dylib に書き換えてやれば OK です。

2:22No comments

2015-10-17

よりコンパクトな Bloom filter 的なものを探して

Approximate membership query (AMQ) が実現できるデータ構造としてそれなりに広く使われていそうな Bloom filter ですが、機能性を高めたバリエーションはそこそこ存在する一方で、空間効率を追求した・コンパクトなバリエーションはあんまり見つからないものです。

ここ最近、ふとデータ構造熱が高まってきたこともあったので、オリジナルの Bloom filter よりもコンパクトに表現できる代替データ構造を探してメモしてみました。

Compressed bloom filters

空間効率を追求するといっても、転送・永続化している状態での空間効率なのか、それともルックアップ可能な状態においての空間効率なのかで全然違うわけですが、この Compressed Bloom Filters は前者の転送時・永続化時の空間効率を選択したバリエーションです。

端的に言えば、Bloom filter のビット列における 0 と 1 の出現確率はランダム (1/2 = 0.5) というわけではなく偏りが生じることがあるため、算術符号で符号化すればよりコンパクトになるじゃん、というものです。 ただ、この圧縮はあくまでも転送・永続化時のことしか考えていないようで、Bloom filter が素早くルックアップできる状態にあるためには結局復号した状態で保持する以外に他ないようです。

Golomb-Compressed Sequence (or Golomb-code sets)

Cache-, Hash- and Space-Efficient Bloom Filters という論文で、Space-Efficient な手法として提案されている approximate membership query を提供するデータ構造です (Bloom filter と同じ機能を提供しているが、厳密には Bloom fitler ではない)。

要素のハッシュ値を算出するところまでは Bloom filter と同じですが、そのハッシュ値を

  1. 昇順ソートして
  2. そのソート順における、左に隣接する値との gap を求めて
  3. その gap を Golomb 符号で符号化

することで、Bloom filter よりもコンパクトな表現を実現しています (ハッシュ値は一様分布しているものとして、そのハッシュ値の gap をとると幾何分布になり、幾何分布に従う数値を符号化するには Golomb 符号が都合いい、ということ)。

この方式でのルックアップ操作は、あるハッシュ値が Golomb-Compressed Sequence に含まれるか否かだけを探索により判定すればいいので、Bloom filter のようなビット列への複数回のランダムアクセスは生じません。 とは言えど、この圧縮表現のままでは効率的なランダムアクセスが実現できないため、

  1. ハッシュ空間を大きさ $I$ の空間に分割して
  2. その分割された空間ごとに Golomb 符号化をし
  3. ルックアップの際はハッシュ値から探索先のハッシュ空間を絞り込んでから逐次 Golomnb 符号を復号する

ことで、復号にかかる時間効率を高められるようにしています。 $I$ を大きくすれば大きくするほど、空間効率がよくなるが探索効率は悪くなり、 $I$ を小さくすると空間効率は悪くなるが探索効率が上がる、というトレードオフの関係になっています。

Cuckoo filter

Cuckoo Filter: Practically Better Than Bloom では、Cuckoo hashing を利用して、approximate membership query を提供するデータ構造を提案しています。

Cuckoo hashing の詳細説明は kumagi 先生の資料 に譲るとして、Cuckoo filter では要素から $f$ ビットのフィンガープリント (ハッシュ値の一つだと考えれば OK) と、2 つのハッシュ値を算出し、 Cuckoo hashing に利用します。より具体的には、2 つのハッシュ値を配列で表現されるバケット (複数のフィンガープリントを記録できる入れ物) のインデックス決定に利用し、フィンガープリントをそのバケットに追記する、という使い方になります。

この Cuckoo filter で使われる 2 つのハッシュ関数はちょっとだけ特殊で、$h_1(x) = hash(x), h_2(x) = h_1(x) \oplus hash(x's fingerprint)$ となっています。つまりは、フィンガープリントと一方のハッシュ値がわかっていれば $h_1(x)$ と $h_2(x)$ を算出することができるわけです。

パラメータとしてはフィンガープリントを表現するビット数や、バケットの大きさ (異なるフィンガープリントを格納できる個数)、バケット数と、ちょっと多めなのが気になりますが空間効率も参照性能も Bloom filter より良さそうです。

さて今回はこのぐらいにして、Golomb-Cmpressed Sequence あたりを実装してみようかな…

15:27No comments

2015-10-01

SCIP を使って最適化問題を解いてみる

最適化問題、とりわけ線形計画問題が気になり始めるお年頃になってきたので、 SCIP というソルバーを使ってみましたよ、というメモ。

インストール

まずは手元にある MBP に、 SCIPをMacにインストール - Qiita の手順を参考にインストールを試してみる。ところが、

src/rational.h:32:10: fatal error: 'gmp.h' file not found

などの gmp.h がない旨のコンパイルエラーが発生してしまう状況に遭遇してインストールできない。 なので、ひとまず make GMP=false としてお茶を濁すことしてみる (GMP を要求するのは ZIMPL らしく、かつその機能を利用することは今のところはないので)。

インタラクティブシェル

ビルド後の scip のバイナリ scip-X.X.X/bin/scip を立ち上げるとインタラクティブシェルが立ち上がる。

read: 問題を記述したファイルを読み込む

ひとまず適当な問題をソルバーで解かせてみようと思い、講義テキストらしきもの (PDF) を参考に、最適化問題を記述した LP ファイル (sample.lp) を作ってみる。

maximize
400 x1 + 300 x2
subject to
60 x1 + 40 x2 <= 3800
20 x1 + 30 x2 <= 2100
20 x1 + 10 x2 <= 1200
end

このファイルを scip のインタラクティブシェル上で読み込んでみる。読み込みには read コマンドを利用する。

SCIP> read /path/to/sample.lp

read problem </path/to/sample.lp>
============

original problem has 2 variables (0 bin, 0 int, 0 impl, 2 cont) and 3 constraints

2 つの変数、3 つの制約条件、と出力がでて、ちゃんと読み込めたようだ。

optimize: 最適化問題を解く

読み込んだ問題を実際に解いてみよう。問題を解くには optimize コマンドを利用する。

SCIP> optimize

feasible solution found by trivial heuristic after 0.0 seconds, objective value 0.000000e+00
presolving:
(round 1, fast)       0 del vars, 0 del conss, 0 add conss, 4 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
presolving (2 rounds: 2 fast, 1 medium, 1 exhaustive):
 0 deleted vars, 0 deleted constraints, 0 added constraints, 4 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
 0 implications, 0 cliques
presolved problem has 2 variables (0 bin, 0 int, 0 impl, 2 cont) and 3 constraints
      3 constraints of type <linear>
Presolving Time: 0.00
transformed 1/1 original solutions to the transformed problem space

 time | node  | left  |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr|  dualbound   | primalbound  |  gap
* 0.0s|     1 |     0 |     3 |     - | 194k|   0 |   - |   2 |   3 |   2 |   3 |   0 |   0 |   0 | 2.700000e+04 | 2.700000e+04 |   0.00%
  0.0s|     1 |     0 |     3 |     - | 194k|   0 |   - |   2 |   3 |   2 |   3 |   0 |   0 |   0 | 2.700000e+04 | 2.700000e+04 |   0.00%

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.00
Solving Nodes      : 1
Primal Bound       : +2.70000000000000e+04 (2 solutions)
Dual Bound         : +2.70000000000000e+04
Gap                : 0.00 %

表示内容が豊富でちょっと面食らってしまうけど、 problem is solved [optimal solution found] がポイント。最適解が求まったぽい。

display: 解を表示する

optimize コマンドで解が求まったら、 display のコマンドでその解を表示してみよう。

SCIP> display solution

objective value:                                27000
x1                                                 30   (obj:400)
x2                                                 50   (obj:300)

ちゃんと最適解が求まっているのがわかる。

write: 解をファイルに書き出す

optimize コマンドで求まった解を他の用途で使いたい、ということは結構よくあるはず。ファイルに書き出すことができればスクリプト言語でパースして利用する事もできるだろう。

それでは write コマンドでファイルに書き出してみよう。

SCIP> write solution result.sol

written solution information to file <result.sol>

出力された result.sol を less などで覗いてみれば、display solution でコンソールに表示した内容と同等のものが出力されているのがわかるはず。

問題の記述方法

SCIP のひととおりの使い方がだいたい分かってきたところで、他の問題も SCIP で解けるように、問題の記述方法を勉強してみよう。

ナップサック問題

まずは最適解問題で定番のナップサック問題。具体的な問題は Wikipedia のページ ナップサック問題 の図より拝借。

maximize
4 d4w12 + 2 d2w2 + 2 d2w1 + 1 d1w1 + 10 d10w4
subject to
weight: 12 d4w12 + 2 d2w2 + 1 d2w1 + 1 d1w1 + 4 d10w4 <= 15
binary
d4w12 d2w2 d2w1 d1w1 d10w4

ナップサック問題に入れる・入れないをフラグ的に binary で表現し、目的関数に価値の合計を、制約条件に重さの合計に対する上限値を設定すれば OK だろう。

N クイーン問題

ソルバーで解いて嬉しいかどうか別として、 N クイーン問題 をソルバーで解かせてみよう。

問題の記述が大変だったので、盤面の大きさは 4x4 にしてみる。

maximize
a1 + a2 + a3 + a4 + b1 + b2 + b3 + b4 + c1 + c2 + c3 + c4 + d1 + d2 + d3 + d4
subject to
rowA: a1 + a2 + a3 + a4 = 1
rowB: b1 + b2 + b3 + b4 = 1
rowC: c1 + c2 + c3 + c4 = 1
rowD: d1 + d2 + d3 + d4 = 1
col1: a1 + b1 + c1 + d1 = 1
col2: a2 + b2 + c2 + d2 = 1
col3: a3 + b3 + c3 + d3 = 1
col4: a4 + b4 + c4 + d4 = 1
diagC1D2: c1 + d2 <= 1
diagB1D3: b1 + c2 + d3 <= 1
diagA1D4: a1 + b2 + c3 + d4 <= 1
diagA2C4: a2 + b3 + c4 <= 1
diagA3B4: a3 + b4 <= 1
diagC4D3: c4 + d3 <= 1
diagB4D2: b4 + c3 + d2 <= 1
diagA4D1: a4 + b3 + c2 + d1 <= 1
diagA3C1: a3 + b2 + c1 <= 1
diagA2B1: a2 + c1 <= 1
binary
a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 d1 d2 d3 d4

すごく冗長な表現になってしまっているように思えるが、ちゃんと解くことができる。いいね!

参考文献

宮代 隆平 の web ページ(整数計画法メモ)

1:32No comments

2015-07-25

クリック率やコンバージョン率の信頼区間を求めたい! (3) シミュレーション編

過去二回にわたって、

と綴ってきた、CTR, CVR の区間推定をするお話の総集編的なエントリです。

今回は commmons-math3 を使って、各区間推定方法における実際のカバレッジを測定するシミュレータを作ってみました。あわせて測定結果より、それぞれの方法の特性を確認していきます。

まずは復習から

「二項比率の区間推定 (英語 Wikipedia)」は、統計的に独立・有限回で、各々の試行において「成功」か「失敗」のどちらかの結果が得られる問題の、「成功が発生する確率 $p$ (二項比率)」の信頼区間を求めることに相当します。

これをクリック率 (CTR) の区間推定に置き換えると、「成功」はすなわちクリックされたこと、「失敗」はクリックされなかったことに相当します。そして「成功が発生する確率」というのは、クリック回数 / インプレッション回数、つまりは CTR となります。

この「二項比率の区間推定」をする方法はいくつかあって、先の英語 Wikipedia にも記載されている方法として

  • Wald confidence interval
  • Clopper-Pearson (or 'Exact') confidence interval
  • Wilson (or 'Score') confidence interval
  • Adjusted Wald confidence interval / Agresti-Coull confidence interval

などがあります。ただそれぞれ、論文で指摘されているとおりの特徴(というよりも欠点)があって、サンプルサイズの大きさや $p$ の値次第で実際のカバレッジが想定外の値になってしまう、という状況が起こりえます。

そのため、自身がとりあつかっている CTR や CVR のインプレッション数、クリック数、コンバージョン数に応じて、これらのいずれかをうまく使い分ける必要がある… と考えたのが、今回の一連のエントリを書き始めたきっかけでした。

シミュレーションしてみる

それではそろそろシミュレーションをしてみて、各区間推定方法の特性を実際に確認してみましょう。

シミュレーション内容

シミュレーションの内容は次のとおりです。

  • 次のサンプルサイズおよび真の二項比率 $p$ のすべての組み合わせごとに、1,000,000 回 の試行をします
    • p : 10% から 1% までの 1 ポイント刻みの値、および 1% から 0.1% までの 0.1 ポイント刻みの値
    • サンプルサイズ : 100 から 1,000 までの 100 刻みの値、および 1,000 から 10,000 までの 1,000 刻みの値
  • 信頼度を 95% としたときのカバレッジを測定します
    • このカバレッジが大きすぎず小さすぎず、 95% の値により近いことが望ましい結果となります
  • 1,000,000 回のサンプリングのうち、求められた信頼区間に $p$ の値が含まれている割合がカバレッジとなります
  • 精度面の検証以外にも、処理時間の測定をして評価をします

プログラム

シミュレーションのプログラムは次のリンク先になります。

komiya-atsushi/binomial-proportion-confidence-interval

結果と評価

測定結果は Google スプレッドシート Comparison of Binomial proportion confidence interval にまとめました。

なお、以下の精度面の評価では Wald confidence interval の結果を省いています (Wald は評価するまでもなく突出して精度が悪く、グラフに含めると見辛くなってしまうため)。

サンプルサイズを変化させたとき

まずはサンプルサイズの大きさを変化させたときの結果に着目してみます。

  • サンプルサイズを大きくすれば、いずれも 95% の信頼度に近いカバレッジが得られる
    • カバレッジのぶれもサンプルサイズが増えるごとに落ち着く
  • 全体的なカバレッジの傾向は、Clopper-Pearson > Agresti-Coull > Wilson となる
    • Clopper-Pearson のカバレッジが一番広く、95% を下回ることはまれ
    • Wilson は常に一番狭いカバレッジとなる
    • Agresti-Coull は、サンプルサイズが小さいときは Clopper-Pearson のように広いカバレッジをとり、サンプルサイズが増えるに従って Wilson のカバレッジに近づく

p を変化させたとき

次に、二項比率 $p$ を変化させたときの結果を見てみます。

  • サンプルサイズがそこそこある状態であれば、 $p$ が大きくなるにつれていずれも 95% の信頼度に近づいていく
    • こちらも、カバレッジのぶれは $p$ が大きくなることで落ち着く傾向となる
  • 全体的なカバレッジの傾向は、Clopper-Pearson > Agresti-Coull > Wilson となる
    • これはサンプルサイズを変化させたときと同じ傾向である
  • サンプルサイズあまりない状態で $p$ が小さい場合、Wilson は極端に狭いカバレッジ (90% 前後) となることがある

計算時間

最後に、今回のシミュレーションをするのに要した時間を、計算方法ごとにグラフにしてみます。

  • Wilson と Agresti-Coull はどちらも大差なし
  • Clopper-Pearson は他に比べて遅くなりがち
    • 他より複雑な計算が必要なため
    • サンプルサイズに比例して実行時間がかかってしまうのは、利用したライブラリ (commons-math3) の実装に起因している?
  • Normal Approximation (Wald) は、区間の幅が 0 になってしまうようなケースの計算時間が含まれていないため、Wilson, Agresti-Coull よりも計算時間が不当に短くなっている

まとめ

計算方法それぞれの特徴

論文を読んだり実際にシミュレーションをしてみて、それぞれの計算方法の特性が明らかになったので表にまとめてみます。

Method 実装が容易 区間の幅 $p$ の偏り 区間の上限/下限
Wald ◎ × (*1) × (*3) × (*4)
Clopper-Pearson / exact × △ (*2) - -
Winson / score × - × (*3) -
Agresti-Coull / Adjusted Wald ◯ - - × (*4)
  • *1 : 狭くなりがち
  • *2 : 広くなりがち
  • *3 : 狭くなる
  • *4 : 下限が 0 を下回る / 上限が 1 を超える

結論

元々の目的であるクリック率やコンバージョン率の区間推定に立ち返って、今回の調査・シミュレーション結果を見てみると、

  • Wald は欠点が多すぎてクリック率などの区間推定には適していない
  • クリック率のように、$p$ が極端に小さい値になりうることを考えると、Winson を利用するのは注意が必要
    • サンプルサイズが十分でない場合は使わない方がいい
  • 適切な幅の区間推定をする上では、Clopper-Pearson もしくは Agresti-Coull がよさそう
    • Clopper-Pearson は、意図して信頼区間を保守的に (慎重に) 広くとりたい場合に向いている
    • Agresti-Coull は下限が 0 より小さくなったり上限が 1 より大きくなったりする点に注意すれば (計算は楽だし) 使い勝手がいい

と言えることでしょう。

16:22No comments

2015-01-24

第 42 回 #TokyoWebmining 深層学習・表現学習 徹底活用 祭りに行ってきたよ

今回の TokyoWebmining はここ最近、特に注目を集めている Deep Learning と word2vec がトピックということで、参加者募集も数分で枠が埋まってしまうほどの大人気っぷりでした。

せっかくなので、(参加したくても参加できなかった方々も多いことかと思いますし)たまにはまとめエントリを、会場内での質問やディスカッションを中心に書いてみようかと思います。

(聞き間違い・勘違いなどがあるかと思いますので、気づかれたかたはツッコミ願います)

深層学習時代の自然言語処理 by @unnonouno さん

Recurrent Neural Network

  • p.11 Recurrent Neural Network
    • 1 個の単語に対して、1 個の dense ベクトルがある
      • 次元数は 100〜1,000 ぐらい
      • RNN への入力ベクトルはこれになる
      • この単語ベクトルは各層で共有される
      • 正則化して sparse にしてみたけど、別によくはならなかった
  • p.14
    • 時間方向に層を重ねることに相当する
      • 層が文長に相当する、ここが他の NN と異なる
  • p.16
    • RNN の学習は、Back Propagation (Through Time) で学習する
      • 時間をさかのぼって学習しているように見える
      • 図的には、赤が Back propagation になる
  • p.17
    • 誤差が最初の方に伝搬しないという問題がある
    • これを解決したのが Long Short-Term Memory という技術
  • p.18 Long Short-Term Memory
    • 隠れ層のベクトル間でされる演算
    • 影響の与えるタイミングと与えないタイミングがあるはず、という考え
    • これによりパラメータが増えることになるが、これは学習対象となっている
    • 昨年後半からこれが流行ってる
    • 機械翻訳や Wikipedia 文章ぽいものの再生成、構文解析などに適用されてる by Google
    • 1 個の文がベクトルになって、そこから文が湧き出てくる

Recursive Neural Network

「両方とも RNN って略すのやめろ」

  • p.22
    • こちらは木構造を学習してつくる
    • 文章の構文解析だけでなく、画像の構造推定に使える
      • 木構造を作る
      • 二つの要素をくっつける順番を学習する
  • p.23 評判分析にも使われてる
    • こちらは木構造が事前に与えらて、ポジネガを判定している
    • 前は feature engineering で頑張って精度を高めていたけど、この RNN を使ったら良くなった
    • 文章全体ではなく、一つの文に対して適用される

本題:構文解析

  • p.32 Shift-Reduce 法
    • ガーデンパス文に弱い
    • これが Recurrent Neural Network に近いんじゃないか?
  • p.41
    • 品詞情報だけだと、構文解析は全然できない
  • p.46
    • 構文解析はまだルール作りはなんとかなるが、意味解析は膨大過ぎてルール作りは辛い

まとめ

  • p.48
    • Recurrent が流行っている
    • 音声認識、特に G とか MS とかの大手では DNN が使われているんじゃなかろうか?

ディスカッション

  • 単語分割、構文解析は精度が出ているが、意味解析とか談話解析はまだまだなので、そのあたりで DNN 使って精度出せるといいね
    • そもそもの問題設定があいまいだったりするけど…
  • テトリスブロックを回転させたもの同士が同じかどうかを判定するタスクで、DNN はうまくいかないというツッコミを入れた論文があった
  • 「言語学者をクビにすればするほど精度が上がる」

ディープラーニング徹底活用 画像認識編 by @atelierhide さん

この発表で一番言いたいこと

  • 「学習済みモデルを徹底活用しよう!」
    • Convolutional Neural Networks (CNNs) のモデル
  • 世界一のモデルを使うことができる
  • 1000 次元のベクトルが出力として得られる

Deep learning frameworks

  • 選択観点
    • 学習済みモデルが提供されているフレームワークを選ぶのがいい
    • Caffe よさそう
    • Caffe と DeCAF はほとんど違いはない
    • OverFeat は使い勝手がよくない
  • Caffe
    • 画像のリサイズなどは、まあまあフレームワークがよろしくやってくれる
      • 横長画像は正方形に変換されてしまうので、その点は注意しないといけない
    • Detection と Recognition は別
      • DNN が効くのは Recognition のほう
    • モデルの学習をする場合は、背景などが写り込んでいないものを選ぶべき
      • 分類はその限りではない

学習済みモデルの活用のアイデア

  1. 特徴抽出器として使う
    • CNNs の最後から 2 番目に得られる部分のベクトルを使う
      • pre-training 相当になっている
    • これを特徴量として、SVM などで分類する
  2. ファインチューニングをする
    • 出力層・分類数を入力画像にあわせて変更し、学習済みモデルのパラメータを最適化する
  3. 物体検出に使う

ディスカッション

  • みんなが Caffe を使い出していて、いろんな適用例が発表されはじめている
  • Caffe に Recurrent / LSTM が入るらしいということで、その手の界隈がざわついている

word2vec のご紹介 by @piroyoung さん

word2vec

Python で word2vec を使う

  • p.36
    • gensim を利用する
      • Paragraph vector も実装されている
    • コーパスをライブラリに喰わせるときに工夫が必要になる
      • ナイーブにやるとメモリが足りなくなる
      • 1 行読んでスペース区切り文を分割する… の処理をイテレーションさせる

素性のクラスタリング

  • word2vec で得られた単語のベクトルをクラスタリング
    • わりとよくクラスタリングできてる

QPR の学習

  • QPR = Quick purchase report, 消費者購買動向データ
  • p.56
    • ウィンドウサイズはものすごく大きなサイズにした
      • バスケット内の商品は、順番には意味がない
      • ただし先ほどの海野さんのツッコミにあるとおり、順番が考慮された結果となってしまった

ディスカッション

  • 文章中の助詞などを省いてみたら結果はどうなるの?
    • 単語同士の関係性を構成する要素になるので、動詞を入れても動詞が出てこなくなる
    • ものにもよるが、助詞を入れた方がいいであろう
  • 次元数 200 以外でやってみた?
    • 次元を上げて、悪くなることはなかった
    • 計算時間はその分かかる

今回の TokyoWebmining の所感

  • Deep learning、いまいちちゃんと理解できてなかったけど、雰囲気はだいぶつかめてきた
  • 画像の取り扱いにおいては Deep learning を利用するのがもはや当たり前っぽい
    • ImageNet の学習済みモデル、応用の幅が広いね!
  • 自然言語処理での Deep learning 活用、研究の進展が速いので、常にキャッチアップしていかないと置いて行かれそう…
  • とにかく Deep learning 熱の高まりっぷりがはんぱない!
18:45No comments

2015-01-19

クリック率やコンバージョン率の信頼区間を求めたい! (2) 実装編

前回 は CTR (クリック率)、CVR (コンバージョン率) に対するいくつかの区間推定方法を、それぞれの特徴とともに列挙してみました。今回はそれらの区間推定方法による実際の信頼区間を、Java や Python, R を用いて求める方法をまとめてみます。

Java による区間推定

Java で二項比率の区間推定をするには、commons-math3 の org.apache.commons.math3.stat.interval パッケージ以下のクラスを使うのが手っ取り早いでしょう。

それぞれの区間推定方法に対応するクラスは以下のとおりです。

  • Wald confidence interval
    • NormalApproximationInterval クラス
  • Clopper-Pearson (or 'Exact') confidence interval
    • ClopperPearsonInterval クラス
  • Wilson (or 'Score') confidence interval
    • WilsonScoreInterval クラス
  • Adjusted Wald confidence interval / Agresti-Coull confidence interval
    • AgrestiCoullInterval クラス

これらのクラスに定義されている #createInterval(int numberOfTrials, int numberOfSuccesses, double confidenceLevel) を呼び出すことで信頼区間を求めることができます。たとえば numberOfTrials にインプレッション数を、 numberOfSuccesses にクリック数を、 confidenceLevel に 0.95 を設定して呼び出せば、95% 信頼水準での CTR の信頼区間が得られます。

サンプルコードは以下のとおり。

注意点として、 CTR や CVR の割合が 0% or 100% になるケース (つまりは、クリックやコンバージョンがまったく発生していない or 毎回発生している状態) において NormalApproximationInterval クラス、もしくは ClopperPearsonInterval クラスの #createInterval(int, int, double) メソッドで信頼区間を求めようとすると、 MathIllegalArgumentException や NotStrictlyPositiveException などの例外が発生してしまいます。

Wald confidence interval ではそもそも区間の幅が 0 になるケースに相当するのでどうしようもないのですが、Clopper-Pearson confidence interval では区間の片側だけでも算出することはできるはずです。

なので、このようなケースでも無理矢理に算出することはできるわけで、例えば ClopperPearsonInterval クラスの実装を以下のように修正すれば例外を生じることなく信頼区間を求めることができます。

Python による区間推定

Python の場合は、statsmodels を使います。

使い方は こちらのドキュメント を参考に、statsmodels.stats.proportion.proportion_confint(count, nobs, alpha, method) を呼び出します。CTR を算出するのであれば count にクリック数を、nobs にインプレッション数を指定し、加えて信頼水準 $100(1-\alpha)\%$ の $\alpha$ を alpha に指定します。

method には、区間推定方法を文字列で指定します。

  • Wald confidence interval
    • normal
  • Clopper-Pearson (or 'Exact') confidence interval
    • beta
  • Wilson (or 'Score') confidence interval
    • wilson
  • Adjusted Wald confidence interval / Agresti-Coull confidence interval
    • agresti_coull

サンプルコードは以下のとおり。

Java 同様に注意すべきこととして、CTR や CVR の割合が 0% or 100% の場合に、Clopper-Pearson confidence interval による区間推定の結果のうち、一方の片側が NaN になってしまうことが挙げられます。この場合、下側のエンドポイントが NaN であれば 0% と、上側のエンドポイントが NaN であれば 100% と読み替えればよいかと思います。

R による区間推定

R では、binom パッケージ の binom.confintt(x, n, conf.level, methods, ...) を使って二項比率の区間推定をします。

methods に "all" を指定すると、すべての区間推定方法の結果を一覧で出力してくれます。もしくは以下の文字列を指定することで、対応する区間推定方法での結果を出力してくれます。

  • Wald confidence interval
    • prop.test
  • Clopper-Pearson (or 'Exact') confidence interval
    • exact
  • Wilson (or 'Score') confidence interval
    • wilson
  • Adjusted Wald confidence interval / Agresti-Coull confidence interval
    • agresti-coull

まとめ

今回挙げた言語の各ライブラリでは、いずれもメソッド・関数を呼び出す程度の簡単なコードで二項比率の区間推定をすることができました。

ただ Java と Python については、CTR / CVR が 0% or 100% といったコーナーケースにおいてあまり好ましくない振る舞いをするため、多少の注意が必要となります。

また、各ライブラリで区間推定方法の呼称が異なることがあるため (Python / statsmodels の beta (Clopper-Pearson) や、R / binom の prop.test (Wald) など)、この点にも注意すべきかと思われます。

(次回こそはシミュレーション結果を…)

1:03No comments

2015-01-07

クリック率やコンバージョン率の信頼区間を求めたい! (1)

わけあってクリック率・コンバージョン率の信頼区間を算出したくなったのだけど、そのやり方を調べてみたら結構ややこしかったので、調べた結果をメモに残しておきます。

はじめに

クリック率 (Click-through rate, CTR) やらコンバージョン率 (Conversion rate, CVR) を扱う仕事をしていると、少なくとも一度ぐらいはそれらの信頼区間を求めて (区間推定して) みたくなるものかと思います。

それというのも、例えば「100 回のインプレッションのうち、1 回のクリックが得られた」という標本 (サンプル) があったとして、これから CTR を点推定すると 1% になるものの、これは「サンプルサイズを増やしたときにも同様に 1% になるのか?」と言ったらそんなことは言えないわけで、ならば「どれくらいの信頼水準のときにどれくらいの範囲に真の CTR が存在しうるのか?」ということを知りたくなるわけです。この範囲を求めることがすなわち信頼区間を求める・区間推定をすることに相当します。

さて以上のようにクリック率・コンバージョン率の区間推定をしてみたいのですが、具体的にはどのようにすればいいのか? これは二項比率 (binomial proportion, この日本語訳で適切なのか、わからない…) の区間推定をすることに等しくなります。

二項比率の区間推定をする方法について、あいにく日本語で網羅的にまとまった解説が Web 上には存在しないのですが (だからこのブログエントリを書いているわけでして…) 英語 Wikipedia のページ がそこそこ充実しているので、わかる人はこちらのページを合わせて参照することをおすすめします。以降はこの Wikipedia ページと、同ページでリファレンスされているいくつかの論文 (後述) をもとに話を進めます。

二項比率の区間推定をするいくつかの方法

さて二項比率の区間推定をする方法として、今回は以下の 4 つを取り上げてみます (他にもベイズ的な確信区間などがあるわけですが、こちらは僕自身まだちゃんと理解しきれていないので割愛します)。

  • Wald confidence interval
  • Clopper-Pearson (or 'Exact') confidence interval
  • Wilson (or 'Score') confidence interval
  • Adjusted Wald confidence interval / Agresti-Coull confidence interval

以下、それぞれの区間推定方法について、数式とともにその特徴などを列挙していきます。

Wald confidence interval

$$\hat{p} \pm z_{\alpha/2} \sqrt{ \hat{p} (1 - \hat{p}) / n}$$

($\alpha$ は信頼係数、$z_{\alpha/2}$ は標準正規分布の上側 $100(\alpha/2)$ % 点、$n$ はサンプルサイズ or 試行回数、$\hat{p}$ は二項比率の推定値)

二項分布 $B(n,p)$ は正規分布 $N(np, np(1-p))$ で近似できることから、二項比率の信頼区間も正規分布 $N(p,p(1-p)/n)$ で近似することができるため、上記の式で信頼区間を求めることができます。

  • 数式がわりと容易である
    • つまりは実装するのも比較的楽、ということ
  • この手法により求まる信頼区間は、信頼水準から得られるそれよりも狭くなる (= 実際のカバレッジが低くなる) 傾向にある
    • サンプルサイズが小さい ($n < 100$ ぐらいの) 場合に、特にその傾向が表れる
    • また、 $p$ が 0.5 から 0 もしくは 1 に偏っているほどに顕著になる
  • 下側信頼限界が負数に、もしくは上側信頼限界が 1 を超える場合がある
    • それぞれ、 $p$ が 0 に近い場合、1 に近い場合にそのような状況になる
  • 成功回数 $x$ が、$x=0$ や $x=n$ の場合は、信頼区間を求めることができない (幅が 0 の区間になる)
    • クリック数が 0、もしくはインプレッション数に等しい場合が該当する

Clopper-Pearson (or 'Exact') confidence interval

$$\left[1 + \frac{n-x+1}{x F_{2x,2(n-x+1),1-\alpha/2}} \right]^{-1} < p < \left[1 + \frac{n-x}{(x+1)F_{2(x+1),2(n-x),\alpha/2}} \right]^{-1}$$

($F_{n,m,z_{\alpha/2}}$ は、自由度 $n,m$ の F 分布における右側 $100\alpha$ 点)

Wald confidence interval は正規分布で近似することで信頼区間を求めていましたが、サンプルサイズが小さい場合や $p$ が 0 もしくは 1 に偏っている場合は正規分布での近似が難しくなります。その代わりに、F 分布を用いることで正確な (?) 信頼区間を求めることができるそうです。

  • サンプルサイズが小さくても、求まる信頼区間は Wald confidence interval のように狭くはなく、比較してカバレッジがよい
    • むしろ逆に、ちょっと広すぎる…

Wilson (or 'Score') confidence interval

$$\left( \hat{p} + \frac{z_{\alpha/2}^{2}}{2n} \pm z_{\alpha/2} \sqrt{[\hat{p}(1 - \hat{p}) + z_{\alpha/2}^{2} / 4n] / n} \right) / (1+z_{\alpha/2}^{2}/n)$$

Wald confidence interval も Clopper-Pearson confidence interval も、それぞれ信頼区間の幅については狭かったり広かったりしてちょっと扱いづらいわけですが、Wilson confidence interval ではその点においてバランスがとれた幅の信頼区間が求まるようです。

  • 数式が複雑である
    • 実装する際にエンバグしやすい ※参考
  • 得られる信頼区間は狭すぎず、広すぎず
  • サンプルサイズによらず、$p$ が 0 もしくは 1 に偏っている場合に信頼区間が狭くなる傾向がある

Adjusted Wald confidence interval / Agresti-Coull confidence interval

$$\tilde{p} \pm z_{a/2} \sqrt{ \tilde{p} (1 - \tilde{p}) / \tilde{n}}$$

$$(\tilde{n} = n + z_{\alpha/2}^{2},\ \tilde{p} = \frac{1}{\tilde{n}} \left(x + \frac{z_{\alpha/2}^{p2}}{2} \right) )$$

Wald confidence interval はサンプルサイズが小さい場合に信頼区間の幅が狭く、結果としてカバレッジが低下する問題がありました。一方でこの Adjusted Wald confidence interval では、信頼係数 $\alpha$ から定まる $z_{\alpha/2}$ を用いて $n,x$ を調整し、 $\tilde{n}, \tilde{p}$ を算出しています。そして、この $\tilde{n}, \tilde{p}$ を用いて、Wald confidence interval の式を使い、信頼区間の近似値を算出しています。

特に $\alpha$ が 0.05 の場合は adding two "successes" and two "failures" と言っているとおり、$n$ に $2 + 2 = 4$ を加え、$x$ に $2$ を加える操作をすればだいたいいい感じになってくれます。

  • 数式はまだ容易な方ではある
  • サンプルサイズが小さい場合であっても、信頼区間が狭くなるようなことはない
    • Wilson confidence interval 同様にバランスのとれた幅の信頼区間が求まる
  • 下側信頼限界が負数に、もしくは上側信頼限界が 1 を超えうる問題は健在している

クリック率・コンバージョン率の特性

ここまで区間推定方法について見てきましたが、これらを適用する先のクリック率やコンバージョン率の特性についても見ておきましょう。

  • クリック率
    • サンプルサイズ (インプレッション数) は十分な大きさとなる
      • コンテキストを考慮した CTR を算出する場合はその限りではない
    • 値は常に小さな値になりがちで、0 に近くなる
      • 1% に満たないことも十分にあり得る
  • コンバージョン率
    • サンプルサイズ (クリック数) が小さいことがある
    • 値はまちまちで、一桁 % のときもあれば二桁 % になることもある
  • 共通して言えること
    • 0% となるケースを考慮するべき

現時点での推測

長々と書いてきましたが、上記をふまえると、クリック率やコンバージョン率の区間推定には Agresti & Coull の Adjusted Wald confidence interval を利用するのがよいのではないか、と考えられます。

ただ厳密には、クリック率・コンバージョン率の特性を想定したテストケースをいくつか用意して、実際のカバレッジを測定するシミュレーションをしてみないことには胸を張って「○○ がいい!」とは言えないかな… と思います (シミュレーションは次回のブログエントリに書く予定)。

参考文献

本ブログエントリは、主に以下 2 つの論文で述べられている内容をまとめたものとなっています。より詳しく知りたい方はこれらの論文を読まれることをおすすめします。

1:08No comments

2014-12-18

#JJUG ナイトセミナー「機械学習・自然言語処理特集!」で Java でカジュアルに機械学習する話をしてきました

はじめに

@making さんからオファーをいただいて、12/17 (水) の JJUG ナイトセミナーで Java でカジュアルに機械学習するお話をしてきました。

Java というコミュニティ的に機械学習ガチ勢の方が圧倒的に少ないことが予想されたので、あんまり小難しい技術の話は含めず初学者向けの内容構成とし、機械学習をシステムに組み込んでいく上でこれは大事だよね… と個人的に思っているポイントを整理してスライドにしていったら、文字が多くなってしまった上に若干エモくて Java 的な話がほんのり程度になってしまったのが今回の反省点です。

なお講演時の動画が YouTube にアップロードされています ので、より詳しい話を知りたい場合はこちらをご覧ください。

Java と機械学習

Java で動く機械学習ライブラリ・フレームワークはわりと数多あって、でも Java で機械学習を利用する際のワークフローをすべてカバーするのがいいかというとそんなことはない、と私は考えています。

特に、モデルを作る際の feature enginnering やそのモデルの評価など、試行錯誤的に・繰り返し手早く実行したい操作については、Java のソースコードをコンパイルして一連の処理を最初から実行する… みたいなことをするよりも、R や IPython (Notebook) などを使ってインタラクティブ・アドホックな操作ができたほうが断然効率がいいのではないでしょうか (僕は R も IPython もほとんど使ったことないので、この辺りは僕の主観が色濃く出ています…)。

じゃあ Java で機械学習する価値がないか、というとそんなことはなくて、何だかんだで Java のコードはそこそこ速く動いてくれるので、サービス的に速度・レイテンシ的な要求がある場合や、機械学習を組み込もうとしているシステムが Java で作られているならば機械学習の部分も Java で統一したい… など主にシステム化以降のところで Java の機械学習を活用するのがいいんじゃないかと思っています。

指標値・メトリクスを設定して機械学習を活用する

これは懇親会の席でとある方から伺ったお話にもあったのですが、ビジネス的 or 精度的なメトリクスを設定せず、ただ何となく流行っているから的な理由で機械学習を導入する… という話をちらほらと耳にします。

わりと身近なレコメンデーション一つをとっても、そのレコメンデーションによって全体の売上が何 % 向上したのか、みたいなビジネス上の指標値を設定することは可能だと思います。そのような指標値をせずに機械学習を導入してしまうと、それはチューニングはできない・機械学習アルゴリズムをおいそれと変更することもできない、ただただ辛みのつまったパンドラの箱に成り下がってしまうので、僕の身の回りでこういうことにならないように、気をつけないといけないよなー、と思った次第でした。

まとめ・感想

JJUG 主催のセミナーにはいままで聴講者としてたまに顔を出していましたが、まさか機械学習のネタで登壇する日が来るとは思ってもみませんでした (以前の納涼 LT 大会にスピーカーとしてエントリしたものの、会社イベントを優先する必要があって止む無く断念したこともありましたが…)。

JJUG は渋谷java ほど カジュアル (= 自分の好き勝手・気ままに話したいことを話す) なコミュニティではないので、発表する内容は理解を優先した構成にしてみました。その分、「この内容は果たして聴講者に伝わるんであろうか」とヤキモキしたりすることもあって、久々に資料作りで消耗しました。でも楽しかったですね!

2:13No comments

2014-12-13

第九回 #渋谷java で飛び入り LT してきました (Slack 用 Logback Appender を実装する話)

はじめに

会社の合宿予定が入っていて参加できそうになかったので、やむなく参加を見送っていた 12/13 (土) の 第九回 渋谷java でしたが、思ったより早く東京に戻ってくることができたので、下記のように

と参加できそうなのかつぶやいてみたところ、カジュアル無茶ぶりコメントをたけぞー先生よりいただいたので適当にネタをでっちあげて LT 発表してきたのでした。

SmartNews ♥ Slack

@amachino さんが先日 Slack の Advent calendar に投稿したとおり、スマートニュースでは 社内のコミュニケーションに Slack を活用しています。 通常の人同士の会話だけでなく Jenkins からの通知や Datadog からのアラートなども Slack に集約しており、普段扱っているコミュニケーションツールの中でも特段利用時間が長い状況になっています。

そのため、「プロダクション環境で動いている Java アプリケーションの実行状況・進捗や、例外が発生したときの詳細を Slack 経由で見たい・知りたい」という要望が Java エンジニア的には自然と沸き起こってくるわけです。

Logback の Appender を実装する

そういうわけで、Java アプリケーションからお手軽に Slack にメッセージをポストする方法として、Logback の Appender 実装を用意する方法を紹介しました。

プロダクション環境で利用するにあたって、HTTP(S) 経由で Slack API を呼び出す際に

  • ロガーメソッドを呼び出す元の実行をブロックしないように (すぐに制御が戻るように) 非同期処理する
  • 非同期処理で Slack API を叩くにしてもログのイベントが前後するのは嫌なので (Array)BlockingQueue を使ってログイベントを直列化する
  • HTTP 通信で失敗したときのためにリトライ処理を入れる

などの仕組みを入れ込んだ実装としています (発表中にお見せしたコードはまだ整備しきれていないので現在は非公開としていますが、いずれ公開する予定です)。

会場参加者からのツッコミ

これは発表の際に java-ja から来られた方 からいただいたツッコミなのですが、Appender 内部で非同期処理をする場合は、 ContextAwareBase クラス (AppenderBase クラスの親クラス) が context フィールドで保持しているオブジェクトの Context#getExecutorService() メソッドの戻り値を使って、その ExecutorService オブジェクト経由でスレッドを立ち上げるといいそうです。

まとめ・感想

  • Logback の Appender 実装はツボさえ押さえれば、あんまり難しくないよ
  • Logback のインタフェースで Slack API を叩けるようになれば、Logback 使っている既存の Java アプリケーションなら容易に Slack に通知を出せるようになるね!
  • java-ja から来た人、ちょっとコワイけど、丁寧な説明だったりアドバイスをいただけたりと、とっても親切だね!
19:441 comment

2014-10-22

僕の Redshift の圧縮エンコード使い分けメモ

最近 Redshift を触っていて、圧縮エンコードについて調べることがあったのでメモメモしておきます。なお、2014 年 10 月時点での情報であることと、わりとざっくりとした確認だったので不正確な情報が混じっているかもしれないのでご承知おきください。

文字列データ (VARCHAR など)

  • 選択肢としては、 text255, text32k, bytedict, lzo あたり
    • 空間効率的には text255 text32k はあんまりよろしくなさげ
    • また、text255 はカラムサイズが 255 を超えるカラムに適用することができない (厳密には、255 バイトを超える文字列が入っている場合に適用できない、となる)
  • 値の種類数が少なく (目安として、256 個以下ぐらい)、かつ種類が増える可能性が低い場合
    • bytedict もしくは lzo を選ぶのがよい
    • 種類数が 256 を超える場合であっても、出現頻度に偏りがある場合は bytedict を選択するのもありっぽい
    • ただし、文字列の平均長が長い場合は bytedict はあんまり性能よろしくない?
  • 最初は値の種類数が少ないが、時間経過とともに使われる値の種類が徐々に増える場合
    • lzo を選ぶのがよい
  • 時間経過とともに使われる値の種類が増えるが、ソートキーを考慮すると使われる値の種類が少数に限定されると想定できる場合
    • lzo を選ぶのがよい
  • 値の種類数が多い場合
    • lzo を選ぶのがよい

というわけで、迷ったら lzo を選べばだいたいいい感じだと思う。

数値データ

  • 選択肢としては、 bytedict, delta/delta32k, mostly8/16/32 あたり
    • lzo はあんまり向いてなさげ
  • 値の種類数が少なく、かつ種類が増える可能性が低い場合
    • 0 付近の値が頻出する場合は mostly8 を選ぶのがよい
    • それ以外では bytedict を選ぶのがよい
  • 時間経過とともに使われる値の種類が増えるが、ソートキーを考慮すると使われる値の種類が少数に限定されると想定できる場合
    • bytedict でよさそう
  • 値の種類数は多いが、出現する値に偏りがある場合
    • 0 近辺に偏っているなら、 mostly8/16/32 などを選ぶのがよい
    • それ以外なら bytedict がよさそう
  • ソートキーを考慮したときに値が昇順に並ぶ場合
    • delta/delta32k を選ぶのがよい
  • それ以外の場合
    • 諦めて、圧縮エンコードは設定しない (raw にする)

正直言って、数値データは実際のデータで性能を確認してみないとわからないと思う…

その他

  • runlength の使いどころがよくわからない…
  • 時間計算量
    • bytedict は時間計算量ちょっと高めな傾向がみられる
    • lzo はバランスがとれている感じ
9:30No comments

2014-09-21

第八回 #渋谷java にて、認証系を Java 8 で自作する話をしてきました

はじめに

毎回、他の発表者の方々が有益情報を発表してくれる中で僕一人が誰得情報をひたすら発信しているわけですが、今回もご多分に漏れず Java 8 で認証系を自作する、というニッチな話をしてきました。

昨今のパスワード流出系のセキュリティインシデントが業界内で話題になるたびに「認証系なんてものは自作するようなもんじゃない」という認識が醸成されつつあると思います。しかし、マイナー or オレオレ Web アプリケーションフレームワークなどを利用しているとそうもいってはおられず、認証系が用意されていないときはやむなく認証系の自前実装が要求されることもあるでしょう。自分自身も周りを見渡していても、過去何度かそういうことがありました。

ただ、実装者の認証セキュリティに対する認識や知識によって脆弱な認証系を作り込むことも少なくなく、そういうのをなるべく減らしたいなー、という思いを込めて今回の発表に至りました。

どうしても認証系を自前実装しなければならないときに気をつけたいこと

前述した発表資料に書いてあることにはなりますが、今一度文章に起こしておきます。

アカウント別 salt の生成と暗号論的擬似乱数生成器の利用

セキュリティを少しかじったことがある人であれば「salt ってやつとパスワードを組み合わせたものをハッシュする」ということぐらいは知っているものと思います。ただ、どうも salt だけがひとり歩きしていることがあったりして、アプリケーションで共通の事前に用意された salt を使いまわす、みたいなアレな実装を見たことがある人はそこそこいるんじゃないでしょうか?

本来は、認証単位であるアカウント別に salt を生成すべきであり、かつ salt の生成には暗号論的擬似乱数生成器を用いるべきです。この salt の生成を Java で実現するならば、

    static byte[] newSalt(int length) {
        try {
            byte[] result = new byte[length];

            SecureRandom.getInstance(
                    // "NativePRNGNonBlocking"
                    // "NativePRNGBlocking"
                    "SHA1PRNG"
            ).nextBytes(result);

            return result;

        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException(e);
        }
    }

のような実装になることでしょう。 SecureRandom.getInstance() の呼び出しで指定しているのは擬似乱数生成アルゴリズムで、Java 7 以前は SHA1PRNG だけだったのが、Java 8 では新たに

  • NativePRNG
  • NativePRNGBlocking
  • NativePRNGNonBlocking

が (Windows を除く) *nix-like なプラットフォーム向け JRE にて導入されたようです。

暗号学的ハッシュ関数の利用とストレッチング

salt を生成したら、あとはパスワードと組み合わせてハッシュ化、なのですが、これも単に SHA-* を使えばいい、というほど簡単ではありません。

結論から言ってしまえば、PBKDF2 などのキー派生 (導出?) 関数を使ってストレッチングすべき、となります。

Java 7 では PBKDF2 の実装は PBKDF2WithHmacSHA1 しか用意されていませんでしたが、Java 8 にて

  • PBKDF2WithHmacSHA224
  • PBKDF2WithHmacSHA256
  • PBKDF2WithHmacSHA384
  • PBKDF2WithHmacSHA512

の 4 つが導入されました。この PBKDF2 を用いたパスワードのハッシュ化コードは以下になります。

    static byte[] hash(String password, byte[] salt, int numIterations, int numHashLength) {
        PBEKeySpec keySpec = new PBEKeySpec(password.toCharArray(), salt, numIterations, numHashLength);

        SecretKeyFactory factory;
        try {
            factory = SecretKeyFactory.getInstance("PBKDF2WithHmacSHA512");

        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException(e);
        }

        try {
            return factory.generateSecret(keySpec)
                    .getEncoded();

        } catch (InvalidKeySpecException e) {
            throw new RuntimeException(e);
        }
    }

まとめ

なんだかんだ書いてはいますが、やっぱり僕含めて素人は認証系の実装をするのはやめたほうがいいですね (過去何度もダメな認証系を作ってしまったし…)。

既存ライブラリの Apache Shiro とか Spring Security とか、僕は使ったことないですが、多分このあたりの面倒なお仕事をこなしえくれるのではないでしょうか。

なお、

こういうライブラリもあるようですよ!

参考文献

2:52No comments

2014-09-17

"Can't connect to MySQL server on 'HOST_NAME' (111)" のエラーが出たときの原因の一つと対処法

VM 上の Ubuntu に apt-get で mysql-server-5.6 をインストールし、VM の外から VM 内部の mysqld に接続しようとしたときにこのエラーが発生した。

原因は my.cnf に

bind-address = 127.0.0.1
が設定されていたためであった。

この行を my.cnf から削りとって、ようやくVM 外部から mysqld に接続できるようになったけど、毎回こんな感じのトラブルで時間を喰われてしまっているわけで、MySQL 力が低いと何かと生きるのが辛い…

23:59No comments

2014-09-15

Java のプロパティファイルは UTF-8 エンコーディングで記述したい

「えーマジ native2ascii!?」「プロパティエディタプラグインが許されるのは J2SE 5.0 までだよねー」

ジャバエンジニアはそろそろ、プロパティファイルを扱う場合に native2ascii やら各種プロパティエディタプラグインやらの呪縛から解放されてもいいと思うのです…

概要

Java でアプリケーションの各種設定を記述したプロパティファイル (.properties) を取り扱う場合、 Properties クラスもしくは ResourceBundle クラスのお世話になるかと思います。

一昔前までは、プロパティファイル内で日本語などいわゆるマルチバイト文字を含む場合に、 native2ascii コマンドを利用して ASCII コードの文字のみで表現できる ユニコードエスケープ (!= UTF-xx エンコーディング) 表現に変換することが必要とされていました。

しかし、Java は 7 or 8 がメインストリームになり、また UTF-8 エンコーディングされたテキストを取り扱うことがわりと当たり前になりつつある昨今、いまだに Eclispe にわざわざプロパティエディタプラグインを導入してプロパティファイルをしこしこ編集したり、プロダクション環境でユニコードエスケープされたプロパティファイルを四苦八苦しながらパラメータ調整したりする現場があったりなかったりするようなので、ここで native2ascii とかプロパティエディタプラグインを必要と せずに UTF-8 エンコーディングされたプロパティファイルを扱う方法についてメモしておきます。

UTF-8 エンコーディングされたプロパティファイルを取り扱う方法

Properties クラスと ResourceBundle クラスそれぞれについて説明します。

その 1 : Properties クラスを使う場合

Properties#load(Reader) メソッドを呼び出す際の Reader オブジェクトを、UTF-8 エンコーディング指定した InputStreamReader オブジェクトにすれば OK です。

すなわち、以下のような実装になるでしょう。

その 2 : ResourceBundle クラスを使う場合

こちらは若干複雑になりますが、 ResourceBundle.Control クラスのサブクラスを用意して対処する方法をとります。

同クラスの newBundle() メソッドのオーバーライド実装にて、 Properties のときと同様に UTF-8 エンコーディング指定した InputStreamReader オブジェクトを用意し、 PropertyResourceBundle クラスのコンストラクタ引数にそのオブジェクトを指定します。

そして実際に ResourceBundle クラスのオブジェクトを取得する際に、その ResourceBundle.Control サブクラスのオブジェクトを ResourceBundle.getBundle(String, ResourceBundle.Control) メソッドの二つ目の引数に指定してやることで、UTF-8 エンコーディングなプロパティファイルを取り扱うことができるようになります。

実装は以下のとおり。

まとめ

  • Properties も ResourceBundle もどちらも、文字エンコーディング指定した InputStreamReader オブジェクトを扱うようにすれば、 native2ascii 的な呪縛から逃れることができるよ
  • UTF-8 エンコーディングなどにしておけば、プロダクション環境上でプロパティファイルをどうしても確認しなきゃいけなくなった場合でも、プロパティファイルに記述した日本語コメントを頼りにスムーズな確認ができるようになるよね
  • プロパティエディタプラグインはもうオワコン扱いでいいよね
23:173 comments

2014-09-11

Java 8 で Base64 エンコーディング機能が導入されたらしいので使ってみた

「何をいまさら」な感じの機能追加だけど、Java 8 から 標準のクラスライブラリで Base64 エンコーディング できるようになった。これはこれで嬉しいことなので、使い方とそのパフォーマンスをメモっておく。

使い方

まずはデモコードから。

エンコーダは以下のメソッド呼び出しで得られる 3 つの種類がある。

  • Base64.getEncoder()
  • Base64.getUrlEncoder()
  • Base64.getMimeEncoder()

対応するデコーダがそれぞれ用意されている。

  • Base64.getDecoder()
  • Base64.getUrlDecoder()
  • Base64.getMimeDecoder()

Base64.getUrlEncoder() で得られるエンコード文字列は、普通の Base64 エンコーディングではファイルパスや URI での利用時に問題となりうる +/ の文字の代わりに -_ を使ってエンコードしてくれる。「Base64 エンコーディングした文字列をファイル名に利用したい!」みたいなケースだととっても有用だと思う。

パフォーマンス

Java 7 以前は Apache Commons Codec の Base64 クラス を使うことが一般的だったぽいので、それとの性能比較をしてみた。

今回は、メソッド呼び出しにおけるオーバーヘッドを見るスイート (上段) と、Base64 の変換処理の性能を見るスイート (下段) の二種類を用意した。

この結果から、

  • 全般的に、Java 8 で導入された Base64 クラスの方が処理性能的に優れている
  • 特に、Java 8 側の変換メソッドを呼び出す際のオーバーヘッドが Commons Codec のそれより明らかに小さいことがわかる
  • 変換処理の性能は、エンコーディングが 6 倍程度、デコーディングが 2 倍ちょっと、Java 8 の Base64 クラスの方が速い

ということがわかるかと思う。

なお、性能測定に用いたプログラムは以下のとおり。

まとめ

  • Base64 だけについて言えば、Commons Codec はその役目を終えた感がある
  • これからは Java 8 の Base64 を積極的に使うのがよさそうだね!
1:381 comment