पहले उभार की शुरुआत | AI का पूरा इतिहास

011955 · नाम और प्रस्ताव

नाम वाला गर्मियों का प्रस्ताव

नाम कहाँ जन्मा और उसके साथ कैसी उम्मीदें जुड़ी थीं?

31 अगस्त, 1955 की तारीख वाले प्रस्ताव में मैकार्थी (McCarthy), मिंस्की (Minsky), रोचेस्टर (Rochester) और शैनन (Shannon), इन 4 लोगों ने अगली गर्मियों में डार्टमथ कॉलेज में होने वाली कार्यशाला की योजना लिखी और रॉकफेलर फाउंडेशन से धन माँगा। उसके शीर्षक में शब्द थे। प्रस्ताव इस अनुमान से शुरू होता है कि सीखने या बुद्धिमत्ता की हर विशेषता का, सिद्धांततः, (अनुवाद)।

दाईं ओर के 7 खाने प्रस्ताव में दिए गए शोध विषय हैं। किसी खाने को दबाने पर उसका विवरण दिखता है। भाषा, न्यूरल नेटवर्क, गणना का आकार, खुद को सुधारने वाली मशीनें। इस अध्याय के कई पृष्ठ इन्हीं विषयों को आगे बढ़ाते हैं।

उन्होंने 2 महीने की अवधि और 10 प्रतिभागियों की योजना बनाई। उनका कहना था कि चुनिंदा वैज्ञानिक एक गर्मी साथ काम करें, तो (अनुवाद)। उन्होंने 13,500 डॉलर का बजट माँगा, लेकिन फाउंडेशन ने 7,500 डॉलर दिए।

बजट की तालिका की मदों का जोड़ 13,000 डॉलर है। यह तालिका में लिखे कुल 13,500 डॉलर से 500 डॉलर कम है (मैकार्थी की वेबसाइट पर पुनर्प्रकाशित संस्करण में इसकी पुष्टि की गई। अंतर का कारण नहीं बताया गया है)।

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात: नाम सबकी सहमति से चुना गया था
मूल स्रोत के अनुसार:नाम मैकार्थी ने चुना था और उस समय भी इस पर आपत्तियाँ थीं। न्यूवेल (Newell) और साइमन (Simon) कई वर्षों तक अलग नाम, , इस्तेमाल करते रहे।

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

021956 · डार्टमथ

गर्मियों की कार्यशाला कैसी थी?

“वह बड़ा सम्मेलन जहाँ AI का जन्म हुआ” असल में कैसी बैठक थी?

1956 की गर्मियों में सोचने वाली मशीनों में रुचि रखने वाले शोधकर्ता डार्टमथ कॉलेज के गणित विभाग की सबसे ऊपरी मंज़िल पर इकट्ठा हुए। प्रतिभागी सोलोमोनॉफ़ (Solomonoff) के नोट के अनुसार, यह लगभग 18 जून से 17 अगस्त तक, करीब 8 सप्ताह चली। तय समय-सारणी वाले सम्मेलन से अधिक यह ऐसी बैठक थी जहाँ लोग अलग-अलग समय पर आते और चर्चा करते थे।

दाईं आकृति में “विवरण: योजना और रिकॉर्ड” दबाने पर, मैकार्थी (McCarthy) ने 26 मई को फाउंडेशन को जो योजना भेजी थी (बैंगनी चौखटे), उसके ऊपर सोलोमोनॉफ़ और मोर (More) के नोट में दर्ज “उस दिन उपस्थित लोग” (गहरे नीले बिंदु) देख सकते हैं। पूरी अवधि में रहने वाले केवल 3 लोग थे। जिन 11 लोगों के आने की योजना थी, उनमें से 2 नहीं आए। रोज़ की चर्चा में लगभग 3〜8 लोग शामिल होते थे।

सबके मिलकर 1 ही समस्या पर काम करने की बात भी हुई। 7 अगस्त को मैकार्थी ने शतरंज का सुझाव दिया, लेकिन यह साझा शोध नहीं बना। बाद में मैकार्थी ने बताया कि धन कम था और सबके दूसरे काम भी थे, इसलिए पूरी गर्मी सबके साथ रहने की योजना पूरी नहीं हो सकी।

प्रतिभागियों की सटीक सूची बची नहीं है (मैकार्थी ने अपनी सूची खो दी थी)। बिंदु केवल नोट में दर्ज दिनों को दिखाते हैं। किसी दिन बिंदु न होने का मतलब यह नहीं कि उस व्यक्ति की उपस्थिति नहीं थी।

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:डार्टमथ की कार्यशाला एक बड़ा सम्मेलन थी जहाँ AI का जन्म हुआ
मूल स्रोत के अनुसार:असल में यह गर्मियों की बैठक थी जिसमें लोग अलग-अलग समय पर आते थे और रोज़ की चर्चा में लगभग 3〜8 लोग होते थे। फाउंडेशन से माँगी गई राशि का लगभग आधा धन मिला और कार्यशाला की कोई रिपोर्ट भी प्रकाशित नहीं हुई।

6वें सप्ताह (23〜27 जुलाई) की रोज़ की चर्चा में शामिल लोगों की संख्या (मोर के नोट)

031956 · खोज

हर संभव प्रमाण बनाते जाएँ तो?

हर संभव प्रमाण को बारी-बारी से बनाते जाएँ, तो क्या कभी न कभी मनचाहा प्रमेय नहीं मिलेगा?

न्यूवेल (Newell), शॉ (Shaw) और साइमन (Simon) ने पुस्तक के तर्क के प्रमेयों पर काम किया। 5 स्वयंसिद्धों से नए प्रमेय बनाने के 3 नियम थे: प्रतिस्थापन, यानी अक्षर की जगह व्यंजक रखना; रूप बदलना, यानी समान अर्थ वाले रूप में लिखना; और निष्कर्ष निकालना, यानी A तथा “यदि A तो B” से B प्राप्त करना।

सबसे सरल तरीका है कि छोटे प्रमाणों से शुरू करके सभी संभव प्रमाण बनाए जाएँ और मनचाहा व्यंजक आने का इंतज़ार किया जाए। इन 3 लोगों ने इसे ब्रिटिश म्यूज़ियम वाला तरीका (British Museum algorithm) कहा और तुलना के लिए इस्तेमाल किया। रिपोर्ट के आँकड़ों में 4वें चरण तक 42 व्यंजक और 8वें चरण तक 246 थे। पुस्तक के पूरे अध्याय 2 के प्रमेय जुटाने के लिए लगभग 100,000,000 व्यंजक बनाने पड़ सकते थे और उन्होंने कई लाख वर्ष लगने का अनुमान लगाया।

संभव उत्तरों को बारी-बारी से जाँचना खोज कहलाता है। हर संभावना जाँचने में उम्मीदवार बहुत ज़्यादा होते हैं, इसलिए अनुभव से मिले छोटे रास्तों के नियमों (ह्यूरिस्टिक्स) से जाँच का दायरा कम करना ज़रूरी है। दाईं आकृति इस साइट की गिनती के तरीके से व्यंजक बनाती है।

चरण n के व्यंजकों की संख्या ≈ (चरण n−1 के व्यंजकों की संख्या) × (1 जगह को बदलने के तरीकों की संख्या)

बदलने के तरीके: p को ¬p करना, → और ¬…∨ को आपस में बदलना, आदि

हर चरण में व्यंजकों की संख्या (ऊर्ध्वाधर अक्ष पर हर कदम 10 गुना)

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

u03_british_museum.py

# u03 「大英博物館のやり方」：証明を片っぱしから作ると、どれだけ増えるか
#
# どの出来事か：1957年1月のロジック・セオリストの報告（記録 logic_theorist_1956）。
#   ニューウェルたちは比較対象として、公理から作れる証明をすべて順に作っていく手法を考え、
#   冗談まじりに British Museum algorithm（大英博物館のやり方）と呼んだ。報告にある数値：
#   4段目までに42個、6段目までに115個、8段目までに246個、11段目までで約1,000個。
#   第2章の定理をすべてそろえるには1億個ほど要るかもしれず、何十万年もかかると見積もった。
# 仕組み：公理（5個）から出発し、1段ごとに、前の段の式の1か所だけを変えた式をすべて作る。
#   変え方は報告の図2と同じ2種類。文字を「でない＋その文字」にする（p → -p）、
#   「ならば」と「でない…または」を入れかえる（p > q ⇔ -p v q）。
#   ※ 数え方はこのサイト独自のもので、報告の数とは一致しない。増え方の傾向を見るためのもの。
# 試してみよう：
#   - SPECIALIZE を True にして、文字どうしの代入（q を p にするなど）も入れると、2.07 は出てくるか
#   - STEPS を 12 にすると、作る式の数はどれだけ増えるか

STEPS = 10
SPECIALIZE = False

AXIOMS = ["(p v p) > p", "p > (q v p)", "(p v q) > (q v p)", "(p v (q v r)) > (q v (p v r))", "(p > q) > ((r v p) > (r v q))"]
TARGETS = {"2.01": "(p > -p) > -p", "2.02": "p > (q > p)", "2.07": "p > (p v p)"}

def parse(s):
    toks = s.replace("(", " ( ").replace(")", " ) ").replace("-", " - ").split()
    pos = 0

def expr():
        nonlocal pos
        left = unary()
        if pos < len(toks) and toks[pos] in (">", "v"):
            op = toks[pos]
            pos += 1
            return ("i" if op == ">" else "o", left, expr())
        return left

def unary():
        nonlocal pos
        t = toks[pos]
        pos += 1
        if t == "-":
            return ("n", unary())
        if t == "(":
            e = expr()
            pos += 1
            return e
        return ("v", t)
    return expr()

def show(e):
    if e[0] == "v":
        return e[1]
    if e[0] == "n":
        return "-" + (show(e[1]) if e[1][0] in ("v", "n") else f"({show(e[1])})")
    a, b = show(e[1]), show(e[2])
    a = a if e[1][0] in ("v", "n") else f"({a})"
    b = b if e[2][0] in ("v", "n") else f"({b})"
    return f"{a} {'>' if e[0] == 'i' else 'v'} {b}"

def letters(e, out=None):
    out = set() if out is None else out
    if e[0] == "v":
        out.add(e[1])
    else:
        for x in e[1:]:
            letters(x, out)
    return out

def put(e, v, new):
    if e[0] == "v":
        return new if e[1] == v else e
    if e[0] == "n":
        return ("n", put(e[1], v, new))
    return (e[0], put(e[1], v, new), put(e[2], v, new))

def replacements(e):
    """1 か所だけ「ならば」⇔「でない…または」を入れかえた式をすべて作る。"""
    out = []
    if e[0] == "i":
        out.append(("o", ("n", e[1]), e[2]))
    if e[0] == "o" and e[1][0] == "n":
        out.append(("i", e[1][1], e[2]))
    if e[0] == "n":
        out += [("n", x) for x in replacements(e[1])]
    if e[0] in ("i", "o"):
        out += [(e[0], x, e[2]) for x in replacements(e[1])]
        out += [(e[0], e[1], x) for x in replacements(e[2])]
    return out

def one_change(e):
    ls = sorted(letters(e))
    out = [put(e, v, ("n", ("v", v))) for v in ls]           # p → -p
    if SPECIALIZE:
        out += [put(e, v, ("v", w)) for v in ls for w in ls if v != w]   # q → p
    return out + replacements(e)

targets = {k: parse(s) for k, s in TARGETS.items()}
seen = {parse(a) for a in AXIOMS}
level = list(seen)
total = len(seen)
found = {}
print(f"段  作った式の合計   （公理 5 個から）")
print(f" 1  {total:>8}")
for step in range(2, STEPS + 1):
    new = []
    for e in level:
        for x in one_change(e):
            if x not in seen:
                seen.add(x)
                new.append(x)
                for k, t in targets.items():
                    if x == t and k not in found:
                        found[k] = (step, total + len(new))
    total += len(new)
    level = new
    hits = "、".join(f"{k} が見つかった（{n} 個目）" for k, (s, n) in found.items() if s == step)
    print(f"{step:>2}  {total:>8}  " + "■" * min(60, total // 100) + ("  " + hits if hits else ""))

for k in TARGETS:
    if k not in found:
        print(f"{k} {TARGETS[k]} は、{STEPS} 段までに見つからなかった")
print("\n例：最後の段で作った式の最初の 5 個")
for e in level[:5]:
    print("   ", show(e))

041956 · लॉजिक थिओरिस्ट

उत्तर से उल्टी दिशा में खोज

प्रोग्राम किसी व्यक्ति की तरह अनुमान लगाकर प्रमेय का प्रमाण कैसे खोज सकता है?

लॉजिक थिओरिस्ट (LT) ने सब कुछ बनाने के बजाय उस व्यंजक से उल्टी दिशा में खोज की जिसे सिद्ध करना था। यह बारी-बारी से 4 तरीके आज़माता है। प्रतिस्थापन में स्वयंसिद्ध या पहले से सिद्ध प्रमेय के अक्षरों की जगह व्यंजक रखकर देखा जाता है कि क्या उसे समस्या के ठीक समान रूप में लिखा जा सकता है। निष्कर्ष निकालने वाला तरीका ऐसा “यदि A तो B” प्रमेय खोजता है जिसका B समस्या से मेल खाता हो और A को नई छोटी समस्या बना देता है। आगे और पीछे की ओर कड़ियाँ जोड़ने के तरीके भी छोटी समस्याएँ बनाते हैं।

1957 की रिपोर्ट के अनुसार, इसने अध्याय 2 के पहले 52 प्रमेयों में से 38 के प्रमाण खोजे। 17 केवल प्रतिस्थापन से हल हुए और 19 को 2 कदम लगे। 2.01 में लगभग 10 सेकंड और 2.45 में लगभग 12 मिनट लगे। 2.31 पर लगभग 23 मिनट बाद खोज के सभी विकल्प समाप्त हो गए। दाईं आकृति इस साइट का बनाया छोटा LT है। “अंत तक चलाएँ” दबाने पर पेड़ नीचे बढ़ता है और हरा रास्ता प्रमाण दिखाता है।

रिपोर्ट ने एक तुलना दी। स्वयंसिद्धों से आगे बढ़ना अगर घास के ढेर में 1 सुई ढूँढ़ने जैसा है, तो लक्ष्य से पीछे लौटना उस रास्ते को ढूँढ़ने जैसा है जिससे सुई ढेर से बाहर निकल सकती है।

आकृति का LT बारीकियों में 1956 के प्रोग्राम से अलग है। रिपोर्ट कहती है कि 4 तरीकों से 2.13 सिद्ध नहीं हो सकता। लेकिन इस साइट के उदाहरण में व्यंजकों के रूप मिलाने का तरीका और उपलब्ध प्रमेयों की शर्तें अलग हैं। इसलिए “उपलब्ध प्रमेय भी इस्तेमाल करें” पर निशान लगाने से 2.13 का प्रमाण भी मिल जाता है।

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

u03_logic_theorist.py

# u03 ロジック・セオリスト：証明を「答えの側から、逆向きに」探す（1956 年の仕組みを小さくした例）
#
# どの出来事か：1956 年、ニューウェル、ショー、サイモンのロジック・セオリスト（記録 logic_theorist_1956）。
#   ホワイトヘッドとラッセルの著書『プリンキピア・マテマティカ』第 2 章の定理の証明を探索した。
#   1957 年の報告では、最初の 52 の定理のうち 38 の証明を見つけた。2.01 は約 10 秒、2.45 は約 12 分。
# 仕組み：原著と同じ 5 つの公理から出発する。証明したい式（問題）に対して、次の 4 つの「方法」を順に試す。
#   1. 代入法：公理や、すでに証明した定理の文字（p, q, r）に式を代入し、問題と一致させられるか調べる
#   2. 切り離し法：「A ならば B」の形の定理で、B が問題と一致するものを探し、A を新しい小さな問題にする
#   3. 前向きのつなぎ：問題が「a ならば c」のとき、「a ならば b」の定理を探し、「b ならば c」を新しい問題にする
#   4. 後ろ向きのつなぎ：「b ならば c」の定理を探し、「a ならば b」を新しい問題にする
#   新しい問題は、すぐ代入法で解けないか試し、解けなければ「あとで考える問題の列」に並べる。
#   ※「A ならば B」は「A でない、または B」と同じとして、形をそろえてから比べる（原著の「置きかえ」の決まり）。
#   ※ これはこのサイトが作成した小さな例。1956 年のプログラムの細かい点（似ているかの判定方法など）は同じではない。
#   報告と同じく、ある定理を証明するときは、公理と、それより前の定理を全部「使ってよい物」として渡す。
# 試してみよう：
#   - ONLY_AXIOMS を True にして、公理だけで始めると、証明できる定理と調べる回数はどう変わるか
#   - GOALS に "2.13" を足すと？（報告では、1956 年のプログラムの 4 つの方法では 2.13 は証明できない。
#     このプログラムは形のそろえ方が違うため、結果が違うことがある。どこが違うか考えてみよう）

AXIOMS = {
    "1.2": "(p v p) > p",
    "1.3": "p > (q v p)",
    "1.4": "(p v q) > (q v p)",
    "1.5": "(p v (q v r)) > (q v (p v r))",
    "1.6": "(p > q) > ((r v p) > (r v q))",
}
# 報告に形が出てくる第 2 章の定理（> は「ならば」、v は「または」、- は「でない」）
THEOREMS = {
    "2.01": "(p > -p) > -p",
    "2.02": "p > (q > p)",
    "2.06": "(p > q) > ((q > r) > (p > r))",
    "2.07": "p > (p v p)",
    "2.12": "p > --p",
    "2.15": "(-p > q) > (-q > p)",
    "2.16": "(p > q) > (-q > -p)",
    "2.17": "(-q > -p) > (p > q)",
    "2.2": "p > (p v q)",
    "2.45": "-(p v q) > -p",
    "2.13": "p v ---p",
    "2.31": "(p v (q v r)) > ((p v q) v r)",
}
GOALS = ["2.01", "2.02", "2.06", "2.07", "2.12", "2.15", "2.16", "2.17", "2.2", "2.45"]
ONLY_AXIOMS = False
MAX_TRIES = 20000          # 調べる定理の数の上限（制限時間の代わり）

# ---------- 式を読む・書く ----------
def parse(s):
    toks = s.replace("(", " ( ").replace(")", " ) ").replace("-", " - ").split()
    pos = 0

def expr():
        nonlocal pos
        left = unary()
        if pos < len(toks) and toks[pos] in (">", "v"):
            op = toks[pos]
            pos += 1
            right = expr()
            return ("i" if op == ">" else "o", left, right)
        return left

def unary():
        nonlocal pos
        t = toks[pos]
        pos += 1
        if t == "-":
            return ("n", unary())
        if t == "(":
            e = expr()
            pos += 1  # ")"
            return e
        return ("v", t)
    return expr()

def show(e):
    if e[0] == "v":
        return e[1]
    if e[0] == "n":
        return "-" + (show(e[1]) if e[1][0] in ("v", "n") else f"({show(e[1])})")
    a, b = show(e[1]), show(e[2])
    a = a if e[1][0] in ("v", "n") else f"({a})"
    b = b if e[2][0] in ("v", "n") else f"({b})"
    return f"{a} {'>' if e[0] == 'i' else 'v'} {b}"

def canon(e):
    """「A ならば B」を「A でない、または B」に直して、形をそろえる。"""
    if e[0] == "v":
        return e
    if e[0] == "n":
        return ("n", canon(e[1]))
    if e[0] == "i":
        return ("o", ("n", canon(e[1])), canon(e[2]))
    return ("o", canon(e[1]), canon(e[2]))

def match(pat, e, sub):
    """定理 pat の文字に式を代入して e と一致させられるか調べる。できれば代入の辞書を返す。"""
    if pat[0] == "v":
        name = pat[1]
        if name in sub:
            return sub if sub[name] == e else None
        s2 = dict(sub)
        s2[name] = e
        return s2
    if pat[0] != e[0]:
        return None
    if pat[0] == "n":
        return match(pat[1], e[1], sub)
    s1 = match(pat[1], e[1], sub)
    return None if s1 is None else match(pat[2], e[2], s1)

def subst(e, sub):
    if e[0] == "v":
        return sub.get(e[1], e)
    if e[0] == "n":
        return ("n", subst(e[1], sub))
    return (e[0], subst(e[1], sub), subst(e[2], sub))

def letters(e, out=None):
    out = set() if out is None else out
    if e[0] == "v":
        out.add(e[1])
    else:
        for x in e[1:]:
            letters(x, out)
    return out

def as_implication(e):
    """形をそろえた式が「A ならば B」（= A でない、または B）なら (A, B) を返す。"""
    if e[0] == "o" and e[1][0] == "n":
        return e[1][1], e[2]
    return None

# ---------- ロジック・セオリスト（小さくした例） ----------
def prove(goal, known):
    tries = 0
    theorems = [(name, canon(parse(s))) for name, s in known]
    root = canon(goal)

def by_substitution(problem):
        nonlocal tries
        for name, t in theorems:
            tries += 1
            if match(t, problem, {}) is not None:
                return name
        return None

first = by_substitution(root)
    if first:
        return [f"代入法：{first} から"], tries
    queue = [(root, [])]
    seen = {root}
    while queue and tries < MAX_TRIES:
        problem, path = queue.pop(0)
        new = []
        for name, t in theorems:
            imp = as_implication(t)
            if not imp:
                continue
            a, b = imp
            tries += 1
            s = match(b, problem, {})                      # 切り離し法
            if s is not None and letters(a) <= set(s):
                new.append((subst(a, s), f"切り離し法：{name}"))
            pi = as_implication(problem)
            if pi:
                pa, pc = pi
                tries += 1
                s = match(a, pa, {})                       # 前向きのつなぎ
                if s is not None and letters(b) <= set(s):
                    new.append((("o", ("n", subst(b, s)), pc), f"前向きのつなぎ：{name}"))
                tries += 1
                s = match(b, pc, {})                       # 後ろ向きのつなぎ
                if s is not None and letters(a) <= set(s):
                    new.append((("o", ("n", pa), subst(a, s)), f"後ろ向きのつなぎ：{name}"))
        for sub_problem, how in new:
            if sub_problem in seen:
                continue
            seen.add(sub_problem)
            done = by_substitution(sub_problem)
            if done:
                return path + [how, f"代入法：{done} から"], tries
            queue.append((sub_problem, path + [how]))
    return None, tries

print("公理：", "  ".join(f"{k} {v}" for k, v in AXIOMS.items()))
print("（> は「ならば」、v は「または」、- は「でない」）\n")
proved = []
for i, g in enumerate(GOALS):
    known = list(AXIOMS.items())
    if ONLY_AXIOMS:
        known += [(k, THEOREMS[k]) for k in proved]            # 自分で証明できたものだけ
    else:
        known += [(k, THEOREMS[k]) for k in GOALS[:i]]         # 報告と同じ：前の定理は全部使ってよい
    steps, tries = prove(parse(THEOREMS[g]), known)
    if steps:
        proved.append(g)
        print(f"{g:<5} {THEOREMS[g]:<30} 見つけた（定理を {tries:,} 回 調べた）")
        print("      問題 → " + " → ".join(steps))
    else:
        print(f"{g:<5} {THEOREMS[g]:<30} 見つからない（{tries:,} 回 調べて打ち切り）")
print(f"\n{len(GOALS)} 個のうち {len(proved)} 個の証明を見つけた（1957 年の報告では、52 個のうち 38 個）")

051957 · सीखने वाली मशीन

गलती पर ही वज़न सुधारें

क्या केवल उदाहरण दिखाकर मशीन को चीज़ों में अंतर करना सिखाया जा सकता है?

1957 में कॉर्नेल एरोनॉटिकल लैबोरेटरी के मनोवैज्ञानिक रोज़ेनब्लाट (Rosenblatt) ने नौसेना अनुसंधान कार्यालय की सहायता से पर शोध शुरू किया। यह तंत्रिका कोशिकाओं के संबंधों की नकल करने वाला कृत्रिम न्यूरॉन है। हर इनपुट (0 या 1) को वज़न (उस इनपुट को कितना महत्व दिया जाए) से गुणा करके जोड़ता है। जोड़ सीमा मान के बराबर या उससे अधिक हो, तो आउटपुट 1 होता है।

सीखने का तरीका सरल है। गलती होने पर ही वज़न को सही उत्तर की दिशा में थोड़ा सुधारें। दाईं आकृति में ● और ○ रखें और “लगातार सीखें” दबाएँ। बैंगनी रेखा घूमती है या अपने समानांतर खिसकती है और गलतियों (बैंगनी घेरों) की संख्या बदलती है। कॉर्नेल के गणितज्ञ ब्लॉक (Block) ने सिद्ध किया कि अगर दोनों समूहों को अलग करने वाली सीधी रेखा मौजूद हो, तो इस सुधार के तरीके से वह ज़रूर मिल जाएगी।

न्यूरल नेटवर्क का इतिहास यहाँ से शुरू होता है। 1 सीधी रेखा से वर्गीकृत न होने वाली समस्याएँ अध्याय 5 में और परतें जोड़ने की बात अध्याय 8 में आएगी।

y＝1 (w₁x₁ ＋w₂x₂ ≧ t), अन्यथा 0। गलती होने पर w ← w＋η(सही उत्तर − y)x, t ← t − η(सही उत्तर − y)

t: सीमा मान
η: सुधार का आकार (आकृति में 0.5)
बैंगनी रेखा: वह सीमा जहाँ w₁x₁ ＋w₂x₂ का मान t के बराबर है

हर 1 चक्र में गलतियों की संख्या

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

u03_perceptron_line.py

# u03 パーセプトロン：間違えた時だけ、重みを正解の向きに修正する
#
# どの出来事か：1957 年からのローゼンブラットのパーセプトロン（記録 perceptron_1957）。
#   入力に重みを掛けて足し合わせ、しきい値以上なら 1、そうでなければ 0 を出力するニューロンを使う。
#   答えを間違えた時だけ重みを直す学習のしかた（誤り訂正学習）で、例から識別のしかたを学習した。
#   同じコーネル大学の数学者ブロックは、分ける境界（直線や平面）が存在するなら、この修正手順で必ず見つかることを証明した。
# 仕組み：点 (x1, x2) を「●」か「○」に分類する。w1·x1 + w2·x2 がしきい値 t 以上なら「●」。
#   間違えたら：●なのに○と判定した → w に x を足し、t を 1 下げる。逆なら引いて、t を上げる。
#   w1·x1 + w2·x2 = t が「分ける線」。重みを変えると線が回転し、t を変えると線が平行移動する。
#   データ点はこのサイトが作った例（固定した乱数）。
# 試してみよう：
#   - OVERLAP を 1.5 にして 2 つの集まりを重ねると、間違いはいつまでも 0 にならないか
#   - 点を 1 つ、わざと反対のグループに入れると、どうなるか

import random

random.seed(1957)
OVERLAP = 0.0   # 2 つの集まりの重なり具合（0 なら直線 1 本で分離できる）
ROUNDS = 20     # すべてのデータを学習させる回数

def make_points(n=12):
    pts = []
    for _ in range(n):
        pts.append((random.uniform(0, 3), random.uniform(3.3 - OVERLAP, 6), 1))    # ●（左上の集まり）
        pts.append((random.uniform(3.3 - OVERLAP, 6), random.uniform(0, 3), 0))    # ○（右下の集まり）
    random.shuffle(pts)
    return pts

def answer(w1, w2, t, x1, x2):
    return 1 if w1 * x1 + w2 * x2 >= t else 0

points = make_points()
w1, w2, t = 0.0, 0.0, 0.0
for r in range(1, ROUNDS + 1):
    mistakes = 0
    for x1, x2, want in points:
        got = answer(w1, w2, t, x1, x2)
        if got != want:
            mistakes += 1
            d = want - got               # +1 か -1
            w1 += d * x1
            w2 += d * x2
            t -= d
    print(f"{r:2d} 周目：間違い {mistakes:2d} 回 " + "■" * mistakes + f"   線：{w1:+.1f}·x1 {w2:+.1f}·x2 = {t:+.1f}")
    if mistakes == 0:
        print("   間違いが 0 になったので、線が止まった")
        break

print("\n点と線の図（● ○ はデータ点、· はモデルが●と判定する場所、空白は○と判定する場所）")
grid = {(round(x1), round(x2)): ("●" if k else "○") for x1, x2, k in points}
for y in range(6, -1, -1):
    row = ""
    for x in range(0, 7):
        row += grid.get((x, y), "·" if answer(w1, w2, t, x, y) else "　")
    print("  " + row)

061957 · भविष्यवाणियाँ

“10 वर्षों के भीतर” 4 भविष्यवाणियाँ

1957 के शोधकर्ताओं को अगले 10 वर्ष कैसे दिखाई देते थे?

14 नवंबर, 1957 को पिट्सबर्ग में एक सम्मेलन के रात्रिभोज में साइमन (Simon) ने न्यूवेल (Newell) के साथ लिखा भाषण दिया (अगले वर्ष पत्रिका में प्रकाशित हुआ)। उन्होंने कहा कि मौजूदा कंप्यूटर ऐसे सवालों को भी लोगों जैसे तरीकों से हल कर सकते हैं जिनकी हल करने की विधि तय नहीं है और अनुभव से सीख सकते हैं। फिर उन्होंने भविष्यवाणी की कि 10 वर्षों के भीतर 4 बातें होंगी।

कंप्यूटर शतरंज का विश्व चैंपियन बनेगा ( [अनुवाद])। एक महत्वपूर्ण नया गणितीय प्रमेय खोजेगा और सिद्ध करेगा। ऐसा संगीत लिखेगा जिसे आलोचक स्वीकार करेंगे। मनोविज्ञान के अधिकांश सिद्धांत प्रोग्राम का रूप लेंगे। उन्होंने यह भी कहा, (अनुवाद)।

कुछ उपलब्धियाँ इन उम्मीदों का आधार थीं: तर्क के प्रमेय सिद्ध करने वाला प्रोग्राम, शतरंज की शुरुआती चालें चलने वाला कंप्यूटर और संगीत रचने वाला इलिनॉय विश्वविद्यालय का ILLIAC। दाईं आकृति में वर्ष आगे बढ़ाने पर भविष्यवाणी की जाँच का वर्ष (1968) और उसके बाद की घटनाएँ दिखती हैं।

कंप्यूटर ने मौजूदा शतरंज विश्व चैंपियन को 1997 में हराया, भविष्यवाणी के लगभग 40 वर्ष बाद। कंप्यूटर ने स्वयं विश्व चैंपियन का खिताब कभी हासिल नहीं किया।

071958 · आलोचना और जवाब

जाँच की तारीख खुद लिखी

भविष्यवाणी को जाँचने योग्य बनाने के लिए क्या चाहिए?

भाषण पत्रिका में प्रकाशित होने के बाद बेलमैन (Bellman) ने एक पत्र में उसकी आलोचना की। 2 लेखकों के जवाब के अनुसार, आलोचना यह थी कि भविष्यवाणियाँ (अनुवाद) थीं। 1958 के जवाब में इन 2 लोगों ने लिखा, (अनुवाद)।

इन 2 लोगों ने समझाया कि उन्होंने समय-सीमा रखकर भविष्यवाणियों को स्पष्ट बनाया, ताकि वे नॉस्ट्राडेमस (Nostradamus) जैसी ऐसी भविष्यवाणियाँ न बन जाएँ जिन्हें परखा ही न जा सके। लेकिन जाँच के लिए, क्या होगा और कब तक होगा के साथ यह कसौटी भी चाहिए कि किस स्थिति में भविष्यवाणी सही मानी जाएगी। दाईं आकृति में समय-सीमा और कसौटी हटाकर देखें। शतरंज का परिणाम स्पष्ट निकलता है, लेकिन प्रमेय, संगीत और मनोविज्ञान की भविष्यवाणियों पर समय-सीमा बीतने के बाद भी अलग-अलग लोग अलग राय दे सकते हैं।

मनोविज्ञान की भविष्यवाणी के बारे में इन 2 लोगों ने जवाब में यह भी लिखा। इस दावे के बारे में कि प्रोग्राम मनोवैज्ञानिक सिद्धांतों के मज़बूत उम्मीदवार हैं, उन्होंने कहा, (अनुवाद)।

शतरंज की कसौटी (मैच में मौजूदा विश्व चैंपियन को हराना) इस साइट ने अस्थायी रूप से तय की है।

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:शुरुआती AI शोधकर्ता बिना आधार बड़ी बातें कहते थे
मूल स्रोत के अनुसार:उस समय भी आलोचना होती थी। भविष्यवाणी करने वालों ने समझाया कि जाँचने योग्य बनाने के लिए समय-सीमा रखी गई थी और जाँच की तारीख (लगभग 1 जनवरी, 1968) भी खुद बताई थी।

081958 · नौसेना का प्रदर्शन

कार्ड का निशान दाईं ओर या बाईं ओर?

जिस दिन अखबार ने बड़ी उम्मीदें लिखीं, उस दिन मशीन ने वास्तव में क्या किया?

जुलाई 1958 में अमेरिकी नौसेना ने वॉशिंगटन में पत्रकारों को एक प्रदर्शन दिखाया। मौसम ब्यूरो (मौसम का सरकारी विभाग) के बड़े IBM 704 कंप्यूटर पर परसेप्ट्रॉन का सिमुलेशन चलाया गया। लगभग 50 कोशिशों के बाद वह कार्ड के निशान का दाईं या बाईं ओर होना पहचानने लगा। विशेष मशीन का निर्माण अभी शुरू नहीं हुआ था।

अगले दिन न्यूयॉर्क टाइम्स की सुर्खी थी, (अनुवाद)। लेख ने बताया कि नौसेना को उम्मीद थी कि यह “भ्रूण” आगे चलकर (अनुवाद) होगा।

दाईं आकृति उस दिन के प्रदर्शन को छोटे रूप में दोहराने वाला उदाहरण है (कार्ड का आकार और निशान इस साइट ने तय किए हैं)। “लगातार 50 कार्ड” दबाने पर वज़नों के नक्शे में ऐसा पैटर्न बनता है जिसमें दायाँ आधा दाईं ओर और बायाँ आधा बाईं ओर वोट देता है। मशीन ने केवल यह सीखा कि कौन-सा खाना किस तरफ वोट देगा। उसे दाएँ और बाएँ शब्दों का अर्थ नहीं मालूम।

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:रोज़ेनब्लाट (Rosenblatt) ने कहा था, “परसेप्ट्रॉन चलेगा, बोलेगा और चेतना रखेगा”
मूल स्रोत के अनुसार:लेख में यह उम्मीद रखने वाली थी। उन्होंने खुद भी कहा था, (अनुवाद)। लेकिन 1961 की रिपोर्ट में उन्होंने अखबारों के रवैये की आलोचना करते हुए उसे (अनुवाद) जैसा बताया।

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

u03_perceptron_cards.py

# u03 パーセプトロン：カードの印は右か左か（1958 年の実演を小さく再現）
#
# どの出来事か：1958 年 7 月、アメリカ海軍が記者に公開した実演（記録 perceptron_navy_demo_1958）。
#   ふつうのコンピュータ IBM 704 の上で、ローゼンブラットのパーセプトロンが、カードの印が右か左かを
#   50 回ほどの試行で識別できるようになった。
# 仕組み：マス目ごとに「重み」があり、印のあるマスの重みを足して、正なら「右」、負なら「左」と判定する。
#   間違えた時だけ、正解の方向に重みを更新する（パーセプトロンの学習規則）。
# 試してみよう：
#   - TRIALS を 20 にすると、まだ誤りが残るか？
#   - MARK を 1 にすると（印が小さいと）、学習に何枚かかるか？
#   - 最後の「重みの地図」は何を表しているか？（コンピュータは「右と左」という言葉を知らない）

import random

random.seed(1958)
SIZE = 10      # カードの大きさ（10×10 のマス目）
MARK = 3       # 印の大きさ（3×3 のマス目）
TRIALS = 60    # 学習のために見せるカードの枚数

def make_card():
    """印を左半分か右半分のどちらかに置いたカードを 1 枚作る。"""
    side = random.choice(["左", "右"])
    if side == "左":
        x0 = random.randint(0, SIZE // 2 - MARK)
    else:
        x0 = random.randint(SIZE // 2, SIZE - MARK)
    y0 = random.randint(0, SIZE - MARK)
    pixels = [0] * (SIZE * SIZE)
    for y in range(y0, y0 + MARK):
        for x in range(x0, x0 + MARK):
            pixels[y * SIZE + x] = 1
    answer = 1 if side == "右" else -1
    return pixels, answer

weights = [0] * (SIZE * SIZE)   # 重みの初期値はすべて 0
bias = 0

def guess(pixels):
    total = bias + sum(w * p for w, p in zip(weights, pixels))
    return 1 if total > 0 else -1

mistakes = []
for trial in range(1, TRIALS + 1):
    pixels, answer = make_card()
    if guess(pixels) != answer:
        # 間違えた時だけ更新する：印のあるマスの重みを、正解の方向に 1 動かす
        for i, p in enumerate(pixels):
            weights[i] += answer * p
        bias += answer
        mistakes.append(trial)

print("間違えたカードの番号:", mistakes)
for start in range(1, TRIALS + 1, 10):
    n = sum(1 for m in mistakes if start <= m < start + 10)
    print(f"  {start:3d}〜{start + 9:3d} 枚目：誤り {n} 回 " + "■" * n)

# 学習後に、新しいテストデータ 200 枚で試す
correct = 0
for _ in range(200):
    pixels, answer = make_card()
    correct += guess(pixels) == answer
print(f"新しいカード 200 枚でテストすると、正解したのは {correct} 枚")

# 重みの可視化（＋は「右」方向、－は「左」方向、・は 0）
print("重みの地図:")
for y in range(SIZE):
    row = ""
    for x in range(SIZE):
        w = weights[y * SIZE + x]
        row += "＋" if w > 0 else ("－" if w < 0 else "・")
    print("  " + row)

091958 · LISP

कोष्ठकों में व्यंजक का रूप बचाएँ

संख्याओं के बजाय प्रतीकों वाले व्यंजकों पर ही गणना कैसे करें?

1958 की शरद ऋतु में मैकार्थी (McCarthy) और मिंस्की (Minsky) ने MIT में शुरू की। उन्होंने कोई प्रस्ताव नहीं लिखा। जब पूछा गया कि क्या चाहिए, तो बताया जाता है कि उन्होंने 1 कमरा, 2 प्रोग्रामर, 1 सचिव और कार्ड में छेद करने की 1 मशीन माँगी। उसी शरद ऋतु में उन्होंने प्रतीकों की सूचियों पर काम करने वाली प्रोग्रामिंग भाषा LISP (लिस्ट प्रोसेसिंग) बनाना शुरू किया।

LISP में (TIMES X (PLUS X A) Y) की तरह कोष्ठकों के भीतर कोष्ठक रखकर व्यंजक लिखे जाते हैं। पहला शब्द बताता है कि क्या करना है और बाकी बताते हैं कि किन चीज़ों पर करना है। मूल काम बहुत थोड़े हैं: पहला तत्व लेना car, बाकी तत्व लेना cdr और शुरुआत में नया तत्व जोड़ना cons, आदि। 1960 के शोधपत्र ने दिखाया कि केवल इनसे, शर्त के अनुसार रास्ता चुनने और खुद को बुलाने वाले फ़ंक्शन से, व्यंजक का अवकलन लिखा जा सकता है।

दाईं आकृति में “X(X+A)Y · शोधपत्र का उदाहरण” चुनें, “1 · 0 को सरल करें (साइट का जोड़ा विकल्प)” से निशान हटाएँ और “X के सापेक्ष अवकलन (DIFF)” दबाएँ। तब शोधपत्र वाला उत्तर पेड़ के रूप में दिखता है। 1 के लिए ONE और 0 के लिए ZERO ज्यों के त्यों रहते हैं। LISP परिवार की भाषाएँ इसके बाद लंबे समय तक AI शोध में प्रमुख रूप से इस्तेमाल हुईं।

d(u·v·w)/dX＝u′·v·w＋u·v′·w＋u·v·w′

′: X के सापेक्ष अवकलज। DIFF इस रूप को कोष्ठकों के भीतर कोष्ठक रखते हुए बनाता है

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

u03_mini_lisp.py

# u03 小さな LISP：かっこの入れ子の式を、式のまま微分する
#
# どの出来事か：1958 年秋から MIT の AI グループが開発したプログラミング言語 LISP（記録 lisp_1958・mit_ai_project_1958）。
#   マッカーシーの 1960 年の論文は、記号式（S 式）を扱う基本操作 car・cdr・cons・atom・eq と、
#   条件分岐、再帰関数だけで、数式の微分を計算する例を示した。
# 仕組み：(TIMES X (PLUS X A) Y) は X(X+A)Y のこと。最初の要素が「何をするか」、残りが「何に」を表す。
#   car はリストの先頭、cdr は先頭を除いた残り、cons は先頭に要素を追加する操作。
#   DIFF（微分）は論文の式をそのまま LISP で書いたもの。MAPLIST は、リストの残りを 1 つずつ関数に渡す。
#   論文と同じく、計算結果の整理は行わない（ONE は 1、ZERO は 0 のこと）。
#   ※ LISP を解釈して実行する部分（eval）は、このサイトが Python で書いた小さな例。
# 試してみよう：
#   - EXPR を (PLUS X (TIMES X X)) に変えてみる（X + X·X の微分）
#   - DIFF に「ZERO をかける項は消す」整理を足すには、どこを変えればよいか

EXPR = "(TIMES X (PLUS X A) Y)"

class Cons:
    def __init__(self, car, cdr):
        self.car, self.cdr = car, cdr

def read(text):
    toks = text.replace("(", " ( ").replace(")", " ) ").split()

def walk(i):
        if toks[i] != "(":
            return (None if toks[i] == "NIL" else toks[i]), i + 1
        items, i = [], i + 1
        while toks[i] != ")":
            x, i = walk(i)
            items.append(x)
        lst = None
        for x in reversed(items):
            lst = Cons(x, lst)
        return lst, i + 1
    return walk(0)[0]

def show(x):
    if x is None:
        return "NIL"
    if isinstance(x, str):
        return x
    parts = []
    while isinstance(x, Cons):
        parts.append(show(x.car))
        x = x.cdr
    return "(" + " ".join(parts) + ")"

BUILTIN = {
    "CAR": lambda x: x.car,
    "CDR": lambda x: x.cdr,
    "CONS": lambda a, b: Cons(a, b),
    "ATOM": lambda x: "T" if not isinstance(x, Cons) else None,
    "EQ": lambda a, b: "T" if (a == b if isinstance(a, str) or a is None else a is b) else None,
    "NULL": lambda x: "T" if x is None else None,
    "NOT": lambda x: "T" if x is None else None,
}
DEFS = {}

def evaluate(e, env):
    if e is None or e == "T":
        return e
    if isinstance(e, str):
        return env[e] if e in env else DEFS.get(e, BUILTIN.get(e))
    head = e.car
    if head == "QUOTE":
        return e.cdr.car
    if head == "COND":
        clause = e.cdr
        while clause is not None:
            if evaluate(clause.car.car, env) is not None:
                return evaluate(clause.car.cdr.car, env)
            clause = clause.cdr
        return None
    if head == "LAMBDA":
        return ("closure", e.cdr.car, e.cdr.cdr.car, env)
    fn = evaluate(head, env)
    args = []
    a = e.cdr
    while a is not None:
        args.append(evaluate(a.car, env))
        a = a.cdr
    if callable(fn):
        return fn(*args)
    _, params, body, fenv = fn
    new = dict(fenv)
    p = params
    for v in args:
        new[p.car] = v
        p = p.cdr
    return evaluate(body, new)

def define(name, text):
    DEFS[name] = evaluate(read(text), {})

define("MAPLIST", "(LAMBDA (X F) (COND ((NULL X) NIL) (T (CONS (F X) (MAPLIST (CDR X) F)))))")
define("DIFF", """(LAMBDA (Y X) (COND
  ((ATOM Y) (COND ((EQ Y X) (QUOTE ONE)) (T (QUOTE ZERO))))
  ((EQ (CAR Y) (QUOTE PLUS)) (CONS (QUOTE PLUS) (MAPLIST (CDR Y) (LAMBDA (Z) (DIFF (CAR Z) X)))))
  ((EQ (CAR Y) (QUOTE TIMES)) (CONS (QUOTE PLUS) (MAPLIST (CDR Y) (LAMBDA (Z)
      (CONS (QUOTE TIMES) (MAPLIST (CDR Y) (LAMBDA (W)
          (COND ((NOT (EQ Z W)) (CAR W)) (T (DIFF (CAR W) X)))))))))))))""")

e = read(EXPR)
print("式           ", show(e))
print("car（先頭）  ", show(evaluate(read("(CAR (QUOTE " + EXPR + "))"), {})))
print("cdr（残り）  ", show(evaluate(read("(CDR (QUOTE " + EXPR + "))"), {})))
print("cons で A を前に", show(evaluate(read("(CONS (QUOTE A) (QUOTE " + EXPR + "))"), {})))
print()
d = evaluate(read("(DIFF (QUOTE " + EXPR + ") (QUOTE X))"), {})
print("X で微分すると")
print("  ", show(d))
print("（1960 年の論文の答えと同じ形：積の微分は、1 つずつ微分した項を足し合わせる）")

101958 · सामान्य समझ

हवाई अड्डे के लिए पहला कदम निकालना

तथ्य वाक्यों में लिखे हों, तो क्या मशीन उनसे कार्रवाई तय कर सकती है?

नवंबर 1958 में ब्रिटेन की राष्ट्रीय भौतिक प्रयोगशाला में नाम का अंतरराष्ट्रीय सम्मेलन हुआ। वहाँ मैकार्थी (McCarthy) ने शीर्षक वाला शोधपत्र प्रस्तुत किया। विचार यह था कि तथ्यों और सलाह को तर्क के सूत्रों में लिखकर उनसे निष्कर्ष निकाला जाए और “... करो” जैसे निष्कर्ष मिलने पर वह काम किया जाए (एडवाइस टेकर)।

शोधपत्र का उदाहरण घर की मेज़ पर बैठे व्यक्ति का हवाई अड्डे तक पहुँचना है। at(I, desk) (मैं मेज़ पर हूँ), at(car, home) (कार घर पर है), walkable(home) (घर में पैदल जा सकते हैं), drivable(county) (काउंटी में कार से जा सकते हैं) जैसी 17 आधार मान्यताओं से बारी-बारी 8 निष्कर्ष निकाले जाते हैं। अंत में do(go(desk, car, walking)), यानी पहले कार तक पैदल जाएँ, निकलता है।

दाईं आकृति में “अगला निष्कर्ष निकालें” दबाएँ। 1 आधार मान्यता हटाने पर योजना नहीं मिलती।

शोधपत्र कहता है कि वह पूरी तरह नहीं बता सकता कि 17 आधार मान्यताओं को कैसे इकट्ठा किया जाए और उनसे निष्कर्ष कैसे निकाले जाएँ। आकृति में निष्कर्ष निकालने का क्रम शोधपत्र के निष्कर्षों के क्रम से मिलाया गया है।

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

u03_advice_taker.py

# u03 アドバイス・テイカー：「空港へ行きたい」から、最初にすることを導く
#
# どの出来事か：1958 年 11 月、イギリスの会議でマッカーシーが出した「常識を持つプログラム」の提案
#   （記録 mtp_symposium_1958・lisp_1958）。事実や助言を文の形で書いておき、そこから結論を導いて、
#   「〜せよ」という結論が出たらそれを実行する。論文の例は「机の前にいる私が、空港へ行く」。
# 仕組み：前提（論文の 17 個のうち、この例に使うもの）を、そのまま Python のデータにした。
#   at(x, y)＝x は y にある。walkable(家)＝家の中は歩ける。drivable(郡)＝郡の中は車で行ける。
#   1. 歩く・車の規則から「この状況なら、この行き方ができる」を作る。
#   2. 「行ったら、そこにいる」と組み合わせて、canachult（その状況で、その行動をすれば、次の状況になる）を作る。
#   3. 2 つの canachult をつないで机から空港までの計画を作り、want（望み）と一致したら、最初の行動を do にする。
#   ※ 論文は、前提の集め方や導き方について、この論文では完全には答えられないと書いている。
#     ここの導き方（順番や候補の作り方）は、このサイトが決めたもの。
# 試してみよう：
#   - FACTS から ("at", "car", "home") を消すと（車が家にないと）、計画は見つかるか
#   - ("drivable", "county") を消すとどうなるか

FACTS = [
    ("at", "I", "desk"), ("at", "desk", "home"), ("at", "car", "home"),
    ("at", "home", "county"), ("at", "airport", "county"),
    ("walkable", "home"), ("drivable", "county"),
]
WANT = ("at", "I", "airport")

# (6) at の推移：at(x,y), at(y,z) → at(x,z)。私（I）は動くので、物の場所だけでつなぐ
at = {(f[1], f[2]) for f in FACTS if f[0] == "at" and f[1] != "I"}
changed = True
while changed:
    changed = False
    for (x, y) in list(at):
        for (y2, z) in list(at):
            if y == y2 and (x, z) not in at:
                at.add((x, z))
                changed = True
places = {p for pair in at for p in pair}
now = next(f[2] for f in FACTS if f[:2] == ("at", "I"))

can = []   # (状況, 行動)
for f in FACTS:
    if f[0] == "walkable":                      # (9)
        x = f[1]
        for y in sorted(places):
            for z in sorted(places):
                if y != z and (y, x) in at and (z, x) in at:
                    can.append((("at", "I", y), ("go", y, z, "walking")))
    if f[0] == "drivable":                      # (10)
        x = f[1]
        for y in sorted(places):
            for z in sorted(places):
                if y != z and (y, x) in at and (z, x) in at and ("car", y) in at:
                    can.append((("at", "I", "car"), ("go", y, z, "driving")))

def after(action):                              # (13) did(go(x,y,z)) → at(I, y)
    return ("at", "I", action[2])

chult = [(s, a, after(a)) for s, a in can]      # (15)

def fmt(t):
    return t[0] + "(" + ", ".join(fmt(x) if isinstance(x, tuple) else x for x in t[1:]) + ")"

plan = None
for s1, a1, r1 in chult:                        # (16) 2 つをつなぐ
    for s2, a2, r2 in chult:
        if r1 == s2 and s1 == ("at", "I", now) and r2 == WANT:
            plan = (s1, a1, r1, a2, r2)
            break
    if plan:
        break

print("前提：", "  ".join(fmt(f) for f in FACTS), "  want(" + fmt(WANT) + ")")
print(f"（at を推移でつなぐと {len(at)} 個。行き方の候補 {len(can)} 個を作った）\n")
if plan:
    s1, a1, r1, a2, r2 = plan
    steps = [
        f"{fmt(s1)} → can({fmt(a1)})",
        f"{fmt(r1)} → can({fmt(a2)})",
        f"did({fmt(a1)}) → {fmt(r1)}",
        f"did({fmt(a2)}) → {fmt(r2)}",
        f"canachult({fmt(s1)}, {fmt(a1)}, {fmt(r1)})",
        f"canachult({fmt(r1)}, {fmt(a2)}, {fmt(r2)})",
        f"canachult({fmt(s1)}, prog({fmt(a1)}, {fmt(a2)}), {fmt(r2)})",
        f"do({fmt(a1)})",
    ]
    for i, s in enumerate(steps, 1):
        print(f"{i}. {s}")
    print("\n→ 最初にすることは、机から車まで歩くこと（論文の 8 つの結論と同じ順）")
else:
    print("机から空港までの計画が見つからない。どの前提が足りないか考えてみよう")

111958 · पैटर्न पहचान

दानवों की आवाज़ों से अक्षर पहचानना

क्या अक्षर पहचानने की व्यवस्था को बहुत से छोटे हिस्सों में बाँटा जा सकता है?

उसी सम्मेलन में सेल्फ्रिज (Selfridge) ने नाम की व्यवस्था प्रस्तुत की (इसका अर्थ है वह जगह जहाँ सभी दानव जुटते हैं)। सबसे नीचे के डेटा दानव अक्षर का कोई हिस्सा (क्षैतिज रेखा, खड़ी रेखा, गोलाई आदि) ढूँढ़ते हैं। वह हिस्सा मिलने का भरोसा जितना अधिक हो, उतनी ज़ोर से आवाज़ लगाते हैं। ऊपर के पहचान दानव अपने अक्षर से मेल खाने वाली आवाज़ें इकट्ठा करते हैं और खुद आवाज़ लगाते हैं। सबसे ऊपर निर्णय दानव सबसे तेज़ आवाज़ वाले अक्षर को उत्तर बनाता है।

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

विशेषताएँ पहचानकर, वज़न लगाकर उन्हें जोड़ने की बनावट परसेप्ट्रॉन और बाद के न्यूरल नेटवर्क के ही तरीके पर आधारित है।

पहचान दानव k की आवाज़ ＝Σ_i आवाज़ का स्तर_k,i × डेटा दानव i की आवाज़

आवाज़ का स्तर_k,i: दानव k का दानव i की आवाज़ सुनने का वज़न (सीखने वाला हिस्सा)
उत्तर: सबसे तेज़ आवाज़ वाला k

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

u03_pandemonium.py

# u03 パンデモニウム：小さな悪魔たちの叫び声で、文字を識別する
#
# どの出来事か：1958年11月、イギリスの会議でセルフリッジが発表した「パンデモニウム」（記録 mtp_symposium_1958）。
#   最下層の「データの悪魔」は、文字の特徴（横棒・縦棒など）を探し、見つかった確かさに応じた大きさの声で叫ぶ。
#   中間の「認識の悪魔」は、自分の文字に合う叫び声の組み合わせを聞いて叫び、最上部の「決める悪魔」が、
#   いちばん大きな声の文字を答えにする。メガホンの音量は外部から少しずつ調整し、
#   成績が最も上がる変更を選ぶ（山登り法）。※説明は Nilsson（2010）による。
#   ここでは成績の点に「全部の声のうち、正しい字の声がしめる割合」を使う（このサイトの決め方）。
# 仕組み：5×5の文字（このサイトが作った例の A・E・L・O・T）に、ノイズ（マスの白黒反転）を加えて見せる。
#   データの悪魔 8 匹（7 匹が文字の部分を探し、1 匹はいつも同じ大きさの声）→ 認識の悪魔 5 匹（文字ごと）→ 決める悪魔。
#   音量の初期値はすべて 0。
# 試してみよう：
#   - NOISE を 0.2 にすると、学習後の成績はどれだけ下がるか
#   - データの悪魔を 1 匹（たとえば「まん中の縦棒」）消すと、どの文字を間違えやすくなるか

import math
import random

random.seed(1958)
NOISE = 0.08      # 1マスの白黒が反転する割合
ROUNDS = 60       # 音量を調整する最大反復回数
STEP = 1.0        # 1回の調整で音量を変更する幅

LETTERS = {
    "A": [".###.", "#...#", "#####", "#...#", "#...#"],
    "E": ["#####", "#....", "####.", "#....", "#####"],
    "L": ["#....", "#....", "#....", "#....", "#####"],
    "O": [".###.", "#...#", "#...#", "#...#", ".###."],
    "T": ["#####", "..#..", "..#..", "..#..", "..#.."],
}
DEMONS = ["上の横棒", "まん中の横棒", "下の横棒", "左の縦棒", "右の縦棒", "まん中の縦棒", "白い角", "いつも"]

def shouts(img):
    """データの悪魔たちの声の大きさ（0〜1）。img は 5×5 の 0/1 配列。"""
    row = lambda r: sum(img[r]) / 5
    col = lambda c: sum(img[r][c] for r in range(5)) / 5
    return [row(0), row(2), row(4), col(0), col(4),
            sum(img[r][2] for r in range(1, 5)) / 4,
            sum(1 - img[r][c] for r, c in ((0, 0), (0, 4), (4, 0), (4, 4))) / 4,
            1.0]   # 「いつも」＝常に一定の声で叫ぶ悪魔（文字ごとの基準値）

def noisy(letter):
    return [[(1 if ch == "#" else 0) ^ (random.random() < NOISE) for ch in rowtxt] for rowtxt in LETTERS[letter]]

def decide(vol, s):
    loud = {k: sum(v * x for v, x in zip(vol[k], s)) for k in LETTERS}
    return max(loud, key=loud.get), loud

def score(vol, data):
    return sum(decide(vol, s)[0] == k for k, s in data) / len(data)

def grade(vol, data):
    """成績の点：すべての声のうち、正しい文字の悪魔の声が占める割合（対数）の平均。0 に近いほどよい。"""
    total = 0
    for k, s in data:
        _, loud = decide(vol, s)
        top = max(loud.values())
        total += (loud[k] - top) - math.log(sum(math.exp(v - top) for v in loud.values()))
    return total / len(data)

train = [(k, shouts(noisy(k))) for k in LETTERS for _ in range(8)]
test = [(k, shouts(noisy(k))) for k in LETTERS for _ in range(40)]
vol = {k: [0.0 for _ in DEMONS] for k in LETTERS}   # 音量の初期値はすべて 0（どの悪魔の声も聞かない）

print(f"初め：訓練データで {score(vol, train):.0%}、テストデータで {score(vol, test):.0%}")
for r in range(1, ROUNDS + 1):
    best, best_s = None, grade(vol, train)
    for k in LETTERS:                       # 各音量を少し増減させてすべて試す
        for i in range(len(DEMONS)):
            for d in (STEP, -STEP):
                vol[k][i] += d
                s = grade(vol, train)
                vol[k][i] -= d
                if s > best_s:
                    best, best_s = (k, i, d), s
    if best is None:
        print(f"{r:2d} 回目：どの変更でもスコアが上がらないため終了（山の頂上に到達）")
        break
    k, i, d = best
    vol[k][i] += d
    if r <= 3 or r % 15 == 0:
        print(f"{r:2d} 回目：「{k}」の悪魔が「{DEMONS[i]}」を聞く音量を{'上げ' if d > 0 else '下げ'}る → 点 {best_s:.2f}、訓練データで {score(vol, train):.0%} 正解")

print(f"\n学習後：テストデータ（{len(test)} 個）を {score(vol, test):.0%} 正しく識別")
k, s = test[3]
ans, loud = decide(vol, s)
print(f"\n例：本当は「{k}」の文字 → データの悪魔の声 " + " ".join(f"{d}{x:.1f}" for d, x in zip(DEMONS, s)))
print("   認識の悪魔の声 " + "  ".join(f"{c}:{v:+.1f}" for c, v in loud.items()) + f" → 決める悪魔の答え「{ans}」")

121959 · GPS

लक्ष्य से घटाने वाली चाल चुनें

क्या किसी भी समस्या के लिए काम करने वाला हल करने का तरीका बनाया जा सकता है?

न्यूवेल (Newell), शॉ (Shaw) और साइमन (Simon) ने लॉजिक थिओरिस्ट के आधार पर बनाया। उन्होंने जून 1959 में पेरिस के सम्मेलन के लिए पहले से जारी रिपोर्ट में इसे प्रस्तुत किया (रिपोर्ट की तारीख 30 दिसंबर, 1958 है)। इसे सामान्य इसलिए कहा गया कि समस्या के विषय (तर्क, बीजगणित, त्रिकोणमिति के सूत्र आदि) और हल करने के तरीके को अलग-अलग बनाया गया था।

इस तरीके के केंद्र में लक्ष्य और साधन का विश्लेषण है। वर्तमान स्थिति और लक्ष्य की तुलना करके अंतर खोजें और उस अंतर को घटाने वाली चाल चुनें। यदि चाल चलने की शर्तें पूरी न हों, तो उन्हें पूरा करना नया छोटा लक्ष्य बन जाता है। इस तरह लक्ष्यों के भीतर लक्ष्य बनते हैं और एक ही प्रक्रिया कई स्तरों पर दोहराई जाती है।

दाईं आकृति की शुरुआती समस्या इस साइट का बनाया उदाहरण है: मक्खन वाला टोस्ट बनाना। कौन-सी चाल कौन-सा अंतर घटाती है, इसकी तालिका बदल दें, तो यही हल करने का तरीका दूसरी समस्या पर भी काम करता है।

रिपोर्ट का एक उद्देश्य यह भी था कि प्रोग्राम का व्यवहार उन रिकॉर्ड के करीब लाया जाए जिनमें विश्वविद्यालय के छात्र तर्क की समस्याएँ हल करते समय अपने विचार ज़ोर से बोल रहे थे। रिपोर्ट के उदाहरण प्रतीकात्मक तर्क, शुरुआती बीजगणित और त्रिकोणमिति के सूत्र थे।

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

u03_gps_means_ends.py

# u03 GPS の「目的と手段の分析」：現在と目標の「ちがい」を見つけ、それを小さくする操作を選ぶ
#
# どの出来事か：1958 年 12 月 30 日付の報告、ニューウェル、ショー、サイモンの GPS（一般問題解決器。記録 gps_1959）。
#   ロジック・セオリストから生まれ、「問題の中身」（論理・代数・三角の公式 など）と「解き方」を分けて作った。
#   解き方の中心が「目的と手段の分析」：現在の状態と目標を比較して違いを見つけ、違いを減らす操作を選ぶ。
#   操作が使えない時は、「その手を使える形にする」ことを新しい小さな目標にする（目標の中に目標ができる）。
# 仕組み：問題の内容は、このサイトが作った例「朝ごはんのバタートーストを作る」。
#   操作ごとに「使う条件」「できること」を書いた表（問題の中身）と、解き方（transform・apply）を分けてある。
#   表を取りかえれば、同じ解き方がほかの問題にも使える。これが GPS の「一般」の意味。
# 試してみよう：
#   - START に "冷蔵庫が開いている" を足すと、操作の数はどう変わるか
#   - OPERATORS を別の問題（たとえば、学校へ行く）に書きかえて、同じ transform で解いてみる

OPERATORS = [   # (操作の名前, 使う条件, できること, なくなること)
    ("冷蔵庫を開ける", [], ["冷蔵庫が開いている"], []),
    ("バターを出す", ["冷蔵庫が開いている"], ["バターが出ている"], []),
    ("パンの袋を開ける", [], ["袋が開いている"], []),
    ("パンを出す", ["袋が開いている"], ["パンを持っている"], []),
    ("パンをトースターに入れる", ["パンを持っている"], ["パンがトースターの中"], ["パンを持っている"]),
    ("パンを焼く", ["パンがトースターの中"], ["パンが焼けている"], []),
    ("バターをぬる", ["パンが焼けている", "バターが出ている"], ["バタートーストができた"], []),
]
START = []
GOAL = ["バタートーストができた"]
steps = []

def transform(state, goal, depth=0):
    """現在の state を、goal を満たす状態にする（GPS の目標の型 1）。"""
    pad = "  " * depth
    for want in goal:
        if want in state:
            continue
        print(f"{pad}ちがい：「{want}」がまだ無い")
        op = next((o for o in OPERATORS if want in o[2]), None)   # 違いを減らす操作を表から探す
        if op is None:
            print(f"{pad}  → 減らす操作が無い。あきらめる")
            return None
        print(f"{pad}  → 減らす操作：「{op[0]}」")
        state = apply(state, op, depth + 1)
        if state is None:
            return None
    return state

def apply(state, op, depth):
    """操作 op を適用する（GPS の目標の型 2）。条件が足りなければ、まずそれを目標にする。"""
    name, need, add, remove = op
    missing = [c for c in need if c not in state]
    if missing:
        print("  " * depth + f"「{name}」を使う条件が足りない → 小さな目標：" + "、".join(missing))
        state = transform(state, missing, depth + 1)
        if state is None:
            return None
    steps.append(name)
    print("  " * depth + f"★ 操作 {len(steps)}：{name}")
    return [s for s in state if s not in remove] + [a for a in add if a not in state]

print("目標：", "、".join(GOAL), "\n")
final = transform(list(START), GOAL)
print("\nできあがり：" if final else "\n解けなかった", "→".join(steps))
print(f"使った操作の数 {len(steps)}")

131959 · जापान

मुझे संगीत पसंद है

उस समय जापान में कैसी “सोचने वाली मशीनें” बन रही थीं?

1958 की गर्मियों के आसपास जापान की इलेक्ट्रोटेक्निकल लैबोरेटरी में “यामातो”, अंग्रेज़ी से जापानी अनुवाद करने वाला विशेष कंप्यूटर, बनाने की योजना शुरू हुई। उनके पास शब्दकोश रखने के लिए बड़ी मेमोरी वाला कंप्यूटर नहीं था, इसलिए ट्रांज़िस्टर कंप्यूटर ETL Mark IV के सर्किट इस्तेमाल करके विशेष मशीन बनाई गई। बजट 6,000,000 येन था और मेमोरी 820,000 बिट का चुंबकीय ड्रम थी। फरवरी 1959 में I like music के छेद वाली कागज़ी टेप डालने पर इसने (अनुवाद) छापा।

जापानी इनपुट की कठिनाइयों (कांजी लिपि और शब्दों की सीमाएँ) से बचने के लिए अंग्रेज़ी से जापानी अनुवाद चुना गया। फिर भी क्रिया को वाक्य के अंत में पहुँचाना, पूर्वसर्गों को खिसकाना और ga तथा o जैसे जापानी व्याकरणिक कण जोड़ना ज़रूरी था। सर्वनाम I को ware, you को nare और he को kare बनाया गया। दाईं आकृति में अनुवाद की प्रक्रिया एक-एक चरण आगे बढ़ाकर देखें।

योजना का निर्देश देने वाले हिरोशी वाडा (Hiroshi Wada) ने याद किया कि पहला अनुवाद छपना शुरू होने तक के 13 सेकंड उन्हें बहुत लंबे लगे थे। परिणाम जून 1959 में पेरिस के पहले अंतरराष्ट्रीय सूचना प्रसंस्करण सम्मेलन में प्रस्तुत किए गए।

आकृति का शब्दकोश और नियम, सर्वनामों के अनुवाद को छोड़कर, इस साइट के बनाए उदाहरण हैं। पेरिस में दिखाए गए I have some eggs in my hand. को यामातो ने कैसे अनुवाद किया, यह स्रोतों में नहीं लिखा है।

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

u03_yamato_translate.py

# u03 「やまと」のように訳す：英文を、辞書と並べ替えの規則でカタカナの日本語に
#
# どの出来事か：1959年、電気試験所の英日翻訳専用機「やまと」（記録 etl_yamato_mt_1959）。
#   最初に訳した「I like music.」は「ワレガ オンガクヲ コノム」。訳を打ち始めるまで13秒かかった。
#   和田弘の回想によると、英文和訳には動詞を文末に置くこと、前置詞を動かすこと、
#   格助詞（ガ・ヲなど）を補うことなどが必要だった。代名詞 I, you, he, she, it, this, that, who は
#   ワレ、ナレ、カレ、サレ、ソレ、コレ、アレ、タレにした（本人は「ヤマトコトバ」と呼んだ）。
# 仕組み：1語ずつ辞書を引く → 主語・動詞・目的語・前置詞のまとまりに分ける → 日本語の順に並べ替える →
#   助詞を補ってカタカナで出力する。辞書と規則は、代名詞を除き、このサイトが作った小さな例。
#   2番目の文は1959年6月のパリの会議で示された文。やまとの実際の訳は資料にないため、ここの訳はこのサイトの規則による。
# 試してみよう：
#   - SENTENCES に "She likes the moon." を足す（辞書に moon を足す必要がある）
#   - 「I like music very much.」のような文は、この規則でどうなるか

PRONOUN = {"i": "ワレ", "you": "ナレ", "he": "カレ", "she": "サレ", "it": "ソレ", "this": "コレ", "that": "アレ", "who": "タレ"}
POSSESSIVE = {"my": "ワレノ", "your": "ナレノ", "his": "カレノ", "her": "サレノ"}
NOUN = {"music": "オンガク", "egg": "タマゴ", "hand": "テ", "book": "ホン", "moon": "ツキ"}
VERB = {"like": "コノム", "have": "モツ", "read": "ヨム", "see": "ミル"}
PREP = {"in": "ニ", "on": "ノウエニ", "with": "ト"}
DET = {"some": "イクツカノ", "the": "", "a": ""}
SENTENCES = ["I like music.", "I have some eggs in my hand.", "He likes music.", "You read a book."]

def base(word):
    """名詞・動詞の語尾（-s）を取り除き、辞書の形に戻す。"""
    if word in NOUN or word in VERB:
        return word
    if word.endswith("s") and (word[:-1] in NOUN or word[:-1] in VERB):
        return word[:-1]
    return word

def translate(sentence, show=True):
    words = [base(w) for w in sentence.lower().rstrip(".").split()]
    if show:
        print("1. 単語に分けて、語尾を取り除く：", words)
    subj, verb = words[0], words[1]
    rest = words[2:]
    obj, phrases, cur = [], [], None
    for w in rest:                                   # 目的語と、前置詞のまとまりに分ける
        if w in PREP:
            cur = [w]
            phrases.append(cur)
        elif cur is not None:
            cur.append(w)
        else:
            obj.append(w)
    if show:
        print(f"2. 文の役割を決める：主語 {subj} ／ 動詞 {verb} ／ 目的語 {obj} ／ 前置詞のまとまり {phrases}")

def noun_phrase(ws):
        parts = [DET.get(w, "") + POSSESSIVE.get(w, "") + NOUN.get(w, "") + PRONOUN.get(w, "") for w in ws]
        return " ".join(p for p in parts if p)
    jp = [PRONOUN.get(subj, NOUN.get(subj, subj)) + "ガ"]            # 主語＋ガ
    for p in phrases:                                                # 前置詞は名詞の後ろへ
        jp.append(noun_phrase(p[1:]) + PREP[p[0]])
    if obj:
        jp.append(noun_phrase(obj) + "ヲ")                            # 目的語＋ヲ
    jp.append(VERB.get(verb, verb))                                  # 動詞は文末へ
    if show:
        print("3. 日本語の語順に並べて、助詞を補う：", jp)
    return " ".join(jp)

for s in SENTENCES:
    print(f"【{s}】")
    print("   → " + translate(s) + "\n")
print("（やまとは、最初の訳を打ち始めるまで 13 秒かかった。この Python は 1 秒もかからない）")

141959 · मशीन लर्निंग

अंक देने का तरीका खुद सुधारना

क्या प्रोग्राम उसे लिखने वाले व्यक्ति से बेहतर खिलाड़ी बन सकता है?

IBM के सैमुअल (Samuel) ने चेकर्स (8×8 के बोर्ड पर मोहरों के ऊपर से कूदकर उन्हें लेने का खेल) का उपयोग करके कंप्यूटर के अनुभव से सीखने पर शोध जारी रखा। सीखने वाला संस्करण 24 फरवरी, 1956 को टेलीविज़न पर दिखाया गया। उनके 1959 के शोधपत्र के सार में लिखा है कि 8〜10 घंटे खेलने से प्रोग्राम उसे लिखने वाले व्यक्ति से बेहतर चालें चलने लगता है।

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

हल करने का पूरा तरीका लिखने के बजाय उदाहरणों और अनुभव से सिखाना मशीन लर्निंग कहलाता है।

w ← w＋η(ऊपर लाया गया स्कोर − आगे देखने से पहले का स्कोर) × विशेषता

w: वज़न
η: सुधार का आकार
स्कोर: विशेषता × वज़न का जोड़ (आकृति के आँकड़े इस साइट के बनाए उदाहरण हैं)

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

u03_samuel_weights.py

# u03 サミュエルの学習法：先を読んだ評価値に近づくように、重みを自分で直す
#
# どの出来事か：1959年、IBMのサミュエルの論文「チェッカーのゲームを使った、機械が学ぶことの研究」（記録 samuel_checkers_1959）。
#   盤面から駒の数の差・動ける手の多さ・中央の支配など「特徴」の数値を集め、重みをかけて足し合わせて局面の評価値にした。
#   数手先まで読み、自分は最大、相手は最小を選ぶミニマックス法で手を決めた。
#   学習方法の 1 つは、先読み前の評価値が先読み後の評価値に近づくように重みを直すこと（説明は Nilsson 2010 による）。
# 仕組み：チェッカーは大きいので、三目並べで同じ仕組みを動かす（ゲームと特徴はこのサイトが作った例）。
#   特徴：自分があと1つでそろう列・相手があと1つでそろう列・自分だけが置いている列・中央・角。
#   自己対戦しながら、1手ごとに「読む前の点数」を「2 手先まで読んだ点数」に少し近づける。
# 試してみよう：
#   - GAMES を 0 にして学習させないと、ランダムに打つ相手への成績はどうなるか
#   - RATE を大きくすると、重みはどう変化するか

import random

random.seed(1959)
GAMES = 300       # 学習用の自己対戦の回数
RATE = 0.01       # 1回に重みを更新する大きさ（学習率）
LINES = [(0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6)]
NAMES = ["あと 1 つでそろう（自分）", "あと 1 つでそろう（相手）", "自分だけの列", "まん中", "角"]
w = [0.0] * len(NAMES)      # 重みの初期値（最初はどの特徴も重視しない）

def winner(b):
    for i, j, k in LINES:
        if b[i] != "." and b[i] == b[j] == b[k]:
            return b[i]
    return None

def features(b, me):
    you = "O" if me == "X" else "X"
    f = [0, 0, 0, 0, 0]
    for line in LINES:
        cells = [b[i] for i in line]
        if cells.count(me) == 2 and cells.count(".") == 1:
            f[0] += 1
        if cells.count(you) == 2 and cells.count(".") == 1:
            f[1] += 1
        if cells.count(me) == 1 and cells.count(".") == 2:
            f[2] += 1
    f[3] = (b[4] == me) - (b[4] == you)
    f[4] = sum((b[i] == me) - (b[i] == you) for i in (0, 2, 6, 8))
    return f

def static(b, me):
    """先読み前の評価値：特徴 × 重み の合計。勝敗が決まっていれば ±10。"""
    win = winner(b)
    if win:
        return 10 if win == me else -10
    if "." not in b:
        return 0
    return sum(wi * fi for wi, fi in zip(w, features(b, me)))

def moves(b):
    return [i for i, c in enumerate(b) if c == "."]

def search(b, me, turn, depth):
    """ミニマックス法：自分の番は最大、相手の番は最小を選んで、評価値を上の局面へ運ぶ。"""
    if depth == 0 or winner(b) or "." not in b:
        return static(b, me), None
    best = None
    for m in moves(b):
        nb = b[:m] + turn + b[m + 1:]
        v, _ = search(nb, me, "O" if turn == "X" else "X", depth - 1)
        if best is None or (v > best[0] if turn == me else v < best[0]):
            best = (v, m)
    return best

def play(first, second, learn=False):
    b, turn = "." * 9, "X"
    players = {"X": first, "O": second}
    while not winner(b) and "." in b:
        if players[turn] == "random":
            m = random.choice(moves(b))
        else:
            v, m = search(b, turn, turn, 2)
            if learn:                            # 先読み前の評価値を、先読み後の評価値に近づける
                f, s = features(b, turn), static(b, turn)
                for i in range(len(w)):
                    w[i] += RATE * (v - s) * f[i]
        b = b[:m] + turn + b[m + 1:]
        turn = "O" if turn == "X" else "X"
    return winner(b)

def test(n=200):
    r = {"勝ち": 0, "引き分け": 0, "負け": 0}
    for g in range(n):
        me = "X" if g % 2 == 0 else "O"
        res = play("ai", "random") if me == "X" else play("random", "ai")
        r["勝ち" if res == me else "負け" if res else "引き分け"] += 1
    return r

random.seed(1)
print("学習前：ランダムに打つ相手と 200 回対戦 →", test())
random.seed(1959)
for g in range(GAMES):
    play("ai", "ai", learn=True)
print("重み：", "  ".join(f"{n} {x:+.2f}" for n, x in zip(NAMES, w)))
random.seed(1)
print(f"自己対戦を {GAMES} 回行って学習した後 →", test())

151960 · Mark I

बेतरतीब तार, मोटर से घूमते नॉब

सीखने वाली मशीन को प्रोग्राम के बजाय असली मशीन के रूप में बनाएँ तो?

23 जून, 1960 को परसेप्ट्रॉन की विशेष मशीन Mark I पहली बार सार्वजनिक रूप से दिखाई गई। वज़नों को मोटर से घूमने वाले (पोटेंशियोमीटर) से बदला जाता था और तार एक बड़े पैच पैनल से जोड़े जाते थे। 1961 की रिपोर्ट के अनुसार, इसमें 512 A कोशिकाएँ और उत्तर देने वाली 8 R कोशिकाएँ थीं। वाइटमैन (Wightman) और मार्टिन (Martin) ने इसे जोड़ा और हे (Hay) ने प्रयोग किए।

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

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

रिपोर्ट में ऐसा प्रयोग भी दर्ज है जिसमें शिक्षक ने जानबूझकर 30% बार गलत उत्तर दिए, फिर भी मशीन E और X को 100% सही पहचानना सीख गई (यह गलती सुधारने वाली सीखने की विधि से अलग तरीका था)। Mark I अब स्मिथसोनियन संस्थान में है।

हर 1 चक्र (16 पट्टियाँ) में गलतियों की संख्या

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

u03_mark1_alpha.py

# u03 Mark I の構造：ランダムな配線（A 細胞）と、学習するつまみ（重み）
#
# どの出来事か：1960 年に公開されたローゼンブラットのパーセプトロン Mark I（記録 perceptron_1957）。
#   ローゼンブラットの 1961 年の報告によると、Mark I は A 細胞 512 個・出力の R 細胞 8 個をもち、
#   重みはモーターで回すつまみ（ポテンショメーター）、配線は大きな差し替え盤だった。
#   網膜（S）→ A 細胞 → R 細胞 と並ぶ構造で、網膜から A 細胞への配線はランダムに選んだ点につなぐだけで学習しない。
#   学習するのは A 細胞から R 細胞への重みだけで、間違えた時だけ修正する（誤り訂正学習）。
# 仕組み：同じ報告の実験 1 にならって、横の棒と縦の棒を識別させる（網膜はここでは 8×8 の小さなもの。
#   上と下、左と右がつながった「輪」になっていて、棒はどの位置にも置ける）。
#   A 細胞が 0 個（網膜を R 細胞に直接つなぐ）だと、何回学習しても誤りが残る。
#   横の棒も縦の棒も光る点の数は同じで、どの重みでも「全部の横の棒の点数の平均」と「全部の縦の棒の点数の平均」が
#   同じになってしまうからだ。ランダムな A 細胞を挟むと、識別できるようになる。
# 試してみよう：
#   - LINKS（A 細胞 1 個が見る点の数）を 1 にすると、どうなるか
#   - A 細胞の数を 512（Mark I と同じ）にしてみる

import random

random.seed(1960)
N = 8          # 網膜は 8×8
WIDTH = 2      # 棒の太さ
LINKS = 4      # A 細胞 1 個が見る網膜の点の数
SWEEPS = 60    # 全部の棒を見せる回数（いちばん多くて）

def bars():
    out = []
    for p in range(N):
        h = [[1 if (r - p) % N < WIDTH else 0 for c in range(N)] for r in range(N)]
        v = [[1 if (c - p) % N < WIDTH else 0 for c in range(N)] for r in range(N)]
        out += [(h, 1), (v, -1)]          # 横の棒＝+1、縦の棒＝-1
    return out

def make_a_units(n):
    units = []
    for _ in range(n):
        pts = [(random.randrange(N), random.randrange(N), random.choice((1, -1))) for _ in range(LINKS)]
        units.append(pts)                 # ランダムな点と、+（光ると上げる）か -（光ると下げる）。＋－の決め方はこのサイトが決めたもの
    return units

def a_layer(img, units):
    if not units:                          # A 細胞なし：網膜の点をそのまま使う
        return [x for row in img for x in row]
    return [1 if sum(s * img[r][c] for r, c, s in u) >= 1 else 0 for u in units]

def train(n_units):
    units = make_a_units(n_units)
    data = [(a_layer(img, units), t) for img, t in bars()]
    w = [0] * len(data[0][0])
    b = 0
    for sweep in range(1, SWEEPS + 1):
        mistakes = 0
        for x, t in data:
            y = 1 if sum(wi * xi for wi, xi in zip(w, x)) + b > 0 else -1
            if y != t:                     # 間違えた時だけ、つまみ（重み）を回す
                mistakes += 1
                w = [wi + t * xi for wi, xi in zip(w, x)]
                b += t
        if mistakes == 0:
            return sweep, 0
    return SWEEPS, mistakes

print(f"横の棒 {N} 本と縦の棒 {N} 本（8×8 の輪の網膜）を識別する\n")
for n in (0, 5, 20, 80, 320):
    sweeps, left = train(n)
    name = "A 細胞なし（網膜を直接つなぐ）" if n == 0 else f"ランダムな A 細胞 {n} 個"
    if left == 0:
        print(f"  {name:<22} → {sweeps} 回目で、誤りが 0 になった")
    else:
        print(f"  {name:<22} → {sweeps} 回学習しても、誤りが {left} 個残る " + "■" * left)

161960 · मनुष्य और कंप्यूटर

1 कंप्यूटर का समय सबमें बाँटना

मशीन से पूरा सोचने का काम कराने से पहले, मनुष्य और कंप्यूटर साथ कैसे काम करें?

मार्च 1960 में लिक्लाइडर (Licklider) ने शोधपत्र प्रकाशित किया। अंजीर के पेड़ और उसका पराग ले जाने वाले कीट के एक-दूसरे की मदद करने की तरह, उन्होंने ऐसी साझेदारी की कल्पना की जिसमें मनुष्य लक्ष्य तय करे, परिकल्पनाएँ बनाए और कसौटियाँ तय करके मूल्यांकन करे, जबकि कंप्यूटर नियमित काम सँभाले। उन्होंने 1957 के वसंत और गर्मियों में अपना काम दर्ज किया। उनके अनुसार, सोचने के समय का लगभग 85% सोचने की तैयारी (खोजना, गणना करना, ग्राफ बनाना आदि) में चला जाता था।

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

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

171976 · जाँच

4 रंग: मनुष्य का तर्क, कंप्यूटर का श्रम

कब कह सकते हैं कि कंप्यूटर ने किसी प्रमेय को सिद्ध किया?

कंप्यूटर के बारे में (अनुवाद) की भविष्यवाणी के 10 वर्षों के भीतर ऐसी कोई घटना दर्ज नहीं मिलती जिसके बारे में यह कहा जा सके। 1976 में अपेल (Appel) और हाकेन (Haken) ने सिद्ध किया (लगभग 1852 से चली आ रही समस्या कि हर नक्शे को 4 रंगों से ऐसे रंगा जा सकता है कि पड़ोसियों के रंग अलग हों)। लेकिन प्रमाण का तर्क और आकृतियों को वर्गीकृत करने की प्रक्रिया मनुष्यों ने बनाई। कंप्यूटर का काम लगभग 2000 आकृतियों को 1-1 करके जाँचना था।

दाईं आकृति में कंप्यूटर इस साइट के बनाए उदाहरण के नक्शे को रंगता है। वह देशों को 1-1 करके रंगता है और जब कोई रंग नहीं बचता, तो 1 कदम पीछे जाता है (बैकट्रैकिंग)। A · B · C · D सभी एक-दूसरे के पड़ोसी हैं, इसलिए कितनी भी कोशिश करें, 3 रंगों से नहीं रंग सकते। 1 नक्शे को रंगने के लिए खोज की गणना और सभी नक्शों के लिए सही प्रमेय का प्रमाण अलग बातें हैं।

अक्टूबर 1996 में प्रमाण खोजने वाले प्रोग्राम EQP ने का प्रमाण लगभग 8 दिनों में अपने आप खोज लिया। यह समस्या 1930 के दशक से अनसुलझी थी। दोनों मामलों में समस्या स्वयं मनुष्यों ने पहले से प्रस्तुत की थी।

जो आपको लगता है कि आप जानते हैंआम तौर पर कही जाने वाली बात:1976 में कंप्यूटर ने चार रंग प्रमेय सिद्ध किया
मूल स्रोत के अनुसार:घोषणा के मूल पाठ के अनुसार, वर्गीकरण की प्रक्रिया मनुष्यों ने हाथ से बनाई थी और कंप्यूटर का काम बहुत सी आकृतियों को 1-1 करके जाँचना था।

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

u03_four_colors.py

# u03 4色で塗り分ける：隣同士が同じ色にならないように、試しては戻る
#
# どの出来事か：1957 年の予言「10 年以内に、計算機が大事な新しい数学の定理を見つけて証明する」の、その後
#   （記録 simon_newell_theorem_1958）。1976年、アペルとハーケンは四色定理（どんな地図も4色で塗り分けられる）を
#   証明した。証明の筋道と形の分類手順は人間が作り、コンピュータは2000近くの形を1つずつ調べる役だった。
# 仕組み：このサイトが作った例の地図（国A〜J）を、隣同士が同じ色にならないように塗る。
#   国を1つずつ順に塗り、塗れる色がなくなったら、1つ前の国に戻って色を変える（バックトラック法）。
#   これは1枚の地図を塗る計算で、定理の証明（すべての地図について成り立つこと）とは別のものである。
# 試してみよう：
#   - COLORS を 3 にすると、この地図は塗れるか（A・B・C・D の 4 つの国は、互いにすべて隣り合っている）
#   - SMART を False にすると（隣が多い国から先に塗る工夫をやめると）、試す回数はどう変わるか。
#     3色の時と4色の時で比べる

COLORS = 4
SMART = True
MAP = [   # このサイトが作った例（1文字が1マス。同じ文字が1つの国）
    "BBBCCCC",
    "BBAACCC",
    "BDAACFF",
    "DDDDDFF",
    "EEGGGII",
    "EHHJJII",
]
NAMES = ["赤", "青", "黄", "緑", "紫"]

NEIGHBORS = {}   # マスが上下・左右で接している国同士が「となり」
for r, row in enumerate(MAP):
    for c, a in enumerate(row):
        NEIGHBORS.setdefault(a, set())
        for rr, cc in ((r + 1, c), (r, c + 1)):
            if rr < len(MAP) and cc < len(row) and MAP[rr][cc] != a:
                b = MAP[rr][cc]
                NEIGHBORS[a].add(b)
                NEIGHBORS.setdefault(b, set()).add(a)

order = sorted(NEIGHBORS, key=lambda c: (-len(NEIGHBORS[c]), c)) if SMART else sorted(NEIGHBORS)
color = {}
tries = backs = 0

def paint(i):
    global tries, backs
    if i == len(order):
        return True
    country = order[i]
    for k in range(COLORS):
        tries += 1
        if all(color.get(n) != k for n in NEIGHBORS[country]):
            color[country] = k
            if paint(i + 1):
                return True
            del color[country]
    backs += 1          # どの色もだめ → 1つ前に戻る
    return False

ok = paint(0)
print(f"{COLORS} 色で、塗る順番 {' → '.join(order)}")
if ok:
    print("塗れた：", "  ".join(f"{c}={NAMES[color[c]]}" for c in sorted(color)))
else:
    print("塗れなかった")
print(f"色を試した回数 {tries}、戻った回数 {backs}")
bad = [(a, b) for a in sorted(NEIGHBORS) for b in sorted(NEIGHBORS[a]) if a < b and ok and color[a] == color[b]]
print("隣同士で同じ色：", bad if bad else "なし")
if ok:
    print("\n地図（色の1文字目）")
    for row in MAP:
        print("  " + "".join(NAMES[color[a]][0] for a in row))

“कृत्रिम बुद्धिमत्ता” नाम वाला गर्मियों का प्रस्ताव

गर्मियों की कार्यशाला कैसी थी?

हर संभव प्रमाण बनाते जाएँ तो?

उत्तर से उल्टी दिशा में खोज

गलती पर ही वज़न सुधारें

“10 वर्षों के भीतर” 4 भविष्यवाणियाँ

जाँच की तारीख खुद लिखी

कार्ड का निशान दाईं ओर या बाईं ओर?

कोष्ठकों में व्यंजक का रूप बचाएँ

हवाई अड्डे के लिए पहला कदम निकालना

दानवों की आवाज़ों से अक्षर पहचानना

लक्ष्य से “अंतर” घटाने वाली चाल चुनें

मुझे संगीत पसंद है

अंक देने का तरीका खुद सुधारना

बेतरतीब तार, मोटर से घूमते नॉब

1 कंप्यूटर का समय सबमें बाँटना

4 रंग: मनुष्य का तर्क, कंप्यूटर का श्रम

इस अध्याय में क्या अभी अनजाना है?

नाम वाला गर्मियों का प्रस्ताव

लक्ष्य से घटाने वाली चाल चुनें