AtCoder上でscikit-learnを使って機械学習してみたい

はじめに

皆さんはAtCoderでscikit-learnが使えるのをご存知でしょうか？
現在*1のAtCoderでは以下のライブラリが利用できます。
numba, numpy, scipy, scikit-learn, networkx
今回はせっかくなのでscikit-learnを利用して問題を解いてみました。

題材

今回の記事の目標は以下の問題をACすることです。

お誕生日コンテスト X - この問題はほんとうにひどい問題であるため，できれば先に他の問題のほうをお楽しみいただければと思っておりまして，ですので他の問題を通し終えて暇になり，かつその暇を

atcoder.jp

数式が画像で与えられるので、それを計算する問題です。画像認識してくださいと言っているようなものですね。

解く

まずインプットを受け取りbool型のndarrayに格納します。

import numpy as np
t = int(input())
w, h = map(int, input().split())
b = np.full((h, w), False, dtype=bool)
for i in range(h):
    b[i] = [x == "#" for x in input()]

インプットにはノイズが含まれるのでメディアンフィルタで除去します。
scipyにndimage.median_filterがあるのでそれを使います。size=6が一番スコアが良さそうでした。

from scipy.ndimage import median_filter
c = median_filter(b, 6)

フォントのサンプルデータが与えられるのでベタ書きして配列に入れます。
ただし貼るだけで40,000字を超えるので、AtCoderのコード文字数上限の2/3以上使ってしまいます。
サンプルデータは#の部分だけ疎行列っぽく保持してデータ量削減できますが、当記事のコードはそのまま配列に入れています。

sample_chars = [None] * 16
SAMPLES_H, SAMPLES_W = 65, 38
sample_chars[0] = """......................................
......................................
# (中略)
......................................"""
# (中略)
samples = np.full((16, SAMPLES_H, SAMPLES_W), False, dtype=bool)
for i in range(16):
    samples[i] = np.array([[y == "#" for y in x]
                          for x in sample_chars[i].split("\n")], dtype=bool)

次に問題文と同じ方法でサンプルデータを作っていきます。
機械学習のお作法よろしく、x_trainに配列、y_trainに答えを格納していきます。
少し実験したところ*と+の誤読が多そうなので多めにテストケースを作っています。

import math
import random
random.seed(11)

def RotatePoint(coordinate, degree, center=(0, 0)):
    xi, yi = coordinate[0] - center[0], coordinate[1] - center[1]
    di = math.radians(degree)
    c, s = math.cos(di), math.sin(di)
    xj = xi * c - yi * s
    yj = xi * s + yi * c
    return xj + center[0], yj + center[1]


def move_center(a, ressize_i, ressize_j):
    res = np.full((ressize_i, ressize_j), False, dtype=bool)
    ave_i = ave_j = count = 0
    dots = []
    for i in range(len(a)):
        for j in range(a.shape[1]):
            if not a[i, j]:
                continue
            ave_i += i
            ave_j += j
            count += 1
            dots.append((i, j))
    ave_i //= count
    ave_j //= count
    for i, j in dots:
        p, q = i - ave_i + (ressize_i >> 1), j - ave_j + (ressize_j >> 1)
        if 0 <= p < ressize_i and 0 <= q < ressize_j:
            res[p, q] = True
    return res

def create_testcase(a):
    b = np.full((SAMPLES_H, SAMPLES_W), False, dtype=bool)
    r = random.uniform(-15, 15)
    for i in range(SAMPLES_H):
        for j in range(SAMPLES_W):
            if not a[i, j]:
                continue
            p, q = RotatePoint((i, j), r, center=(
                SAMPLES_H // 2, SAMPLES_W // 2))
            if 0 <= p < SAMPLES_H and 0 <= q < SAMPLES_W:
                b[int(p), int(q)] = True
    a, b = b, np.full((SAMPLES_H, SAMPLES_W), False, dtype=bool)
    m = random.uniform(0.9, 1)
    mh = random.uniform(0.9, 1)
    mw = random.uniform(0.9, 1)
    for i in range(SAMPLES_H):
        for j in range(SAMPLES_W):
            if not a[i, j]:
                continue
            b[int(i * m * mh), int(j * m * mw)] = True
    a, b = b, np.full((SAMPLES_H, SAMPLES_W), False, dtype=bool)
    sx = random.uniform(-0.1, 0.1)
    sy = random.uniform(-0.1, 0.1)
    for i in range(SAMPLES_H):
        for j in range(SAMPLES_W):
            if not a[i, j]:
                continue
            b[i + int(j * sy), j + int(i * sx)] = True
    return move_center(median_filter(b, 6), SAMPLES_H, SAMPLES_W)

TESTCASE_COUNT = 320
x_train = [None] * TESTCASE_COUNT
y_train = np.zeros(TESTCASE_COUNT, dtype=int)
SEARCH_COUNTS = (2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4,)
# "0123456789)/-(+*"
search_chars = [0] * sum(SEARCH_COUNTS)
index = 0
for k, i in enumerate(SEARCH_COUNTS):
    for j in range(index, index + i):
        search_chars[j] = k
    index += i
for i in range(TESTCASE_COUNT):
    j = search_chars[i * len(search_chars) // TESTCASE_COUNT]
    x_train[i] = create_testcase(samples[j]).flatten()
    y_train[i] = j

ようやくscikit-learnの出番です。
少し実験したところSVCが一番良さそうだったので、それを採用しています。
paramsは手元でoptunaを使って出してみたのですが、あまり変わらなかったので適当です。

from sklearn import svm
params = {'kernel': 'linear', 'C': 1.870188616833552,
          'gamma': 0.01730071376054783}
clf = svm.SVC(**params)
clf.fit(x_train, y_train)

あとはインプットを転置させて行が全部空白なら切断して……ということを繰り返してx_testに格納していきます。

x_test = []
input_chars = []
buf = []
for i in c.T:
    if True in i:
        buf.append(i)
    else:
        if len(buf) > 4:
            input_chars.append(np.array(buf, dtype=bool).T)
            buf = []
if len(buf) > 4:
    input_chars.append(np.array(buf, dtype=bool).T)
for a in input_chars:
    x_test.append(move_center(a, SAMPLES_H, SAMPLES_W).flatten())

最後に予測して計算して出力です。
ただし負数の割り算の仕様上、eval関数ではWAになるので注意が必要です。

def calc_expr(expr):
    import os
    os.system("echo $((%s))" % expr)


chars = "0123456789)/-(+*"
calc_expr("".join([chars[x] for x in clf.predict(x_test)]))

テスト

↓

$((0-6/(8*9/3+9-7*3/5/8/9)-6*0-0+3/3*8*(4*0)-(9)-(9)))

うまく行ってそう？(多分)

結果

seedとparamsとテストケース数とテストケースの比率が全部噛み合って祈りが通じればACです。

atcoder.jp

最後に

時間制限もあり絶対正答できるくらいの精度は無いのですが、とりあえずACできて目標を達成できました。
こんな問題はネタコンテストでしか出ないでしょうけど、一度くらい本番でsklearnを使ってたいというお気持ちになりました。

*1:2022年8月現在

徒然

思いついたら書きます

AtCoder上でscikit-learnを使って機械学習してみたい

はじめに

題材

解く

テスト

結果

最後に