アルゴリズム解説
機械学習の予備知識は要りません。「重みを掛けて足す」ところから始めて、 このプロジェクトで使っている 5 つのアルゴリズムがそれぞれ何を保証しているのかまで たどり着きます。数式は出てきますが、すべて日本語で言い換えを付けています。
1. 解いている問題
毎時間、電力需要を予測する仕事を任されたとします。手元には 30 人の予測担当者がいます。 ある人は「1 時間前と同じ値」と言い、別の人は「昨日の同じ時刻と同じ値」と言い、 また別の人は「直近 24 時間の平均」と言います。この担当者たちを Expert と呼びます。
あなたの仕事は、この 30 個の意見から 1 つの予測を作ることです。 そして 1 時間後には正解が分かるので、誰が当たって誰が外したかを見て、次の予測に活かせます。 これを延々と繰り返す — この設定を オンライン予測（online prediction）、 なかでも Expert の助言を使うものを Prediction with Expert Advice と呼びます。
Expert 自身を賢くする話ではありません。与えられた Expert 群をどう混ぜるかだけを考えます。 だからこそ、Expert が何であっても（統計モデルでも、深層学習でも、人間の勘でも）同じ理論が使えます。
2. まず素朴に：全部平均する
いちばん簡単なのは 30 人の予測を単純平均することです（Equal Weight）。 悪くない出発点で、実際に多くの場面で単一モデルより安定します。しかし弱点があります: 明らかに的外れな Expert が 1 人いるだけで、平均が引きずられるのです。
このプロジェクトの Expert 群には「直近 168 時間の平均」のように、 急変時にはまったく当たらないものも含まれています。実験では等重み平均が 最良の Expert より 2〜3 倍悪い結果になりました。 当たっている人を重く、外している人を軽くしたい — これが Hedge の動機です。
3. Hedge：当たっている Expert を重くする
各 Expert に重み \(w_i\) を持たせます。最初は全員同じ（\(w_i = 1\)）。予測は重みの比で混ぜます:
$$\hat{y} = \sum_{i=1}^{N} p_i f_i, \qquad p_i = \frac{w_i}{\sum_j w_j}$$正解 \(y\) が分かったら、各 Expert の損失 \(\ell_i\)（ここでは絶対誤差 \(|y - f_i|\)）を計算し、 重みを掛け算で減らします:
$$w_i \leftarrow w_i \cdot e^{-\eta\, \ell_i}$$損失が大きいほど \(e^{-\eta \ell_i}\) は小さくなるので、外した Expert の重みは強く削られます。 \(\eta\)（イータ）はどれくらい強く削るかを決める数字で、学習率と呼びます。
数値で追ってみる
Expert が 3 人、\(\eta = 1\) の場合。最初の重みは全員 1/3 です。
| Expert | 1 回目の損失 | 更新後の重み | 2 回目の損失 | 累積損失 | 更新後の重み |
|---|---|---|---|---|---|
| A（よく当たる） | 0.1 | 0.482 | 0.2 | 0.3 | 0.571 |
| B（ふつう） | 0.5 | 0.323 | 0.4 | 0.9 | 0.314 |
| C（外しがち） | 1.0 | 0.196 | 0.9 | 1.9 | 0.115 |
A の重みが 0.333 → 0.482 → 0.571 と増え、C は 0.333 → 0.196 → 0.115 と減っていきます。 掛け算で更新するので、重みは累積損失だけで決まります: \(w_i \propto e^{-\eta L_i}\)（\(L_i\) は Expert \(i\) の累積損失）。 これは後で効いてくる重要な性質です。
実装メモ：なぜ対数で持つのか
数万ステップ回すと \(e^{-\eta L_i}\) は簡単に \(10^{-300}\) を下回り、
浮動小数点では 0 になってしまいます（アンダーフロー）。そこで実装では
\(\log w_i\) を保持し、更新は引き算 log_w -= eta * losses、
正規化は softmax 相当（最大値を引いてから exp）で行います。
本リポジトリの src/ensemble/hedge.py がこの方式です。
4. 「良さ」の測り方：後悔（regret）
オンライン予測では「正解率」ではなく 後悔（regret）という指標を使います。定義はとても素直です:
$$R_T = \underbrace{\sum_{t=1}^{T} \ell(\hat{y}_t)}_{\text{自分の累積損失}} \;-\; \underbrace{\min_{i}\sum_{t=1}^{T} \ell_i(t)}_{\text{最良の 1 本の累積損失}}$$日本語にすると「後から振り返って、いちばん良かった Expert 1 人にずっと任せておけばよかった量」です。 regret が 0 なら「最良の 1 本と同じ成績」、負なら「最良の 1 本より良かった」ことになります。
Hedge には次の保証があります（損失が \([0,1]\) に収まる場合）:
$$R_T \le \sqrt{\tfrac{T}{2}\ln N} \quad\Longrightarrow\quad \frac{R_T}{T} \to 0$$つまり 1 ステップあたりの後悔はゼロに近づく。 これは「どの Expert が良いかを事前に知らなくても、後から見た最良の 1 本にほぼ追いつける」 という、とても強い主張です。しかも Expert の中身に何の仮定も要りません。
保証の基準は 「最良の固定 Expert」です。「それを超える」とは一言も言っていません。 実際、絶対誤差のような線形な損失では、指数重みで超えることは原理的にできません （専門用語では「絶対損失は mixable でない」と言います）。 データが定常で、最良 Expert が最初から最後まで同じ 1 本なら、Hedge にできることは何もない — これが本プロジェクトの結果が退屈だった理由そのものです（実験レポート参照）。
補足：二乗損失なら話が変わる
損失を二乗誤差にすると、指数重み法は exp-concave な損失に対する強い保証
（\(R_T = O(\log N)\)、\(\sqrt{T}\) が消える）を持ちます。さらに、誤差が打ち消し合う
Expert 群では、凸結合がすべての Expert を上回ることが実際に起こります。
本リポジトリのテスト tests/test_new_aggregators.py には、
誤差が逆相関する 3 つの Expert に対して ML-Poly が全 Expert を上回ることを
確認するテストが入っています。
5. 学習率 η をどう決めるか
η は「重みをどれだけ急に動かすか」を決めます。極端な例で考えると分かりやすいです。
- η が大きすぎる：たまたま 1 回外しただけの Expert を切り捨ててしまい、予測がガタつく。
- η が小さすぎる：重みがほとんど動かず、いつまでも等重み平均のまま。
適切な η はデータの性質と損失のスケールに依存し、事前には分かりません。対策は 3 通りあります。
(a) 損失を正規化する
そもそも損失の大きさが系列ごとに違う（1 MW 単位の系列と 10,000 MW 単位の系列）と、
同じ η でも効き方がまるで変わります。そこで各系列の
「訓練期間で直近値予測をしたときの MAE」で損失を割り、\(O(1)\) に揃えます。
本リポジトリの --scale-loss by_train_mae がこれです。
(b) Meta-η（二段 Hedge）
η の候補（\(2^0, 2^{-1}, \ldots, 2^{-10}\)）ごとに独立した Hedge を走らせ、
その 11 個の出力をもう一段の Hedge で混ぜる方法です。
「学習率そのものを学習する」ので、手でチューニングしなくて済みます。
本リポジトリの既定はこれ（src/ensemble/meta_eta.py）。
(c) AdaHedge（パラメータなし）
実際に観測された mixability gap（重み付き平均の損失と、理論上の下限との差）を 足し上げ、その値から η を決めます:
$$\eta_{t+1} = \frac{\ln N}{\Delta_t}, \qquad \Delta_t = \sum_{s \le t}\Big(\underbrace{\langle w_s, \ell_s\rangle}_{\text{期待損失}} - \underbrace{-\tfrac{1}{\eta_s}\ln\langle w_s, e^{-\eta_s \ell_s}\rangle}_{\text{mix loss}}\Big)$$
予測が簡単な期間は \(\Delta\) が伸びず η が大きいまま（＝最良 Expert に素早く張り付く）、
難しい期間は \(\Delta\) が伸びて η が下がる（＝慎重に混ぜる）、という自動調整になります。
候補グリッドも地平線 \(T\) も要りません（src/ensemble/adahedge.py）。
6. Fixed-Share：一度見捨てた Expert に戻れるようにする
ここが本プロジェクトでいちばん効いた部分です。
Hedge の重みは \(w_i \propto e^{-\eta L_i}\) でした。つまり累積損失だけで決まります。 1 万ステップ回った後、ある Expert の累積損失がライバルより 100 だけ大きいと、 その重みは \(e^{-100} \approx 10^{-44}\)。ここから復帰するには、 ライバルより累積で 100 も勝ち越す必要があります。何千ステップもかかります。
しかし現実のデータでは、状況が変われば「勝つべき Expert」も変わります。 夏と冬、平日と休日、平常時とロックダウン。Hedge は過去に引きずられて動けないのです。
Fixed-Share（Herbster & Warmuth, 1998）の解決策は拍子抜けするほど簡単です。 毎ステップ、指数更新のあとに重みの一部を全員へ配り直します:
$$w \leftarrow (1-\alpha)\, w \;+\; \frac{\alpha}{N}$$これだけで、どの Expert の重みも \(\alpha/N\) を下回らなくなります。 負け続けた Expert も「最低限の席」を持ち続けるので、状況が変われば 数十ステップで首位に返り咲けます。
理論的には、比較対象が変わります。Hedge の基準が「最良の固定 Expert」だったのに対し、 Fixed-Share の基準は「途中で \(m\) 回まで乗り換えてよい最良の Expert 系列」です。 乗り換えオラクルは固定 1 本より当然強いので、Fixed-Share は最良の固定 Expert を実際に下回れます。
唯一のつまみが \(\alpha\) です。切り替えが \(m\) 回起きると分かっていれば \(\alpha = m/(T-1)\) が理論的な目安ですが、 実験では広い範囲で効くことが確認できました（追試結果の α 感度）。 \(\alpha = 0\) にすると Hedge に完全に一致します。
7. ML-Poly：アンサンブル自身を基準にする
もう 1 つ性格の違うアルゴリズムを入れてあります。Hedge が各 Expert の損失を累積するのに対し、 ML-Poly（Gaillard, Stoltz & van Erven, 2014）はアンサンブル自身に対する後悔を累積します:
$$r_{i,t} = \ell(\hat{y}_t) - \ell_i(t), \qquad R_{i,t} = \sum_{s \le t} r_{i,s}$$そして「今のアンサンブルより良かった Expert」にだけ重みを置きます:
$$p_{i,t} \propto \eta_{i,t-1}\,\max(R_{i,t-1},\, 0), \qquad \eta_{i,t} = \frac{1}{1 + \sum_{s\le t} r_{i,s}^2}$$
学習率が Expert ごとに、観測された分散から自動で決まるのが特徴です（つまみゼロ）。
基準がアンサンブル自身なので、Expert の誤差が打ち消し合う場合には
全 Expert を上回ることがあります。R の opera パッケージで
電力需要予測の実務に使われている手法です（src/ensemble/ml_poly.py）。
8. まとめ：どれをいつ使うか
| アルゴリズム | 比較対象（何に追いつくか） | つまみ | 効く場面 |
|---|---|---|---|
| Equal Weight | —（ただの平均） | なし | Expert の質が揃っているとき |
| Follow the Leader | 最良の固定 Expert | なし | 完全に定常なデータ |
| Hedge | 最良の固定 Expert | η | 定常だが最良 Expert が事前に不明 |
| Meta-η Hedge | 最良の固定 Expert | η の候補集合 | η を決めたくないとき |
| AdaHedge | 最良の固定 Expert | なし | η を決めたくないとき（候補も不要） |
| Fixed-Share | 最良の切り替え系列 | α, η | レジームが変わる／非定常なデータ |
| ML-Poly | アンサンブル自身への後悔 | なし | Expert の誤差が打ち消し合うとき |
Hedge 系（Hedge / Meta-η / AdaHedge）は「最良の 1 本に追いつく」ためのもので、 それを超えることは設計上ありません。超えたいなら、比較対象を変えるアルゴリズム — 乗り換えを許す Fixed-Share、アンサンブル自身を基準にする ML-Poly — が必要です。 実際にどれくらい差が出るかは追試結果で確認できます。
参考文献
- Cesa-Bianchi, N. & Lugosi, G. (2006). Prediction, Learning, and Games. Cambridge University Press. — 理論の教科書。
- Freund, Y. & Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. JCSS, 55(1), 119–139. — Hedge の原論文。
- Herbster, M. & Warmuth, M. K. (1998). Tracking the best expert. Machine Learning, 32(2), 151–178. — Fixed-Share の原論文。
- de Rooij, S., van Erven, T., Grünwald, P. D. & Koolen, W. M. (2014). Follow the leader if you can, hedge if you must. JMLR, 15, 1281–1316. — AdaHedge。
- Gaillard, P., Stoltz, G. & van Erven, T. (2014). A second-order bound with excess losses. COLT. — ML-Poly。
- Devaine, M., Gaillard, P., Goude, Y. & Stoltz, G. (2013). Forecasting electricity consumption by aggregating specialized experts. Machine Learning, 90(2), 231–260. — 電力需要予測への応用。
- Obst, D., de Vilmarest, J. & Goude, Y. (2021). Adaptive methods for short-term electricity load forecasting during COVID-19 lockdown in France. IEEE Trans. Power Systems, 36(5), 4754–4763.