डेटा से खुद सीखना | AI का पूरा इतिहास

012006 · डीप लर्निंग की शुरुआत

3 शर्तें एक साथ पूरी हुईं

2006 में नया क्या था—विचार या परिस्थितियाँ?

कई परतों वाले न्यूरल नेटवर्क सिर्फ़ बैकप्रोपेगेशन (अध्याय 8) से अच्छी तरह नहीं सीख पाते थे। 2006 में जेफ़्री हिंटन (Geoffrey Hinton) और उनके साथियों ने पहले सही उत्तर दिए बिना डेटा की विशेषताएँ सीखने (प्री-ट्रेनिंग), फिर पूरे नेटवर्क को बैकप्रोपेगेशन से सँवारने की विधि दिखाई। इसका वर्णन उन्होंने (अनुवाद) के रूप में किया। हाथ से लिखे अंकों के MNIST डेटा पर त्रुटि दर 1.25% थी।

उसी साल Science के एक शोधपत्र ने लिखा, (अनुवाद)। उसने गणना की गति, डेटा की मात्रा और वज़नों के अच्छे शुरुआती मान गिनाए और आगे लिखा, (अनुवाद)।

दाईं ओर के चित्र में 3 शर्तों की बत्तियाँ जलाकर या बुझाकर खड़ी और आड़ी पट्टियों वाली छवियों के पुनर्निर्माण की तुलना कर सकते हैं। प्री-ट्रेनिंग से शुरुआती वज़न तय करने पर नेटवर्क सही उत्तरों के बिना एक-एक परत सीखता है, फिर पूरे नेटवर्क को बैकप्रोपेगेशन से सँवारा जाता है (बत्तियों का असर इस साइट का बनाया उदाहरण है)।

Δw_ij ＝η（⟨v_ih_j⟩_डेटा − ⟨v_ih_j⟩_{पुनर्निर्माण}）

v, h: दृश्य परत (पिक्सेल) और छिपी परत के न्यूरॉन
w: वज़न
⟨ ⟩: औसत (डेटा और पुनर्निर्माण के अंतर से वज़न सुधारे जाते हैं; रिस्ट्रिक्टेड बोल्ट्ज़मान मशीन की विधि)

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:2006 में हिंटन ने डीप लर्निंग नाम का नया विचार खोजा
मूल स्रोत के अनुसार:शोधपत्र ने खुद लिखा कि इसकी उपयोगिता 1980 के दशक से स्पष्ट थी। मुख्य नई बात शुरुआती वज़न चुनने की विधि थी, जिसके बारे में उसने कहा, (अनुवाद)। उसी 2006 में योशुआ बेंजियो (Yoshua Bengio) और उनके साथियों ने भी मिलती-जुलती विधि दी।

पुनर्निर्माण की त्रुटि (सीखने के साथ घटती है)

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_rbm_layer.py

# u09 1層ずつの事前学習：正解を与えずに画像の特徴をつかむ（制限ボルツマンマシン）
#
# どの出来事か：2006年、ヒントンたちが深いニューラルネットワークを「1 層ずつ」（訳）学習させる方法を示した
#   （記録 hinton_deep_belief_nets_2006）。論文は「今、3 つの条件がすべてそろった」（訳）と書いた。
# 仕組み：4×4＝16画素の画像（縦棒か横棒が1本）を、答え（どの棒か）を与えずに見せ続ける。
#   可視ニューロン v（16個）と隠れ層のニューロン h（8個）をつなぐ重み w を、
#     データを見た時に v と h が一緒に出る度合い − 自分で再構成した時に v と h が一緒に出る度合い
#   の差に基づいて更新する（コントラスティブ・ダイバージェンス。CD-1）。
#   学習が進むほど、隠れ層のニューロンの出力が、画像ごとに異なる組み合わせ（コード）になり、そこから元の画像を再構成できる。
#   画像はこのサイトが作った例。
# 試してみよう：
#   - HIDDEN（隠れ層のニューロン数）を 2・4・8 にする。棒は 8 本あるので、少ないと表現しきれない
#   - ETA（学習率）を 0.01 や 0.5 にする

import math
import random

random.seed(2006)
HIDDEN = 8
ETA = 0.1
ROUNDS = 3000

def bars():
    """縦棒4本・横棒4本の、計8枚の画像"""
    pics = []
    for k in range(4):
        pics.append([1 if (i % 4) == k else 0 for i in range(16)])   # たて
        pics.append([1 if (i // 4) == k else 0 for i in range(16)])  # よこ
    return pics

def sig(x):
    return 1 / (1 + math.exp(-x))

PICS = bars()
w = [[random.gauss(0, 0.1) for _ in range(HIDDEN)] for _ in range(16)]
a = [0.0] * 16          # 可視ニューロンのバイアス
b = [0.0] * HIDDEN      # 隠れ層ニューロンのバイアス

def up(v):
    return [sig(b[j] + sum(v[i] * w[i][j] for i in range(16))) for j in range(HIDDEN)]

def down(h):
    return [sig(a[i] + sum(h[j] * w[i][j] for j in range(HIDDEN))) for i in range(16)]

def recon_error():
    e = 0
    for v in PICS:
        r = down(up(v))
        e += sum((v[i] - r[i]) ** 2 for i in range(16))
    return e / len(PICS)

print("学習回数 → 再構成誤差（小さいほど、元の画像を正しく再構成できる）")
for t in range(ROUNDS + 1):
    if t % 500 == 0:
        e = recon_error()
        print(f"  {t:5d} 回 → {e:.3f}  " + "#" * int(e * 10))
    v0 = random.choice(PICS)
    p0 = up(v0)
    h0 = [1 if random.random() < p else 0 for p in p0]
    v1 = down(h0)
    p1 = up(v1)
    for i in range(16):
        for j in range(HIDDEN):
            w[i][j] += ETA * (v0[i] * p0[j] - v1[i] * p1[j])
        a[i] += ETA * (v0[i] - v1[i])
    for j in range(HIDDEN):
        b[j] += ETA * (p0[j] - p1[j])

print()
print("8 つの画像と、隠れ層ニューロンの出力（1＝強く反応）、再構成した画像")
codes = set()
for k, v in enumerate(PICS):
    h = up(v)
    code = "".join("1" if x > 0.5 else "0" for x in h)
    codes.add(code)
    r = down([1 if x > 0.5 else 0 for x in h])
    pic = "/".join("".join("#" if v[i * 4 + c] else "." for c in range(4)) for i in range(4))
    rec = "/".join("".join("#" if r[i * 4 + c] > 0.5 else "." for c in range(4)) for i in range(4))
    print(f"  画像 {k + 1}：{pic}  → コード {code} → 再構成 {rec}")
print(f"異なるコードの数：{len(codes)} ／ 8")
print("正解を与えていないのに、8 つの画像を別々のコードで表現し、そこから再構成できるようになった。")
print("このコードを次の層の入力にして、同様に学習させるのが「1 層ずつ」の事前学習。")

021763 · 1961 · बेयस

परिणाम से कारण की ओर

क्या केवल संकेत देने वाले शब्दों से दस्तावेज़ का विषय पहचाना जा सकता है?

बेयस का प्रमेय साक्ष्य मिलने के बाद किसी कारण या परिकल्पना की संभावना को दोबारा गणना करने का विचार है। शोधपत्र 23 दिसंबर 1763 को ब्रिटेन की रॉयल सोसायटी में पढ़ा गया। इसके लेखक थॉमस बेयस (Thomas Bayes) का निधन हो चुका था। उनके मित्र प्राइस (Price) ने उनके कागज़ों में इसे ढूँढकर भेजा था।

1961 में RAND संस्थान के एम. ई. मैरन (M. E. Maron) ने इस विचार से शोधपत्रों के सारांशों को 32 विषयों में बाँटने का प्रयोग किया। उन्होंने मान लिया कि विषय तय होने पर शब्द एक-दूसरे से स्वतंत्र रूप से आते हैं और बस हर शब्द की संभावना को आपस में गुणा किया (आज इसे सरल बेयस या नाइव बेयस कहते हैं)। कम-से-कम 2 संकेत शब्दों वाले 85 नए सारांशों में पहला चुना गया विषय 44 (51.8%) के लिए सही था। सबसे ऊपर के 3 विषयों को गिनने पर 68 (80%) सही थे।

दाईं ओर के चित्र में संकेत शब्द दबाने पर गुणा के ज़रिए विषयों की संभावनाएँ बदलती हैं (शब्द और संभावनाएँ इस साइट के बनाए उदाहरण हैं)।

P(विषय | शब्द) ∝ P(विषय) × Π P(शब्द | विषय)

P(A | B): शर्त B के तहत A होने की संभावना
Π: हर शब्द के लिए गुणा करना
∝: समानुपाती (अंत में इस तरह भाग देते हैं कि कुल 1 हो जाए)

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:नाइव (सरल) बेयस ऐसी विधि है जो भोलेपन से मानती है कि शब्दों का एक-दूसरे से कोई संबंध नहीं
मूल स्रोत के अनुसार:मैरन ने खुद लिखा था कि स्वतंत्रता की धारणा स्पष्ट रूप से सही नहीं है, लेकिन गणना आसान करने के लिए उसे अपनाया गया। शोधपत्र में न naive शब्द मिलता है, न Bayes नाम।

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_naive_bayes.py

# u09 単純ベイズ：手がかりの単語から、文書の分野を確率で分類する
#
# どの出来事か：1763年のベイズの論文（記録 bayes_essay_1763）と、1961年のマロンによる自動索引づけの実験
#   （記録 naive_bayes_maron_1961）。マロンは要約405本のうち260本で集計し、残る145本は準備の間は見ずに、テストに使った。
# 仕組み：分野ごとに、単語が出る割合を数えておく。新しい文書が来たら、
#     P(分野) × P(単語1 | 分野) × P(単語2 | 分野) × …
#   を分野ごとに計算し、確率が最も高い分野に分類する。単語どうしは互いに関係なく出現すると仮定している（実際には成り立たない仮定）。
#   一度も出現しなかった単語で確率が0にならないよう、回数に1を足しておく（ラプラススムージング）。
#   文書と単語は、このサイトが作った例（マロンの実際のデータではない）。
# 試してみよう：
#   - 訓練データの文書数 TRAIN_PER を 4・10・40 と変えて、訓練データとテストデータの正解率の差を見る
#   - SMOOTH を 0.01 にすると、どうなるか

import math
import random

random.seed(1961)
TRAIN_PER = 4
TEST_PER = 30
SMOOTH = 1.0

# 分野ごとに出現しやすい単語（このサイトが作った例）
FIELDS = {
    "計算機の回路": ["回路", "論理", "素子", "電圧", "記憶", "速さ", "磁気", "設計"],
    "数の計算": ["誤差", "行列", "式", "近似", "反復", "速さ", "記憶", "表"],
    "パターン認識": ["文字", "学習", "特徴", "確率", "判定", "画像", "誤差", "表"],
}
COMMON = ["方法", "結果", "計算", "装置", "問題", "新しい"]

def make_doc(field):
    words = random.sample(FIELDS[field], 2)                  # その分野の単語を2つ選ぶ
    for _ in range(2):
        other = random.choice([f for f in FIELDS if f != field])
        if random.random() < 0.6:
            words.append(random.choice(FIELDS[other]))       # ほかの分野の単語もよく混ざる
    words += random.sample(COMMON, 2)                          # どの分野にも出現する共通単語
    return words

def make_set(n):
    return [(f, make_doc(f)) for f in FIELDS for _ in range(n)]

train, test = make_set(TRAIN_PER), make_set(TEST_PER)
vocab = sorted({w for _, d in train + test for w in d})
count = {f: {w: 0 for w in vocab} for f in FIELDS}
docs = {f: 0 for f in FIELDS}
for f, d in train:
    docs[f] += 1
    for w in set(d):
        count[f][w] += 1

def scores(doc):
    out = {}
    for f in FIELDS:
        s = math.log(docs[f] / len(train))
        for w in set(doc):
            p = (count[f][w] + SMOOTH) / (docs[f] + 2 * SMOOTH)   # その分野の文書で w が出現する確率
            s += math.log(p)
        out[f] = s
    m = max(out.values())
    z = sum(math.exp(v - m) for v in out.values())
    return {f: math.exp(v - m) / z for f, v in out.items()}

def accuracy(data):
    ok = 0
    for f, d in data:
        sc = scores(d)
        ok += max(sc, key=sc.get) == f
    return ok / len(data)

print(f"訓練データ {len(train)} 本・テストデータ {len(test)} 本（テストデータは集計時に見ていない）")
print(f"  訓練データでの正解率：{accuracy(train):.0%}")
print(f"  テストデータでの正解率：{accuracy(test):.0%}")
print()
doc = ["特徴", "確率", "式", "方法", "計算"]
print("新しい文書の単語：", "・".join(doc))
for f, p in sorted(scores(doc).items(), key=lambda x: -x[1]):
    print(f"  {f:8s} {p:6.1%} " + "#" * int(p * 40))
print("単語を1つ足すごとに、各分野の確率が掛け算で変化する。")

031805 · न्यूनतम वर्ग विधि

त्रुटियों के वर्गों का न्यूनतम योग

मापे गए बिंदु बिखरे हों, तो कौन-सी सीधी रेखा सबसे अच्छा “मेल खाती” है?

1805 में पेरिस के आद्रियाँ-मारी लजांद्र (Adrien-Marie Legendre) ने धूमकेतुओं की कक्षा की गणना पर लिखी पुस्तक के परिशिष्ट में न्यूनतम वर्ग विधि प्रकाशित की। समीकरणों की संख्या अज्ञात मानों से अधिक हो, तो सभी त्रुटियों को 0 नहीं कर सकते। उन्होंने लिखा कि हर त्रुटि का वर्ग लेकर उन्हें जोड़ना और मान इस तरह चुनना कि कुल योग सबसे छोटा हो, सबसे सामान्य, सटीक और आसान तरीका है। इससे त्रुटियाँ एक-दूसरे को संतुलित करती हैं और बहुत बड़ी त्रुटियाँ परिणाम को अपनी ओर खींच नहीं पातीं, यह भी उन्होंने समझाया।

दाईं ओर के चित्र में त्रुटियाँ असली वर्गों के क्षेत्रफल के रूप में दिखती हैं। बिंदुओं को खिसकाएँ या रेखा की ढाल बदलें (अंतःखंड अपने-आप बदलता है) और कुल क्षेत्रफल घटाने की कोशिश करें। “न्यूनतम वर्ग (घाटी के तल पर)” दबाने से सूत्र द्वारा एक ही बार में निकाली गई रेखा बनती है। डेटा के अनुसार सूत्र के मान तय करना—इस अध्याय की कई विधियाँ इसी रूप से शुरू होती हैं।

S＝Σ（y_i − (a x_i ＋b)）² को न्यूनतम करें
a＝Σ(x_i − x̄)(y_i − ȳ) ÷ Σ(x_i − x̄)², b＝ ȳ − a x̄

(x_i, y_i): मापे गए डेटा के बिंदु
a, b: रेखा की ढाल और अंतःखंड
x̄, ȳ: x और y के औसत

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:न्यूनतम वर्ग विधि गाउस (Gauss) ने बनाई
मूल स्रोत के अनुसार:इसे सबसे पहले छापकर प्रकाशित करने वाले लजांद्र थे (1805)। गाउस ने 1809 की पुस्तक में लिखा कि वे इसे 1795 से इस्तेमाल कर रहे थे। स्टीफ़न स्टिग्लर (Stephen Stigler, 1981) ने माना कि गाउस के पहले होने की संभावना अधिक है, पर प्रमाण निर्णायक नहीं। अमेरिका के रॉबर्ट एड्रेन (Robert Adrain) ने भी 1808〜1809 में इसे प्रकाशित किया।

ढाल a बदलने पर त्रुटियों के वर्गों का योग (घाटी का तल न्यूनतम वर्ग है)

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_least_squares.py

# u09 最小二乗法：誤差を 2 乗して足し合わせ、最小になる直線を求める
#
# どの出来事か：1805 年、ルジャンドルが彗星の軌道に関する著書の付録で発表（記録 least_squares_1805）。
#   ガウスは 1809 年の著書で、1795 年から使っていたと記述した。
# 仕組み：直線 y = a x + b と各点の誤差（縦方向）を 2 乗して足した和 S を、最小にする a と b を求める。
#   S を a と b で微分して 0 とおくと、
#     a = Σ(x - x平均)(y - y平均) / Σ(x - x平均)^2 、 b = y平均 - a × x平均
#   が一度に求まる。ここでは、数式で求めた答えと、a を少しずつ変えて S の谷の底を探した答えが一致することを確かめる。
#   データ点はこのサイトが作った例。
# 試してみよう：
#   - 点を 1 つだけ大きくずらす（外れ値）。2 乗するため、その点に直線が強く引き寄せられる
#   - 誤差の「絶対値」の和で探すと、答えはどう変わるか（ABS = True）

import random

random.seed(1805)
ABS = False
xs = [i * 0.5 for i in range(12)]
ys = [1.2 * x + 0.8 + random.gauss(0, 0.5) for x in xs]
# ys[10] += 6   # ← 外れ値を入れてみる

n = len(xs)
mx, my = sum(xs) / n, sum(ys) / n
a = sum((x - mx) * (y - my) for x, y in zip(xs, ys)) / sum((x - mx) ** 2 for x in xs)
b = my - a * mx

def S(a_, b_):
    if ABS:
        return sum(abs(y - (a_ * x + b_)) for x, y in zip(xs, ys))
    return sum((y - (a_ * x + b_)) ** 2 for x, y in zip(xs, ys))

print(f"式で一度に求めた直線：y = {a:.3f} x + {b:.3f}　（誤差の 2 乗の和 S = {S(a, b):.3f}）")
print()
print("傾き a を変えたときの S（b はその都度最適な値にする）")
best = None
for k in range(0, 25):
    a_ = 0.6 + k * 0.05
    b_ = my - a_ * mx
    s = S(a_, b_)
    if best is None or s < best[1]:
        best = (a_, s)
    print(f"  a = {a_:.2f} → S = {s:7.2f} " + "#" * min(60, int(s * 2)))
print(f"谷の底：a ≒ {best[0]:.2f}（式の答え {a:.3f} と同じ所）")
print()
print("点ごとの誤差（正方形の 1 辺）と、その 2 乗（正方形の面積）")
for x, y in zip(xs, ys):
    e = y - (a * x + b)
    print(f"  x = {x:4.1f}  誤差 {e:+.2f}  面積 {e * e:.2f}")

041838 · 1958 · S आकार का वक्र

जनसंख्या के सूत्र से संभावना तक

ऐसा अनुमान कैसे बनाएँ जो हमेशा 0 और 1 के बीच रहे?

1838 में बेल्जियम के पियेर फ़्राँस्वा वेरहुल्स्ट (Pierre François Verhulst) ने जनसंख्या की बढ़त का सूत्र दिया। इसमें दोगुनी होती बढ़त की ताकत mp से जनसंख्या बढ़ने के साथ मज़बूत होता ब्रेक np² घटाया जाता है। हल का वक्र S आकार का होता है और जनसंख्या ऊपरी सीमा m／n के पास पहुँचती है। 1845 में उन्होंने इस वक्र का नाम logistique रखा (कारण नहीं बताया)।

बाद में यही S आकार का वक्र संभावना का अनुमान लगाने में इस्तेमाल हुआ। जिन डेटा के उत्तर “हाँ (1)” या “नहीं (0)” होते हैं, उनमें समझाने वाले चरों से 1 होने की संभावना बताने की विधि लॉजिस्टिक रिग्रेशन है। सीधी रेखा का अनुमान 0 से नीचे या 1 से ऊपर जा सकता है, लेकिन S आकार का वक्र हमेशा 0 और 1 के बीच रहता है। 1958 में लंदन विश्वविद्यालय के डेविड कॉक्स (David Cox) ने 0 और 1 वाले डेटा के रिग्रेशन पर शोधपत्र प्रकाशित किया।

दाईं ओर “जनसंख्या (1838)” में m और n बदलें। “हाँ · नहीं (1958)” में “1 कदम सीखें” दबाकर देखें कि S आकार का वक्र बिंदुओं से कैसे मेल खाने लगता है।

dp/dt＝mp − np²
P(y＝1)＝1 ÷（1＋e^−(ax＋b)）

p, m, n: जनसंख्या, बढ़त की ताकत और ब्रेक की ताकत
a, b: सीखने से तय होने वाले मान
e: लगभग 2.718 (प्राकृतिक लघुगणक का आधार)

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:लॉजिस्टिक रिग्रेशन कॉक्स ने 1958 में बनाया
मूल स्रोत के अनुसार:1994 के साक्षात्कार में कॉक्स ने खुद कहा कि वे नहीं जानते कि सबसे पहले किसने बनाया; शायद कॉर्नफ़ील्ड (Cornfield) ने किया हो। 1944 में बर्कसन (Berkson) ने लॉजिस्टिक फ़ंक्शन इस्तेमाल करके शब्द बनाया था।

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_logistic.py

# u09 S字の曲線：人口の式（1838）と、はい・いいえの確率を学習するロジスティック回帰（1958）
#
# どの出来事か：1838年、フェルフルストが人口増加モデルの式 dp/dt = m p - n p^2 を発表（記録 verhulst_logistic_1838）。
#   1958年、コックスが 0 と 1 のデータの回帰分析に関する論文を発表（記録 logistic_regression_cox_1958）。
# 仕組み：
#   (1) 人口の式で、少しずつ時間を進めて計算する。人口は上限 m/n に近づき、S字の曲線を描く。
#   (2) 同じS字の曲線 1 / (1 + e^-(a x + b)) を、はい(1)・いいえ(0) のデータに当てはめる。
#       「その点が本当に出る確からしさ」が大きくなる向きに、a と b を少しずつ更新する（勾配を上る）。
#   データはこのサイトが作った例（勉強時間と、合格したかどうかの想定）。
# 試してみよう：
#   - M と N を変えて、上限 M/N が変わることを確かめる
#   - ETA（学習率）を 0.01 や 1.0 に変えてみる

import math
import random

random.seed(1838)
M, N = 0.03, 0.00001    # 増加の勢いと抑制の強さ（仮の数値）
ETA = 0.3

print(f"(1) 人口の式：上限 M/N = {M / N:,.0f}")
p, t = 100.0, 0
while t <= 600:
    if t % 50 == 0:
        print(f"  {t:3d} 年目 {p:8,.0f} " + "#" * int(p / (M / N) * 40))
    p += (M * p - N * p * p) * 1.0
    t += 1

print()
print("(2) ロジスティック回帰：勉強時間 x と、合格（1）・不合格（0）")
data = []
for _ in range(40):
    x = random.uniform(0, 10)
    prob = 1 / (1 + math.exp(-(1.1 * x - 5.5)))
    data.append((x, 1 if random.random() < prob else 0))

a, b = 0.0, 0.0
for step in range(1, 3001):
    ga = gb = 0.0
    for x, y in data:
        q = 1 / (1 + math.exp(-(a * x + b)))
        ga += (y - q) * x
        gb += (y - q)
    a += ETA * ga / len(data)
    b += ETA * gb / len(data)
    if step in (1, 10, 100, 1000, 3000):
        ll = sum(math.log(1 / (1 + math.exp(-(a * x + b)))) if y else math.log(1 - 1 / (1 + math.exp(-(a * x + b)))) for x, y in data)
        print(f"  {step:4d} 回目：a = {a:.2f}, b = {b:.2f}, 対数尤度 = {ll:.2f}")
print()
print("学習したS字曲線：勉強時間 → 合格確率")
for x in range(0, 11):
    q = 1 / (1 + math.exp(-(a * x + b)))
    print(f"  {x:2d} 時間 {q:5.1%} " + "#" * int(q * 40))
print("直線と違い、予測は常に 0% と 100% の間に収まる。")

051901 · 1933 · मुख्य घटक विश्लेषण

बिंदुओं के सबसे पास कौन-सी रेखा?

x और y दोनों के माप में त्रुटि हो, तो “मेल खाने वाली रेखा” कैसे चुनें?

न्यूनतम वर्ग की रेखा केवल y में त्रुटि मानकर ऊपर-नीचे के अंतर को घटाती है। इसलिए x या y में से किसे आधार बनाएँ, इससे रेखा बदल जाती है। 1901 में लंदन के कार्ल पियर्सन (Karl Pearson) ने सोचा कि हर बिंदु से रेखा पर डाले गए लंब की लंबाई के वर्गों का योग न्यूनतम करना चाहिए। वह रेखा बिंदुओं के केंद्र से गुज़रती है और उनके बिखराव को दिखाने वाले दीर्घवृत्त के सबसे लंबे अक्ष की दिशा में होती है।

दाईं ओर “पियर्सन के 10 बिंदु” चुनने पर 10 बिंदु ठीक उनके शोधपत्र के संख्यात्मक उदाहरण वाले हैं। “लंब” चुनकर रेखा घुमाएँ और वह दिशा खोजें जहाँ लंबों के वर्गों का औसत सबसे छोटा हो। शोधपत्र में ढाल −0.546 है। x से y का अनुमान लगाने वाले रिग्रेशन में −0.5396 और y से x का अनुमान लगाने में −0.5659 मिलता है, इसलिए 3 अलग रेखाएँ बनती हैं।

1933 में कोलंबिया विश्वविद्यालय के हैरोल्ड होटेलिंग (Harold Hotelling) ने आपस में संबंधित कई परीक्षणों के अंकों से सबसे अधिक बिखराव समझाने वाले घटकों को क्रम से निकालने की विधि को (अनुवाद) कहा।

Σ d_i² को न्यूनतम करने वाली दिशा ＝ बिंदुओं के सबसे अधिक बिखराव की दिशा (पहला मुख्य घटक)

d_i: iवें बिंदु से रेखा पर डाले गए लंब की लंबाई
बिखराव का दीर्घवृत्त: डेटा का बिखराव दिखाने वाला दीर्घवृत्त

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:मुख्य घटक विश्लेषण होटेलिंग ने 1933 में बनाया
मूल स्रोत के अनुसार:बिंदुओं के सबसे पास की रेखा बिखराव के सबसे लंबे अक्ष की दिशा में होती है, यह पियर्सन 1901 में दिखा चुके थे।

रेखा की दिशा और लंबों के वर्गों का औसत

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_pca.py

# u09 主成分分析：点に最も近い直線（1901 年のピアソンの数値例）と、主成分の抽出（1933 年のホテリング）
#
# どの出来事か：1901 年、ピアソンが、点から直線への垂線の 2 乗の和が最小になる直線は、
#   点の散らばりを表す楕円の長軸の向きになると示した（記録 pearson_closest_fit_1901）。
#   1933 年、ホテリングが「主成分の方法」（訳）と名づけた（記録 hotelling_principal_components_1933）。
# 仕組み：
#   (1) ピアソンの論文の 10 個の点（論文の数値例そのもの）で、3 本の直線の傾きを比べる。
#       論文の数値：最も近い直線 -0.546、y を x から予測する回帰 -0.5396、x を y から予測する回帰 -0.5659。
#   (2) 3 つのテストの得点（このサイトが作った例）から、分散が最も大きい向きを、
#       「かけては長さをそろえる」を繰り返して探す（べき乗法）。
# 試してみよう：
#   - (1) で、直線の向き theta を別の値に置きかえて、垂線の 2 乗の平均が最小になる角度を探す
#   - (2) で、テストの得点の作り方を変える

import math
import random

P = [(0, 5.9), (0.9, 5.4), (1.8, 4.4), (2.6, 4.6), (3.3, 3.5),
     (4.4, 3.7), (5.2, 2.8), (6.1, 2.8), (6.5, 2.4), (7.4, 1.5)]
n = len(P)
mx = sum(x for x, _ in P) / n
my = sum(y for _, y in P) / n
sxx = sum((x - mx) ** 2 for x, _ in P) / n
syy = sum((y - my) ** 2 for _, y in P) / n
sxy = sum((x - mx) * (y - my) for x, y in P) / n
print(f"(1) ピアソンの 10 個の点：重心 ({mx:.2f}, {my:.2f})、相関係数 {sxy / math.sqrt(sxx * syy):.4f}")
theta = 0.5 * math.atan2(2 * sxy, sxx - syy)
print(f"  最も近い直線（垂線の 2 乗の和が最小）の傾き：{math.tan(theta):.4f}")
print(f"  y を x から予測する回帰直線の傾き：        {sxy / sxx:.4f}")
print(f"  x を y から予測する回帰直線の傾き：        {syy / sxy:.4f}")

def mean_sq_perp(th):
    c, s = math.cos(th), math.sin(th)
    return sum(((x - mx) * s - (y - my) * c) ** 2 for x, y in P) / n

print("  直線の向き（度）→ 垂線の 2 乗の平均")
for deg in range(-40, -15, 2):
    v = mean_sq_perp(math.radians(deg))
    print(f"    {deg:4d}° → {v:.4f} " + "#" * int(v * 60))
print(f"  最小になるのは {math.degrees(theta):.1f}°（傾き {math.tan(theta):.3f}）で、値は {mean_sq_perp(theta):.4f}")

print()
print("(2) 3 つのテスト（計算の速さ・読解の速さ・語彙）の得点から、主成分を取り出す")
random.seed(1933)
rows = []
for _ in range(200):
    g = random.gauss(0, 1)          # 背後にある共通の要因（仮）
    s = random.gauss(0, 1)          # 読解と語彙にだけ影響する要因（仮）
    rows.append([g + 0.5 * random.gauss(0, 1), g + 0.8 * s + 0.4 * random.gauss(0, 1), 0.6 * g + 0.9 * s + 0.4 * random.gauss(0, 1)])
k = 3
mean = [sum(r[j] for r in rows) / len(rows) for j in range(k)]
C = [[sum((r[i] - mean[i]) * (r[j] - mean[j]) for r in rows) / len(rows) for j in range(k)] for i in range(k)]
total = sum(C[i][i] for i in range(k))
for comp in range(k):
    v = [1.0, 1.0, 1.0]
    for _ in range(200):
        w = [sum(C[i][j] * v[j] for j in range(k)) for i in range(k)]
        L = math.sqrt(sum(x * x for x in w))
        v = [x / L for x in w]
    lam = sum(v[i] * sum(C[i][j] * v[j] for j in range(k)) for i in range(k))
    print(f"  第 {comp + 1} 主成分：方向 ({v[0]:+.2f}, {v[1]:+.2f}, {v[2]:+.2f})、分散の {lam / total:.0%} を説明")
    C = [[C[i][j] - lam * v[i] * v[j] for j in range(k)] for i in range(k)]   # 取り出した成分を引いて、次へ
print("分散の大きい順に取り出す。小さい成分は省いてもよい（数を減らしてまとめる）。")

061950 · जापान · परिमाणीकरण

डेटा से अंक तय करना

“अच्छी तरह ढलना · सामान्य · विद्रोही” जैसे उत्तरों को कितने अंक दें?

जापान के 1948 के पढ़ने-लिखने की क्षमता के सर्वेक्षण के अंत के आसपास, सांख्यिकीय गणित संस्थान के चिकिओ हयाशी (Chikio Hayashi) से एक दंड कानून के विद्वान ने सलाह माँगी। वे पैरोल पर रिहाई के निर्णय को सांख्यिकी से अधिक भरोसेमंद बनाना चाहते थे। तब तक लोग हर उत्तर को −2 से 2 जैसे अंक देकर जोड़ते थे।

हयाशी योकोहामा जेल गए। उन्होंने देखा कि जेल में अच्छी तरह ढलने वाले आदर्श कैदी और बहुत विद्रोही कैदी, दोनों में दोबारा अपराध की प्रवृत्ति थी, जबकि बीच वाले लोग सबसे कम दोबारा अपराध करते थे। इसलिए वे उत्तर को दिए जाने वाले मान खुद डेटा से तय करने की विधि तक पहुँचे, जिससे दोबारा अपराध करने और नहीं करने वाले समूह साफ़ अलग हों (1950 का अंग्रेज़ी शोधपत्र)।

दाईं ओर लोगों द्वारा तय किए गए अंकों और डेटा से निकले अंकों की तुलना करें (लोगों की संख्या इस साइट का बनाया उदाहरण है)।

अंक s ऐसे चुनें कि सहसंबंध अनुपात η² अधिकतम हो

s: उत्तर (श्रेणी) को दिया गया मान
η²: कुल बिखराव का वह हिस्सा जो समूहों के अंतर से समझाया जा सके (आज के परिमाणीकरण प्रकार II का रूप)

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:परिमाणीकरण प्रकार I〜IV हयाशी ने इसी क्रम में बनाए और नाम दिए
मूल स्रोत के अनुसार:पहले पैरोल का अनुमान लगाने की विधि पूरी हुई (आज का प्रकार II)। I〜IV के नाम सामाजिक मनोवैज्ञानिक हिरोशी अकुतो (Hiroshi Akuto) ने 1964 में दिए; इनका बनने के क्रम से संबंध नहीं है।

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_quantification.py

# u09 数量化：選択肢（カテゴリー）に与える点数を、データから決める
#
# どの出来事か：1950 年、林知己夫が仮釈放の予測のために考えた方法（記録 hayashi_quantification_1950）。
#   それまでは、選択肢ごとに -2, -1, 0, 1, 2 のような点数を人が決めて合計していた。
#   林は、よくなじむ優等生も、ひどく反抗的な人も再犯しやすく、中くらいの人が最も再犯しにくい傾向を読み取った。
# 仕組み：質問は 2 つ（刑務所の生活へのなじみ方、働きぶり）。選択肢ごとの点数を未知数とし、
#   「再犯しなかった組」と「した組」の点数の平均の差が、全体のばらつきに比べて最大になるように決める
#   （今の数量化 II 類と同じ形。1950 年の論文は、予測の的中率を最大にする問題として書いた）。
#   人数は、このサイトが作った例（林の実際のデータではない）。
# 試してみよう：
#   - 人が決めた点数 HUMAN1・HUMAN2 を変えて、的中率を比べる
#   - データの作り方（RISK1・RISK2）を変えて、データから決めた点数がどう変わるかを見る

import random

random.seed(1950)
Q1 = ["よくなじむ", "ふつう", "反抗的"]          # 刑務所の生活へのなじみ方
Q2 = ["よく働く", "ふつう", "怠ける"]            # 働きぶり
# 再犯率（このサイトが作った仮の数）：なじみ方は「ふつう」が最も低い
RISK1 = {"よくなじむ": 0.55, "ふつう": 0.10, "反抗的": 0.60}
RISK2 = {"よく働く": 0.05, "ふつう": 0.15, "怠ける": 0.35}
HUMAN1 = {"よくなじむ": 2, "ふつう": 0, "反抗的": -2}   # 人が決めた点数（高いほど再犯しにくい想定）
HUMAN2 = {"よく働く": 1, "ふつう": 0, "怠ける": -1}

people = []
for _ in range(600):
    a, b = random.choice(Q1), random.choice(Q2)
    r = 1 - (1 - RISK1[a]) * (1 - RISK2[b])
    people.append((a, b, 1 if random.random() < r else 0))   # 1 = 再犯した

def hit_rate(score):
    """最適なしきい値を設定したときの、再犯の有無の的中率"""
    vals = sorted({score(a, b) for a, b, _ in people})
    best = 0
    for t in vals:
        for sign in (1, -1):
            ok = sum((sign * (score(a, b) - t) < 0) == (y == 1) for a, b, y in people)
            best = max(best, ok / len(people))
    return best

# データから点数を決める：選択肢ごとの 0/1 の列を作り、組の平均の差 ÷ ばらつき を最大化する（判別分析と同じ計算）
cols = [("Q1", c) for c in Q1[1:]] + [("Q2", c) for c in Q2[1:]]   # 各質問の1項目を基準（0点）にする
X = [[(1 if (q == "Q1" and a == c) or (q == "Q2" and b == c) else 0) for q, c in cols] for a, b, _ in people]
Y = [y for _, _, y in people]
k = len(cols)
g = {0: [x for x, y in zip(X, Y) if y == 0], 1: [x for x, y in zip(X, Y) if y == 1]}
m = {t: [sum(r[j] for r in g[t]) / len(g[t]) for j in range(k)] for t in g}
W = [[0.0] * k for _ in range(k)]
for t in g:
    for r in g[t]:
        d = [r[j] - m[t][j] for j in range(k)]
        for i in range(k):
            for j in range(k):
                W[i][j] += d[i] * d[j]
diff = [m[0][j] - m[1][j] for j in range(k)]
# W w = diff を解く（ガウスの消去法）
A = [W[i][:] + [diff[i]] for i in range(k)]
for c in range(k):
    p = max(range(c, k), key=lambda r: abs(A[r][c]))
    A[c], A[p] = A[p], A[c]
    for r in range(k):
        if r != c:
            f = A[r][c] / A[c][c]
            A[r] = [A[r][j] - f * A[c][j] for j in range(k + 1)]
w = [A[i][k] / A[i][i] for i in range(k)]
scale = 2 / max(abs(v) for v in w)
data1 = {Q1[0]: 0.0, **{c: w[i] * scale for i, (q, c) in enumerate(cols) if q == "Q1"}}
data2 = {Q2[0]: 0.0, **{c: w[i] * scale for i, (q, c) in enumerate(cols) if q == "Q2"}}

print("なじみ方ごとの再犯率（データ）")
for c in Q1:
    grp = [y for a, _, y in people if a == c]
    print(f"  {c:6s} {sum(grp) / len(grp):5.1%} " + "#" * int(sum(grp) / len(grp) * 50))
print()
print("選択肢への配点（高いほど再犯しにくい）")
print("  選択肢      人が決めた点数   データから決めた点数")
for c in Q1:
    print(f"  なじみ：{c:6s}  {HUMAN1[c]:+5.1f}           {data1[c]:+5.2f}")
for c in Q2:
    print(f"  働き　：{c:6s}  {HUMAN2[c]:+5.1f}           {data2[c]:+5.2f}")
print()
print(f"的中率：人が決めた点数 {hit_rate(lambda a, b: HUMAN1[a] + HUMAN2[b]):.1%}"
      f" ／ データから決めた点数 {hit_rate(lambda a, b: data1[a] + data2[b]):.1%}")
print("データから決めると、「ふつう」に最も高い点数がつく。点数は一方向にまっすぐ並ぶとは限らない。")

071951 · 1967 · k निकटतम पड़ोसी

बस सबसे पास के उदाहरण से सीखना

याद किए उदाहरणों में सबसे पास वाले की नकल से कितना सही अनुमान लगा सकते हैं?

k निकटतम पड़ोसी विधि में नए बिंदु के सबसे पास के k डेटा बिंदु ढूँढकर उसे उनमें सबसे अधिक संख्या वाले वर्ग में रखा जाता है। पहले से डेटा के वितरण का रूप नहीं माना जाता। फ़रवरी 1951 में फ़िक्स (Fix) और हॉजेस (Hodges) ने अमेरिकी वायु सेना के विमानन चिकित्सा विद्यालय की रिपोर्ट में इस प्रकार के नियम पर विचार किया। उन्होंने दिखाया कि डेटा की संख्या n के साथ k भी बढ़े (लेकिन k／n, 0 की ओर जाए), तो वर्गीकरण सर्वोत्तम वर्गीकरण के पास पहुँचता है।

1967 में स्टैनफ़ोर्ड के कवर (Cover) और हार्ट (Hart) ने साबित किया कि केवल सबसे पास के 1 बिंदु का अनुसरण करने वाली निकटतम पड़ोसी विधि (k＝1) में भी, अनंत डेटा हो तो त्रुटि दर सैद्धांतिक न्यूनतम (बेयस त्रुटि दर) की 2 गुनी से अधिक नहीं होती। शोधपत्र कहता है कि इस अर्थ में अनंत डेटा की वर्गीकरण संबंधी आधी जानकारी सबसे पास के 1 बिंदु में होती है।

दाईं ओर बिंदु रखें और k बदलें। k＝1 पर प्रशिक्षण के सारे डेटा सही पहचाने जाते हैं, लेकिन शोर वाले बिंदुओं के आसपास छोटे द्वीप बन जाते हैं।

R* ≤ R ≤ R*（2 − M R* ÷（M − 1））≤ 2R*

R: निकटतम पड़ोसी विधि की त्रुटि दर (अनंत डेटा होने पर)
R*: बेयस त्रुटि दर (वितरण पूरी तरह ज्ञात होने पर भी बची त्रुटि)
M: वर्गों की संख्या

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:k निकटतम पड़ोसी विधि कवर और हार्ट ने 1967 में बनाई
मूल स्रोत के अनुसार:दोनों ने खुद लिखा कि पड़ोसी नियमों को पहले सूत्रबद्ध करके उनके गुणों का अध्ययन संभवतः फ़िक्स और हॉजेस ने किया था। 1951 की रिपोर्ट किसी शोध पत्रिका में प्रकाशित नहीं हुई।

R* और R की ऊपरी सीमा (2 वर्ग होने पर)

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_knn.py

# u09 k 近傍法：近くの k 個の多数決で、新しい点の分類を決める
#
# どの出来事か：機械学習の基本手法の 1 つ（元の論文の年は、第 9 章の k 近傍法の見開きの記録で確かめる）。
# 仕組み：正解のついた点（訓練データ）を覚えておくだけ。新しい点が来たら、最も近い k 個の点を探し、多数決で分類する。
#   k が小さいと、わずかなノイズにも引きずられる（過剰適合）。大きすぎると、境界がぼやける。点はこのサイトが作った例。
# 試してみよう：
#   - K を 1・5・25 と変えて、テストデータでの正解率を見る
#   - NOISE（正解をわざと入れ替える割合）を 0 や 0.3 にする

import math
import random

random.seed(2009)
NOISE = 0.15
K = 5

def make(n):
    pts = []
    for _ in range(n):
        x, y = random.random(), random.random()
        t = 1 if y > 0.5 + 0.25 * math.sin(x * 6) else 0      # 本来の境界（波の形）
        if random.random() < NOISE:
            t = 1 - t
        pts.append((x, y, t))
    return pts

def predict(train, x, y, k):
    near = sorted(train, key=lambda p: (p[0] - x) ** 2 + (p[1] - y) ** 2)[:k]
    return 1 if sum(p[2] for p in near) * 2 > k else 0

train, test = make(200), make(200)
print("k（近くの何個で多数決） → 訓練データでの正解率 / テストデータでの正解率")
for k in (1, 3, K, 15, 25, 75):
    acc_tr = sum(predict(train, x, y, k) == t for x, y, t in train) / len(train)
    acc_te = sum(predict(train, x, y, k) == t for x, y, t in test) / len(test)
    print(f"  k = {k:2d} → 訓練 {acc_tr:.0%} / テスト {acc_te:.0%}")
print("k = 1 は訓練データをすべて正解するが、テストデータでは正解率が下がる（ノイズまで学習するため）")

081957 · 1967 · k-means

बाँटें, फिर औसत पर खिसकाएँ

सही उत्तर दिए बिना डेटा को k समूहों में बाँट सकते हैं?

k-means में (1) बिंदुओं को सबसे पास के प्रतिनिधि के समूह में बाँटना और (2) प्रतिनिधि को उस समूह के औसत पर खिसकाना, बारी-बारी दोहराया जाता है। इससे समूहों के भीतर का बिखराव घटता है। हर दोहराव में कुल बिखराव घटता है या उतना ही रहता है।

एक जैसी प्रक्रिया तक कई लोग अलग-अलग पहुँचे थे। 1957 में बेल लैब्स के लॉयड (Lloyd) ने संकेत के वोल्टेज को निश्चित संख्या के प्रतिनिधि मानों में बदलकर भेजने (PCM) के लिए, न्यूनतम त्रुटि वाले विभाजन और प्रतिनिधि खोजने की प्रक्रिया लिखी। उनकी पांडुलिपि संस्थान के भीतर बाँटी गई (पत्रिका में लगभग 25 साल बाद छपी)। 1967 में कैलिफ़ोर्निया विश्वविद्यालय, लॉस एंजेलिस के जेम्स मैकक्वीन (James MacQueen) ने बिंदुओं को एक-एक करके निकटतम समूह में डालने और तुरंत औसत बदलने की प्रक्रिया को k-means नाम दिया।

दाईं ओर “बाँटें” और “खिसकाएँ” बारी-बारी दबाएँ। प्रतिनिधियों की शुरुआती जगह बदलने पर कभी अलग उत्तर मिल सकता है।

W＝Σ_समूह Σ_{समूह के बिंदु x} ‖x − μ_समूह‖²

x, μ: बिंदु और समूह का प्रतिनिधि (औसत)
‖ ‖²: दूरी का वर्ग
W: समूहों के भीतर बिखराव का कुल योग

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:k-means मैकक्वीन ने 1967 में खोजा
मूल स्रोत के अनुसार:उसी शोधपत्र में उन्होंने पहले के उदाहरणों में सेबेस्ट्येन (Sebestyen, 1962), फ़ॉर्जी (Forgy) और जेनरिच (Jennrich), तथा वॉलेस (Wallace) और बॉल (Ball) गिनाए। 1956 में स्टाइनहाउस (Steinhaus) और 1957 में लॉयड भी यही विचार दे चुके थे।

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_kmeans.py

# u09 k-means：近い代表点に分け、代表点を平均へ動かす、を繰り返す
#
# どの出来事か：1957 年、ロイドがベル研究所の中で回した原稿（記録 lloyd_quantization_1957）と、
#   1967 年、マックイーンが k-means と名づけた論文（記録 macqueen_kmeans_1967）。
# 仕組み：
#   (A) 2 段の繰り返し（今の教科書の形。ロイドの方法 I と同じ形）：全部の点を一番近い代表点に分け直す → 代表点をグループの平均へ。
#   (B) マックイーンの逐次型：点を 1 つずつ見て、一番近いグループに入れ、そのグループの平均をすぐ更新する。
#   どちらも、グループ内のばらつき W（平均からの距離の 2 乗の合計）を小さくしていく。点はこのサイトが作った例。
# 試してみよう：
#   - K を 2・3・5 に変える（本当の山は 3 つ）
#   - SEED を変えて、代表点の初期値によって、違う答えで止まることがあるかを見る

import random

SEED = 1957
K = 3
random.seed(1)
CENTERS = [(2, 2), (7, 3), (4, 8)]
pts = [(cx + random.gauss(0, 1.0), cy + random.gauss(0, 1.0)) for cx, cy in CENTERS for _ in range(40)]

def d2(p, q):
    return (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2

def W(reps, groups):
    return sum(d2(p, reps[g]) for p, g in zip(pts, groups))

random.seed(SEED)
reps = random.sample(pts, K)
print("(A) 2 段の繰り返し：分ける → 平均へ動かす")
for it in range(1, 20):
    groups = [min(range(K), key=lambda j: d2(p, reps[j])) for p in pts]
    w_before = W(reps, groups)
    new = []
    for j in range(K):
        mem = [p for p, g in zip(pts, groups) if g == j]
        new.append((sum(x for x, _ in mem) / len(mem), sum(y for _, y in mem) / len(mem)) if mem else reps[j])
    print(f"  {it:2d} 回目：W = {w_before:8.2f} " + "#" * int(w_before / 15))
    if new == reps:
        print("  代表点が動かなくなったため終了")
        break
    reps = new
print("  最終的な代表点：", "  ".join(f"({x:.2f}, {y:.2f})" for x, y in reps))

print()
print("(B) マックイーンの逐次型：点を 1 つずつ入れて、平均をすぐ更新する")
random.seed(SEED)
order = pts[:]
random.shuffle(order)
means = [list(p) for p in order[:K]]
counts = [1] * K
for p in order[K:]:
    j = min(range(K), key=lambda i: d2(p, means[i]))
    counts[j] += 1
    means[j][0] += (p[0] - means[j][0]) / counts[j]
    means[j][1] += (p[1] - means[j][1]) / counts[j]
print("  最終的な平均値：", "  ".join(f"({x:.2f}, {y:.2f})" for x, y in means), " グループの要素数：", counts)
print("本当の山の中心：", CENTERS)

091958 · 1963 · पदानुक्रमित क्लस्टरिंग

समान चीज़ों को जोड़कर वृक्ष बनाना

समूहों की संख्या तय किए बिना डेटा के समूह कैसे खोजें?

1958 में कैनसस विश्वविद्यालय के कीट वैज्ञानिक सोकल (Sokal) और मिचेनर (Michener) ने मधुमक्खियों की 97 प्रजातियों की तुलना प्रति प्रजाति 122 विशेषताओं से की। पहले समान प्रजातियों को समूह में रखा, फिर बने हुए समूहों को जोड़ते गए और पूरे डेटा को वृक्ष जैसे चित्र (डेंड्रोग्राम) में समेटा।

1963 में अमेरिकी वायु सेना के एक अड्डे की प्रयोगशाला के वार्ड (Ward) ने इसे एक सामान्य प्रक्रिया बनाया। मौजूद समूहों में से 2 चुनने के सभी संयोजन जाँचें और वे 2 जोड़ें जिनसे समूहबद्धता की गुणवत्ता बताने वाला मान (उद्देश्य फलन) सबसे अच्छा हो। सबके 1 समूह होने तक दोहराएँ।

दाईं ओर ठीक वार्ड के शोधपत्र का उदाहरण है। 10 लोगों के अंक 2, 6, 5, 6, 2, 2, 2, 0, 0, 0 को 1 समूह में रखें, तो औसत से अंतर के वर्गों का योग 50.5 है। {0,0,0} {2,2,2,2} {5} {6,6} के 4 समूह बनाने पर वह 0 हो जाता है। “2 समूह जोड़ें” दबाकर वृक्ष बढ़ते देखें।

जोड़ने वाले 2 समूह ＝ वे 2 समूह जिन्हें जोड़ने पर ESS सबसे कम बढ़े (इस मॉडल का उद्देश्य फलन)

ESS: हर समूह के औसत से अंतरों के वर्गों के योग का कुल योग

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:वार्ड विधि उन समूहों को जोड़ती है जिनसे अंतरों के वर्गों का योग सबसे कम बढ़े
मूल स्रोत के अनुसार:1963 का शोधपत्र इसे सामान्य प्रक्रिया के रूप में देता है, जिसमें खोज करने वाला अपने उद्देश्य के अनुसार कोई भी उद्देश्य फलन चुन सकता है। वर्गों का योग समझाने के उदाहरणों में से केवल 1 था।

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_ward.py

# u09 階層的クラスタリング：2 つずつ統合してグループの木を作る（1963 年のウォードの論文の例）
#
# どの出来事か：1958 年、ソーカルとミッチェナーがハチ 97 種を樹形図にまとめた（記録 sokal_michener_tree_1958）。
#   1963 年、ウォードが、2 つずつ統合してグループを減らす一般的な手順を示した（記録 ward_hierarchical_1963）。
# 仕組み：初めは 1 人 1 グループ。統合できる 2 グループの組み合わせをすべて調べ、
#   統合した時の ESS（グループごとの、平均からの偏差の 2 乗の合計）の増加量が最も小さい 2 グループを統合する。1 グループになるまで繰り返す。
#   点数 2, 6, 5, 6, 2, 2, 2, 0, 0, 0 は、ウォードの論文の例そのもの（1 グループなら ESS 50.5、4 グループ {0,0,0}{2,2,2,2}{5}{6,6} なら 0）。
#   ※ 論文では、目的関数は分析者が目的に応じて選べると書かれている。ESS はその例の 1 つ。
# 試してみよう：
#   - SCORES を自分で決めた数値にする
#   - 統合方法を「一番近い 2 人の距離」（最短距離法）に変えると、樹形図の形がどう変わるか（LINK = "single"）

SCORES = [2, 6, 5, 6, 2, 2, 2, 0, 0, 0]
LINK = "ward"

def ess(g):
    m = sum(SCORES[i] for i in g) / len(g)
    return sum((SCORES[i] - m) ** 2 for i in g)

groups = [[i] for i in range(len(SCORES))]
names = {tuple(g): f"{SCORES[g[0]]}" for g in groups}
print("初め：10 グループ（1 人 1 グループ）、ESS の合計 = 0")
print(f"1 グループにまとめた時の ESS = {ess(list(range(len(SCORES)))):.1f}")
print()
step = 0
while len(groups) > 1:
    best = None
    for i in range(len(groups)):
        for j in range(i + 1, len(groups)):
            if LINK == "ward":
                cost = ess(groups[i] + groups[j]) - ess(groups[i]) - ess(groups[j])
            else:
                cost = min(abs(SCORES[a] - SCORES[b]) for a in groups[i] for b in groups[j])
            if best is None or cost < best[0] - 1e-12:
                best = (cost, i, j)
    cost, i, j = best
    merged = groups[i] + groups[j]
    groups = [g for k, g in enumerate(groups) if k not in (i, j)] + [merged]
    step += 1
    total = sum(ess(g) for g in groups)
    show = "  ".join("{" + ",".join(str(SCORES[x]) for x in sorted(g, key=lambda x: SCORES[x])) + "}" for g in sorted(groups, key=lambda g: sum(SCORES[x] for x in g) / len(g)))
    print(f"{step:2d} 回目：{len(groups):2d} グループ  ESS の合計 {total:5.1f}  増加量 {cost:5.2f}  {show}")
print()
print("4 グループの段階で ESS の合計は 0 のまま。そこから先は、統合するたびに ESS が大きく増える。")
print("どこで樹形図を切るか（何グループにするか）は、増加量の大きさを見て分析者が決める。")

101966 · 1975 · हिडन मार्कोव मॉडल

संकेतों से छिपी अवस्था पहचानना

आवाज़ जैसे संकेतों को कैसे पहचानें, जो उसी शब्द के लिए भी हर बार बदलते हैं?

1966 में अमेरिका के इंस्टीट्यूट फ़ॉर डिफ़ेंस एनालिसिस के बाउम (Baum) और पेट्री (Petrie) ने गणितीय मॉडल बनाया, जिसमें बाहर से न दिखने वाली अवस्थाएँ संभावनाओं के अनुसार बदलती हैं और हर अवस्था से संभावनाओं के अनुसार संकेत निकलते हैं। केवल निकले हुए संकेतों के क्रम से अवस्थाएँ बदलने और संकेत निकलने की संभावनाएँ निकाली जा सकती हैं। यही आज का हिडन मार्कोव मॉडल (HMM) है।

1975 में जेम्स बेकर (James Baker) ने आवाज़ समझने वाली प्रणाली DRAGON में इसका इस्तेमाल किया। 1976 में IBM के फ़्रेडरिक जेलिनेक (Frederick Jelinek) ने इसे लगातार बोली पहचानने में अपनाया। 1989 में AT&T बेल लैब्स के रैबिनर (Rabiner) की व्याख्या से यह व्यापक रूप से जाना गया।

दाईं ओर छिपी अवस्थाएँ (आवाज़ · खामोशी) बदलती हैं और केवल आवाज़ की तीव्रता देखी जा सकती है। इससे अवस्थाओं का सबसे संभावित क्रम निकाला जाता है (विटरबी एल्गोरिद्म)।

वह क्रम खोजें जिसके लिए P(अवस्थाओं का क्रम | संकेतों का क्रम) अधिकतम हो

अवस्थाएँ और संकेत: अवस्थाएँ सीधे नहीं दिखतीं (आवाज़ · खामोशी), केवल संकेत दिखते हैं (आवाज़ की तीव्रता)
विटरबी: आगे बढ़ते हुए अब तक का केवल सबसे संभावित रास्ता रखने वाली डायनैमिक प्रोग्रामिंग विधि (अध्याय 5 के DP मिलान जैसा विचार)

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:हिडन मार्कोव मॉडल आते ही आवाज़ पहचान की क्षमता बहुत बढ़ गई
मूल स्रोत के अनुसार:रैबिनर (1989) के एक-एक अंक बोलने वाले प्रयोगों में HMM और पुराने पैटर्न मिलान (DTW) की त्रुटि दर लगभग समान थी (1.3% बनाम 2.0%, 1.8% बनाम 1.1%)। इसकी ताकत आवाज़ की प्रक्रिया को दर्शाने और बड़े शब्द-संग्रह की पहचान तक फैलने में थी।

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_hmm.py

# u09 隠れマルコフモデル：出てきた記号だけから、隠れた状態の並びを当てる（ビタビアルゴリズム）
#
# どの出来事か：1966年、バウムとペトリーが、隠れた状態が移り変わり記号が出てくるモデルの数学を作った
#   （記録 baum_petrie_hmm_1966）。1975年のベイカーの DRAGON から音声認識に導入され、1989年のラビナーの解説で
#   広く知られた（記録 hmm_speech_1975）。
# 仕組み：見えない状態は「声」と「静か」の 2 つ。見えるのは音の大きさ（小・中・大）だけ。
#   (1) 決まった確率で、状態の系列と音の大きさの列を作る。
#   (2) 音の大きさの列だけから、前向きアルゴリズムで「その列が出る確率」を求める。
#   (3) ビタビアルゴリズム（途中までの最も確からしい経路だけを覚えて進む動的計画法）で、最もありそうな状態の系列を推定する。
#   確率は、このサイトが決めた仮の値。
# 試してみよう：
#   - STAY（同じ状態が続く確率）を 0.5 にすると、当てる割合はどうなるか
#   - EMIT の数を近づけて、音の大きさを「まぎらわしく」する

import math
import random

random.seed(1966)
STATES = ["静", "声"]
SYMBOLS = ["小", "中", "大"]
STAY = 0.9
TRANS = [[STAY, 1 - STAY], [1 - STAY, STAY]]
EMIT = [[0.70, 0.25, 0.05],    # 静か：小さい音が多い
        [0.10, 0.35, 0.55]]    # 声　：大きい音が多い
START = [0.5, 0.5]
T = 60

def pick(ps):
    r, s = random.random(), 0
    for i, p in enumerate(ps):
        s += p
        if r < s:
            return i
    return len(ps) - 1

truth, obs = [], []
s = pick(START)
for t in range(T):
    truth.append(s)
    obs.append(pick(EMIT[s]))
    s = pick(TRANS[s])

# (2) 前向きアルゴリズムの計算
alpha = [START[i] * EMIT[i][obs[0]] for i in range(2)]
logp = 0.0
for t in range(1, T):
    z = sum(alpha)
    logp += math.log(z)
    alpha = [a / z for a in alpha]
    alpha = [sum(alpha[i] * TRANS[i][j] for i in range(2)) * EMIT[j][obs[t]] for j in range(2)]
logp += math.log(sum(alpha))

# (3) ビタビアルゴリズム
V = [[math.log(START[i] * EMIT[i][obs[0]]) for i in range(2)]]
back = []
for t in range(1, T):
    row, bp = [], []
    for j in range(2):
        cand = [V[-1][i] + math.log(TRANS[i][j]) for i in range(2)]
        i_best = max(range(2), key=lambda i: cand[i])
        row.append(cand[i_best] + math.log(EMIT[j][obs[t]]))
        bp.append(i_best)
    V.append(row)
    back.append(bp)
path = [max(range(2), key=lambda i: V[-1][i])]
for bp in reversed(back):
    path.append(bp[path[-1]])
path.reverse()

# 比較用：各時刻の記号だけから最も確率の高い状態を選ぶ（前後を見ない）
naive = [max(range(2), key=lambda i: EMIT[i][o]) for o in obs]

print("見えた音の大きさ：", "".join(SYMBOLS[o] for o in obs))
print("本当の状態      ：", "".join(STATES[s] for s in truth))
print("ビタビで当てた  ：", "".join(STATES[s] for s in path))
print("1 コマずつ当てた：", "".join(STATES[s] for s in naive))
ok_v = sum(a == b for a, b in zip(path, truth)) / T
ok_n = sum(a == b for a, b in zip(naive, truth)) / T
print(f"当たった割合：ビタビ {ok_v:.0%} ／ 1 コマずつ {ok_n:.0%}")
print(f"この音の列が、このモデルから出る確率：10 の {logp / math.log(10):.1f} 乗")
print("前後のつながり（状態はしばらく続く）を使うと、1 コマずつ決めるより当たる。")

111971〜2010 · जापान · मॉडल चुनना

ज़रूरत से ज़्यादा मेल को कैसे पहचानें

जितने अधिक मान समायोजित करें, डेटा से उतना अच्छा मेल होगा। कहाँ रुकें?

समायोजित करने वाले मान (पैरामीटर) जितने अधिक हों, सूत्र मौजूद डेटा से उतना सटीक मेल खाता है। लेकिन नए डेटा पर गलत होने की संभावना बढ़ती है (ओवरफ़िटिंग)। 1971 में सांख्यिकीय गणित संस्थान के हिरोतुगु अकाइके (Hirotugu Akaike) ने डेटा से मेल में पैरामीटर की संख्या का दंड जोड़ने वाला मानदंड AIC प्रस्तुत किया। जितना छोटा, उतना अच्छा।

1974 में लंदन के स्टोन (Stone) ने क्रॉस-वैलिडेशन पर शोधपत्र लिखा। इसमें डेटा को सीखने और जाँचने के भागों में बाँटते हैं, विभाजन बदलते हुए औसत नतीजे से मॉडल चुनते हैं। 1977 में उन्होंने दिखाया कि अधिक डेटा होने पर एक-एक उदाहरण छोड़कर किया गया क्रॉस-वैलिडेशन और AIC एक जैसा व्यवहार करते हैं। 2010 में टोक्यो प्रौद्योगिकी संस्थान के सुमिओ वतानाबे (Sumio Watanabe) ने WAIC बनाया, जो उन न्यूरल नेटवर्क आदि पर भी लागू होता है जहाँ AIC की धारणाएँ पूरी नहीं होतीं। उन्होंने साबित किया कि यह एक-एक उदाहरण छोड़ने वाले क्रॉस-वैलिडेशन के समान मान की ओर जाता है।

दाईं ओर बहुपद की घात बढ़ाएँ। प्रशिक्षण त्रुटि घटती रहती है, लेकिन क्रॉस-वैलिडेशन की त्रुटि और AIC कुछ समय बाद बढ़ने लगते हैं।

AIC＝ −2 log L̂ ＋2k

L̂: अधिकतम लाइकलीहुड (डेटा को सबसे संभावित बनाने वाले मानों पर उसकी संभाव्यता)
k: पैरामीटर की संख्या

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:AIC का A, अकाइके (Akaike) का A है
मूल स्रोत के अनुसार:उन्होंने 1974 के शोधपत्र में लिखा कि A इसलिए चुना कि बाद में BIC, DIC जैसे मिलते-जुलते मानदंड आ सकें। 1981 की यादों में भी इसे an information criterion का संक्षेप बताया। वतानाबे के शोधपत्र में WAIC का W भी widely applicable (व्यापक रूप से लागू) का संक्षेप है।

हर घात पर प्रशिक्षण त्रुटि, क्रॉस-वैलिडेशन त्रुटि और AIC

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_aic_cv.py

# u09 過学習（当てはまりすぎ）を見抜く：AIC と、1 つ抜き交差検証
#
# どの出来事か：1971 年に赤池弘次が発表した AIC（記録 aic_akaike_1973）、1974 年のストーンの交差検証
#   （記録 cross_validation_stone_1974）、2010 年の渡辺澄夫の WAIC（記録 waic_watanabe_2010）。
# 仕組み：データ点（このサイトが作った例。元は滑らかな曲線＋ばらつき）に、0 次から 9 次の多項式を最小二乗法で当てはめる。
#   - 訓練誤差：当てはめに使った点そのものに対する誤差。次数を上げるほど下がり続ける。
#   - 1 つ抜き交差検証：1 点を除いた残りで当てはめ、除いた 1 点を予測する。全データで繰り返した平均誤差。
#   - AIC = n log(二乗平均誤差) + 2k （誤差が正規分布に従うとした式。k はパラメータ数）
#   交差検証と AIC は、どちらも途中の次数で最小になる。
# 試してみよう：
#   - N（データの数）を 10 や 100 に変えてみる
#   - NOISE を 0 に近づけると、選ばれる次数はどうなるか

import math
import random

random.seed(1971)
N = 20
NOISE = 0.25
xs = [i / (N - 1) * 2 - 1 for i in range(N)]
ys = [math.sin(2.2 * x) + 0.3 * x * x + random.gauss(0, NOISE) for x in xs]

def fit(xx, yy, deg):
    """最小二乗法で deg 次の多項式を当てはめる（正規方程式をガウスの消去法で解く）"""
    k = deg + 1
    A = [[sum(x ** (i + j) for x in xx) for j in range(k)] + [sum(y * x ** i for x, y in zip(xx, yy))] for i in range(k)]
    for c in range(k):
        p = max(range(c, k), key=lambda r: abs(A[r][c]))
        A[c], A[p] = A[p], A[c]
        if abs(A[c][c]) < 1e-12:
            continue
        for r in range(k):
            if r != c:
                f = A[r][c] / A[c][c]
                A[r] = [A[r][j] - f * A[c][j] for j in range(k + 1)]
    return [A[i][k] / A[i][i] if abs(A[i][i]) > 1e-12 else 0 for i in range(k)]

def pred(cf, x):
    return sum(c * x ** i for i, c in enumerate(cf))

print("次数    訓練誤差    交差検証の誤差     AIC")
rows = []
for deg in range(0, 10):
    cf = fit(xs, ys, deg)
    train = sum((y - pred(cf, x)) ** 2 for x, y in zip(xs, ys)) / N
    cv = 0
    for i in range(N):
        cfi = fit(xs[:i] + xs[i + 1:], ys[:i] + ys[i + 1:], deg)
        cv += (ys[i] - pred(cfi, xs[i])) ** 2
    cv /= N
    aic = N * math.log(train) + 2 * (deg + 2)      # 係数 deg+1 個と、ばらつき（分散）1 個
    rows.append((deg, train, cv, aic))
    print(f"  {deg}   {train:9.4f}   {cv:12.4f}   {aic:8.2f}  " + "#" * min(40, int(cv * 40)))
best_cv = min(rows, key=lambda r: r[2])[0]
best_aic = min(rows, key=lambda r: r[3])[0]
print(f"交差検証で選ぶ次数：{best_cv}　／　AIC で選ぶ次数：{best_aic}")
print("訓練誤差だけで選ぶと、常に最大の次数（過学習・当てはまりすぎ）を選んでしまう。")

121977 · EM एल्गोरिद्म

छिपे हिस्से भरकर फिर गणना करना

डेटा का कुछ हिस्सा छिपा हो, तो सबसे संभावित मान कैसे निकालें?

1977 में हार्वर्ड विश्वविद्यालय आदि के आर्थर डेम्प्स्टर (Arthur Dempster), नैन लेयर्ड (Nan Laird) और डोनाल्ड रुबिन (Donald Rubin) ने आंशिक रूप से छिपे डेटा से संभावित पैरामीटर निकालने की सामान्य विधि दी। इसमें मौजूदा मानों से छिपे हिस्से का अपेक्षित मान निकालने का E चरण (expectation) और भरे हुए डेटा से मान दोबारा निकालने का M चरण (maximization) बारी-बारी दोहराया जाता है। हर दोहराव में डेटा का लाइकलीहुड घटता नहीं है।

पहला उदाहरण आनुवंशिक प्रक्रिया से 197 जानवरों के 4 प्रकारों में 125, 18, 20, 34 के रूप में बँटने का डेटा है। दाईं ओर “197 जानवरों का उदाहरण” चुनकर “E：भरें” और “M：फिर गणना करें” बारी-बारी दबाएँ। π, 0.5 से शुरू होकर 8 दोहराव में 0.6268214… पर टिकता है—शोधपत्र की तालिका 1 जैसा। “2 चोटियाँ” में मिले-जुले बिंदु अलग चोटियों में बँटते हैं।

E：x₂ ＝125 ×（π／4）÷（1／2＋π／4）
M：π＝（x₂ ＋34）÷（x₂ ＋18＋20＋34）

π: निकाला जाने वाला मान (आनुवंशिक मॉडल की संभावना)
x₂: 125 जानवरों में से छिपे दूसरे समूह में आने वाली संख्या का अपेक्षित मान

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:EM एल्गोरिद्म डेम्प्स्टर और साथियों ने 1977 में खोजा
मूल स्रोत के अनुसार:तीनों ने खुद लिखा कि विशेष मामलों में यह पहले कई बार प्रस्तावित हो चुका था (हार्टली (Hartley), 1958; बाउम (Baum) और साथी आदि)। उनका योगदान सामान्य रूप देना, नाम रखना और लाइकलीहुड न घटने का प्रमाण था।

हर दोहराव पर π

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_em.py

# u09 EM アルゴリズム：見えないデータを補って（E）、パラメータを推定し直す（M）を繰り返す
#
# どの出来事か：1977 年、デンプスター、レアード、ルービンが EM アルゴリズムと名づけ、一般化した
#   （記録 dempster_em_1977）。論文の最初の例は、遺伝の仕組みにより 197 匹の動物が 4 つの種類に
#   125, 18, 20, 34 匹ずつ分かれたデータである（ラオの 1965 年の著書の例）。種類の確率は (1/2 + π/4, (1-π)/4, (1-π)/4, π/4)。
# 仕組み：
#   (1) 1 つ目の種類（125 匹）を、確率 1/2 の組と π/4 の組の 2 つに分ける。どちらに何匹いるかは観測できない。
#       E ステップ：現在の π を使って、π/4 の組にいそうな期待数 x2 を計算する。
#       M ステップ：補ったデータを使って π を計算し直す。
#       π = 0.5 から始めると、論文の表 1 と同じ数値の推移になる（8 回で 0.626821484）。
#   (2) 2 つの山（正規分布）が混ざった点を、山ごとに分ける、同じ形の計算。点はこのサイトが作った例。
# 試してみよう：
#   - (1) の π の初期値を 0.1 や 0.9 に変えても、同じ値に収束するか
#   - (2) の山の中心 MU_TRUE を近づけると、どうなるか

import math
import random

print("(1) 197 匹の例（論文の表 1 と同じ計算）")
y1, y2, y3, y4 = 125, 18, 20, 34
pi = 0.5
star = None
seq = [pi]
for p in range(8):
    x2 = y1 * (pi / 4) / (0.5 + pi / 4)            # E ステップ
    pi = (x2 + y4) / (x2 + y2 + y3 + y4)            # M ステップ
    seq.append(pi)
# 収束値（二次方程式の解）
a, b, c = 197, -(y1 - 2 * y2 - 2 * y3 - y4), -2 * y4
star = (-b + math.sqrt(b * b - 4 * a * c)) / (2 * a)
for p, v in enumerate(seq):
    print(f"  p = {p}：π = {v:.9f}　差 π* - π = {star - v:.9f}")
print(f"  収束値 π* = {star:.9f}（論文の表 1 と、最後の桁の丸め方を除いて同じ）")

print()
print("(2) 2 つの山（正規分布）が混ざった点を、山ごとに分ける")
random.seed(1977)
MU_TRUE = (-2.0, 1.5)
data = [random.gauss(MU_TRUE[0], 1.0) for _ in range(150)] + [random.gauss(MU_TRUE[1], 0.8) for _ in range(100)]
mu, sd, w = [-0.5, 0.5], [1.5, 1.5], [0.5, 0.5]

def normal(x, m, s):
    return math.exp(-((x - m) ** 2) / (2 * s * s)) / (s * math.sqrt(2 * math.pi))

for it in range(1, 31):
    # E ステップ：各点が、どちらの山から来たかの確率（負担率）を計算する
    r = []
    ll = 0
    for x in data:
        p0, p1 = w[0] * normal(x, mu[0], sd[0]), w[1] * normal(x, mu[1], sd[1])
        ll += math.log(p0 + p1)
        r.append(p0 / (p0 + p1))
    # M ステップ：負担率で重みづけして、平均・標準偏差・割合を再計算する
    n0 = sum(r)
    n1 = len(data) - n0
    mu = [sum(ri * x for ri, x in zip(r, data)) / n0, sum((1 - ri) * x for ri, x in zip(r, data)) / n1]
    sd = [math.sqrt(sum(ri * (x - mu[0]) ** 2 for ri, x in zip(r, data)) / n0),
          math.sqrt(sum((1 - ri) * (x - mu[1]) ** 2 for ri, x in zip(r, data)) / n1)]
    w = [n0 / len(data), n1 / len(data)]
    if it in (1, 2, 3, 5, 10, 20, 30):
        print(f"  {it:2d} 回目：山 1 の平均 {mu[0]:+.2f}、山 2 の平均 {mu[1]:+.2f}、割合 {w[0]:.2f} : {w[1]:.2f}、対数尤度 {ll:.1f}")
print(f"真の平均：{MU_TRUE[0]:+.2f} と {MU_TRUE[1]:+.2f}、割合 0.60 : 0.40")
print("対数尤度は、繰り返しても下がることはない（論文が証明したこと）。")

131979 · जापान · ओत्सु का द्विआधारीकरण

सफ़ेद-काले की सीमा खुद तय करना

धूसर छवि को सफ़ेद और काले में बाँटने के लिए चमक की सीमा कैसे चुनें?

अक्षरों या वस्तुओं को पृष्ठभूमि से अलग करने के लिए पिक्सेल को किसी चमक (थ्रेशोल्ड) के दोनों ओर 2 वर्गों में बाँटते हैं। 1979 में इलेक्ट्रोटेक्निकल प्रयोगशाला के नोबुयुकी ओत्सु (Nobuyuki Otsu) ने इस सीमा को अपने-आप तय करने की विधि अंग्रेज़ी शोधपत्र में दी। चमक के आवृत्ति वितरण (हिस्टोग्राम) को सीमा k पर 2 भागों में बाँटने पर वह k चुनते हैं जिसके लिए समूहों के बीच बिखराव (वर्गों के बीच विचरण) अधिकतम हो। यह हर समूह के भीतर बिखराव न्यूनतम करने के बराबर है।

गणना में केवल उस चमक तक पिक्सेल का अनुपात और उनकी चमक का योग चाहिए, इसलिए यह बहुत आसान है। यह सही उत्तर वाले उदाहरणों के बिना सीमा तय करने वाली अनसुपरवाइज़्ड विधि है। शोधपत्र में नए और पुराने रिबन से टाइपराइटर पर लिखे A अक्षर, कपड़े के पैटर्न और कोशिकाओं की छवियाँ उदाहरण थीं।

दाईं ओर सीमा बदलकर ग्राफ़ की चोटी खोजें (छवि इस साइट का बनाया उदाहरण है)।

σ_B²(k)＝ω₀ ω₁（μ₀ − μ₁）²　→　वह k चुनें जहाँ σ_B² अधिकतम हो

ω₀, ω₁: गहरे और हल्के समूहों में पिक्सेल के अनुपात
μ₀, μ₁: हर समूह की औसत चमक

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:ओत्सु का द्विआधारीकरण छवि को सफ़ेद-काला बनाने की छोटी तरकीब है
मूल स्रोत के अनुसार:ओत्सु ने इसे विभेदक विश्लेषण से निकाला और पैटर्न पहचान की मूल समस्याओं में 1 माना। निष्कर्ष में भी लिखा कि हिस्टोग्राम उपलब्ध हो तो इसे अन्य अनसुपरवाइज़्ड वर्गीकरण में इस्तेमाल कर सकते हैं।

सीमा k और वर्गों के बीच विचरण σB²

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_otsu.py

# u09 大津の二値化：白と黒の境目（しきい値）を、2 つの組が最もよく分かれる値として自動で決める
#
# どの出来事か：1979 年、大津展之（電子技術総合研究所）の英語論文（記録 otsu_threshold_1979）。
# 仕組み：明るさ 0〜15 の度数分布（ヒストグラム）を、明るさ k で「暗い組」と「明るい組」に分ける。
#     クラス間分散 σB^2(k) = ω0 × ω1 × (μ0 - μ1)^2
#   （ω は組の画素の割合、μ は組の明るさの平均）が最大になる k を選ぶ。
#   計算には、その明るさまでの画素の割合と明るさの合計（0 次と 1 次の累積モーメント）だけを使う。
#   画像は、このサイトが作った例の文字「A」（16×16）に、明るさのむらとノイズを加えたもの。
# 試してみよう：
#   - NOISE を大きくすると、しきい値と白黒画像はどうなるか
#   - 自分で決めたしきい値 MY_K と比べる

import random

random.seed(1979)
NOISE = 1.6
MY_K = 5
ART = [
    "................",
    ".......##.......",
    "......####......",
    "......#..#......",
    ".....##..##.....",
    ".....#....#.....",
    "....##....##....",
    "....########....",
    "...##########...",
    "...##......##...",
    "..##........##..",
    "..##........##..",
    ".##..........##.",
    ".##..........##.",
    "................",
    "................",
]
img = []
for y, row in enumerate(ART):
    line = []
    for x, ch in enumerate(row):
        base = 3 if ch == "#" else 11          # 文字は暗く、紙は明るい
        v = base + 0.15 * x + random.gauss(0, NOISE)   # 右ほど少し明るい（むら）
        line.append(max(0, min(15, round(v))))
    img.append(line)

L = 16
hist = [0] * L
for row in img:
    for v in row:
        hist[v] += 1
N = sum(hist)
p = [h / N for h in hist]
mu_T = sum(i * p[i] for i in range(L))
best, table = None, []
w, m = 0.0, 0.0
for k in range(L - 1):
    w += p[k]            # 0 次の累積モーメント（k までの割合）
    m += k * p[k]        # 1 次の累積モーメント（k までの明るさの合計）
    if 0 < w < 1:
        sb = (mu_T * w - m) ** 2 / (w * (1 - w))     # ω0 ω1 (μ0 - μ1)^2 と同じ値
    else:
        sb = 0
    table.append(sb)
    if best is None or sb > best[1]:
        best = (k, sb)

print("明るさ  画素の数  クラス間分散")
for k in range(L):
    sb = table[k] if k < len(table) else 0
    print(f"  {k:2d}    {hist[k]:4d} {'#' * (hist[k] // 2):20s}  {sb:6.2f} {'*' * int(sb * 2)}")
K = best[0]
print(f"大津の方法で選んだしきい値：明るさ {K} 以下を黒にする")

def show(k):
    for row in img:
        print("  " + "".join("#" if v <= k else "." for v in row))

print()
print(f"大津のしきい値 {K} で白黒にした画像")
show(K)
print()
print(f"自分で決めたしきい値 {MY_K} で白黒にした画像")
show(MY_K)

141985 · बेयज़ियन नेटवर्क

साक्ष्य से संभावनाएँ जाल में बदलती हैं

क्या कई संकेतों से संभावना के नियम तोड़े बिना तर्क निकाल सकते हैं?

1980 के दशक के शुरुआती कई विशेषज्ञ प्रणालियाँ (अध्याय 6) अनिश्चित तर्क के लिए तदर्थ गणना नियम इस्तेमाल करती थीं। कैलिफ़ोर्निया विश्वविद्यालय के जूडिया पर्ल (Judea Pearl) ने 1982 में लिखा कि कई AI शोधकर्ता यह मिथक मानते हैं कि संभावना के कुछ नियम तो तोड़ने ही होंगे। उन्होंने ऐसा ग्राफ़ सोचा जिसमें बातें बिंदु हों, सीधी निर्भरता तीर से जुड़े और उसकी ताकत सशर्त संभावना से व्यक्त हो। उन्होंने दिखाया कि इसमें बिंदु केवल अपने पड़ोसियों से छोटे संदेश लेकर-देकर पूरे नेटवर्क की संभावनाएँ सही ढंग से बदल सकते हैं। 1985 में उन्होंने इस रूप को बेयज़ियन नेटवर्क कहा।

दाईं ओर छोटा नेटवर्क है जहाँ “बारिश” और “पानी देना”, “घास गीली होना” के कारण हैं (संभावनाएँ इस साइट के बनाए उदाहरण हैं)। “घास गीली थी” जोड़ने से बारिश और पानी देने, दोनों की संभावना बढ़ती है। फिर “बारिश हुई थी” जोड़ने पर पानी देने की संभावना घटती है। एक कारण से ही बात समझ में आ जाती है।

P(बारिश | गीला)＝P(गीला | बारिश) × P(बारिश) ÷ P(गीला)

P(A | B): B ज्ञात होने पर A की संभावना
तीर: सीधे कारण से परिणाम की दिशा

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:बेयज़ियन नेटवर्क डेटा से सीखने के सांख्यिकीय औज़ार के रूप में पैदा हुआ
मूल स्रोत के अनुसार:पर्ल की 1985 की रिपोर्ट का शीर्षक साक्ष्य से अनुमान लगाने वाली अपने-आप काम करती स्मृति के मॉडल पर था और उसे संज्ञानात्मक विज्ञान के सम्मेलन में प्रस्तुत किया गया। 1982 का शोधपत्र विशेषज्ञ प्रणालियों की तदर्थ गणना के उत्तर के रूप में लिखा गया था।

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_bayesnet.py

# u09 ベイジアンネットワーク：証拠が得られると、確率がネットワークを伝わる
#
# どの出来事か：1985年、パールがベイジアンネットワークと名づけた報告（記録 pearl_bayesian_network_1985）。
#   1982年には、確率の規則を曲げずに、ノードどうしの短いメッセージのやりとりで、全体を更新できると示していた。
# 仕組み：3つの事象「雨」「水まき」「芝生がぬれる」の小さなネットワーク。矢印は 雨 → ぬれる、水まき → ぬれる。
#   それぞれの確率（条件付き確率表）は、このサイトが設定した仮の値。
#   全部の組み合わせ（2×2×2 ＝ 8 通り）の確率を書き出し、証拠に合わないものを除いて、残りで割り直す（正規化）。
#   ここでは小さいので全部数えるが、大きなネットワークでは、パールのメッセージのやりとりが必要になる。
#   「ぬれていた」と分かると雨も水まきも確率が上がるが、さらに「雨だった」と分かると、水まきの確率は下がる
#   （雨によって説明がつき、もう片方の可能性が下がるため）。
# 試してみよう：
#   - P_RAIN（雨の確率）や WET の表を変えてみる
#   - 「水まきをした」と分かったときの、雨の確率を計算してみる

import itertools

P_RAIN = 0.2
P_SPRINKLER = 0.3
WET = {(0, 0): 0.02, (0, 1): 0.85, (1, 0): 0.90, (1, 1): 0.98}   # P(ぬれる | 雨, 水まき)

def joint(r, s, w):
    pr = P_RAIN if r else 1 - P_RAIN
    ps = P_SPRINKLER if s else 1 - P_SPRINKLER
    pw = WET[(r, s)] if w else 1 - WET[(r, s)]
    return pr * ps * pw

def ask(target, evidence):
    """evidence（例：{'w': 1}）が与えられたときの、target が 1 である確率"""
    num = den = 0.0
    for r, s, w in itertools.product((0, 1), repeat=3):
        v = {"r": r, "s": s, "w": w}
        if any(v[k] != x for k, x in evidence.items()):
            continue
        p = joint(r, s, w)
        den += p
        if v[target]:
            num += p
    return num / den

def bar(p):
    return f"{p:6.1%} " + "#" * int(p * 40)

print("何も分かっていない時")
print("  雨      ", bar(ask("r", {})))
print("  水まき  ", bar(ask("s", {})))
print("  ぬれる  ", bar(ask("w", {})))
print("「芝生がぬれていた」と分かった時")
print("  雨      ", bar(ask("r", {"w": 1})))
print("  水まき  ", bar(ask("s", {"w": 1})))
print("さらに「雨だった」と分かった時")
print("  水まき  ", bar(ask("s", {"w": 1, "r": 1})))
print()
print("8 通りの組み合わせと確率（雨・水まき・ぬれる）")
for r, s, w in itertools.product((0, 1), repeat=3):
    print(f"  雨{r} 水まき{s} ぬれる{w}：{joint(r, s, w):.4f}")

151986 · निर्णय वृक्ष

सबसे पहले कौन-सा सवाल पूछें?

सवालों से उत्तर देने वाला “वृक्ष” कैसे बनाएँ?

निर्णय वृक्ष “मौसम कैसा है?” और “नमी अधिक है?” जैसे सवालों को शाखाओं में रखता है। उत्तर के अनुसार शाखा पर आगे बढ़कर पत्ती पर पहुँचते ही जवाब देता है। 1986 में ऑस्ट्रेलिया के क्विनलन (Quinlan) ने ID3 नाम की निर्माण विधि शोधपत्र में दी। डेटा बाँटने पर सबसे अधिक जानकारी (इन्फ़ॉर्मेशन गेन, बिट में मापा जाता है) देने वाला सवाल पहले चुनते हैं और हर नई शाखा में यही दोहराते हैं।

दाईं ओर की 14 पर्चियाँ शोधपत्र की तालिका 1 की पंक्तियाँ हैं। उन पर पंक्ति संख्या और उत्तर P या N दिखते हैं। “विवरण：स्रोत की 14 पंक्तियाँ · पूरा वृक्ष · जानकारी की मात्रा” खोलने पर शनिवार सुबह का मौसम, तापमान, नमी और हवा भी पढ़ सकते हैं। मौसम से बाँटने पर सबसे अधिक 0.246 बिट जानकारी मिलती है, इसलिए मौसम वृक्ष की जड़ बनता है। सवाल दबाकर खुद वृक्ष बढ़ाएँ।

इन्फ़ॉर्मेशन गेन ＝I(पूरा डेटा) − Σ（बँटे समूह का अनुपात × I(वह समूह)）　　I＝ −p log₂ p − n log₂ n

p, n: समूह में P और N के अनुपात
I: उत्तर जानने के लिए आवश्यक जानकारी (बिट)

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:निर्णय वृक्ष AI (मशीन लर्निंग) के शोध से निकले
मूल स्रोत के अनुसार:सांख्यिकी में भी अलग धाराएँ थीं: मॉर्गन (Morgan) और सॉनक्विस्ट (Sonquist) का AID (1963) तथा ब्राइमन (Breiman) और साथियों का CART (1984)। 1986 के शोधपत्र की संदर्भ सूची में CART नहीं है और दोनों धाराएँ अलग-अलग बढ़ीं। इसमें पाठ्यपुस्तक के “मौसम और टेनिस” जैसे उदाहरण का रूप है, लेकिन टेनिस शब्द नहीं आता।

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_id3.py

# u09 決定木（ID3）：情報利得が最も大きい質問から順に選んで、木を作る
#
# どの出来事か：1986 年、クインランが ID3 を論文『Induction of Decision Trees』にまとめた（記録 decision_tree_id3_1986）。
# 仕組み：下の 14 行は、論文の表 1（土曜の朝の天気・気温・湿度・風と、答え P か N）そのもの。
#   答えを知るのに必要な情報量 I = -p log2 p - n log2 n（p, n は P と N の割合）。
#   ある質問でデータを分けると、分けた組ごとの I の平均が残る。減った分が情報利得になる。一番大きい質問を根にして、
#   分かれた先でも同じ処理をくり返す。論文では、天気で分けると 0.246 ビットで最大になる。
# 試してみよう：
#   - 表の 1 行の答えを入れ替えると、木はどう変わるか
#   - 情報利得の代わりに「分けた組の数が多いほど得」になる基準を使うと、どうなるか

import math

COLS = ["天気", "気温", "湿度", "風"]
ROWS = [
    ("sunny", "hot", "high", "false", "N"),
    ("sunny", "hot", "high", "true", "N"),
    ("overcast", "hot", "high", "false", "P"),
    ("rain", "mild", "high", "false", "P"),
    ("rain", "cool", "normal", "false", "P"),
    ("rain", "cool", "normal", "true", "N"),
    ("overcast", "cool", "normal", "true", "P"),
    ("sunny", "mild", "high", "false", "N"),
    ("sunny", "cool", "normal", "false", "P"),
    ("rain", "mild", "normal", "false", "P"),
    ("sunny", "mild", "normal", "true", "P"),
    ("overcast", "mild", "high", "true", "P"),
    ("overcast", "hot", "normal", "false", "P"),
    ("rain", "mild", "high", "true", "N"),
]

def info(rows):
    n = len(rows)
    if n == 0:
        return 0.0
    p = sum(r[-1] == "P" for r in rows) / n
    return -sum(q * math.log2(q) for q in (p, 1 - p) if q > 0)

def gain(rows, c):
    vals = sorted({r[c] for r in rows})
    rest = sum(len([r for r in rows if r[c] == v]) / len(rows) * info([r for r in rows if r[c] == v]) for v in vals)
    return info(rows) - rest

print(f"全体の情報量 I(9 P, 5 N) = {info(ROWS):.3f} ビット")
for c, name in enumerate(COLS):
    print(f"  {name}で分けたときの情報利得：{gain(ROWS, c):.3f} ビット")
print("  （論文は途中の値を丸めて 0.940 - 0.694 = 0.246 と書いている。湿度も同じ理由で 0.151）")
print()

def grow(rows, cols, depth=0):
    pad = "    " * depth
    labels = {r[-1] for r in rows}
    if len(labels) == 1:
        print(f"{pad}→ 答え {labels.pop()}（{len(rows)} 件）")
        return
    if not cols:
        print(f"{pad}→ 分類できない（{len(rows)} 件）")
        return
    c = max(cols, key=lambda c: gain(rows, c))
    print(f"{pad}「{COLS[c]}は？」（情報利得 {gain(rows, c):.3f}）")
    for v in sorted({r[c] for r in rows}):
        print(f"{pad}  {v}:")
        grow([r for r in rows if r[c] == v], [x for x in cols if x != c], depth + 1)

print("ID3 が作った決定木")
grow(ROWS, list(range(4)))

161988 · 1989 · 1994 · रीइन्फोर्समेंट लर्निंग

पुरस्कार से सीखना

सही उत्तर बताए बिना, कभी-कभी सिर्फ़ “पुरस्कार” देकर सीखना संभव है?

रीइन्फोर्समेंट लर्निंग में पुरस्कार के सहारे कोशिश और गलती से व्यवहार सीखा जाता है। 1988 में GTE प्रयोगशाला के रिचर्ड सटन (Richard Sutton) ने TD विधि का सिद्धांत दिया, जो अंतिम परिणाम का इंतज़ार किए बिना कल के अनुमान से अंतर के आधार पर आज का अनुमान सुधारती है। 1989 में क्रिस्टोफ़र वॉटकिंस (Christopher Watkins) ने डॉक्टरेट थीसिस में Q-लर्निंग दी। इसमें अवस्था x पर क्रिया a के मूल्य Q(x, a) को हर कोशिश के साथ थोड़ा सुधारा जाता है। उन्होंने साबित किया कि हर क्रिया बार-बार आज़माने से सर्वोत्तम मूल्यों के पास पहुँच सकते हैं।

1994 में टोक्यो प्रौद्योगिकी संस्थान के काज़ुतेरु मियाज़ाकी (Kazuteru Miyazaki), मासायुकी यामामुरा (Masayuki Yamamura) और शिगेनोबु कोबायाशी (Shigenobu Kobayashi) ने profit sharing का अध्ययन किया। पुरस्कार मिलने पर यह उससे पहले की क्रियाओं की पूरी शृंखला को मज़बूत करती है। उन्होंने केवल चक्कर लगवाने वाली क्रियाएँ न सीखने की शर्तें साबित कीं और जापानी कृत्रिम बुद्धिमत्ता सोसायटी का शोधपत्र पुरस्कार पाया।

दाईं ओर की भूलभुलैया में खज़ाने (पुरस्कार) तक जाने का रास्ता Q-लर्निंग और profit sharing से सिखाएँ।

Q(x, a) ← Q(x, a)＋α（r＋γ max_b Q(x′, b) − Q(x, a)）

r, x′: मिला पुरस्कार और अगली अवस्था
α, γ: सीखने की दर और भविष्य के पुरस्कार को कम महत्व देने की छूट दर (0〜1)

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:TD लर्निंग सटन ने 1988 में खोजी
मूल स्रोत के अनुसार:सटन ने खुद लिखा कि TD विधि सैमुअल (Samuel) के चेकर्स प्रोग्राम (1959, अध्याय 3) आदि में पहले इस्तेमाल हुई थी, लेकिन अच्छी तरह समझी नहीं गई थी। Q-लर्निंग भी 1992 के शोधपत्र में नहीं, 1989 की डॉक्टरेट थीसिस में पैदा हुई थी।

कोशिशों की संख्या और खज़ाने तक पहुँचने के कदम

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_q_learning.py

# u09 強化学習：報酬を手がかりに行動の選び方を学習する（TD法・Q学習・profit sharing）
#
# どの出来事か：1988 年のサットンの TD 法（記録 sutton_td_1988）、1989 年のワトキンスの Q 学習
#   （記録 watkins_q_learning_1989）、1994 年の宮崎和光・山村雅幸・小林重信の profit sharing の理論
#   （記録 miyazaki_profit_sharing_1994）。
# 仕組み：
#   (1) サットンの論文の例：中央の D から左右に 1 歩ずつランダムに進み、左端 A か右端 G に着いたら終了する。
#       G に着いたら報酬 1。各地点から G に着く確率を、次の地点の予測との誤差で更新していく（TD法）。
#       理論値は B〜F で 1/6, 2/6, 3/6, 4/6, 5/6。
#   (2) 5×5 の迷路（このサイトが作った例）で、ゴール（宝）までの進み方を学習する。
#       Q学習：Q(x,a) ← Q(x,a) + α (r + γ max Q(x',b) - Q(x,a)) を 1 歩ごとに更新。
#       profit sharing：ゴールに着いたら、それまでの行動をまとめて、ゴールに近い行動ほど大きく強化する。
#       1 歩さかのぼるごとに強化量を 1/S にする。宮崎たちの論文は、S ≥ L + 1 なら遠回りの行動を学習しないと証明し、
#       L は実装では「行動の種類 − 1」とすれば十分、と書いている。ここでは行動が 4 種類なので S = 4。
# 試してみよう：
#   - ALPHA（学習率）や GAMMA（将来の報酬に対する割引率）を変える
#   - EPS（ランダムに試す探索の割合）を 0 にすると、どうなるか
#   - S_RATIO を 1.2 にして（条件を満たさない）、profit sharing の矢印がどうなるかを見る

import random

random.seed(1988)

print("(1) サットンのランダムウォーク（A B C D E F G）：TD法で、各地点から G に着く確率を学習する")
V = [0.0] + [0.5] * 5 + [0.0]    # A と G は端。B〜F の初期予測値は 0.5
ALPHA_TD = 0.01
for ep in range(1, 3001):
    s = 3
    while 0 < s < 6:
        s2 = s + random.choice((-1, 1))
        r = 1.0 if s2 == 6 else 0.0
        target = r if s2 in (0, 6) else V[s2]
        V[s] += ALPHA_TD * (target - V[s])      # 次の予測（または結果）との誤差で更新する
        s = s2
    if ep in (1, 10, 100, 1000, 3000):
        print(f"  {ep:4d} 回：" + "  ".join(f"{'BCDEF'[i - 1]} {V[i]:.2f}" for i in range(1, 6)))
print("  理論値：" + "  ".join(f"{'BCDEF'[i - 1]} {i / 6:.2f}" for i in range(1, 6)))

print()
print("(2) 迷路でゴールまでの経路を学習する（S＝スタート、G＝ゴール、#＝壁）")
MAZE = ["S...#",
        ".##.#",
        "...#.",
        ".#...",
        "...#G"]
H, Wd = len(MAZE), len(MAZE[0])
MOVES = [(-1, 0), (1, 0), (0, -1), (0, 1)]
ARROW = "↑↓←→"
ALPHA, GAMMA, EPS = 0.5, 0.9, 0.1
S_RATIO = 4          # profit sharing の強化減少比 S（行動 4 種類 → L = 3 → S ≥ 4）

def step(pos, a):
    y, x = pos[0] + MOVES[a][0], pos[1] + MOVES[a][1]
    if not (0 <= y < H and 0 <= x < Wd) or MAZE[y][x] == "#":
        return pos, -0.05, False          # 壁にぶつかったら進めない（小さなペナルティ）
    if MAZE[y][x] == "G":
        return (y, x), 1.0, True
    return (y, x), 0.0, False

def choose(Q, pos):
    if random.random() < EPS:
        return random.randrange(4)
    q = Q[pos]
    m = max(q)
    return random.choice([a for a in range(4) if q[a] == m])

def run(method, episodes=300):
    Q = {(y, x): [0.0] * 4 for y in range(H) for x in range(Wd)}
    steps_log = []
    for ep in range(episodes):
        pos, done, n, hist = (0, 0), False, 0, []
        while not done and n < 200:
            a = choose(Q, pos)
            nxt, r, done = step(pos, a)
            if method == "Q":
                target = r + (0 if done else GAMMA * max(Q[nxt]))
                Q[pos][a] += ALPHA * (target - Q[pos][a])
            else:
                hist.append((pos, a))
            pos, n = nxt, n + 1
        if method == "PS" and done:
            credit = 1.0
            for p, a in reversed(hist):           # ゴールに近い行動ほど大きく強化する（等比で減らす）
                Q[p][a] += credit
                credit /= S_RATIO
        steps_log.append(n)
    return Q, steps_log

for method, name in (("Q", "Q 学習"), ("PS", "profit sharing")):
    random.seed(1989)
    Q, log = run(method)
    print(f"  {name}：ゴールに着くまでの平均歩数　最初の 10 回 {sum(log[:10]) / 10:.1f} 歩 → 最後の 10 回 {sum(log[-10:]) / 10:.1f} 歩")
    for y in range(H):
        line = ""
        for x in range(Wd):
            c = MAZE[y][x]
            line += c if c in "#G" else ARROW[max(range(4), key=lambda a: Q[(y, x)][a])]
        print("     " + line)
print("  最短ルートは 8 歩。正解の道順を教えていないのに、報酬だけから進み方ができあがる。")

171990 · 1995 · 1999 · बूस्टिंग

गलतियों के अनुसार कमज़ोर मॉडल जोड़ना

अंदाज़े से थोड़ा बेहतर तरीकों को मिलाकर मज़बूत तरीका बना सकते हैं?

शुरुआत एक सैद्धांतिक सवाल से हुई: अंदाज़े से बस थोड़ा बेहतर कमज़ोर लर्निंग और मनचाही सटीकता वाली मज़बूत लर्निंग की क्षमता क्या समान है? 1990 में MIT के रॉबर्ट शापायर (Robert Schapire) ने दोनों की समान क्षमता साबित की और कमज़ोर विधि को मज़बूत बनाने का एल्गोरिद्म दिया। 1995 में योआव फ़्रॉयंड (Yoav Freund) और शापायर ने AdaBoost प्रस्तुत किया। यह पिछले दौर में गलत पहचाने गए डेटा को अधिक वज़न देता है, अगले वर्गीकारक को उससे सिखाता है और अंत में वज़न वाले बहुमत से निर्णय मिलाता है।

1999 में स्टैनफ़ोर्ड के फ़्रीडमैन (Friedman) ने ग्रेडिएंट बूस्टिंग को ढलान पर नीचे जाने वाले अनुकूलन के रूप में सामान्य किया। इसमें अगला छोटा निर्णय वृक्ष मौजूदा अनुमान और सही उत्तर की त्रुटि (अवशेष) बताता है और नतीजे थोड़ा-थोड़ा जोड़े जाते हैं।

दाईं ओर “1 दौर जोड़ें” दबाने पर गलत पहचाने गए बिंदु बड़े होते हैं और अगली सीमा उन्हें वर्गीकृत करने आती है।

α_t ＝ ½ log((1 − ε_t) ÷ ε_t)　　गलत उदाहरण का वज़न ← वज़न × e^α_t

ε_t: tवें वर्गीकारक की वज़न वाली त्रुटि दर
α_t: बहुमत में उस वर्गीकारक का वज़न

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:बूस्टिंग में ओवरफ़िटिंग नहीं होती
मूल स्रोत के अनुसार:शापायर ने 2013 की व्याख्या में ऐसा उदाहरण दिया जिसमें प्रशिक्षण त्रुटि 0 होने के बाद भी परीक्षण त्रुटि घटती रही (5वें दौर में 8.4% → 1000वें में 3.1%)। फिर भी उन्होंने लिखा कि बूस्टिंग में भी ओवरफ़िटिंग हो सकती है।

हर दौर में प्रशिक्षण डेटा की गलतियों की संख्या

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_boosting.py

# u09 ブースティング：弱学習器を、誤りに合わせて重ねる（AdaBoost と勾配ブースティング）
#
# どの出来事か：1990 年、シャピーアが弱い学習は強い学習に変えられると証明し、1995 年にフロイントとシャピーアが
#   AdaBoost を発表（記録 boosting_1990）。1999 年、フリードマンが勾配ブースティングを一般化（記録 gradient_boosting_1999）。
# 仕組み：
#   (1) AdaBoost：弱い分類器は「たて か よこ の線 1 本で分けるだけ」（切り株）。
#       誤った点の重みを e^α 倍にして、次の切り株はそこを分類しに来る。最後は重み付き多数決。
#   (2) 勾配ブースティング：現在の予測と正解の誤差（残差）に、小さな木（1 回だけ分ける）を合わせ、
#       学習率 ν を掛けて少しずつ足す。
#   点はこのサイトが作った例（円の内と外で組が分かれる。線 1 本では分けられない）。
# 試してみよう：
#   - ROUNDS を 1・5・50 と変えて、訓練データとテストデータの誤り率を見る
#   - NU（学習率）を 1.0 と 0.1 で比べる

import math
import random

random.seed(1995)
ROUNDS = 40
NU = 0.3

def make(n):
    pts = []
    for _ in range(n):
        x, y = random.uniform(-1, 1), random.uniform(-1, 1)
        pts.append((x, y, 1 if x * x + y * y < 0.45 else -1))
    return pts

train, test = make(150), make(500)

def stump_best(data, w):
    best = None
    for d in (0, 1):
        vals = sorted({p[d] for p in data})
        for i in range(len(vals) - 1):
            t = (vals[i] + vals[i + 1]) / 2
            for s in (1, -1):
                err = sum(wi for p, wi in zip(data, w) if (s if p[d] < t else -s) != p[2])
                if best is None or err < best[0]:
                    best = (err, d, t, s)
    return best

def stump(h, p):
    _, d, t, s = h
    return s if p[d] < t else -s

print("(1) AdaBoost（弱い分類器は、線 1 本の切り株）")
w = [1 / len(train)] * len(train)
H = []
for r in range(1, ROUNDS + 1):
    h = stump_best(train, w)
    eps = max(1e-9, h[0] / sum(w))
    alpha = 0.5 * math.log((1 - eps) / eps)
    H.append((alpha, h))
    w = [wi * math.exp(-alpha * p[2] * stump(h, p)) for wi, p in zip(w, train)]   # 誤った点は e^α 倍
    z = sum(w)
    w = [wi / z for wi in w]

def F(p):
        return 1 if sum(a * stump(hh, p) for a, hh in H) > 0 else -1
    if r in (1, 2, 5, 10, 20, 40, ROUNDS):
        tr = sum(F(p) != p[2] for p in train) / len(train)
        te = sum(F(p) != p[2] for p in test) / len(test)
        print(f"  {r:3d} 回：この回の切り株の誤り率 {eps:5.1%}（重みつき）  訓練 {tr:5.1%}  テスト {te:5.1%}")

print()
print("(2) 勾配ブースティング：1 本の線の上の点に、残差を少しずつ埋めて合わせる")
xs = [i / 40 for i in range(41)]
ys = [math.sin(6 * x) + 0.3 * x + random.gauss(0, 0.1) for x in xs]
pred = [sum(ys) / len(ys)] * len(xs)
for r in range(1, 101):
    res = [y - p for y, p in zip(ys, pred)]
    best = None
    for i in range(1, len(xs)):
        t = (xs[i - 1] + xs[i]) / 2
        L = [e for x, e in zip(xs, res) if x < t]
        R = [e for x, e in zip(xs, res) if x >= t]
        ml, mr = sum(L) / len(L), sum(R) / len(R)
        sse = sum((e - ml) ** 2 for e in L) + sum((e - mr) ** 2 for e in R)
        if best is None or sse < best[0]:
            best = (sse, t, ml, mr)
    _, t, ml, mr = best
    pred = [p + NU * (ml if x < t else mr) for x, p in zip(xs, pred)]
    if r in (1, 5, 20, 100):
        mse = sum((y - p) ** 2 for y, p in zip(ys, pred)) / len(ys)
        print(f"  {r:3d} 回：誤差の 2 乗の平均 {mse:.4f} " + "#" * int(mse * 60))
print("小さな木を 1 本ずつ足すたびに、残った誤差が埋まっていく。")

181992 · सपोर्ट वेक्टर मशीन

सीमा के दोनों ओर सबसे अधिक जगह

2 समूहों को बाँटने वाली कई रेखाएँ खींच सकते हैं। सबसे अच्छी कौन-सी है?

जुलाई 1992 में बर्नहार्ड बोसर (Bernhard Boser), इसाबेल गियों (Isabelle Guyon) और व्लादिमीर वापनिक (Vladimir Vapnik) ने, AT&T बेल लैब्स में काम करते हुए, COLT '92 सम्मेलन में नई लर्निंग विधि प्रस्तुत की। इसमें 2 समूहों की सीमा इस तरह खींचते हैं कि सबसे पास के बिंदु से दूरी (मार्जिन, खाली जगह) अधिकतम हो। सीमा केवल अपने सबसे पास के कुछ बिंदुओं से तय होती है; दूसरे बिंदु खिसकाने से नहीं बदलती।

इसे केवल बिंदुओं की समानता मापने वाला फलन (कर्नेल) इस्तेमाल करने के रूप में लिखने पर मुड़ी हुई सीमा के लिए भी उसी गणना से मार्जिन अधिकतम कर सकते हैं। डाक पर हाथ से लिखे अंकों (प्रशिक्षण की 7300 छवियाँ, परीक्षण की 2000) में चौथी घात के बहुपद कर्नेल से त्रुटि दर 4.9% थी। उसी डेटा पर 5 परतों के न्यूरल नेटवर्क (5.1%) से यह थोड़ी कम थी।

दाईं ओर बिंदुओं को खींचें। घेरे वाले बिंदुओं (सीमा को सहारा देने वाले बिंदुओं) के अलावा किसी बिंदु को खिसकाने से रेखा नहीं बदलती, जब तक वह मार्जिन की पट्टी में नहीं आता।

मार्जिन अधिकतम करें ⇔ ‖w‖ न्यूनतम करें
K(x, x′)＝exp(−γ‖x − x′‖²)

w, b: सीमा की दिशा और स्थान (हर बिंदु के लिए y_i(w·x_i＋b) ≥ 1; y समूह को ＋1 · −1 से दिखाता है)
K, γ: कर्नेल (बिंदुओं की समानता) और प्रभाव के दायरे का संकरापन

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:सपोर्ट वेक्टर मशीन कोरिन्ना कॉर्टेस (Corinna Cortes) और वापनिक ने 1995 में खोजी
मूल स्रोत के अनुसार:मार्जिन अधिकतम करने और कर्नेल से मुड़ी सीमाओं पर काम करने की विधि तीनों 1992 में प्रस्तुत कर चुके थे। उस शोधपत्र में support vector शब्द नहीं है; सीमा को सहारा देने वाले बिंदुओं को supporting patterns कहा गया है। कर्नेल के विचार के लिए आइज़रमान (Aizerman) और साथियों की पोटेंशियल फ़ंक्शन विधि (1964) भी उद्धृत है।

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_svm.py

# u09 サポートベクターマシン：境界からの余白（マージン）を最大にする。カーネル法で曲線の境界にも対応
#
# どの出来事か：1992年、ボーザー、ギヨン、バプニクが COLT '92 で発表（記録 svm_kernel_1992）。
#   論文は、境目を支える点を supporting patterns と呼んだ。
# 仕組み：点同士の類似度（カーネル）K だけを使う形（双対形式）で、各点の重み α を決める。
#   ここでは SMO（2つずつ α を更新する、1998年にプラットが提案した解法）を簡単にしたものを使う。
#   α が 0 でない点が「境目を支える点」。それ以外の点は、動かしても境界線は変わらない。
#   (1) 直線の境界（線形カーネル K = x·x'）
#   (2) 曲線の境界（動径基底関数カーネル K = exp(-γ‖x - x'‖²)）
#   データはこのサイトが作った例。
# 試してみよう：
#   - C（誤りをどれだけ許容しないか）を 0.1 と 100 で比べる
#   - GAMMA を 0.5 と 20 で比べる

import math
import random

random.seed(1992)
C = 10.0
GAMMA = 2.0

def smo(X, Y, K, C, passes=20, tol=1e-3):
    n = len(X)
    a, b = [0.0] * n, 0.0
    G = [[K(X[i], X[j]) for j in range(n)] for i in range(n)]
    f = lambda i: sum(a[k] * Y[k] * G[k][i] for k in range(n) if a[k] > 0) + b
    it = 0
    while it < passes:
        changed = 0
        for i in range(n):
            Ei = f(i) - Y[i]
            if (Y[i] * Ei < -tol and a[i] < C) or (Y[i] * Ei > tol and a[i] > 0):
                j = random.randrange(n - 1)
                j += j >= i
                Ej = f(j) - Y[j]
                ai, aj = a[i], a[j]
                if Y[i] != Y[j]:
                    L, H = max(0, aj - ai), min(C, C + aj - ai)
                else:
                    L, H = max(0, ai + aj - C), min(C, ai + aj)
                eta = 2 * G[i][j] - G[i][i] - G[j][j]
                if L == H or eta >= 0:
                    continue
                a[j] = min(H, max(L, aj - Y[j] * (Ei - Ej) / eta))
                if abs(a[j] - aj) < 1e-5:
                    continue
                a[i] = ai + Y[i] * Y[j] * (aj - a[j])
                b1 = b - Ei - Y[i] * (a[i] - ai) * G[i][i] - Y[j] * (a[j] - aj) * G[i][j]
                b2 = b - Ej - Y[i] * (a[i] - ai) * G[i][j] - Y[j] * (a[j] - aj) * G[j][j]
                b = b1 if 0 < a[i] < C else (b2 if 0 < a[j] < C else (b1 + b2) / 2)
                changed += 1
        it = it + 1 if changed == 0 else 0
    return a, b

def decide(X, Y, a, b, K, p):
    return sum(ai * yi * K(xi, p) for ai, yi, xi in zip(a, Y, X) if ai > 1e-6) + b

lin = lambda u, v: u[0] * v[0] + u[1] * v[1]
rbf = lambda u, v: math.exp(-GAMMA * ((u[0] - v[0]) ** 2 + (u[1] - v[1]) ** 2))

print("(1) 直線の境界：2つのグループの点")
X = [(random.gauss(-1, 0.45), random.gauss(-0.6, 0.45)) for _ in range(20)] + [(random.gauss(1, 0.45), random.gauss(0.7, 0.45)) for _ in range(20)]
Y = [-1] * 20 + [1] * 20
a, b = smo(X, Y, lin, C)
w = [sum(ai * yi * xi[d] for ai, yi, xi in zip(a, Y, X)) for d in (0, 1)]
norm = math.hypot(*w)
sv = [i for i in range(len(X)) if a[i] > 1e-6]
print(f"  境界線：{w[0]:.2f} x + {w[1]:.2f} y + {b:.2f} = 0")
print(f"  マージンの幅（境界線から最も近い点まで）：{1 / norm:.3f}")
print(f"  境目を支える点：{len(sv)} 個（点は全部で {len(X)} 個）→ ", ", ".join(f"({X[i][0]:.2f},{X[i][1]:.2f})" for i in sv))
mis = sum((1 if decide(X, Y, a, b, lin, p) > 0 else -1) != y for p, y in zip(X, Y))
print(f"  訓練データで間違えた点：{mis} 個")

print()
print("(2) 曲線の境界：中心のグループと周囲のグループ（直線1本では分けられない）")
X2, Y2 = [], []
for _ in range(60):
    r, t = random.uniform(0, 1.6), random.uniform(0, 2 * math.pi)
    X2.append((r * math.cos(t), r * math.sin(t)))
    Y2.append(1 if r < 0.8 else -1)
for name, K in (("線形のカーネル", lin), ("動径基底のカーネル", rbf)):
    a2, b2 = smo(X2, Y2, K, C)
    mis = sum((1 if decide(X2, Y2, a2, b2, K, p) > 0 else -1) != y for p, y in zip(X2, Y2))
    print(f"  {name}：訓練データで間違えた点 {mis} 個 ／ 60 個、境目を支える点 {sum(1 for v in a2 if v > 1e-6)} 個")
a2, b2 = smo(X2, Y2, rbf, C)
print("  動径基底のカーネルで分類した地図（o＝中心のグループ、.＝周囲のグループ）")
for gy in range(8, -9, -2):
    print("    " + "".join("o" if decide(X2, Y2, a2, b2, rbf, (gx / 5, gy / 5)) > 0 else "." for gx in range(-8, 9)))

191995 · 2001 · रैंडम फ़ॉरेस्ट

बेतरतीब बने वृक्षों का बहुमत

1 वृक्ष प्रशिक्षण डेटा से ज़रूरत से ज़्यादा मेल खाता है। कई जोड़ने पर क्या होगा?

निर्णय वृक्ष को गहरा करने पर वह प्रशिक्षण डेटा से पूरा मेल खाता है, पर शोर भी याद कर लेता है। 1995 में AT&T बेल लैब्स की टिन काम हो (Tin Kam Ho) ने दिखाया कि विशेषताओं का कुछ हिस्सा बेतरतीब चुनकर इस्तेमाल करने वाले कई वृक्ष मिलाने से हाथ से लिखे अंक पहचानने की सटीकता बढ़ती है (random decision forests)।

2001 में कैलिफ़ोर्निया विश्वविद्यालय, बर्कले के लियो ब्राइमन (Leo Breiman) ने रैंडम फ़ॉरेस्ट को व्यवस्थित किया। बेतरतीब फिर चुने गए डेटा से वृक्ष बनाते हैं और हर शाखा पर बेतरतीब चुनी विशेषताओं में से सबसे अच्छा विभाजन चुनते हैं। वृक्ष बढ़ाने पर त्रुटि दर एक मान पर टिक जाती है। लगभग 3 में से 1 हिस्सा जो नहीं चुना गया (out-of-bag), उससे अलग परीक्षण डेटा के बिना त्रुटि दर का अनुमान लगा सकते हैं।

दाईं ओर वृक्षों की संख्या बढ़ाने पर टेढ़ी-मेढ़ी सीमा चिकनी होती है।

फ़ॉरेस्ट का उत्तर ＝ बहुमत (वृक्ष₁ का उत्तर, वृक्ष₂ का उत्तर, …, वृक्ष_B का उत्तर)

B: वृक्षों की संख्या
फ़ॉरेस्ट की त्रुटि: हर वृक्ष की ताकत (सटीकता) और वृक्षों के सहसंबंध (समानता) से तय होती है

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:रैंडम फ़ॉरेस्ट का विचार ब्राइमन को अकेले आया
मूल स्रोत के अनुसार:मिलते-जुलते नाम वाली random decision forests हो 1995 में प्रस्तुत कर चुकी थीं। ब्राइमन ने खुद बैगिंग (1996), हो की विधि तथा अमित (Amit) और गेमन (Geman, 1997) को पिछले काम में गिनाया और उन्हें मिलाकर random forests कहा।

वृक्षों की संख्या और out-of-bag से अनुमानित त्रुटि दर

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_random_forest.py

# u09 ランダムフォレスト：ランダムに少しずつ変えた決定木の多数決
#
# どの出来事か：2001年、ブレイマンの論文『Random Forests』（記録 random_forest_2001）。
#   1995年にはホーの random decision forests があった。
# 仕組み：
#   - 1本の木：訓練データから重複を許して（復元抽出で）同数を選び、分岐ごとにランダムに選んだ一部の特徴量から
#     最もよい分割を選んで、深く成長させる。
#   - 森：決定木を B 本作成して多数決をとる。その木に選ばれなかったデータ（out-of-bag。約3分の1）で誤り率を見積もる。
#   データはこのサイトが作った例（4つの特徴量のうち2つだけが正解に関係し、正解にはノイズが混ざる）。
# 試してみよう：
#   - B（決定木の本数）を 1・10・100 と変えて、テストデータの誤り率と out-of-bag の推定値を比べる
#   - MTRY（分岐ごとに調べる特徴量の数）を 1〜4 に変更する

import math
import random

random.seed(2001)
B_LIST = [1, 3, 10, 30, 100]
MTRY = 2
NOISE = 0.1

def make(n):
    out = []
    for _ in range(n):
        f = [random.uniform(-1, 1) for _ in range(4)]
        y = 1 if math.sin(3 * f[0]) + f[1] > 0 else 0
        if random.random() < NOISE:
            y = 1 - y
        out.append((f, y))
    return out

train, test = make(200), make(1000)

def gini(rows):
    if not rows:
        return 0
    p = sum(y for _, y in rows) / len(rows)
    return 2 * p * (1 - p)

def build(rows, depth=0):
    ys = [y for _, y in rows]
    if len(set(ys)) == 1 or len(rows) < 2 or depth > 12:
        return round(sum(ys) / len(ys))
    best = None
    for d in random.sample(range(4), MTRY):
        vals = sorted({f[d] for f, _ in rows})
        for i in range(0, len(vals) - 1, max(1, len(vals) // 12)):
            t = (vals[i] + vals[i + 1]) / 2
            L = [r for r in rows if r[0][d] < t]
            R = [r for r in rows if r[0][d] >= t]
            s = len(L) * gini(L) + len(R) * gini(R)
            if best is None or s < best[0]:
                best = (s, d, t, L, R)
    if best is None or not best[3] or not best[4]:
        return round(sum(ys) / len(ys))
    _, d, t, L, R = best
    return (d, t, build(L, depth + 1), build(R, depth + 1))

def run(tree, f):
    while isinstance(tree, tuple):
        d, t, l, r = tree
        tree = l if f[d] < t else r
    return tree

trees, inbag = [], []
for b in range(max(B_LIST)):
    idx = [random.randrange(len(train)) for _ in range(len(train))]
    trees.append(build([train[i] for i in idx]))
    inbag.append(set(idx))

print(f"訓練データ {len(train)} 個・テストデータ {len(test)} 個。正解には {NOISE:.0%} のノイズが混ざる")
print(f"1本の決定木が使わない（out-of-bag の）データの割合：{1 - len(inbag[0]) / len(train):.0%}（理論値は約 37%）")
print("  木の本数    訓練の誤り率    テストの誤り率    out-of-bag の推定値")
for B in B_LIST:
    vote = lambda f: 1 if sum(run(t, f) for t in trees[:B]) * 2 > B else 0
    tr = sum(vote(f) != y for f, y in train) / len(train)
    te = sum(vote(f) != y for f, y in test) / len(test)
    oob_err, oob_n = 0, 0
    for i, (f, y) in enumerate(train):
        vs = [run(trees[k], f) for k in range(B) if i not in inbag[k]]
        if vs:
            oob_n += 1
            oob_err += (1 if sum(vs) * 2 > len(vs) else 0) != y
    print(f"  {B:5d}     {tr:10.1%}     {te:12.1%}     {oob_err / max(1, oob_n):14.1%}")
print("木を増やすと、テストデータの誤り率はある値に落ち着く。out-of-bag の推定値は、テストデータの結果に近い。")

201873 · 1936 · सिंगुलर वैल्यू डीकंपोज़िशन

हर तालिका को 3 भागों में बाँटना

संख्याओं की तालिका (मैट्रिक्स) को कम संख्याओं से अच्छी तरह कैसे दर्शाएँ?

सिंगुलर वैल्यू डीकंपोज़िशन (SVD) किसी भी मैट्रिक्स को घुमाना → हर अक्ष पर फैलाना या सिकोड़ना → फिर घुमाना, ऐसे 3 गुणनों में बाँट सकता है। फैलाव के गुणकों को सिंगुलर वैल्यू कहते हैं। यूजेनियो बेल्ट्रामी (Eugenio Beltrami) ने 1873 में इसे सबसे पहले प्रकाशित किया, इटली के विश्वविद्यालय छात्रों की गणित पत्रिका में। अगले साल 1874 में कामीय जोर्दाँ (Camille Jordan) ने भी स्वतंत्र रूप से इसे दिखाया।

केवल बड़ी सिंगुलर वैल्यू रखने से मूल तालिका का कम संख्याओं में सटीक सन्निकटन बना सकते हैं। 1936 में शिकागो विश्वविद्यालय के कार्ल एकार्ट (Carl Eckart) और गेल यंग (Gale Young) ने मनोवैज्ञानिक परीक्षणों के अंकों के विश्लेषण से जुड़ी समस्या हल की: कम रैंक में सबसे अच्छा सन्निकटन देने वाला मैट्रिक्स खोजें। उत्तर छोटे सिंगुलर मानों को 0 कर देने से मिलता है।

दाईं ओर “वृत्त (2×2)” में वृत्त “घुमाएँ · फैलाएँ · घुमाएँ” से दीर्घवृत्त बनता है। “चित्र (24×24)” में 24×24 संख्याओं की तालिका से बना चित्र केवल k सिंगुलर वैल्यू रखकर फिर बनाया जाता है (चित्र इस साइट का बनाया उदाहरण है)।

A＝U Σ V^T　　A_k ＝σ₁u₁v₁^T ＋ … ＋σ_ku_kv_k^T

U, V: घुमाना (दिशा बदलना)
Σ: हर अक्ष पर फैलाना (सिंगुलर वैल्यू σ₁ ≥ σ₂ ≥ … को विकर्ण पर रखने वाली तालिका)
A_k: केवल सबसे बड़े k मानों वाला सन्निकटन

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:सन्निकटन का प्रमेय एकार्ट और यंग (1936) ने खोजा
मूल स्रोत के अनुसार:स्टुअर्ट (Stewart, 1992) के अनुसार एरहार्ड श्मिट (Erhard Schmidt) ने 1907 में इसे साबित किया था और दोनों ने फिर खोजा।

सिंगुलर वैल्यू का आकार (बड़े से छोटे क्रम में)

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_svd.py

# u09 特異値分解：どんな行列も「回す・伸ばす・回す」に分解できる。大きい特異値だけで復元する
#
# どの出来事か：1873 年のベルトラミ、1874 年のジョルダン（記録 beltrami_svd_1873）、
#   1936 年のエッカートとヤング（記録 eckart_young_low_rank_1936。定理そのものは 1907 年のシュミット）。
# 仕組み：
#   (1) 2×2 の行列 A が円を楕円に移すとき、楕円の長い半径と短い半径が特異値 σ1, σ2 になる。
#   (2) 24×24 の行列で描いた画像（このサイトが作った例）を、べき乗法で特異値の大きい順に分解し、
#       k 個だけ残して復元する。残す数が少ないほど保持する数値は減るが、画像はぼやける。
#       小さい特異値を切り捨てたものが、同じ k の中で最も誤差が小さい近似になる（シュミット、エッカートとヤング）。
# 試してみよう：
#   - (1) の A を別の行列にする
#   - (2) の画像 ART を自分で描きかえる。縦横の直線だけの画像は、少ない k で復元できる

import math

print("(1) 2×2 の行列 A が円を楕円に移す")
A = [[1.2, 0.8], [0.3, 1.0]]
best_long, best_short = (0, None), (1e9, None)
for d in range(0, 360, 1):
    t = math.radians(d)
    x, y = math.cos(t), math.sin(t)
    u = (A[0][0] * x + A[0][1] * y, A[1][0] * x + A[1][1] * y)
    L = math.hypot(*u)
    if L > best_long[0]:
        best_long = (L, d)
    if L < best_short[0]:
        best_short = (L, d)
ata = [[A[0][0] ** 2 + A[1][0] ** 2, A[0][0] * A[0][1] + A[1][0] * A[1][1]], [0, A[0][1] ** 2 + A[1][1] ** 2]]
ata[1][0] = ata[0][1]
tr, det = ata[0][0] + ata[1][1], ata[0][0] * ata[1][1] - ata[0][1] ** 2
s1 = math.sqrt((tr + math.sqrt(tr * tr - 4 * det)) / 2)
s2 = math.sqrt((tr - math.sqrt(tr * tr - 4 * det)) / 2)
print(f"  円の上の向きを 1° ずつ調べた、最も長くなる向き {best_long[1]}° → 長さ {best_long[0]:.3f}")
print(f"  最も短くなる向き {best_short[1]}° → 長さ {best_short[0]:.3f}")
print(f"  式で求めた特異値：σ1 = {s1:.3f}、σ2 = {s2:.3f}（楕円の長い半径と短い半径）")

print()
print("(2) 24×24 の画像を、大きい特異値 k 個だけで復元する")
ART = [
    "........................",
    "........................",
    "..######......######....",
    "..######......######....",
    "..##..##......##..##....",
    "..##..##......##..##....",
    "..######......######....",
    "..######......######....",
    "........................",
    "..........##............",
    "..........##............",
    ".........####...........",
    ".........####...........",
    "........................",
    "....##............##....",
    "....###..........###....",
    ".....###........###.....",
    "......############......",
    ".......##########.......",
    "........................",
    "..####################..",
    "..####################..",
    "........................",
    "........................",
]
M = [[1.0 if c == "#" else 0.0 for c in row] for row in ART]
n = len(M)

def matvec(Mx, v):
    return [sum(Mx[i][j] * v[j] for j in range(n)) for i in range(n)]

def tmatvec(Mx, v):
    return [sum(Mx[i][j] * v[i] for i in range(n)) for j in range(n)]

R = [row[:] for row in M]
parts = []
for k in range(8):
    v = [1.0 + 0.01 * j for j in range(n)]
    for _ in range(100):
        u = matvec(R, v)
        v = tmatvec(R, u)
        L = math.sqrt(sum(x * x for x in v)) or 1
        v = [x / L for x in v]
    u = matvec(R, v)
    s = math.sqrt(sum(x * x for x in u))
    if s < 1e-9:
        break
    u = [x / s for x in u]
    parts.append((s, u, v))
    R = [[R[i][j] - s * u[i] * v[j] for j in range(n)] for i in range(n)]

print("  特異値（大きい順）：", "  ".join(f"{s:.2f}" for s, _, _ in parts))
total = sum(x * x for row in M for x in row)
for k in (1, 2, 4, 6):
    Ak = [[sum(s * u[i] * v[j] for s, u, v in parts[:k]) for j in range(n)] for i in range(n)]
    err = sum((M[i][j] - Ak[i][j]) ** 2 for i in range(n) for j in range(n))
    print(f"  k = {k}：保持する数値 {k * (2 * n + 1)} 個（元は {n * n} 個）、誤差の 2 乗の和 {err:.2f}（元の画像の {err / total:.0%}）")
    for i in range(0, n, 2):
        print("      " + "".join("#" if Ak[i][j] > 0.5 else ("+" if Ak[i][j] > 0.25 else ".") for j in range(n)))

212006〜2009 · Netflix Prize

खाली जगहों वाली तालिका से सीखना

किसी व्यक्ति ने फ़िल्म नहीं देखी हो, तो उसके दिए जाने वाले अंक बता सकते हैं?

अक्टूबर 2006 में Netflix ने प्रतियोगिता शुरू की। उसकी अपनी सिफ़ारिश प्रणाली से 10% अधिक सटीकता से लोगों की फ़िल्म रेटिंग का अनुमान लगाने पर 10 लाख डॉलर का पुरस्कार था। डेटा में लगभग 4 लाख 80 हज़ार लोगों की लगभग 18 हज़ार फ़िल्मों पर 10 करोड़ से अधिक रेटिंग थीं।

11 दिसंबर 2006 को प्रतियोगी साइमन फ़ंक (Simon Funk) ने अपनी पूरी विधि ब्लॉग पर प्रकाशित की। व्यक्ति की पसंद और फ़िल्म की विशेषताओं को 40-40 संख्याओं से दर्शाया और उनके गुणनफलों के योग से रेटिंग का अनुमान लगाया। तालिका के लगभग 8.5 अरब खानों में 8.4 अरब खाली थे, इसलिए असली सिंगुलर वैल्यू डीकंपोज़िशन इस्तेमाल नहीं कर सकते थे। उन्होंने केवल ज्ञात रेटिंग से त्रुटि निकाली और मानों को थोड़ा-थोड़ा सुधारा। उन्होंने इसे संशोधित SVD कहा।

दाईं ओर “लगातार सीखें” दबाने पर खाली खाने भरते हैं (तालिका इस साइट का बनाया उदाहरण है)।

अनुमान r̂ ＝p_u · q_m
p_u ← p_u ＋η e q_m（q_m के लिए भी यही रूप; e＝r − r̂）

p_u, q_m: व्यक्ति u की पसंद और फ़िल्म m की विशेषताएँ (संख्याओं के समूह)
r, η: ज्ञात रेटिंग और सीखने की दर

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:Netflix ने प्रतियोगिता में मिली विधि से अपनी सिफ़ारिशें बेहतर कीं
मूल स्रोत के अनुसार:कंपनी के ब्लॉग (2012) के अनुसार विजेता विधि में मेहनत के अनुसार लाभ नहीं था, इसलिए उसे नहीं अपनाया गया।

दोहराव की संख्या और जाँच के डेटा पर त्रुटि

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_funk_mf.py

# u09 Netflix Prize の「手直しした SVD」：空欄の多い表を、既知の評価だけで学習する
#
# どの出来事か：2006〜2009 年の Netflix Prize（記録 netflix_prize_2006_2009）と、2006 年 12 月 11 日に
#   ファンクがブログに書いた手法（記録 funk_netflix_svd_2006。実際は 40 個ずつの特徴量、学習率 0.001）。
# 仕組み：人 u の好みを F 個の数値 p_u、映画 m の特徴を F 個の数値 q_m で表し、評価の予測値を p_u・q_m（内積）とする。
#   既知の評価 r だけについて誤差 e = r - p_u・q_m を計算し、
#     p_u ← p_u + η (e q_m - λ p_u)、 q_m ← q_m + η (e p_u - λ q_m)
#   と更新する（λ は値が大きくなりすぎるのを防ぐ正則化項）。空欄のマスは計算に使わない。
#   評価の表は、このサイトが作った例（30 人 × 10 本。実は 2 つの好みの軸から作り、3 割ほどを隠す）。
# 試してみよう：
#   - F（特徴量の数）を 1・2・5 と変えて、隠した評価の誤差を比べる
#   - LAMBDA を 0 にすると、訓練データの誤差と、隠したマスの誤差はどうなるか

import math
import random

random.seed(2006)
USERS, MOVIES, F = 30, 10, 2
ETA, LAMBDA, ROUNDS = 0.02, 0.02, 400
MOVIE_NAMES = ["宇宙戦争", "ロボット", "恋の手紙", "海辺の夏", "探偵A", "探偵B", "怪獣", "花の歌", "時の旅", "家族"]

# 本当の好み（このサイトが作った例）：軸 1＝SF・冒険が好き、軸 2＝恋愛・家族の話が好き
true_u = [[random.uniform(-1, 1), random.uniform(-1, 1)] for _ in range(USERS)]
true_m = [[1, -0.3], [0.9, 0], [-0.5, 1], [-0.2, 0.9], [0.3, 0.3], [0.4, 0.2], [1, -0.6], [-0.6, 0.8], [0.7, 0.5], [-0.3, 1]]
R = [[max(1, min(5, round(3 + 1.6 * (tu[0] * tm[0] + tu[1] * tm[1]) + random.gauss(0, 0.3)))) for tm in true_m] for tu in true_u]
known, hidden = [], []
for u in range(USERS):
    for m in range(MOVIES):
        (hidden if random.random() < 0.3 else known).append((u, m, R[u][m]))

mean = sum(r for _, _, r in known) / len(known)
P = [[random.gauss(0, 0.1) for _ in range(F)] for _ in range(USERS)]
Q = [[random.gauss(0, 0.1) for _ in range(F)] for _ in range(MOVIES)]

def pred(u, m):
    return mean + sum(P[u][k] * Q[m][k] for k in range(F))

def rmse(data):
    return math.sqrt(sum((r - pred(u, m)) ** 2 for u, m, r in data) / len(data))

print(f"表：{USERS} 人 × {MOVIES} 本 = {USERS * MOVIES} マス。既知の {len(known)} マスで学習し、隠した {len(hidden)} マスで検証する")
print(f"  学習前（全体平均 {mean:.2f} と予測）：隠したマスの誤差 {rmse(hidden):.3f}")
for rd in range(1, ROUNDS + 1):
    random.shuffle(known)
    for u, m, r in known:
        e = r - pred(u, m)
        for k in range(F):
            pu, qm = P[u][k], Q[m][k]
            P[u][k] += ETA * (e * qm - LAMBDA * pu)
            Q[m][k] += ETA * (e * pu - LAMBDA * qm)
    if rd in (1, 10, 50, 100, 400):
        print(f"  {rd:3d} 周：訓練データの誤差 {rmse(known):.3f}　隠したマスの誤差 {rmse(hidden):.3f}")
print("  周を重ねすぎると、隠したマスの誤差がまた少し増えることがある（既知のマスに合わせすぎ）。")

print()
print("人 1 の評価（○＝既知の評価、？＝隠した評価。数値は予測値）")
hid = {(u, m) for u, m, _ in hidden}
for m in range(MOVIES):
    mark = "？" if (0, m) in hid else "○"
    print(f"  {MOVIE_NAMES[m]:6s} {mark} 実際 {R[0][m]}  予測 {pred(0, m):.1f}")
print("映画ごとに学習した 2 つの特徴量（どの好みの軸に近いか。軸の意味は与えていない）")
for m in range(MOVIES):
    print(f"  {MOVIE_NAMES[m]:6s} ({Q[m][0]:+.2f}, {Q[m][1]:+.2f})")

221770 · 2005 · 2009 · अंदर इंसान है

सही लेबल किसने लगाए?

जब “AI ने तस्वीरें देखकर खुद सीखा”, तो सही उत्तर कहाँ से आए?

नवंबर 2005 में Amazon ने मेकैनिकल टर्क शुरू किया। इस सेवा में प्रोग्राम लोगों से छोटे काम करवाकर परिणाम लेते हैं। घोषणा में कंप्यूटर द्वारा कई लोगों से काम करवाकर परिणाम इस्तेमाल करने को (अनुवाद) कहा गया।

2009 में प्रिंस्टन विश्वविद्यालय के ली (Li) और साथियों ने ImageNet प्रस्तुत किया (तब 32 लाख छवियाँ)। इसमें शब्दार्थ को ऊपर-नीचे के क्रम में व्यवस्थित करने वाले WordNet की संज्ञाओं के समूहों के लिए तस्वीरें जुटाईं। तस्वीरें सर्च इंजन से ली गईं। वास्तव में संबंधित वस्तु है या नहीं, यह मेकैनिकल टर्क पर पैसे लेकर काम करने वाले दुनिया भर के लोगों ने एक-एक तस्वीर जाँचकर कई वोटों से तय किया (शोधपत्र का पृष्ठ 4)। “अंदर इंसान है” वाली बात केवल 1770 की शतरंज मशीन (जिसे टर्क कहा गया) तक सीमित नहीं है।

दाईं ओर मतदान की प्रक्रिया है (हर व्यक्ति की सटीकता के मान इस साइट में कल्पित हैं)।

बहुमत की सटीकता ＝Σ_k＞n/2 C(n, k) p^k（1 − p）^n−k

n: 1 तस्वीर जाँचने वाले लोगों की संख्या (विषम)
p: हर व्यक्ति की सटीकता
C(n, k): n लोगों में से k चुनने के संयोजनों की संख्या

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:Amazon कहता है कि नाम 1770 की शतरंज मशीन (टर्क) से आया
मूल स्रोत के अनुसार:इस साइट द्वारा जाँची गई Amazon की 2005 की घोषणा और मौजूदा मुख्य पृष्ठ में नाम का स्रोत नहीं लिखा है।

लोगों की संख्या और बहुमत की सटीकता

232009 · डेटा के अनुसार चलें

प्रशिक्षण और परीक्षण अलग रखकर जाँचें

पेचीदा प्रणाली और बहुत सारा डेटा—कौन जीतेगा?

2009 में Google के हलेवी (Halevy), नॉरविग (Norvig) और परेरा (Pereira) ने (अनुवाद) नाम का शोधपत्र लिखा। उसमें कहा गया, (अनुवाद), और सलाह दी गई, (अनुवाद)।

लेकिन सीखी हुई क्षमता का पता ऐसे डेटा पर मूल्यांकन से ही चलता है जो सीखने में इस्तेमाल नहीं हुआ हो। दाईं ओर प्रशिक्षण डेटा की संख्या बदलें। कम डेटा होने पर प्रशिक्षण में 100% सही उत्तर मिलते हैं, पर परीक्षण में सटीकता कम होती है (ओवरफ़िटिंग)।

परीक्षण की सटीकता ＝ सीखने में इस्तेमाल न हुए उदाहरणों में सही उत्तरों की संख्या ÷ उन उदाहरणों की संख्या

अभ्यास का डेटा (प्रशिक्षण डेटा): मॉडल को सिखाने वाला डेटा
परीक्षण का डेटा: सीखने के बाद केवल क्षमता जाँचने के लिए इस्तेमाल होने वाला डेटा

इस अध्याय के डेटा का आकार (हर अगला निशान 10 गुना)

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_digits_train_test.py

# u09 データから学習する：訓練データとテストデータに分け、データ量で正解率がどう変わるかを見る（numpy を使う）
#
# どの出来事か：2006 年からのディープラーニング（深層学習）の広まりと、2009 年の ImageNet（記録 imagenet_2009）。
#   2009 年の論文の題は「データの不合理なほどの有効性」（訳）。情報Ⅱ の「訓練データとテストデータ」
#   「過剰適合（練習の問題だけ覚えて、新しい問題に弱くなる）」と同じ話。
# 仕組み：手書き風の数字（u04 と同じパターンを、ずらしや画素の反転で崩したもの。本物の手書きではない）を、
#   入力 35 → 隠れ層 32 → 出力 10 のニューラルネットワークで学習する。行列の積（numpy）を多く計算する。
#   この「行列の計算がたくさん要る」ことが、2010 年ごろから GPU（画像処理用の半導体）で解決された。
# 試してみよう：
#   - 下の for 文の (5, 20, 80, 300)（1 つの数字あたりの訓練データの数）を変えて、訓練データとテストデータの正解率の差を見る
#   - NOISE を上げる

import numpy as np

rng = np.random.default_rng(2006)
NOISE = 0.08
FONT = {
    0: [".###.", "#...#", "#..##", "#.#.#", "##..#", "#...#", ".###."],
    1: ["..#..", ".##..", "..#..", "..#..", "..#..", "..#..", ".###."],
    2: [".###.", "#...#", "....#", "...#.", "..#..", ".#...", "#####"],
    3: ["#####", "...#.", "..#..", "...#.", "....#", "#...#", ".###."],
    4: ["...#.", "..##.", ".#.#.", "#..#.", "#####", "...#.", "...#."],
    5: ["#####", "#....", "####.", "....#", "....#", "#...#", ".###."],
    6: ["..##.", ".#...", "#....", "####.", "#...#", "#...#", ".###."],
    7: ["#####", "....#", "...#.", "..#..", ".#...", ".#...", ".#..."],
    8: [".###.", "#...#", "#...#", ".###.", "#...#", "#...#", ".###."],
    9: [".###.", "#...#", "#...#", ".####", "....#", "...#.", ".##.."],
}
BASE = {d: np.array([[c == "#" for c in r] for r in rows], dtype=float) for d, rows in FONT.items()}

def make(n_per_digit):
    X, y = [], []
    for d, g in BASE.items():
        for _ in range(n_per_digit):
            dy, dx = rng.integers(-1, 2), rng.integers(-1, 2)
            s = np.zeros_like(g)                                                        # 上下左右に 1 マスずらす（はみ出た部分は消える）
            s[max(0, dy):g.shape[0] + min(0, dy), max(0, dx):g.shape[1] + min(0, dx)] = g[max(0, -dy):g.shape[0] - max(0, dy), max(0, -dx):g.shape[1] - max(0, dx)]
            flip = rng.random(s.shape) < NOISE
            X.append(np.where(flip, 1 - s, s).ravel())                                  # 画素を反転させる
            y.append(d)
    return np.array(X), np.array(y)

def train(X, y, hidden=32, epochs=500, rate=0.5):
    W1 = rng.normal(0, 0.3, (X.shape[1], hidden)); b1 = np.zeros(hidden)
    W2 = rng.normal(0, 0.3, (hidden, 10)); b2 = np.zeros(10)
    Y = np.eye(10)[y]
    for _ in range(epochs):
        h = np.tanh(X @ W1 + b1)                      # 隠れ層（行列の積）
        z = h @ W2 + b2
        p = np.exp(z - z.max(1, keepdims=True)); p /= p.sum(1, keepdims=True)   # 出力層：数字ごとの確率
        dz = (p - Y) / len(X)                         # 出力の誤差
        dh = (dz @ W2.T) * (1 - h ** 2)               # 誤差逆伝播法で伝える（u08 と同じ）
        W2 -= rate * h.T @ dz; b2 -= rate * dz.sum(0)
        W1 -= rate * X.T @ dh; b1 -= rate * dh.sum(0)
    return lambda Xn: (np.tanh(Xn @ W1 + b1) @ W2 + b2).argmax(1)

X_test, y_test = make(100)   # テストデータ：学習に使わない 1000 字
print("1 つの数字あたりの訓練データの数 → 訓練データでの正解率 / テストデータでの正解率")
for per in (5, 20, 80, 300):
    X, y = make(per)
    predict = train(X, y)
    print(f"  {per:3d} 字 × 10 数字 → 訓練 {np.mean(predict(X) == y):.0%} / テスト {np.mean(predict(X_test) == y_test):.0%}")
print("訓練データの正解率だけ高く、テストが低い＝過学習（過剰適合）。データを増やすと差が縮まる")

242006 · 2009 · GPU

एक ही गणना, कई साथ-साथ

गेम की तस्वीरें बनाने वाले पुर्ज़े ने AI को सीखने में तेज़ कैसे बनाया?

गेम की छवियाँ बनाने वाला GPU कई छोटे कोर से एक जैसी गणना साथ-साथ कर सकता है (2006 के GeForce 8800 GTX में अधिकतम 128)। नवंबर 2006 में NVIDIA ने CUDA प्रस्तुत किया, जिससे सामान्य C भाषा में इस पुर्ज़े को छवियों के अलावा अन्य गणनाओं में भी इस्तेमाल कर सकते थे।

न्यूरल नेटवर्क को सिखाने का अधिकांश काम “गुणा और जोड़” दोहराना है। हर गणना एक जैसे रूप की है, इसलिए बाँटकर साथ-साथ कर सकते हैं। 2009 में स्टैनफ़ोर्ड के रजत रैना (Rajat Raina), आनंद माधवन (Anand Madhavan) और एंड्रू एंग (Andrew Ng) ने सही उत्तरों के बिना सीखने वाला गहरा नेटवर्क GeForce GTX 280 पर सिखाया। यह 2 कोर वाले CPU से अधिकतम 70 गुना तेज़ था। 10 करोड़ पैरामीटर वाले 4 परतों के नेटवर्क का प्रशिक्षण कई हफ़्तों की जगह लगभग 1 दिन में पूरा होने लगा। प्रशिक्षण समय के वर्णन में (अनुवाद) और (अनुवाद) लिखा गया था।

दाईं ओर कोर की संख्या बदलकर गुणा की तालिका भरने की दौड़ है (इस साइट का बनाया मॉडल)। अधिक कोर होने पर उतने ही समय में अधिक खाने भरते हैं।

समय ≒ गणनाओं की संख्या ÷（कोर की संख्या × 1 कोर की गति）

मॉडल की धारणा: हर खाने की गणना में समान मेहनत और काम बाँटने में 0 मेहनत मानी गई है (असल में डेटा पहुँचाने आदि में समय लगता है)

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:डीप लर्निंग GPU से फैली
मूल स्रोत के अनुसार:Google के 2012 के बड़े प्रयोग (बिल्ली का शोधपत्र और DistBelief) में GPU की जगह हज़ारों सामान्य कंप्यूटर इस्तेमाल हुए। शोधपत्र ने लिखा कि उस समय के GPU की मेमरी (6 GB से कम) में न समाने वाले बड़े मॉडल आसानी से तेज़ नहीं होते। केवल 1 ही रास्ता नहीं था।

252009〜2012 · आवाज़

छवियों से पहले आवाज़ में

डीप लर्निंग वाले AI की पहली बड़ी सफलता क्या छवियों में थी?

लगभग 2009 से डीप लर्निंग आवाज़ पहचान में लंबे समय से इस्तेमाल सांख्यिकीय विधियों (GMM) से आगे निकलने लगी। 2012 में टोरंटो विश्वविद्यालय, Microsoft Research, Google और IBM के 4 समूहों ने एक शोधपत्र बनाया, जिसके बारे में लिखा गया, (अनुवाद)। उसमें बातचीत लिखने के परीक्षण में शब्द त्रुटि दर 27.4% से 18.5% करने जैसे नतीजे दिए। अगस्त 2012 तक Google इसे Android की आवाज़ पहचान में अपना चुका था। ये सभी घटनाएँ अक्टूबर 2012 की छवि प्रतियोगिता से पहले की हैं।

उसी समय आवाज़ से अनुरोध करने वाले ऐप एक के बाद एक आए (अगस्त 2010 में NICT का VoiceTra, अक्टूबर 2011 में Apple का Siri, 1 मार्च 2012 को NTT Docomo का Shabette Concier। जापानी Siri उसके 1 हफ़्ते बाद आया)।

दाईं ओर आवाज़ पहचान की त्रुटियाँ गिनने की विधि है (शब्द त्रुटि दर)।

त्रुटि दर ＝（बदले शब्द ＋ छूटे शब्द ＋ अतिरिक्त शब्द）÷ सही वाक्य के शब्दों की संख्या

गिनने की विधि: 2 वाक्यों को सबसे कम सुधारों से मिलाकर गिनना (डायनैमिक प्रोग्रामिंग; अध्याय 5 के DP मिलान जैसा विचार)

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:डीप लर्निंग की पहली बड़ी सफलता 2012 की शरद ऋतु की छवि प्रतियोगिता थी
मूल स्रोत के अनुसार:आवाज़ पहचान में 2009 से नतीजे आने लगे और अगस्त 2012 तक Google ने इसे Android में अपनाया था। Google का ब्लॉग आवाज़ में न्यूरल नेटवर्क के पहले प्रयास के रूप में 1980 के दशक के अंत का शोधपत्र बताता है (ओसाका के ATR के 2 शोधकर्ता सहलेखक थे)।

262010〜2012 · गहरे नेटवर्क

गहरी परतों में भी संकेत बना रहे

30 परतें एक के ऊपर एक रखने पर क्या होता है?

गहरे न्यूरल नेटवर्क में त्रुटि को पीछे ले जाने वाला संकेत हर परत से गुज़रते हुए कमज़ोर या बहुत बड़ा हो सकता है। 2010〜2012 में इसे रोकने के 3 उपाय साथ आए।

एक है एक्टिवेशन फ़ंक्शन ReLU (धनात्मक इनपुट वैसा ही, ऋणात्मक इनपुट 0; धनात्मक ओर ढाल हमेशा 1)। दूसरा है न्यूरॉन की संख्या के अनुसार वज़नों के शुरुआती मानों का दायरा तय करना (ग्लोरो (Glorot) और बेंजियो (Bengio), 2010)। तीसरा है ड्रॉपआउट (2012), जिसमें हर प्रशिक्षण चरण पर छिपी परत के आधे न्यूरॉन बेतरतीब आराम करते हैं।

दाईं ओर एक्टिवेशन फ़ंक्शन और शुरुआती मान बदलकर हर परत में संकेत का आकार देखें।

ReLU(x)＝max(0, x)
वज़नों का दायरा ±√6 ÷ √(n_{इनपुट} ＋n_{आउटपुट}), मानक विचलन √(2 ÷ n_{इनपुट})

n_{इनपुट}, n_{आउटपुट}: परत के इनपुट और आउटपुट न्यूरॉन की संख्या (दायरा ग्लोरो और बेंजियो की विधि है, मानक विचलन काइमिंग ही (Kaiming He) और साथियों की विधि)

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:ReLU हिंटन और साथियों ने 2010 में खोजा
मूल स्रोत के अनुसार:2010 का शोधपत्र खुद जैरेट (Jarrett) और साथियों के 2009 के प्रयास का उल्लेख करता है। इसी रूप का एक्टिवेशन फ़ंक्शन कुनिहिको फ़ुकुशिमा (Kunihiko Fukushima) के 1968〜1969 के नेटवर्क में है (अध्याय 4), लेकिन 2010〜2012 के 3 शोधपत्र फ़ुकुशिमा को उद्धृत नहीं करते।

हर परत में पीछे जाने वाले संकेत का आकार (हर अगला निशान 10 गुना)

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_relu_init.py

# u09 深く重ねても信号が消えない工夫：活性化関数（シグモイド・ReLU）と重みの初期値
#
# どの出来事か：ReLU（記録 relu_rectified_linear_2010）、グロロとベンジオの初期値（記録 weight_init_glorot_2010。
#   2015 年のヒーたちの ReLU 用の決め方も）、ドロップアウト（記録 dropout_2012）。
# 仕組み：
#   (1) 幅 64 の層を 30 段重ねたニューラルネットワークに、ランダムな入力を通し、出力側から 1 を逆伝播させる。
#       層ごとに、順伝播する値のばらつきと、逆伝播する勾配の大きさを測る。
#       重みの初期値：±1/√n（従来の方法）、グロロとベンジオ ±√6/√(n入+n出)、ヒーたち 標準偏差 √(2/n)。
#   (2) ドロップアウト：学習時はニューロンを確率 0.5 で休ませる。推論時は全ニューロンを使い、出力を半分にする。
#       すると、推論時の出力が、学習時の出力の平均と同じ大きさになる。
#   重みと入力は、このサイトが作った乱数。
# 試してみよう：
#   - LAYERS を 10 や 50 にする
#   - シグモイドとヒーたちの組み合わせ、ReLU とグロロたちの組み合わせを比べる

import math
import random

random.seed(2010)
WIDTH, LAYERS = 64, 30

def make_weights(kind):
    W = []
    for _ in range(LAYERS):
        if kind == "old":
            r = 1 / math.sqrt(WIDTH)
            W.append([[random.uniform(-r, r) for _ in range(WIDTH)] for _ in range(WIDTH)])
        elif kind == "glorot":
            r = math.sqrt(6) / math.sqrt(WIDTH + WIDTH)
            W.append([[random.uniform(-r, r) for _ in range(WIDTH)] for _ in range(WIDTH)])
        else:
            s = math.sqrt(2 / WIDTH)
            W.append([[random.gauss(0, s) for _ in range(WIDTH)] for _ in range(WIDTH)])
    return W

ACT = {
    "sigmoid": (lambda x: 1 / (1 + math.exp(-x)), lambda y: y * (1 - y)),
    "tanh": (math.tanh, lambda y: 1 - y * y),
    "relu": (lambda x: x if x > 0 else 0.0, lambda y: 1.0 if y > 0 else 0.0),
}

def run(act, kind):
    f, df = ACT[act]
    W = make_weights(kind)
    x = [random.gauss(0, 1) for _ in range(WIDTH)]
    outs = [x]
    for L in range(LAYERS):
        z = [sum(W[L][i][j] * outs[-1][j] for j in range(WIDTH)) for i in range(WIDTH)]
        outs.append([f(v) for v in z])
    g = [1.0] * WIDTH
    grads = []
    for L in reversed(range(LAYERS)):
        d = [g[i] * df(outs[L + 1][i]) for i in range(WIDTH)]
        g = [sum(W[L][i][j] * d[i] for i in range(WIDTH)) for j in range(WIDTH)]
        grads.append(math.sqrt(sum(v * v for v in g) / WIDTH))
    return grads[::-1]

print("(1) 30 段のネットワークで逆伝播する勾配の大きさ（1 段目・10 段目・20 段目・30 段目）")
print("  活性化関数 重みの初期値      1段目      10段目     20段目     30段目")
for act in ("sigmoid", "tanh", "relu"):
    for kind, name in (("old", "±1/√n"), ("glorot", "グロロとベンジオ"), ("he", "ヒーたち")):
        g = run(act, kind)
        print(f"  {act:8s} {name:12s}  " + "  ".join(f"{g[i]:9.2e}" for i in (0, 9, 19, 29)))
print("  1 段目の値が極端に小さい組み合わせは、入力に近い層がほとんど学習できない（勾配消失）。")

print()
print("(2) ドロップアウト：学習時はニューロンを半分ずつ休ませ、推論時は出力を半分にする")
h = [random.uniform(0, 1) for _ in range(WIDTH)]
w = [random.gauss(0, 1) for _ in range(WIDTH)]
trials = []
for _ in range(2000):
    mask = [1 if random.random() < 0.5 else 0 for _ in range(WIDTH)]
    trials.append(sum(wi * hi * mi for wi, hi, mi in zip(w, h, mask)))
full = sum(wi * hi for wi, hi in zip(w, h))
print(f"  学習時（2000 回、毎回違う半分を休ませた）の出力の平均：{sum(trials) / len(trials):+.3f}")
print(f"  推論時（全ニューロンを使い、出力を半分に）：           {full * 0.5:+.3f}")
print("  ほぼ同じ。多数の細いネットワークの答えを平均したものに近い答えになる。")

272012 · 1 साल में 3 नतीजे

यातायात संकेत और Google की बिल्ली

2012 में डीप लर्निंग के कितने नतीजे आए?

फ़रवरी में स्विस संस्थान IDSIA के डैन चिरेशान (Dan Cireşan), उएली मायेर (Ueli Meier) और युर्गेन श्मिडह्यूबर (Jürgen Schmidhuber) ने कई गहरे कन्वोल्यूशनल नेटवर्क के परिणामों का औसत लेने वाली विधि GPU पर सिखाई। जर्मन यातायात संकेतों की पहचान (परीक्षण की 12,569 छवियाँ) में त्रुटि दर 0.54% हुई। शोधपत्र के अनुसार मनुष्यों की त्रुटि दर इसकी दोगुनी थी। लेकिन केवल 43 प्रकार के उत्तर थे, इसलिए कठिनाई 1000 प्रकार की तस्वीरों जैसी नहीं थी।

जून में Google और स्टैनफ़ोर्ड विश्वविद्यालय के क्वोक ले (Quoc Le), एंड्रू एंग (Andrew Ng) और साथियों ने YouTube के 1 करोड़ वीडियो से एक-एक छवि ली और सही लेबल दिए बिना 1 अरब कनेक्शन वाला 9 परतों का नेटवर्क सिखाया (1000 कंप्यूटर, 16,000 कोर और 3 दिन)। बिना सिखाए भी मानव चेहरों पर प्रतिक्रिया करने वाले न्यूरॉन बने, और बिल्ली के चेहरे तथा मानव शरीर पर प्रतिक्रिया करने वाले भी बने। Google के ब्लॉग ने ज़ोर दिया कि (अनुवाद)।

फिर अक्टूबर में छवि पहचान की प्रतियोगिता हुई (अगला पृष्ठ)। दाईं ओर बिल्ली के न्यूरॉन के परिणाम की तुलना “बेतरतीब उत्तर देने पर” से करें।

शोधपत्र की तालिका 1: मानव चेहरे का न्यूरॉन 81.7%, बिल्ली के चेहरे का न्यूरॉन 74.8%, बेतरतीब उत्तर देने पर 64.8% (बिल्ली का परीक्षण)। परिणाम को बिना कुछ किए मिलने वाले अंकों से तुलना करके पढ़ें।

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:Google का AI खुद बिल्ली पहचानना सीख गया
मूल स्रोत के अनुसार:शोधपत्र का मुख्य नतीजा मानव चेहरे का न्यूरॉन (81.7%) है और बिल्ली के चेहरे का न्यूरॉन 74.8% है। इस परीक्षण में बेतरतीब उत्तर भी 64.8% सही होते थे (शोधपत्र की तालिका 1)।

282012 · छवि प्रतियोगिता

बड़ी जीत, दूसरा टोक्यो विश्वविद्यालय

अक्टूबर 2012 की छवि प्रतियोगिता के बारे में (अनुवाद) क्यों कहा गया?

तस्वीरों में 1000 प्रकार की वस्तुएँ पहचानने की प्रतियोगिता ILSVRC में टोरंटो विश्वविद्यालय के एलेक्स क्रिज़ेव्स्की (Alex Krizhevsky), इल्या सुत्स्केवर (Ilya Sutskever) और हिंटन (Hinton) की टीम SuperVision ने 5 उत्तर देने वाले नियम में त्रुटि दर 15.3% की (केवल प्रतियोगिता का डेटा इस्तेमाल करने पर 16.4%)। दूसरे स्थान की टोक्यो विश्वविद्यालय टीम (ISI) की दर 26.2% थी और लगभग 11 प्रतिशत अंकों का अंतर था। उन्होंने 6 करोड़ पैरामीटर वाला 8 परतों का कन्वोल्यूशनल न्यूरल नेटवर्क गेम वाले 2 GPU पर सिखाया। आयोजकों ने कई प्रकार की वस्तुएँ पहचानने के शोध के लिए इस साल के बारे में लिखा, (अनुवाद)।

कन्वोल्यूशन में छवि पर छोटी खिड़की (फ़िल्टर) खिसकाकर खिड़की जैसी आकृति वाली जगह पर तेज़ प्रतिक्रिया निकाली जाती है। यह संरचना कुनिहिको फ़ुकुशिमा (Kunihiko Fukushima) के 1979 के निओकॉग्निट्रॉन (अध्याय 5) और यान लेकुन (Yann LeCun) तथा साथियों के 1989 के नेटवर्क से चली आई है। दाईं ओर खिड़की की आकृति चुनकर उसे छवि पर खिसकाएँ। नीचे के ग्राफ़ में प्रतियोगिता की 8 सालों की प्रथम स्थान वाली त्रुटि दर है।

आउटपुट(i, j)＝Σ_a Σ_b खिड़की(a, b) × छवि(i＋a, j＋b)

खिड़की: 3×3 वज़नों की तालिका (सीखने पर खड़ी रेखाओं, आड़ी रेखाओं आदि पर प्रतिक्रिया करने वाले रूप बनते हैं)

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:डीप लर्निंग 2012 में अचानक पैदा हुई
मूल स्रोत के अनुसार:विजेता विधि लेकुन और साथियों के 1989 के नेटवर्क (मूलतः फ़ुकुशिमा के 1979 के निओकॉग्निट्रॉन) को बड़ा करके GPU पर सिखाने से बनी। शोधपत्र ने भी लिखा, (अनुवाद)।

प्रतियोगिता की प्रथम स्थान वाली त्रुटि दर (2010〜2017)

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_convolution.py

# u09 畳み込み：フィルター（小さな窓）を画像の上ですべらせ、同じ形の部分で強く反応させる
#
# どの出来事か：2012 年の画像認識の大会 ILSVRC で、トロント大学の SuperVision が 8 層の畳み込みニューラルネットワークで大差の 1 位
#   （記録 ilsvrc_2012_supervision）。1 位の誤り率は 2010 年の 28.2% から 2017 年には 2.3% へ下がった
#   （記録 ilsvrc_winning_error_2010_2017）。畳み込みの構造は、1979 年の福島邦彦によるネオコグニトロンや、
#   1989 年のルカンたちのネットワークから続く。
# 仕組み：
#   (1) 12×12 の画像（このサイトが作った例）に、3×3 の窓を 3 種類（たての線・よこの線・ななめの線）すべらせ、
#       出力(i, j) = Σ 窓(a, b) × 画像(i + a, j + b) を計算する。窓の形と一致する場所で値が大きくなる。
#   (2) 大会の 1 位の誤り率を、年ごとに棒グラフで並べる（記録の数値）。
#   実際のニューラルネットワークは、フィルターの数値を自動で学習し、何層も重ねる。ここでは人が決めた窓を使う。
# 試してみよう：
#   - 窓を自分で作る（たとえば、角を見つける窓）
#   - 画像 ART を描きかえる

ART = [
    "............",
    ".#########..",
    ".#.......#..",
    ".#.......#..",
    ".#...#...#..",
    ".#....#..#..",
    ".#.....#.#..",
    ".#......##..",
    ".#.......#..",
    ".#########..",
    "............",
    "............",
]
IMG = [[1 if c == "#" else 0 for c in row] for row in ART]
KERNELS = {
    "たての線": [[-1, 2, -1], [-1, 2, -1], [-1, 2, -1]],
    "よこの線": [[-1, -1, -1], [2, 2, 2], [-1, -1, -1]],
    "ななめの線": [[2, -1, -1], [-1, 2, -1], [-1, -1, 2]],
}

def conv(img, k):
    n = len(img) - 2
    return [[sum(k[a][b] * img[i + a][j + b] for a in range(3) for b in range(3)) for j in range(n)] for i in range(n)]

print("(1) 元の画像（12×12）")
for row in ART:
    print("    " + row)
for name, k in KERNELS.items():
    out = conv(IMG, k)
    top = max(max(r) for r in out)
    print(f"  窓「{name}」をすべらせた出力（◆＝一番強い {top}、◇＝半分以上）")
    for r in out:
        print("    " + "".join("◆" if v == top else ("◇" if v >= top / 2 else "・") for v in r))

print()
print("(2) 大会の 1 位の誤り率（5 回答えてよいルール）")
ERR = [(2010, 28.2), (2011, 25.8), (2012, 15.3), (2013, 11.7), (2014, 6.7), (2015, 3.6), (2016, 3.0), (2017, 2.3)]
for y, e in ERR:
    print(f"  {y} {e:5.1f}% " + "#" * int(e * 1.5))
print("  2012 年の 2 位（東京大学のチーム）は 26.2%。")

292005〜2012 · जापान · शोगी और चेकर्स

चालों से सीखना, बहुमत से खेलना

शोगी सॉफ़्टवेयर की ताकत क्या उसे बनाने वाले की शोगी क्षमता से तय होती है?

पहले अधिकतर शोगी सॉफ़्टवेयर में बनाने वाले खुद तय करते थे कि खेल की स्थिति को अच्छा या बुरा बताने के अंक कैसे दें। रसायन शोधकर्ता कुनिहितो होकी (Kunihito Hoki) के Bonanza (2005 में जारी) ने पेशेवर खिलाड़ियों के खेल रिकॉर्ड जैसी चालें चलने के लिए अंक देना मशीन से सिखवाया। मई 2006 में पहली बार भाग लेकर विश्व कंप्यूटर शोगी चैंपियनशिप जीती। मार्च 2007 में रयूओ ख़िताबधारी अकिरा वतानाबे (Akira Watanabe) से सार्वजनिक मैच खेला (112 चालों में वतानाबे जीते)।

अक्टूबर 2010 में जापान की सूचना प्रसंस्करण सोसायटी का “अकारा2010” महिला ओशो ख़िताबधारी इचियो शिमिज़ु (Ichiyo Shimizu) से जीता। इसमें जापान के शीर्ष 4 प्रोग्राम एक ही स्थिति पर सोचते थे और सबसे अधिक चुनी गई चाल बहुमत से खेली जाती थी। जनवरी 2012 के पहले शोगी देनओ-सेन में Bonanza पर आधारित Bonkras ने सेवानिवृत्त खिलाड़ी और जापान शोगी संघ के तत्कालीन अध्यक्ष, आजीवन किसेई ख़िताबधारी कुनिओ योनेनागा (Kunio Yonenaga), को 113 चालों में हराया।

दाईं ओर ऐसी लर्निंग विधि है जो वज़नों को बदलकर पेशेवर की चाल को सबसे अधिक अंक दिलाती है (इस साइट का बनाया मॉडल)।

w ← w＋η（f(पेशेवर की चाल) − f(m)）

m: वह चाल जिसके अंक पेशेवर की चाल से अधिक हो गए
w, η: अंक देने के वज़न और सीखने की दर
f: चाल के बाद की स्थिति की विशेषताएँ (मोहरे का लाभ, राजा की सुरक्षा, मोहरों का काम)

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:मज़बूत शोगी सॉफ़्टवेयर बनाने के लिए बनाने वाला भी शोगी में मज़बूत हो
मूल स्रोत के अनुसार:Bonanza के लेखक रसायन शोधकर्ता थे जो शोगी लगभग नहीं जानते थे, फिर भी खेल रिकॉर्ड से मशीन को अंक देना सिखाकर पहली भागीदारी में विश्व प्रतियोगिता जीत गए।

प्रशिक्षण के दौर और पेशेवर वाली चाल चुनने का अनुपात

यह “आज़माएँ” वाली प्रक्रिया का Python कोड है। ▶ चलाएँ दबाने पर नीचे नतीजा दिखेगा। संख्याएँ बदलकर फिर से चलाकर देखें।

u09_bonanza_learn.py

# u09 棋譜から、点のつけ方を学習する：プロの手が最も高得点になるように、重みを更新する（このサイトの模式）
#
# どの出来事か：保木邦仁の将棋ソフト Bonanza（2005 年公開）は、プロの棋譜と同じ手を指すように、
#   局面の評価方法を機械に学習させ、2006 年の世界コンピュータ将棋選手権で優勝した（記録 bonanza_2006_watanabe_2007）。
#   2010 年の「あから2010」は、4 つのソフトの多数決で指した（記録 akara2010_shimizu_2010）。
# 仕組み：局面ごとに、指せる手が 5 つある。手を指したあとの局面を 3 つの特徴
#   （駒の得・玉の守り・駒の働き）で表し、得点 ＝ w1×駒の得 ＋ w2×玉の守り ＋ w3×駒の働き とする。
#   プロの手より得点の高い手 m があれば、w ← w ＋ η (f(プロの手) − f(m)) と更新する。
#   ※ Bonanza の実際の学習方法そのものではない。「プロの手と同じ手を選ぶように点のつけ方を直す」という考えの模式。
#   局面・手・「プロの好み」は、このサイトが作った例。
#   最後に、少しずつ重みが異なる 4 つのソフトで、多数決をしてみる。
# 試してみよう：
#   - ETA（学習率）を変える
#   - 多数決に参加するソフトの数 VOTERS を 1・4・9 にする

import random

random.seed(2006)
ETA = 0.05
VOTERS = 4
PRO = [1.0, 0.8, 0.5]      # 「プロの好み」（学習する側は知らない。このサイトの仮の数）

def make_position():
    return [[random.gauss(0, 1) for _ in range(3)] for _ in range(5)]

def pro_move(pos):
    return max(range(5), key=lambda m: sum(p * f for p, f in zip(PRO, pos[m])) + random.gauss(0, 0.3))

def best(w, pos):
    return max(range(5), key=lambda m: sum(a * b for a, b in zip(w, pos[m])))

games = [(p, pro_move(p)) for p in (make_position() for _ in range(400))]
test = [(p, pro_move(p)) for p in (make_position() for _ in range(400))]

def agree(w, data):
    return sum(best(w, p) == m for p, m in data) / len(data)

w = [0.0, 0.0, 1.0]    # 初めは「駒の働き」だけを見る（重みの初期値）
print("学習回数 → 新しい局面でプロと同じ手を選べた割合")
for rnd in range(0, 6):
    print(f"  {rnd} 周：{agree(w, test):5.1%} " + "#" * int(agree(w, test) * 40) + f"  重み ({w[0]:.2f}, {w[1]:.2f}, {w[2]:.2f})")
    for pos, pm in games:
        for m in range(5):
            if m != pm and sum(a * b for a, b in zip(w, pos[m])) >= sum(a * b for a, b in zip(w, pos[pm])):
                w = [wi + ETA * (a - b) for wi, a, b in zip(w, pos[pm], pos[m])]

print()
print(f"少しずつ重みが異なる {VOTERS} つのソフトで、多数決をする")
soft = [[wi + random.gauss(0, 0.35) for wi in w] for _ in range(VOTERS)]
for k, s in enumerate(soft):
    print(f"  ソフト {k + 1}：プロと同じ手 {agree(s, test):5.1%}")

def vote(pos):
    count = [0] * 5
    for s in soft:
        count[best(s, pos)] += 1
    return max(range(5), key=lambda m: (count[m], -m))

print(f"  多数決　：プロと同じ手 {sum(vote(p) == m for p, m in test) / len(test):5.1%}")

302001 · 2011 · जापान · भविष्यवाणियाँ

समयसीमा वाले लक्ष्य और बाज़ार अनुमान

इस समय जापान में “इस साल तक” के कौन-से लक्ष्य थे?

नवंबर 2011 में राष्ट्रीय सूचना विज्ञान संस्थान ने (अनुवाद) नाम की टोडाई रोबोट परियोजना शुरू की। उद्देश्य था 1980 के बाद छोटे हिस्सों में बँटे AI शोध को जोड़ना और युवाओं को सपना देना। ठोस पड़ाव के रूप में (अनुवाद) और (अनुवाद) जैसे समयसीमा वाले लक्ष्य रखे (नतीजों से तुलना अध्याय 10 में है)।

उससे 10 साल पहले, 2001 में जापान के मशीनरी और रोबोट उद्योग संगठनों की रिपोर्ट ने 2010 में लगभग 3 लाख करोड़ येन का रोबोट बाज़ार (जिसमें दैनिक जीवन का क्षेत्र 1.5 लाख करोड़ येन) और 2025 में लगभग 8 लाख करोड़ येन का अनुमान दिया। वास्तव में विनिर्माण के बाहर अगली पीढ़ी के रोबोटों का बाज़ार सालाना 1.4〜6.8 अरब येन था, 10 अरब येन तक भी नहीं पहुँचा और उलटे सिकुड़ रहा था (उन्नत औद्योगिक विज्ञान और प्रौद्योगिकी संस्थान के हिरोहिको अराई (Hirohiko Arai) का 2009 का विश्लेषण)। सरकार की 2015 की रणनीति में भी पूरे रोबोट बाज़ार को (अनुवाद) लिखा गया।

दाईं ओर अनुमान और वास्तविक आँकड़े हर निशान पर 10 गुना बढ़ते पैमाने पर हैं।

अनुमान ÷ वास्तविक मान ＝ कितने गुने का अंतर

10 गुने वाला पैमाना: 1 → 10 → 100 समान दूरी पर हैं (2 बिंदुओं की दूरी बताती है कि अंतर कितने गुने का है)

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात: (अनुवाद; रोबोट शोधकर्ताओं में सामान्य धारणा)
मूल स्रोत के अनुसार:उद्योग संघ के खुद के सर्वेक्षण में अगली पीढ़ी के रोबोटों का बाज़ार सालाना 1.4〜6.8 अरब येन ही रहा और उलटे सिकुड़ रहा था (सालाना औसत −10.2%)।

3 शर्तें एक साथ पूरी हुईं

परिणाम से कारण की ओर

त्रुटियों के वर्गों का न्यूनतम योग

जनसंख्या के सूत्र से संभावना तक

बिंदुओं के सबसे पास कौन-सी रेखा?

डेटा से अंक तय करना

बस सबसे पास के उदाहरण से सीखना

बाँटें, फिर औसत पर खिसकाएँ

समान चीज़ों को जोड़कर वृक्ष बनाना

संकेतों से छिपी अवस्था पहचानना

ज़रूरत से ज़्यादा मेल को कैसे पहचानें

छिपे हिस्से भरकर फिर गणना करना

सफ़ेद-काले की सीमा खुद तय करना

साक्ष्य से संभावनाएँ जाल में बदलती हैं

सबसे पहले कौन-सा सवाल पूछें?

पुरस्कार से सीखना

गलतियों के अनुसार कमज़ोर मॉडल जोड़ना

सीमा के दोनों ओर सबसे अधिक जगह

बेतरतीब बने वृक्षों का बहुमत

हर तालिका को 3 भागों में बाँटना

खाली जगहों वाली तालिका से सीखना

सही लेबल किसने लगाए?

प्रशिक्षण और परीक्षण अलग रखकर जाँचें

एक ही गणना, कई साथ-साथ

छवियों से पहले आवाज़ में

गहरी परतों में भी संकेत बना रहे

यातायात संकेत और Google की बिल्ली

बड़ी जीत, दूसरा टोक्यो विश्वविद्यालय

चालों से सीखना, बहुमत से खेलना

समयसीमा वाले लक्ष्य और बाज़ार अनुमान

औज़ार पुराने थे, एक साथ आना नया था

गो सॉफ़्टवेयर को मज़बूत बनाने वाली “मोंटे कार्लो ट्री सर्च” की बुनियाद के 2 शोधपत्र

गो सॉफ़्टवेयर को मज़बूत बनाने वाली की बुनियाद के 2 शोधपत्र