学習する天然ニューラルネット

主に機械学習に関する覚書や情報の整理

ランダムフォレストと検定を用いた特徴量選択手法 Boruta

  • 特徴量選択とは
  • Borutaとは
  • とりあえず使ってみる
    • ベースラインの判別
    • Borutaの判別
  • Borutaのアイデアの概要
  • Borutaのアルゴリズム
    • 1. 判別に寄与しないはずの偽の特徴量を作る。
    • 2. 偽の特徴量と一緒にランダムフォレストを訓練。
    • 3. 各特徴量の重要度と偽の特徴量の特徴量を比較。
    • 4. 複数回比較し検定を行うことで、本当に重要な特徴量のみを選択。
  • 検定について
    • 1. 棄却したい帰無仮説と受容したい対立仮説を用意する。
    • 2. 観測値から検定統計量Tを定める。
    • 3. 帰無仮説が正しいとしてTの分布を求める。
    • 4. 十分小さい有意水準αを定め、帰無仮説が正しいときにとなる領域を棄却域とする。
    • 5. 観測されたTがに入っていたら対立仮説を受容し、入っていなければ帰無仮説を受容する。
  • まとめ
  • 補足
  • 使う際のTips等 2019/01/06追記
  • 参考

特徴量選択とは

特徴量選択(Feature Selection, 変数選択とも)はデータサイエンスにおいて非常に重要である。 Kaggle等のコンペティションではひたすら判別の精度を重要視するが、実務上どうしてそのような判別をしたのかという理由のほうが大事である(回帰問題も同様)。 例えば、なにかの製造工程をイメージしてみよう。 当然欠陥品は生じるだろうが、この欠陥品を見分けるシステムよりも欠陥品を減らせる改良のほうが良いだろう(もちろん見分けるのも大事だが)。 そこで、判別においてどのような特徴量が重要だったか選ぶことができれば、改良への糸口が見えてくるだろう。

また、特徴量選択した結果、モデルの学習や推論が高速化されたり、過学習しづらくなったり、結果判別の精度が良くなったりする。

Borutaとは

ランダムフォレストと検定を用いた特徴量選択の方法の一つである。 Witold R. Rudnicki, Miron B. Kursaらが考案。

R実装 CRAN - Package Boruta

Python実装 (バグあり。まとめ後に補足します。)(アップデートされてました pip install Borutaしましょう)

github.com

(名前の由来はスラヴ神話の森の神の名前らしいです。こんな見た目してます。)

f:id:aotamasaki:20190105193106p:plain

このBorutaという手法は経験上非常に強力で、判別や回帰の性能が著しく低下したことはない。低下しても誤差の範囲内。むしろ性能が良くなることが多い。

続きを読む

Confident Learningは誤った教師から学習するか? ~ tf-idfのデータセットでノイズ生成から評価まで ~

概要

現実の判別問題において教師が完璧であることは珍しい。ラベリング作業において、知識不足や勘違いなどで引き起こされるヒューマンエラーはデータセットを汚染する。

このような間違った教師のことを、noisy label (corrupted label や polluted labelとも)という。誤った教師を用いると学習はうまく行かず判別性能は下がってしまう。近年ではこれに対処しようという研究が増えている。

ICML2020に Confident Learning: Estimating Uncertainty in Dataset Labels という論文が投稿された。しかも、よく整備された実装cleanlabまで提供されていた。

今回はRCV1-v2という文章をtf-idf(特徴量)にしたデータセットを用いて、Confident Learning (CL)が効果を発揮するのか実験を行った。またcleanlabを用いた実装を公開する。

結論としては、CLを用いると確かにnoisy labelなデータセットでも判別性能がよくなった。更にpseudo-labelingと組み合わせるともっと良くなるという結果が得られた。

目次

  • 概要
  • 目次
  • Confident Learning (CL)
  • 実験計画
    • 1. ML:clean
    • 2. ML:noisy
    • 3. CL:without noises
    • 4. CL:pseudo for noises
    • 5. CL:pseudo for noises and test
  • データセットと実験設定
  • 実験結果
  • cleanlabの一部機能の解説
    • 学習に関して
    • データ生成に関して
    • 今回の実験の実装
  • まとめ
  • 参考
続きを読む

Confident Learning -そのラベルは正しいか?-

これは何?

ICML2020に投稿された Confident Learning: Estimating Uncertainty in Dataset Labels という論文が非常に面白かったので、その論文まとめを公開する。

論文 [1911.00068] Confident Learning: Estimating Uncertainty in Dataset Labels

超概要

  • データセットにラベルが間違ったものがある(noisy label)。そういうサンプルを検出したい
  • Confident Learningという方法を提案。現実的な状況下でSOTAを達成
  • PyPIに実装を公開済みですぐに使用可能(pip install cleanlab)

GitHub - cgnorthcutt/cleanlab: Find label errors in datasets, weak supervision, and learning with noisy labels.

目次

  • これは何?
  • 超概要
  • 目次
  • 私感
  • 論文の概要
  • Class-conditional classification Noise Process
  • Confident Learningの概要
    • 入力
    • 出力
    • CLの処理
  • 同時分布Qの推定
    • Cを作るカウント方法
    • Qへの正規化
  • データクリーニング
  • 実験結果
    • 同時分布Qをうまく推定できているか
    • Noisy Labelを検出できているか
    • 他手法との比較
  • まとめ
  • 参考
続きを読む

らくらくp進全探索 コピペで使えるPython実装

何をしたか?

連続するp進数を次々返してくれるiteratorを実装しました(といっても標準ライブラリにラップしただけ)。 例えば、3桁の3進数だったら000, 001, 002, 010, 012 ..., 222 というものを次々に返してくれます。 実際には桁ごとにリストの1要素を構成していて,pが10以上でも問題なく動作します。

1種類あたりp個の選択肢があり、n種に対して全探索したい場合、これをn桁のp進全探索と呼ぶことにします。 この全探索を生成するコードは以下です。

続きを読む

降順リストに対するbisectの実装 list.sort(reverse=True)に対する配列二分法

はじめに

Pythonにおいて、降順リスト向けの配列二分法アルゴリズムを実装しました。

使用するメリット

  • コピペで標準ライブラリに準拠した動作をします。
  • 標準ライブラリと異なり、降順リストを扱います。
  • 昇順リストに変換し直す計算量と、昇順のidxを降順のidxに変換する思考リソースを削減します
続きを読む

めぐる式二分探索 コピペで使えるPython実装

  • はじめに
  • めぐる式二分探索のメリットと参考文献
  • コピペ用
  • 例題

はじめに

AtCoderで二分探索を実装するときバグらせないように考えると結構時間かかりませんか?自分はかかります。

競技プログラミング界隈ではめぐる式二分探索という二分探索の書き方(流派?)があり、使いやすい、バグりにくくなど様々なメリットがあります。

Python実装を公開しているブログはパット見、見つからなかったのでおいておきます。使用例もおいておきます。

めぐる式二分探索のメリットと参考文献

めぐる式二分探索を使うメリットとして以下があげられます。

  • 配列化できない関数を探索可能 (bisectモジュールでは不可)
  • バグりにくい (終了状態がきちんとしている)
  • ライブラリとして扱うことが可能で実装が高速化される
  • 思考リソースの消耗を防げる (条件を満たすかそうでないかだけ考えれば良い)
続きを読む

螺旋本をPythonで解く Part4

  • はじめに
  • 17章 動的計画法
    • P412 DPL_1_A: Coin Changing Problem
    • P416 DPL_1_B: 0-1 Knapsack Problem
    • P421 DPL_1_D: Longest Increasing Subsequence
    • P425 DPL_3_A: Largest Square
    • P428 DPL_3_B: Largest Rectangle
  • 18章 整数論
    • P436 ALDS_1_C: Prime Numbers
    • P441 ALDS1_1_B: Greatest Common Divisor
    • P445 NTL_1_B: Power
  • 19章 ヒューリスティック探索 (省略)
  • 終わりに
続きを読む

螺旋本をPythonで解く Part3

  • はじめに
  • 14章 高度なデータ構造
    • P318 DSL_1_A: Disjoint Set: Union Find Tree
    • P324 DSL_2_C: Range Search (kD Tree)
  • 15章 高度なグラフアルゴリズム
    • P336 GRL_1_C: All Pairs Shortest Path
    • P342 GRL_4_B: Topological Sort
    • P348 GRL_3_A: Articulation Point
    • P353 GRL_5_A: Diameter of a Tree
    • P358 GRL_2_A: Minimum Spanning Tree
  • 16章 計算幾何学
    • P384 CGL_1_C: Counter-Clockwise
    • P387 CGL_2_B: Intersection
    • P398 CGL_3_C: Polygon-Point Containment
    • P401 CGL_4_A: Convex Hull
    • P405 CGL_6_A: Segment Intersections: Manhattan Geometry
  • つづく
続きを読む