Averaged Perceptron

Litsea は、単語分割と品詞推定を同時に行うために Averaged Perceptron アルゴリズムによる多クラス分類を使用します。本章では、Litsea に実装されているアルゴリズムについて説明します。

概要

AdaBoost が二値分類（境界 / 非境界）を行うのに対し、Averaged Perceptron は 18 クラスの多クラス分類を行い、各文字位置に対してセグメントラベルを予測します:

• 17 個の境界ラベル: B-ADJ, B-ADP, B-ADV, B-AUX, B-CCONJ, B-DET, B-INTJ, B-NOUN, B-NUM, B-PART, B-PRON, B-PROPN, B-PUNCT, B-SCONJ, B-SYM, B-VERB, B-X
• 1 個の非境界ラベル: O（単語の継続）

これらのラベルは Universal Dependencies プロジェクトの 17 個の Universal POS (UPOS) タグに対応し、B- プレフィックスで単語境界を示します。これにより、単語境界の検出と品詞の推定を 1 つの分類ステップで同時に行えます。

アルゴリズム

重み表現

各クラスは独立した重みベクトルを持ちます。重みは疎なマップとして格納されます:

weights: HashMap<Feature, HashMap<Class, f64>>

例:

weights["UW4:猫"]["B-NOUN"] = 2.5
weights["UC4:H"]["B-NOUN"]  = 1.8
weights["UW4:猫"]["O"]      = -0.3
...

特徴量の集合に対し、各クラスのスコアは特徴量の重みを合算して計算し、最大スコアのクラスを予測ラベルとします:

score(class) = sum(weights[feature][class] for feature in input_features)
prediction = argmax(score(class) for all classes)

更新規則

各学習インスタンスについて、予測が正解と異なる場合に重みを更新します:

For each training instance (features, truth):
    guess = predict(features)

    if guess != truth:
        For each feature f in features:
            weights[f][truth] += 1.0   # 正解クラスの重みを増加
            weights[f][guess] -= 1.0   # 誤予測クラスの重みを減少

この単純な更新規則により、正解クラスの特徴量が強化され、誤予測クラスの特徴量が弱められます。これにより、将来の類似入力に対して正しい予測がより起こりやすくなります。

平均化

基本的なパーセプトロンに対する重要な改善点が重みの平均化です。最終的な重みは学習データの末尾に過適合する傾向があるため、学習中に観測されたすべての重みベクトルの平均を最終モデルとして使用します。これにより、未知データへの汎化性能が向上します。

実装では効率のために累積和アプローチを使用します:

# 各ステップの重みを累積
cumulative[feature][class] += weights[feature][class] * elapsed_steps

# 学習終了時に平均化
averaged[feature][class] = cumulative[feature][class] / total_steps

これにより、すべての中間重みベクトルを保存することなく同じ結果が得られます。この平均化により、学習データの順序への依存が軽減され、汎化性能が向上します。

エポックによる学習

学習は指定されたエポック数だけ学習データを繰り返します。各エポックでは、すべての学習インスタンスを順に処理します:

For each epoch (1 to num_epochs):
    For each instance in training data:
        features = extract_features(instance)
        predicted = argmax(score(class) for all classes)
        if predicted != correct_label:
            update weights
        accumulate weights for averaging

AtomicBool フラグにより、Ctrl+C などで学習を中断し、その時点でのモデルを保存することも可能です。

#![allow(unused)]
fn main() {
use std::sync::Arc;
use std::sync::atomic::AtomicBool;
use litsea::perceptron::AveragedPerceptron;

let mut perceptron = AveragedPerceptron::new();
// ... インスタンスを追加 ...
let running = Arc::new(AtomicBool::new(true));
perceptron.train(10, running);  // 10エポック
}

モデルファイル形式

学習されたモデルはテキストファイルとして保存されます:

18
B-ADJ
B-ADP
B-ADV
...
O
UW4:猫	B-NOUN	2.5
UC4:H	B-NOUN	1.8
UW4:猫	O	-0.3
...

• 1行目: クラス数（18）
• 続くN行: クラス名（1行に1つ）
• 残りの行: 特徴量の重み、タブ区切り 特徴名\tクラス名\t重み
• 重みがゼロの特徴量は省略

AdaBoost との比較

ハイパーパラメータ