2015-10-29

追記: 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 です。

2015-10-17

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 あたりを実装してみようかな…

2015-10-01

最適化問題、とりわけ線形計画問題が気になり始めるお年頃になってきたので、 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 ページ(整数計画法メモ)