2021-04-01

Javaはメソッド内のローカル変数の個数が65534個までならコンパイルできる

JVMの仕様書の4.11節に，

The greatest number of local variables in the local variables array of a frame created upon invocation of a method (§2.6) is limited to 65535 ... (メソッド呼び出し時に生成されるフレームは local variables arrayを持っており，そこにローカル変数が含まれていますが，そのローカル変数の個数は最大で65535個に制限されています．)

と書いてあったので，実際のところメソッド内でローカル変数は幾つまでならコンパイルできるのか，調べてみます．

docs.oracle.com

メソッド内に定義できるローカル変数の最大の個数を調べる

今回は AdoptOpenJDK 16.0.0.hs を使います．

指定した個数のローカル変数定義を含むようなJavaコードを，以下のpythonの簡単なスクリプトで生成します．

gist.github.com

ではまず，65535個のローカル変数定義を含む場合です．

$ mkdir main
$ python make_code_with_many_local_variables.py -n 65535 --out main/Main.java && javac main/Main.java && java main.Main
main/Main.java:5: エラー: ローカル変数が多すぎます
    public static void main(String[] args) {
                       ^
エラー1個

確かにコンパイルエラーが出ます．

次に，一つ減らして65534個の場合を試してみます．

$ python make_code_with_many_local_variables.py -n 65534 --out main/Main.java && javac main/Main.java && java main.Main
hello, world!

コンパイルが通り，実行も出来ました．メソッド内では65534個までローカル変数を定義できるようです．

仕様書よりも一つ数が小さい件については，現在調査中です． local variable arrayの一つは，メソッド内のローカル変数以外に使われているのかなと想像しています．

2021-03-31

ベータ版が出たSpring Nativeを動かしてみた

Spring Nativeのベータ版が出たとのことだったので，公式リポジトリに含まれるサンプルを動かしてみました．

Spring Nativeとは

Spring Nativeは，Springアプリケーションのコンパイル，ネイティブバイナリの作成を可能にするというものです．ネイティブバイナリ化により，遅いといわれることの多いSpringアプリケーションの起動が高速になることが期待されます． AWS LambdaなどサーバーレスにSpringを使いたい場合，特に便利そうです．コンパイルにはGraalVMのNative Image機能を用いています．

www.publickey1.jp

なお，Spring Nativeと同じようなモチベーションを持つのがQuarkusのようです．

あれ、Spring BootもNativeにできるようになったの? Quarkusと思い切り競合しそう
— id (@ido_kara_deru) 2021年3月26日

動作環境

OS: Ubuntu 20.04
CPU: Intel Core i7-7500U CPU @ 2.70GHz 4コア
メモリ: 16GB

Spring Nativeのサンプルを動かす

公式のリポジトリからコードを落としてきます．

$ git clone git@github.com:spring-projects-experimental/spring-native.git
$ cd spring-native

今回はSpring MVC+Tomcatによるサンプルを動かしてみます．

$ cd samples/webmvc-tomcat

READMEに従い，以下のとおりコンパイルします．Dockerイメージまで作成してくれるようです．

$ mvn spring-boot:build-image

手元の環境ではコンパイルに約3分半かかりました．

リポジトリに docker-compose.yml が含まれているので， docker-compose コマンドで起動します．

$ docker-compose up

立ち上がっているか確かめてみます．

$ curl localhost:8080
Hello from Spring MVC and Tomcat

確かに立ち上がっています．

起動時間の比較

最後に，通常に起動した場合と，Native Image化して起動した場合で起動時間を比較してみます．なお起動時間は，Spring Bootの起動メッセージに表示される値を使っています．

通常	Native Image化
1.065s	0.046s

約20倍起動が高速になっているようです．このぐらい早くなると，サーバーレスで使う場合は大分ご利益がありそうです．

今回はあくまでサンプルの簡単なアプリケーションでしたが，もっと大規模で複雑な場合はどの程度高速化されるか，既存のSpringアプリケーションをSpring Nativeに対応させるにはどの程度コストがかかるのか，気になるところです．ベータが取れたバージョンのリリースも楽しみです．

2020-12-31

「情報検索：検索エンジンの実装と評価」１1章融合・メタ機械学習

「情報検索検索エンジンの実装と評価」Advent Calendar 23日目の記事です． adventar.org 本記事では，11章「融合・メタ機械学習」についてまとめます．

11章「融合・メタ機械学習」で扱う内容って？

一言で言えば，「アンサンブル学習」と「ランキング学習」です．

複数のモデルの出力を統合したモデルを考えることで，よりよい性能を得ようとするのが「アンサンブル学習(ensemble learning)」です．本章では，具体的な手法として 融合（凝集） ， スタッキング ， バギング ， ブースティング について扱います．

ランキング学習(learning to rank, LTR)は，結果がはっきりしているランキング例を用いて，ランク付け関数を学習するような手法です．クエリを入力とし，順序付きの検索結果を出力するモデルを作成したいときなどにも，ランキング学習は用いられます．

検索結果の融合

複数の出力を統合する一番シンプルなアプローチとして，複数の検索エンジンから返されるドキュメントリストをひとつに統合する検索結果の融合(search-result fusion)があります．検索結果の統合は， 固定カットオフ検索 , ランク凝集 , スコア凝集 の3つに分けて考えることが出来ます．

固定カットオフ検索

固定カットオフ検索は，それぞれのリストからの固定数のドキュメントが考慮される方法です．各リストにおけるドキュメントのランクは考慮しません．一番シンプルな方法として，それぞれのリストを投票とみなして，投票数が多い上位のドキュメントを選択する方法があります．

ランク凝集・スコア凝集

ランク凝縮はそれぞれのリストにおける各ドキュメントのランクを考慮する方法，スコア凝縮はそれぞれのリストの各ドキュメントのスコアも考慮する方法です．具体的なランク凝縮の方法として，逆順位融合(reciprocal rank fusion(RRF))があります．RRFでは，以下の式で表されるスコアでドキュメントを並べます．

$RRF_{score} = \sum_i \frac{1}{k + r_i ( d ) }$

ここで，dはドキュメント,iは統合するリストの添字， $r_i(d)$ はリストiにおけるドキュメントdの順位の逆数で，kは適当な定数です．要は，逆数順位の調和平均（逆数で平均をとって，さらにその逆数をとったもの）のようなものです． kとしては60を使うと良好な結果が得られることが知られているそうです．

スタッキング適応フィルタ

スタッキング (stacking)とは，メタ格付け器(meta-classifier, メタ識別器)を作成して，モデルの組み合わせ方もメタ識別器に学習させよう，という方法です． kaggleなどのデータ分析コンペでも，特性の異なる複数のモデルを組み合わせ，汎化性能を得るための手法として頻繁に用いられています．

本節では，メーラーに付随しているスパムフィルタのように，逐次モデルが更新されている適応フィルタを題材とし，スタッキングが説明されています．

バッチ格付け器のスタッキング

本節では，バッチ格付け器のスタッキングの際に問題となる，学習データと，実際に評価する本番のデータとの分布のズレについて扱っています．バッチ格付け器(batch classifier, バッチ識別器)は，11.2節のスパムフィルタのように逐次的にモデルがされない，学習データによって一度だけが学習されるような場合での格付け器を指します．このような場合，格付け器をスタッキングしようとすると，スタッキングされたモデルが学習データに過適合してしまい，本番環境で思ったような性能が出ない問題が置きがちです．

格付け器の過適合を避ける方法のひとつとして． ホールドアウト検証があります．これは，データを学習データTと，ホールドアウト集合（holdout set）または検証集合(validation set)Vの二つにわけ，Tを各モデルの学習に使い，Vを検証に使う，というものです．

より正確な検証方法として，交差検証(cross validation)もあります． k分割交差検証では，データをk個の集合に分割した後，ひとつを検証集合，残りを学習データとして，k回検証を繰り返します．

バギング

ブートストラップ凝集 (bootstrap aggregating)または バギング(bagging)とは，学習データLから重複を認めてサンプリングをしてブートストラップ訓練集合 $T_i$ を作り，それぞれのブートストラップ訓練集合 T_i ごとにモデルを作成したのち，それらを統合したモデルを得る方法です．

一般に，学習データLを単純に分割してT_iを作り，それぞれでモデルを作って統合することには，ほとんどメリットはありません．ひとつの大きな集合でT=Lで訓練すれば，同等の効果を得られるためです．バギングのミソは重複を認めてサンプリングして訓練集合を作っていることで，これによりブートストラップ集合はデータの母集団のよい近似になります．

バギングの代表的なアルゴリズムとしては，決定木を用いたランダムフォレストが挙げられます．

ブースティング

ブースティング (boosting)は，k番目の学習器で間違えたデータを，次には間違えにくくなるよう，各ドキュメント（学習データ）の重みを変えてk+1番目の学習器を学習し，最後にすべての学習器を統合する手法です．

バギングは汎化誤差を最小化するためにランダムに訓練データを操作しますが，ブースティングは学習誤差を最小化するために系統的に訓練データを操作します．ブースティングでもバギングでもよい分類機を生成できますが，基礎となる仮定はかなり異なっています．

ブースティングの代表的なアルゴリズムとしては，カメラの顔認識にも用いられているAdaBoostや，近年幅広く用いられているGBDT(gradient boosting decision tree, 勾配ブースティング決定木)などがあります．

「情報検索：検索エンジンの実装と評価」１2章有効性の評価

「情報検索検索エンジンの実装と評価」Advent Calendar 14日目の記事です． adventar.org 本記事では，12章「有効性の評価」についてまとめます．

有効性の評価とは

まず，そもそも「有効性(effective)」とは何かですが，ここでは「検索結果の品質」のことを指します．検索エンジンがあったとき，そのシステムによる検索結果の品質をどう評価するか，というお話です．

なお，情報検索システムの評価に関する本としては，以下の和書があります．

https://www.amazon.co.jp/dp/4339024961

12.1 伝統的な有効性評価指標

まず，基本となる評価指標として， 適合率 再現率 P@k 検索結果の上位k件の適合率(P@k) 平均適合率 逆数順位 があります．これらの情報検索における伝統的な評価指標は，評価に際して以下のような仮定をおいています．

ユーザーの情報要求があり，それらが検索クエリで代表され，与えられたドキュメントコレクションのそれぞれのドキュメントは，その情報要求に対して関連，非関連のどちらかである．
ドキュメントdの関連性は，その情報要求とドキュメントdだけに依存する．ドキュメントコレクション中に存在する他のドキュメントに対する検索エンジンのランキングとは独立である．

シンプルですが，納得できる仮定だとは思います．このようなモデルの本で，以下のような伝統的な評価指標が定義出来ます．

再現率と再現率

再現率(recall) は，検索結果が，実際に関連のある文章のうちどの程度拾えているか，を示す割合です．検索結果の文章の集合を Res , 実際に関連がある文章の集合を Rel と書くと，以下の用に数式で書けます．

$recall = \frac{|Res \cap Rel |}{ |Rel|}$

ただし，再現率は，極端な話，すべての文章を検索結果として出してしまえば，100%になってしまいます．そのため，検索結果のうち，関連ある文章はどの程度か，を示す割合である 適合率(precision) が用いられます．数式で書くと以下のようになります．

$precision = \frac{|Res \cap Rel |}{ |Res| }$

検索結果の上位k件の適合率(P@k)

単純な適合率は，暗黙のうちに，ユーザーが検索結果を全件目を通す，という仮定をおいています．しかし，実際に私たちが検索エンジンを使うときを想像してみると，普通は検索結果の上位数件に目を通すだけだと思います．そのようなケースを考慮したのが 検索結果の上位k件の適合率(P@k) です．

平均適合率

P@k を求める時，kを幾つにするか，というのは悩ましい問題です． 平均適合率(Average Precision) は， P@k をある種のルールのもとで平均を取ることで，この問題を解決しようとしたものです．

$AP = \frac{1}{|Rel|} \sum^{|Res|}_{i=1}{ relevant(i) \cdot P@i }$

ここで， $relecant(i)$ は，上からi番目の検索結果が関連あるドキュメントなら1，関連のないドキュメントなら0を取ります．つまり，平均適合率は， k件目の検索結果が関連ある文章であるような P@k の和を取って，関連あるドキュメントの数で割った値になります．

平均適合率は，ある文章が含まれないという情報を，その文章対応する適合率が0であるという形で計算することで含んでいます．そのため，平均適合率は，暗黙的に再現率の情報を含んでいると考えることも出来ます．

逆数順位

今まで見てきた評価指標は，検索結果がどのような順番で並んでいるかを，そこまで気にして来ませんでした．しかし，私たちが検索エンジンを使う時，欲しい情報がどのぐらい早く結果として出てくるかは重要です．

逆数順位(reciprocal rank (RR)) は，関連する文章がどれだけ早く結果として表示されるかを評価する指標です．数式で書くと以下のようになります．

$RR = \frac{1}{ \min ( k | Res k \in Rel ) }$

ようは，関連する文章がk件目 に初めてでてきた時，逆数順位は 1/k です．ここで逆数順位は，ユーザーはお目当ての関連する文章を1件でも見つけたら，そこで満足して検索をやめることを仮定しています．

12.2 TREC

TREC（Text REtrieval Conference, テキスト検索会議）は，情報検索分野の発展の上で大きな役割を果たしてきたワークショップです． TRECで規定された評価の方法論は，情報検索システムの評価におけるデファクトスタンダードを提供していると言っても良いでしょう．本節では，そのTRECの評価の方法論について説明します．

1. 主催者によるトピック集合とドキュメントの配布

TRECは，まず主催者がトピック集合を作成し，ドキュメントのコレクションと合わせて参加者に配布します．ドキュメントコレクションは，新聞や雑誌の記事といった，専門家によって書かれたドキュメントからなります．また，トピックには，Web検索のクエリなどではよく見られるような，誤字脱字やスペルミスなどはほぼ含まれません

2. 参加者によるトピックからのクエリの生成

参加者はトピックからクエリを生成します．この際，一般的には，クエリはトピックから自動生成する必要があります．

3. 参加者による実行結果の提出

参加者は，各トピックに対するクエリをコレクション上で実行し，上位k件のランク付けされたリストを主催者に提出します．このリストはrunと呼ばれます．kは $k = 1000$ が用いられることが多いようです．

4. 主催者による評価用のドキュメント集合（プール）の作成

主催者は，参加者から受け取ったrunから，それぞれ上位k件を取り出し，その和集合を評価用のドキュメント集合（プール）とします． kとしては多くの場合 $k=100$ が用いられます．そして，このプールに対し，トピックに対して関連しているか，関連していないかの二値のラベルが人手で付与されます．これらの判断結果はqrelと呼ばれます．qrelを用い，適合率や再現率，平均適合率などといった各システムの有効性指標が計算されます．

トピック，ドキュメントコレクションとqrelは，，他の実験でも再利用できるテストコレクションとして提供されます．

12.3 統計指標を用いた評価

本節は，検索エンジンを学ぶ人のための統計学再入門，といった趣きの節です．統計学の教科書に載っているような内容が多く，また分量的にかなり多いため，本記事では割愛します．

とはいえ，実際に検索エンジンを評価するシチュエーションを想定して統計学の道具立てが説明されており，誤解・誤用しやすいポイントも説明されているため，一読の価値はあります．本節の冒頭部分には，情報検索分野において統計学の不適切な使用が少なくなく，自分のこの文章がその状況を変える一助になるように，との著者の願いが書かれています．

12.4 判断処理数の最小化

パターン認識や機械学習でいうところのアノテーションの工数を削減する話です．情報検索の場合，クエリに対して，文章が関連しているな否かという評価が与えられるため，すべての文章に評価を与えようとすると，判断処理数はクエリ数と文章数の掛け算で増えていきます．そのようなすべての文章に評価を与える徹底的な評価(exhaustive adjudication)は，昨今のデータ量では到底不可能です．判断処理数を削減するため，関連がありそうなドキュメントを抽出し，それらに対してのみ判断を与えることや，評価対象をランダムにサンプリングし，そこから全体の有効性指標を統計的に推定するサンプル抽出法などが行われます．

判断するドキュメントの選択

TRECで用いられているプーリング法は，各システムの上位k位までのドキュメントを集めてプールを作り，そのプールに対してのみ評価を行うことで，判断するドキュメント数を削減していました．本項では，その他判断するドキュメントの選択に関わる話題について紹介します．

相互検索と判断
- 相互検索と判断(Interactive Search and Judging(ISJ))は，熟練した検索者が検索エンジンを用い，可能な限り関連するドキュメントを検索し，ラベル付けすることで評価を行います． ISJによってより短い時間で作成されたqrelによる評価結果が，TRECの公式結果とほぼ同等であるとの報告もあるようです．
前方移動プーリング
- 前方移動プーリング(Move-to-Front Pooling(MFP))は，性能のよいシステムによって上位にランク付けされたドキュメントについて，優先的に関連性の評価を行います．
浅いプーリング
- プーリングの深さk，すなわち各システムの上位から取ってくる結果の件数kを変えるのは．判断の工数を調整する簡単な方法です．
トピック数の増減
- コレクションのトピック数nを増減するのも，判断の工数を調整する簡単な方法です．判断の工数を固定したとき，トピック数やプールの深さをどう決めるかは，ISJやMTFなどの手法でも検討が必要になります．
プーリング戦略の評価
- 二つの異なるシステムランキングは，伝統的にはケンドールの順位相関件数τを使って比較されてきました．順位相関件数τは，もし二つのランキングが同一なら $\tau = 1$ を取り，反対のランキングであれば $\tau = -1$ になります．

サンプル抽出法

プールから一部分のサンプルを無作為に抽出し，有効性指標を推定することも可能です．平均適合率の推定値（推定平均適合率, inferred average precision, infAP）は，以下のようになります．

$AP = \frac{1}{|Rel|} \cdot \sum^{|Res|}_{i=1} relevant(i) \cdot E(P@i)$

E[P@i] の部分を推定することになります．

12.5 新しい有効性評価指標

12.1節で述べられていたとおり，古典的な有効性指標は極めてシンプルな検索行動のモデルを仮定しているため，より現実的な状況でシステムの有効性を評価する上ではあまり適切でない場合も多いです．そのようなより現実的な設定のための評価指標を紹介します．

段階的な関連度

平均適合率などでは，クエリと文章の関係は関係は関連か非関連のどちらかであると仮定しています．しかし，実際は関連と非関連の間にはグラデーションがあるはずです．

nDCG（normalized Discounted Cumulative Gain, 正規化された割引累積利得） は，段階的な関連度を考慮した指標です． nDCGの計算は以下の4ステップからなります

1. 利得ベクトルの構成 検索システムが出力したランク付けされた文章のリストに対し，それぞれの文章の関連度に対応する利得(gain)を割り当てて利得ベクトル(gain vector) Gを作ります．

$G = (5, 10, 0, 5, 1, ..)$

2. 累積利得ベクトルの計算 つぎに，累積利得ベクトル(cumulative gain vector) CGを計算します．CG[k]は， k-1までのGの和です．

$CG(k) = \sum^{k}_{i=1}{G(i)}$

3. 割引累積利得の計算 順番が後にくる文章の利得を減点するようにして割引累積利得(discounted cumulative gain, DCG)を計算します．DCGは以下の式で定義されます．(以下では対数を利得の割引関数として使っているが，他の関数を使う場合もあり）

[tex: DCG(k) = \sum^{k}{i=1}{ \frac{G(i)}{\log{2}{1+i}}}]

4. 割引累積利得の正規化 最後に，割引累積利得を，最も理想的な結果が得られた場合の割引累積利得DCG'で正規化します．

$ｎDCG(k) = \frac{DCG(k)}{DCG'(k)}$

不完全で偏った関連性評価

情報検索のテストコレクションには,関連性が評価されていない文章が含まれることが多いです．慣例的には，これら未評価の文章は関連性なしとして扱われてきました．一方で，未評価の文章を単純に関連性なしとして扱ってしまうと問題があるケースもあります．例えば，Web検索サービスのように，定期的にクローリングされた文章がテストコレクションに追加されるような場合，未評価であっても関連性のある文章が存在することは大いにありえます．

このような不完全で偏った状況でも，システムランキングの安定性において比較的良好なことが報告されている指標として ランク有効性指標(rank effectiveness measure(RankEff)) があります． RankEffは，以下の式で定義されます．

$RankEff(k) = \frac{1}{|Rel|} \sum^{|Res|}_{i=1} relevant(i) 1 - \frac{|Res(1..i) \cap Non| }{ |Non| }$

ここで， Non は評価済みの非関連文章の集合です．

検索結果の新規性と多様性

古典的な評価指標が考慮していない観点として，情報の新規性と多様性があります．

新規性がある検索結果とは，列挙されている文章にそれぞれお互いに重複しないような情報が記載されている場合です．夏目漱石と検索した場合，あるページには小説家としての漱石が記載されており，またあるページには英文学者としての漱石について記されている，といった具合いです．

多様性が問題になるのは，クエリは多義性を含むような場合です．例えば，ジャガーと検索された場合，猫科の動物としてのジャガーか，車か，フェンダー社製のギターか，ユーザーがどの情報を求めているのかわかりません．このような場合，ユーザーの母集団における興味を考慮しつつ，それぞれの内容が多様に含まれる結果を出すのが望ましいと考えられます．

新規性と多様性も考慮した評価指標として，α-nDCGというのがあります． α-nDCGでは，クエリは複数の意図・情報の塊（ナゲット）からなると考えます．そして，それぞれ文章について，幾つナゲットを含んでいるをカウントしたものを利得とし，nDCGを計算します．

2020-10-15

ブログ引っ越してきました

以下よりブログを引っ越してきました．今後ともよろしくおねがいします．

mofumofuchan1.hatenablog.com

mofumofu1729の計算機日記

プログラミングの勉強メモや日々の雑記など