Posts

Pegasos: Primal Estimated sub-GrAdient SOlver for SVM

Pegasosは、SVMの学習のための反復的なアルゴリズムであり、2022年3月現在、scikit-learnのSGDClassifierで学習率を更新に採用されている。 Pegasosは、目的関数の最小値の近似値をもとめる。 求める最小値との誤差を\(\epsilon\), SVMの正則化パラメタを\(\lambda\), 各サンプルの説明変数の0でない要素数の上限を\(d\)とすると、線形カーネルをつかうSVMの時間計算量は、\(\tilde{O}(d/\lambda \epsilon)\)になる。 訓練データの数が計算量に影響しないので、教師データの数に対してスケールする。

An Interior-Point Method for Large-Scale L1-Regularized Least Squares

前処理付共役勾配法により、スパースな説明変数をもつリッジ回帰の学習を高速化する。 リッジ回帰の目的関数は、凸関数だが微分可能ではない。 また、リッジ回帰の係数はスパースになりやすい。 そこで、目的関数を最小化する係数の探索を、線形不等式制約つきの凸二次計画問題とらえ、前処理付共役勾配法をつかった内点法で係数の更新方向を探索する。

Regularization Paths for Generalized Linear Models via Coordinate Descent

ラッソ、リッジ、またはその両方をくみあわせたelastictnetを正則化項にもつ一般化線形モデルの学習を高速化する座標降下法である。 座標降下法を単純に実装すると、スパースで次元数の多い特徴だと学習に時間がかかる。 表題の手法は、その単純なパラメタの更新式の一部を、説明変数の内積におきかえ、学習データの数や次元数に対して学習時間を短縮する。

Using TF-IDF to Determine Word Relevance in Document Queries(2003)

自然言語による文書検索で、TF-IDFをベースラインにつかう利点と欠点を調べた。 クエリにある各単語のTF-IDF値の総和が最大の文書を最も関連する文書とみなす。 実験では、TFのみで検索する手法よりも予測性能がよかったが、類義語同士の同一判定をできない問題があった。

An algorithm for suffix stripping (1980)

Poterのステミングで知られる。 アルゴリズムが単純で、辞書を必要としないところに特徴がある。 規則にしたがって単語の接尾辞を段階的に変換し、変換後の文字列を語幹とみなす。

Bringing GNU Emacs to Native Code

Emacs 28から利用できるlibgccjitによるネイティブコンパイルの解説である。 パッケージアーカイブELPAにあるelisp-benchmarksによる比較ではバイトコンパイルよりも2.3倍から42倍の高速化を実現した。 ネイティブコンパイル時は、はじめに、Emacs Lispのコードをバイトコンパイラで、Emacs VM(Lisp Assembly Program, LAP)の中間表現に変換する。 つぎに、LAPをS式で静的単一代入形式の中間表現LIMPLEに変換する。 LIMPLEは、GCCの中間表現GIMPLEに由来し、ネイティブコンパイルの中核技術にあたる。 さいごに、LIMPLEをlibgccjitの中間表現に変換し、GCCでネイティブに実行可能なプログラムにコンパイルする。

Data Structure for Text Sequences

テキストエディタのためのデータ構造として、array, gap, list, line pointers, fixed size buffers, piece tablesを評価する。 とくに、Piece tablesを評価し詳しく解説する。 Piece tableはテキストを2つのバッファに記録する。 2つのバッファはfile buffer, add bufferで、file bufferは初期状態のテキストを保存し、add bufferは新たに挿入される文字列を保存する追記のみのバッファである。 名前のpieceはバッファ内の連続する部分文字列を意味する。 そして、pieceへのポインタのシーケンスがpiece tableである。 ポインタは、どちらのバッファか、参照する部分文字列の開始位置、長さの3つの情報からなる。

SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS

文書の特徴を点、引用などの文書間の関係を辺であらわすグラフ構造に畳込みニューラルネットワークを適用する。 半教師あり学習であり、ラベルのない文書は近くにある文書とおなじラベルになると仮定する。 Zhu et al.の先行研究は、辺の情報をネットワークにあたず、文書の特徴のみを入力する。 表題の手法では、文書の特徴にくわえ、隣接行列で表現した辺の情報もネットワークにあたえる。 グラフの辺の数に対して線形にスケールし、隠れ層でグラフの分散表現を獲得できる。

Dynamic Routing Between Capsules (2017)

カプセルはおなじ層にあるニューロン(ユニット)のグループであり、カプセルの出力するベクトルは入力にある特定のエンティティの分散表現になる。 表題のdynamic routingは、カプセルの出力ベクトルを1つ上の層のどのカプセルに渡すべきかを学習する手法である。 これにより、プーリング層で失われるエンティティの空間上の位置情報をカプセルの出力するベクトルで表現する。 実験では、2層の畳み込み層と1層の全結合層からなる浅いニューラルネットワークをMNISTに適用し、長さでエンティティが存在する確率を、向きでエンティティの特徴を表現できるベクトルを学習できることを示した。

Hierarchical Attention Networks for Document Classification (2016)

Hierarchical Attention Network(HAN)は、単語は文から文書は文からなる文書の構造をアーキテクチャに反映し、単語の注意から文の注意を、文の注意から文書の注意を計算する。 順方向と逆方向の2つのGRUでエンコードした単語の分散表現から注意を計算し、文ごとに、単語の注意の重みつき和を計算し文の分散表現とする。 さらに、文の分散表現を別の順、逆方向GRUにあたえ、単語とおなじように各文の注意を計算し、その重みつき和を文書の分散表現としてあつかう。 最後に、文書の分散表現を全結合層に入力し、ソフトマックス関数で文書のクラスを推定する。 単語の文の注意を推定できるため、単語と文の2つの粒度で文書の重要な箇所を可視化することができる。