螺旋本をPythonで解く Part2

螺旋本をPythonで解く Part1

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

モチベーション

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

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

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

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

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

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

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

目次

AI・機械学習ハンズオン 〜実践Kaggle 初級編〜に参加しました

はじめに

今回はただの日記です。 AI・機械学習ハンズオン 〜実践Kaggle 初級編〜に参加したので、感想を書く。 これから行く人が知りたいだろう情報も書くように心がける。

新曲をプレイするとスコアはいくつ？ 〜最大値を利用したスコアの分布推定〜

概要

本記事では音楽ゲーム(以下音ゲ)において、曲をプレイすると得られるスコアを確率変数として、その分布を推定することを試みた。 音ゲのスコアは慣習的に最大値のみが保存されるような仕組みになっている。 そのため、曲をプレイすると得られるスコアは一覧として得られない。 得られるデータと言えば、その曲を何回プレイして最高のスコアはいくつだったかだけである。 そこで、本記事では、その最大値から背景にあるスコアの分布を推定することを試みた。

本記事をすらすらと読むためには、大学学部レベルの確率統計を履修している必要がある。

どうやらスマホでは本記事の数式が見切れてしまうようである。スマホの方は横画面にして読んでほしい。

PriorityQueue Classを作る [Pythonで競プロ]

この問題を解くのにpriority queueを使う方法がある。 atcoder.jp

Pythonでpriority queueを実装するためには２つ方法があるがどちらも欠点がある。

1. heapqを用いた方法

   • こちらを用いて実装する方が多いと思う。でもめちゃくちゃ使いづらくないですか？
   • これで用意されている関数は、リストに対してin-placeで処理を施す。
   • クラスが用意されていない。

2. from deque import PriorityQueue を用いた方法

   • クラスが用意されていて1よりも扱いやすいが、2倍ぐらい遅い。
   • 中身が確認できない。(中身でfor を回す等の作業ができない。)

そこで、1をベースにPriorityQueueクラスを用意した。 pushやpopをメソッドとすることで、heapqをそのまま使うよりもスッキリ見やすく実装することができる。 また、インスタンスをそのまま実行するとheapの中身が見られるようにした。

from heapq import heapify, heappop, heappush, heappushpop

class PriorityQueue:
    def __init__(self, heap):
        '''
        heap ... list
        '''
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

    def __len__(self):
        return len(self.heap)

冒頭に上げた問題で使い方の具体例を示すと、こう。

import sys
read = sys.stdin.readline

def read_ints():
    return list(map(int, read().split()))

X, Y, Z, K = read_ints()
A = read_ints()
B = read_ints()
C = read_ints()

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)


from heapq import heapify, heappop, heappush, heappushpop

class PriorityQueue:
    def __init__(self, heap):
        '''
        heap ... list
        '''
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap


heap = []  # ヒープといっても順序を工夫したただのリスト

q = PriorityQueue(heap) #ここでインスタンスを作ってます
q.push((-(A[0] + B[0] + C[0]), 0, 0, 0))

considered = set()
ans = []
for k_th in range(1, K+1):
    heap_max, i, j, k = q.pop() #ここで一番小さな要素(先頭が見られる)を取り出してます
    ans.append(-heap_max)
    for di, dj, dk in zip([1, 0, 0], [0, 1, 0], [0, 0, 1]):
        i_new, j_new, k_new = i + di, j + dj, k + dk
        if i_new >= X or j_new >= Y or k_new >= Z:
            continue
        if (i_new, j_new, k_new) in considered:
            continue
        considered.add((i_new, j_new, k_new))
        q.push((-(A[i_new] + B[j_new] + C[k_new]), i_new, j_new, k_new)) #ここで要素の追加を行っています。


print(*ans, sep='\n')