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

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

めぐる式二分探索 コピペで使える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
  • つづく
続きを読む

螺旋本をPythonで解く Part2

  • はじめに
  • 8章 木
    • P188 ALDS1_7_A: Rooted Trees
    • P193 ALDS1_7_B: Binary Tree
    • P198 ALDS1_7_C: Tree Walk
    • P203 ALDS1_7_D: Reconstruction of the Tree
  • 9章 二分探索木
    • P209 ALDS1_8_A: Binary Search Tree 1
    • P214 ALDS1_8_B: Binary Search Tree 2
    • P217 ALDS1_8_C: Binary Search Tree 3
  • 10章 ヒープ
    • P234 ALDS1_9_A: Complete Binary Tree
    • P236 ALDS1_9_B: Maximum Heap
    • P240 ALDS1_9_C: Priority Queue
  • 11章 動的計画法
  • 12章 グラフ
    • P269 ALDS1_11_A: Graph
    • P273 ALDS1_11_B: Depth First Search
    • P282 ALDS1_11_C: Breadth First Search
    • P287 ALDS1_11_D: Connected Components
  • 13章 重み付きグラフ
    • P296 ALDS1_12_A: Minimum Spanning Tree
    • P302 ALDS1_12_B: Single Source Shortest Path 1
    • P309 ALDS1_12_C: Single Source Shortest Path 2
  • つづく
続きを読む

螺旋本をPythonで解く Part1

  • はじめに
  • 2章 アルゴリズムと計算量
    • P46 ALDS1_1_D: Maximum Profit
  • 3章 初等的整列
  • 4章 データ構造
    • P82 ALDS1_3_A: Stack
    • P87 ALDS1_3_B: Queue
    • P95 ALDS1_3_C: Doubly Linked List
    • P114 ALDS1_3_D: Areas on the Cross-Section Diagram
  • 5章 探索
    • P119 ALDS1_4_A: Linear Search
    • P122 ALDS1_4_B: Binary Search
    • P127 ALDS1_4_C: Dictionary
    • P136 ALDs1_4_D: Allocation
  • 6章 再帰・分割統治法
    • P142 ALDS1_5_A: Exhaustive Search
    • P146 ALDS1_5_C: Koch Curve
  • 7章 高等的整列
    • P152 ALDS1_5_B: Merge Sort
    • P158 ALDS1_6_B: Partition
    • P163 ALDS1_6_C: Quick Sort
    • P168 ALDS1_6_A: Counting Sort
    • P175 ALDS1_5_D: The Number of Inversions
    • P179 ALDS1_6_D: Minimum Cost Sort
  • つづく
続きを読む

中心極限定理による分布収束のアニメーション nを増やすと標本平均はどうばらつくか

f:id:aotamasaki:20191011122748p:plain

モチベーション

中心極限定理は一言で言うと、「平均する対象を増やすと、その標本平均は正規分布に従うようになる」という定理である。これの解釈はあとで与える。 この定理は直感的にはわかりにくく誤用する人も多いため、twitterでhotなトピックになった。本記事はそれに便乗した形で書いた。

本記事では、中心極限定理の直感的解釈を与える。また平均する対象を増やしたときに、標本平均の分布がどのように収束していくのかを可視化する。

続きを読む

特徴量重要度にバイアスが生じる状況ご存知ですか?

f:id:aotamasaki:20190715230720p:plain

なぜこの記事を書いたのか?

決定木をベースにしたアルゴリズムのほとんどに特徴量重要度という指標が存在する。データに対する知識が少ない場合はこの指標を見て特徴量に対する洞察深めることができる。KaggleではEDAのときにとりあえず重要度を見てみるなんてこともするようだ。

しかし、この特徴量重要度にはバイアスが存在していて、特定の条件下では信用出来ないことがある。そういった条件を広く知ってほしいということでこの記事を書いた。

この記事では人工データを生成しバイアスを再現してみた。また、こういったバイアスに対処したという論文を見つけたので軽く紹介する。おまけとしてgainベース以外の特徴量重要度についても紹介する。

目次

  • なぜこの記事を書いたのか?
  • 想定読者と実験の枠組み
    • 想定読者
    • 限定する枠組み
  • 特徴量重要度とは?
  • 特徴量重要度にバイアスが生じる条件
    • 1. 解像度が低い場合
    • 2. 特徴量同士にdependancyがある場合
  • 実験
    • 実験設定
    • データの解像度が低い場合
      • データ生成の設定
      • 結果
    • 特徴量同士にdependancyがある場合
      • データ生成の設定
      • 結果
    • その他(おまけ)
      • 特徴量の分布でバイアスは生じるか
      • 判別に寄与する状況下ではどうなるの?
  • 特徴量重要度のバイアスに対抗するには?
  • 3種の特徴量重要度
    • split frequency
    • gini importances
    • permutation importances
  • まとめ
  • 参考
続きを読む