Open yos1up opened 5 years ago
高次元（m次元）データの2点間のユークリッド距離を知りたかったり，与えられた点とデータ点とのユークリッド距離を知りたかったりする時（例えば K-近傍法を行いたい場合など）に，予め前処理として高次元データをPCAで次元圧縮しておき，低次元（k次元）上でのユークリッド距離で近似することで，計算を高速に行えるが，この方法は精度は高くない．著者らは，同じ計算量の別の近似法を提示しており，これは上記の素朴な方法よりも平均的に精度が高い．実データセットでも精度の向上を確認．なお，近似法の導出には最大エントロピー法を用いた議論を行っている．この議論はその他の（ユークリッド距離を求める以外の）PCAの応用タスクにも応用可能であり，例えばレイリー商の近似法も改善できる．
PCA，レイリー商，次元削減，低ランク近似，最大エントロピー法
https://arxiv.org/abs/1907.11094
Guihong Wan, Crystal Maung, Haim Schweitzer
2019/7/24
同じ計算量，かつ極めてシンプルな手法で，精度を改善している．
最大エントロピー法の議論．PCAから得られる量に関する確率分布を最大エントロピー法で求めようとすると，得られる公式らしい．
解析的および実データで．
目から鱗が出るような論文．
彼らの近似式 $d_{ent}(a_1, a_2)^2 = || w_1 - w_2 ||^2 + || a_1 ||^2 + || a_2 ||^2 - || w_1 ||^2 - || w_2 ||^2$ は書き換えると厳密に $|| a_1 - w_1 ||^2 + || w_1 - w_2 ||^2 + || w_2 - a_2 ||^2$ となる．ベクトル $a_1 - w_1$ と $a_2 - w_2$ は大体直交すると思えば，これは大体 $|| a_1 - a_2 ||^2$ に一致するので，妥当そう.
ざっくり言うと
高次元（m次元）データの2点間のユークリッド距離を知りたかったり，与えられた点とデータ点とのユークリッド距離を知りたかったりする時（例えば K-近傍法を行いたい場合など）に，予め前処理として高次元データをPCAで次元圧縮しておき，低次元（k次元）上でのユークリッド距離で近似することで，計算を高速に行えるが，この方法は精度は高くない．著者らは，同じ計算量の別の近似法を提示しており，これは上記の素朴な方法よりも平均的に精度が高い．実データセットでも精度の向上を確認．なお，近似法の導出には最大エントロピー法を用いた議論を行っている．この議論はその他の（ユークリッド距離を求める以外の）PCAの応用タスクにも応用可能であり，例えばレイリー商の近似法も改善できる．
キーワード
PCA，レイリー商，次元削減，低ランク近似，最大エントロピー法
1. 情報
論文リンク
https://arxiv.org/abs/1907.11094
著者
Guihong Wan, Crystal Maung, Haim Schweitzer
投稿日付
2019/7/24
2. 先行研究と比べてどこがすごい？
同じ計算量，かつ極めてシンプルな手法で，精度を改善している．
最大エントロピー法の議論．PCAから得られる量に関する確率分布を最大エントロピー法で求めようとすると，得られる公式らしい．
3. 技術や手法のキモはどこ？
4. どうやって有効だと検証した？
解析的および実データで．
5. 議論はある？
6. 次に読むべき論文は？
7. 実装の詳細
8. データセット
9. 結果の詳細
雑感&メモ
目から鱗が出るような論文．
彼らの近似式 $d_{ent}(a_1, a_2)^2 = || w_1 - w_2 ||^2 + || a_1 ||^2 + || a_2 ||^2 - || w_1 ||^2 - || w_2 ||^2$ は書き換えると厳密に $|| a_1 - w_1 ||^2 + || w_1 - w_2 ||^2 + || w_2 - a_2 ||^2$ となる．ベクトル $a_1 - w_1$ と $a_2 - w_2$ は大体直交すると思えば，これは大体 $|| a_1 - a_2 ||^2$ に一致するので，妥当そう.