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.

目次

らくらく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

螺旋本をPythonで解く Part3

螺旋本をPythonで解く Part2