![アルゴリズム - 背景知識
論文のメインアイデア
古典尤度における共変量ベクトルの未知の位置を一様に平均化することで集約さ
れた共変量の尤度を計算すること
あるbinにおける尤度の貢献度は に比例する
ここで
Υ ? =
b ?
k
Υ ? ×
b ?
k
1
? × Υ ? ?
b ?
k
D
RD
Υ ?
=
b ?
k
d
(y ?
, y ?
] ?
b ?
d?1
d
b ?
d
d
R
?∞ < y ?
<
0
d
y ?
<
1
d
… < y ?
<
B ?
k
d
∞
( ? g ?
(y ?
∣x ?
, θ)dx ?
)
∫Υ ?
b
X,Y n n n
s ?
b](https://image.slidesharecdn.com/logisticregressionmodelsforaggregateddata-211229094148/85/Logistic-regression-models-for-aggregated-data-6-320.jpg)
![アルゴリズム - 形式化 (Using both classical data and
histograms)
S ? =
k (X ) :
π
~ (k)
R →
N ?
×D
k
{τ ?
, … , N ?
} ×
k k
u
Rv×D
x ?
(k)
? ,? b ? = 1 ?
, … , B ?
({
s ? = ? 1{x ? ∈ Υ ?
}??if?s ? ≤ τ ?
b ?
k ∑n=1
N ?
k
n
(k)
b ?
k b ?
k k
x ? = {x ? : x ? ∈ Υ ?
}??otherwise
b ?
k n
(k)
n
(k)
b ?
k
k k k})
ここで , は少なくとも 個の観
測値を含むビンの数
は 個未満の観測値を含むビンに保持されたデータポイントの
数
尤度は以下
L ?
(s; β) ∝
MM ? ? ? P ?
(Y = k∣X = x)dx ? ? P ?
(Y = k∣X = x) ? ?? (8)
k∈Ω
∏
b ?
=1 ?
k k
∏
B ?
k
(∫
Υ ?
b ?
k
M )
s ?
1{s ?
≥τ ?
}
b ?
k b ?
k k
?
?
x∈x ?
b ?
k
(k)
∏ M
?
?
1{s ?
<τ ?
}
b ?
k k
τ ? ∈
k {1, … , N ?
}
k u ∈ [0, … , B ? ×
k
1
… × B ?
]
k
D
τ ?
k
v = N ? ?
k ?
∑s ?
b ?
k
τ ?
k](https://image.slidesharecdn.com/logisticregressionmodelsforaggregateddata-211229094148/85/Logistic-regression-models-for-aggregated-data-14-320.jpg)
![シミュレーションデータ
共変量は8次元のスキュー正規分布から生成
左:相関ゼロ, 右:[0, 0.75]の一様相関
K = 2](https://image.slidesharecdn.com/logisticregressionmodelsforaggregateddata-211229094148/85/Logistic-regression-models-for-aggregated-data-28-320.jpg)
[読会]Logistic regression models for aggregated data
- 1. 論文紹介 Logistic regression models for aggregated data Tom Whitaker et al., 2020
- 3. 概要 - モチベーション ロジスティック回帰は基本的なモデルだけどクソデカデータだと計算量が法外に デカくなる 説明変数をヒストグラムの形に集計してそれを基に推定すれば計算量と精度のい いとこどり出来るのでは？ Symbolic Data Analysis (SDA)の考えが拡張できると考えた
- 4. 概要 - 貢献 ヒストグラムに基づく確率変数を入力とした効率的な一対他対応の近似複合尤度 モデル(composite likelihood model)を導出 複合尤度に基づいたアイデアを発展させた 規格化定数を必要としない損失を用いることが出来る 普通のロジスティック回帰や最新のサブサンプリングアルゴリズムと同等の分類 精度を大幅に低い計算コストで達成できることを実証
- 5. アルゴリズム - Notations histogram bin: outcome value: covariate value: 以下の設定と考えてもよい は直接観測出来ない ヒストグラムの各ビン でビンボリューム に含まれる共変量ベクト ル の数のみがわかる #classes: #covariate vectors contained within bin: parameter: , likelihood: 仮定される の分布： b Y ∈ Ω = {1, … , K} X x b Υ ? b s ? b K s ? b θ ? L(x, y; θ) ∝ ? g ? (y ? ∣x ? , θ)?for?N?i.i.d.pairs(x ? , y ? ) ∏n=1 N X,Y n n n n Y g ? (y ? ∣x ? , θ) X,Y n n
- 6. アルゴリズム - 背景知識 論文のメインアイデア 古典尤度における共変量ベクトルの未知の位置を一様に平均化することで集約さ れた共変量の尤度を計算すること あるbinにおける尤度の貢献度は に比例する ここで Υ ? = b ? k Υ ? × b ? k 1 ? × Υ ? ? b ? k D RD Υ ? = b ? k d (y ? , y ? ] ? b ? d?1 d b ? d d R ?∞ < y ? < 0 d y ? < 1 d … < y ? < B ? k d ∞ ( ? g ? (y ? ∣x ? , θ)dx ? ) ∫Υ ? b X,Y n n n s ? b
- 7. アルゴリズム - 背景知識 OvRロジスティック回帰 (One-vs-Rest logistic regression) log ? = ( P ? (Y = k∣X) O P ? (Y = k∣X) O ) β ? + k0 β ? X k T P ? (Y = O k∣X) = ? 1 + eβ ? +β ? X k0 k T e + β ? X β ? k0 k T L ? (x, y; β) = O ? ? P ? (Y = y ? ∣X = x ? ) ? P ? (Y = k∣X = x ? ) ? ?? (3) n=1 ∏ N ? ? O n n k∈Ω?{y ? } n ∏ O n ? ? 最尤推定 (MLE)での最適化の目的関数 ? = β ^O argmax ? ?logL ? (x, y; β) β O
- 8. アルゴリズム - 背景知識 本論文で提案しているのはSDA尤度と通常の尤度を混合して利用する混合モデル bin内のサンプルサイズが大きい場合はSDA尤度を利用しサンプルサイズが小 さい場合は通常の尤度を利用 こうした方が計算量が少ない 混合モデルは説明変数の数がそんなに多くない場合に使用するのは適さない 低次元の周辺ヒストグラム (marginal histograms) を使うことを想定
- 9. アルゴリズム - 形式化 (Classification for aggregated data) X = (k) (X ? ∣Y ? = n n k, n = 1, … , N) ∈ RD×N ? k S ? = k π(X ) : (k) D ? → X(k) D ? , x ? S(k) (k) s ? k L(s ? ; θ, ?) ∝ k ? f ? (s ? ∣x , ?)g ? (x ; θ)dx ??(4) ∫ D ? X(k) S ? ∣X =x k (k) (k) k (k) X(k) (k) (k) where N ? = k ? 1{Y ? = n=1 ∑ N n k} X ∈ (k) D ? ?(D ? = X(k) X(k) R ) D×N ? k
- 10. アルゴリズム - 形式化 (Classification for aggregated data) パラメータ はシンボルの構築に関連する量（ビンの数とその位置など） 所与の場合が多いので以降略記されていることが多い は 所与の時の の条件付き確率密度 これは の集約に関連 一般的な標記であり考慮される分布要約のタイプに応じて異なる形態をとる はパラメータ , データ を持つモデルの標準的な尤度関数 ここで 本論文の式(4)の意味 同じ を持つ共変量 をヒストグラム（固定ビンまたはランダムビンを持 つ） に集約 ロジスティック回帰モデル をフィットさせる ? f ? (?; ?) S ? ∣X k (k) X(k) S ? k x ? (k) s ? k g ? (x ; θ) X(k) (k) θ x(k) x = (k) (x ? , … , x ? ) 1 (k) N ? k (k) k X(k) S ? k g ? (x ; θ) X(k) (k)
- 11. アルゴリズム - 形式化 (Logistic regressions using histogram-valued data) クラス における特徴量の各次元内のbin数: binのインデックス: ? ??(5) S ? = π(X ) : R → {0, … , N ? } k (k) N ? ×D k k B ? ×…×B ? k 1 k D x ? s ? = (s ? = ? 1{x ? ∈ Υ ? }, … , s ? = ? 1{x ? ∈ Υ ? }) (k) k 1 ? k ∑n=1 N ? k n (k) 1 ? k B ? k ∑n=1 N ? k n (k) B ? k L ? (s; β) ∝ SO ? ? ? ? P ? (Y = k∣X = x)dx ? ? P ? (Y = k ∣X = x)dx ? ?? (7) k∈Ω ∏ b ? =1 ? k k ∏ B ? k ? ? ∫ Υ ? b ? k O k ∈Ω{k} ′ ∏ ∫ Υb ? k O ′ ? ? s ? b ? k k B ? k d b ? = k (b , … , b ? ), b ? = 1 ? k D ? k d ? k 1, … , B ? d k
- 12. アルゴリズム - 形式化 (Logistic regressions using histogram-valued data) 式(7)をsymbolic One-vs-Rest(SOvR) logistic modelと呼ぶ Heitjan (1989), Beranger et al. (2018)で は各ヒストグラムのビンの数を 無限に近づけると に近づくことが示されている ヒストグラムに集約したモデルが分離可能であっても集約してない普通のモデル が分離可能ではない しかしビンの作り方によって分離可能ではなくなる可能性もある ビン化することによって情報損失/精度低下があり得る 改善方法提案してる L ? (s; β) SO L ? (x, y; β) O
- 13. アルゴリズム - 形式化 (Using both classical data and histograms) ビン内のデータ数が少ないと の計算コストを の計算コストが超える これは次元数 が大きいほど起こりやすい ビンに下限値 を設けて下限値に満たない場合は を計算する ことで効率化を図った の設定によって計算量が逆に高くなる場合がある 標準的な尤度計算をするよりも計算量が少なくなるように を設定する L ? O L ? SO D τ ? ∈ k {1, … , N ? } k L ? O τ ? k τ ? k
- 14. アルゴリズム - 形式化 (Using both classical data and histograms) S ? = k (X ) : π ~ (k) R → N ? ×D k {τ ? , … , N ? } × k k u Rv×D x ? (k) ? ,? b ? = 1 ? , … , B ? ({ s ? = ? 1{x ? ∈ Υ ? }??if?s ? ≤ τ ? b ? k ∑n=1 N ? k n (k) b ? k b ? k k x ? = {x ? : x ? ∈ Υ ? }??otherwise b ? k n (k) n (k) b ? k k k k}) ここで , は少なくとも 個の観 測値を含むビンの数 は 個未満の観測値を含むビンに保持されたデータポイントの 数 尤度は以下 L ? (s; β) ∝ MM ? ? ? P ? (Y = k∣X = x)dx ? ? P ? (Y = k∣X = x) ? ?? (8) k∈Ω ∏ b ? =1 ? k k ∏ B ? k (∫ Υ ? b ? k M ) s ? 1{s ? ≥τ ? } b ? k b ? k k ? ? x∈x ? b ? k (k) ∏ M ? ? 1{s ? <τ ? } b ? k k τ ? ∈ k {1, … , N ? } k u ∈ [0, … , B ? × k 1 … × B ? ] k D τ ? k v = N ? ? k ? ∑s ? b ? k τ ? k
- 15. アルゴリズム - 形式化 (Composite likelihoods for logistic regression models) 今までの工夫で計算効率をかなり改善できたが多変量ヒストグラムは共変量の数( )が増えるとデータサマリーとして非常に非効率 で尤度関数 , は解析的な解を持たない 自明でない設定では数値積分する必要がある が大きい場合には計算コストが膨大になりデータアグリゲートする目的 （計算効率の向上）が損なわれる可能性が生じる D D > 2 L ? (s; β) SM L ? (s; β) SO D
- 16. アルゴリズム - 形式化 (Composite likelihoods for logistic regression models) 高次元ヒストグラムのビンに入るデータの確率を計算するという問題を回避する ためにWhitakerら(2020)が複合尤度法の導入を提案している 高次元ヒストグラムの尤度関数を低次元周辺ヒストグラムの尤度関数の加重 積で近似するというもの これにより漸近的に尤度ベースのパラメータの一致推定量が得られる (Lindsay, 1988, Varin et al., 2011)（らしい） 全ての重みが等しいとすると以下で計算出来る は における 個の周辺事象の 番目の尤度関数 L (θ) ∝ (j) ? L ? (θ) ∏i=1 m i L ? (θ) i j m i
- 17. アルゴリズム - 形式化 (Composite likelihoods for logistic regression models) これで良さそう...と一体いつから錯覚していた？ プロビット回帰やロジスティック回帰で重要な変数を省略すると残りの係数の推 定ベクトルが に潰される現象が起こるらしい(Wooldridge 2002, Cramer 2007) この理由からロジスティック回帰の問題に複合尤度アプローチを直接適用するこ とはできない Cramer(2007)でOvRの設定すべての予測変数が独立であるという仮定のもとでロ ジスティック回帰の非省略係数が回帰因子が省略されないシナリオでの回帰係数 の関数として記述できることを示されている Cramer(2007)では設定が異なっていたため省略された変数の情報を使うことが難 しかった しかし複合尤度の設定では各共変量に関する情報が利用可能 省略されている共変量を補償するために各周辺尤度の計算で実装できた 0
- 18. アルゴリズム - 形式化 (Composite likelihoods for logistic regression models) standard D-dimensional OvR logistic regression model L ? (x, y; β) = O (j) ? L ? (x , y; ? ) i∈I ? j ∏ O i β ~i histogram-base D-dimensional OvR logistic regression model L ? (s; β) = SO (j) ? L ? (s , y; ? ) i∈I ? j ∏ SO i β ~i 係数
- 19. アルゴリズム - 形式化 (Composite likelihoods for logistic regression models) ここで ? i = (i ? , … , i ? ) ? {1, … , D} 1 I I ? = {i : ∣i∣ = j} j X = (X ? , … , X ? ) ∈ R ??where??X ? ∈ R (k)i 1 (k)i N ? k (k)i j×N ? k n (k)i j i ? , i ? ∈ I ? 1 ′ 2 ′ 1 ?i X = α ? X + ? ? i′ ii′ T i ii′ の時 j = 1 λ
- 20. アルゴリズム - 形式化 (Composite likelihoods for logistic regression models) と は近似複合尤度関数であり真の複合尤度関数ではない 不偏推定量でも一致推定量でもない しかし実験ではフルデータを使ったナイーブな推定量よりも精度よかった 計算量少ないのは言わずもがな の一番簡単な例が式(10)に記載してある アグリゲーション関数はこれ と を混合した場合の近似複合尤度 L ? (s; β) = OO (1) L ? ({x }; β)L ? (s; β) O (1) (k)i SO (1) L ? (x, y; β) O (j) L ? (s; β) SO (j) L ? (s; β) SO (j) L ? O L ? SO
- 22. アルゴリズム - 疑似コード
- 24. 実験 シミュレーションデータ パラメータ推定能力と分類能力の検証 分類性能評価の指標はprediction accuracy (PA) 値は1000回平均値 シミュレーションで見ているのは以下 i. ビンの数の変化による評価項目値の変化 ii. サンプルサイズ（観測データ数） を変化させてサンプリングモデルと比較 N
- 25. 実験 実データ 以下の2つのデータセットを使った性能比較 i. SUSYデータセット 超対称性粒子を生成する信号プロセスとそうでないバックグラウンドプ ロセスの分類 K=2, D=18 train:4 500 000, test:500 000 ii. Crop typeデータセット 衛星画像使った作物の分類 K=7, D=7（特徴量作ったらしい） train:200 000, test:34 485
- 26. シミュレーションデータ 上段:多変量正規分布, 下段:スキュー正規分布, 左:共変量にゼロ相関仮定, 右:非ゼロ相関 仮定
- 27. シミュレーションデータ 上段:多変量正規分布, 下段:スキュー正規分布, 左:共変量にゼロ相関仮定, 右:非ゼロ相関 仮定
- 33. 実データ Lasso正則化を用いた標準的な多項式尤度 との比較 L ? (x, y; β) M