El inicio del primer auge | Toda la historia de la IA

011955 · Nombre y propuesta

La propuesta de verano que presentó la

¿Dónde nació el nombre y con qué expectativas?

En un documento fechado el 31 de agosto de 1955, McCarthy, Minsky, Rochester y Shannon escribieron una propuesta para un encuentro de investigación en Dartmouth College durante el verano siguiente y solicitaron financiación a la Fundación Rockefeller. En el título aparecía el término . La propuesta partía de la conjetura de que cualquier aspecto del aprendizaje o de la inteligencia podía, en principio, ser “descrito con tal precisión que se pueda hacer que una máquina lo simule” (traducción).

Los 7 recuadros de la derecha corresponden a los temas de investigación de la propuesta. Al pulsarlos, aparece su contenido: lenguaje, redes neuronales, magnitud de los cálculos, máquinas que se mejoran a sí mismas. Muchas de las páginas dobles de este capítulo continúan alguno de esos temas.

Se preveía una duración de 2 meses y la participación de 10 personas. Escribieron que, si un grupo de científicos seleccionados trabajaba en conjunto durante un verano, (traducción). El presupuesto solicitado fue de 13,500 dólares, pero la fundación concedió 7,500 dólares.

Los importes de la tabla presupuestaria suman 13,000 dólares: faltan 500 dólares para alcanzar el total de 13,500 dólares que figura en ella. Esto se comprobó en la reproducción disponible en el sitio de McCarthy; no se explica la razón de la diferencia.

Lo que se cree saberLo que suele decirse:El nombre se decidió por unanimidad
Según la fuente original:Lo eligió McCarthy y ya entonces hubo objeciones. Newell y Simon usaron durante años otro nombre: .

Lo que se cree saberLo que suele decirse:Los participantes de Dartmouth pretendían completar la IA en un verano
Según la fuente original:La propuesta dice (traducción). No dice que fueran a completarla.

021956 · Dartmouth

Cómo fue el encuentro de un verano

¿Cómo fue en realidad aquella “gran conferencia en la que nació la IA”?

En el verano de 1956, varios investigadores interesados en las máquinas pensantes se reunieron en el último piso del departamento de matemáticas de Dartmouth College. Según las notas de Solomonoff, uno de los participantes, el encuentro duró unas 8 semanas, desde alrededor del 18 de junio hasta el 17 de agosto. Más que una conferencia con un calendario fijo, fue un encuentro al que las personas llegaban por turnos para conversar.

En la figura de la derecha, al pulsar “Detalles: plan y registros”, se puede superponer al plan que McCarthy comunicó a la fundación el 26 de mayo (marcos morados) la información sobre “quiénes estaban ese día” que quedó en las notas de Solomonoff y More (puntos azul oscuro). Solo 3 personas estuvieron durante todo el período, y 2 de las 11 previstas no llegaron. En las conversaciones diarias participaron unas 3–8 personas.

También se habló de trabajar todos en un mismo problema. El 7 de agosto, McCarthy propuso el ajedrez, pero no se convirtió en un proyecto conjunto. McCarthy contó después que, por falta de fondos y porque cada participante tenía otros compromisos, no se cumplió el plan de reunirlos a todos durante un verano entero.

No se conserva una lista exacta de participantes; McCarthy perdió la suya. Los puntos representan únicamente los días anotados, por lo que la ausencia de un punto no significa necesariamente que esa persona no estuviera allí.

Lo que se cree saberLo que suele decirse:El encuentro de Dartmouth fue una gran conferencia en la que nació la IA
Según la fuente original:En realidad fue un encuentro de verano al que las personas llegaban y del que se iban, con unas 3–8 personas en las conversaciones diarias. La financiación de la fundación fue aproximadamente la mitad de lo solicitado y tampoco se publicó un informe del encuentro.

Número de participantes en las conversaciones diarias de la semana 6 (23–27 de julio), según las notas de More

031956 · Búsqueda

Si se construyen todas las demostraciones

Si se construyen todas las demostraciones posibles en orden, ¿no se llegará tarde o temprano al teorema buscado?

Newell, Shaw y Simon se enfrentaron a los teoremas de lógica del libro . A partir de 5 axiomas, construían nuevos teoremas mediante 3 reglas: sustitución, que reemplaza letras por expresiones; reemplazo, que transforma una expresión en otra de igual significado; y separación, que obtiene B a partir de A y de “si A, entonces B”.

El método más sencillo consiste en construir todas las demostraciones posibles, comenzando por las más cortas, y esperar a que aparezca la expresión buscada. Los 3 lo llamaron método del Museo Británico (British Museum algorithm) y lo usaron como punto de comparación. Según las cifras del informe, hasta el paso 4 se obtienen 42 expresiones, y hasta el paso 8, 246. Para reunir todo el capítulo 2, podrían hacer falta unos 100 millones, y estimaron que llevaría cientos de miles de años.

Examinar una tras otra las posibles respuestas se llama búsqueda. Como una búsqueda exhaustiva tiene demasiados candidatos, hace falta reducir el campo de búsqueda con reglas prácticas que ofrecen atajos (heurísticas). La figura de la derecha genera expresiones según el modo de contarlas de este sitio.

Número de expresiones en el paso n ≈ (número de expresiones en el paso n−1) × (número de formas de cambiar 1 posición)

Formas de cambiar: convertir p en ¬p, intercambiar → y ¬…∨, etc.

Número de expresiones por paso (el eje vertical aumenta por factores de 10)

Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.

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 · Logic Theorist

Buscar hacia atrás desde la respuesta

¿Cómo se puede buscar la demostración de un teorema mediante conjeturas orientadoras, como hace una persona?

En lugar de construirlo todo, Logic Theorist (LT) buscaba hacia atrás desde la expresión que quería demostrar. Probaba 4 métodos en orden. El método de sustitución reemplaza las letras de un axioma o de un teorema ya demostrado por expresiones y comprueba si puede obtener exactamente la forma del problema. El método de separación busca un teorema “si A, entonces B” cuya B coincida con el problema, y convierte A en un nuevo problema más pequeño. El encadenamiento hacia delante y hacia atrás también crea problemas más pequeños.

Según el informe de 1957, encontró demostraciones de 38 de los primeros 52 teoremas del capítulo 2. Para 17 bastó la sustitución, y 19 se resolvieron en 2 pasos. 2.01 llevó unos 10 segundos y 2.45, unos 12 minutos. En 2.31, las opciones de búsqueda se agotaron tras unos 23 minutos. La figura de la derecha es un pequeño LT creado por este sitio. Al pulsar “Hasta el final”, el árbol crece hacia abajo y el camino verde forma la demostración.

El informe ofrecía esta comparación: si avanzar desde los axiomas es como buscar una aguja en un pajar, retroceder desde el objetivo se parece a buscar el camino por el que la aguja sale del pajar.

El LT de la figura difiere en los detalles del programa de 1956. El informe dice que los 4 métodos no pueden demostrar 2.13, pero este ejemplo del sitio usa una manera distinta de hacer coincidir las expresiones y otras condiciones para los teoremas preparados. Por eso, al marcar “Usar también los teoremas preparados”, encuentra también una demostración de 2.13.

Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.

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 · Una máquina que aprende

Corregir los pesos solo cuando hay errores

¿Puede una máquina aprender a distinguir cosas con solo mostrarle ejemplos?

En 1957, Rosenblatt, psicólogo del Laboratorio Aeronáutico de Cornell, comenzó a investigar el con apoyo de la Oficina de Investigación Naval. Es una neurona artificial que imita las conexiones entre las células nerviosas: multiplica las entradas (0 o 1) por pesos (cuánto cuenta cada entrada), suma los resultados y produce 1 si el total alcanza o supera un umbral.

El método de aprendizaje es sencillo: solo cuando se equivoca, corrige un poco los pesos en la dirección de la respuesta correcta. Al colocar ● y ○ en la figura de la derecha y pulsar “Seguir aprendiendo”, la línea morada gira o se desplaza en paralelo, y cambia el número de errores (círculos morados). Block, matemático también de Cornell, demostró que, si existe una recta que separe los grupos, este método de corrección siempre encontrará una.

La historia de las redes neuronales comienza aquí. Los problemas que no se pueden clasificar con 1 sola recta se tratan en el capítulo 5, y la combinación de capas, en el capítulo 8.

y＝1 si w₁x₁ ＋w₂x₂ ≧ t; en caso contrario, 0. Si hay un error: w ← w＋η(respuesta correcta − y)x, t ← t − η(respuesta correcta − y)

t: umbral
η: magnitud de la corrección (0.5 en la figura)
línea morada: frontera donde w₁x₁ ＋w₂x₂ es igual a t

Número de errores en cada recorrido

Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.

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 · Predicciones

4 predicciones para “dentro de 10 años”

¿Cómo imaginaban los investigadores de 1957 los 10 años siguientes?

El 14 de noviembre de 1957, durante la cena de un congreso en Pittsburgh, Simon dio una conferencia escrita junto con Newell (se publicó en una revista al año siguiente). Explicó que las computadoras de entonces podían resolver problemas sin un método de solución fijo de maneras parecidas a las humanas y aprender de la experiencia. Después, predijo que ocurrirían 4 cosas en un plazo de 10 años.

Una computadora se convertiría en campeona mundial de ajedrez (“a menos que las reglas le impidan competir” (traducción)). Descubriría y demostraría un nuevo teorema matemático importante. Compondría una pieza musical aceptada por los críticos. La mayoría de las teorías psicológicas adoptarían la forma de programas. También afirmó que “ya existen en el mundo máquinas que piensan, aprenden y crean” (traducción).

Ya había resultados que servían de punto de partida: un programa que demostraba teoremas de lógica, una computadora que jugaba ajedrez a un nivel básico y la ILLIAC de la Universidad de Illinois, que componía música. Al avanzar los años en la figura de la derecha, aparecen el año de comprobación (1968) y los acontecimientos posteriores.

Una computadora venció al campeón mundial de ajedrez en ejercicio en 1997, unos 40 años después de la predicción. Ninguna computadora ha obtenido el título de campeona mundial en sí.

071958 · Crítica y respuesta

Fijaron ellos mismos el día de comprobación

¿Qué hace falta para que una predicción pueda comprobarse?

Cuando la conferencia se publicó en la revista, Bellman la criticó en una carta. Según la respuesta de los 2 autores, la crítica describía las predicciones con estas palabras: “incorrecto, irresponsable y sensacionalista” (traducción). En su respuesta de 1958, ambos escribieron: “El mejor momento para juzgar si las predicciones son correctas será alrededor del 1 de enero de 1968” (traducción).

Los 2 explicaron que habían fijado un plazo y formulado predicciones concretas para evitar que fueran imposibles de comprobar, como las de Nostradamus. Pero, además de indicar qué ocurrirá y para cuándo, hace falta un criterio que permita decidir si la predicción se cumplió. En la figura de la derecha se pueden quitar el plazo y el criterio de evaluación. En el ajedrez, el resultado es claro; en las predicciones sobre teoremas, música y psicología, las evaluaciones pueden variar según la persona incluso al llegar la fecha límite.

Sobre la predicción de psicología, también se refirieron en su respuesta a la afirmación de que los programas eran candidatos sólidos a teorías psicológicas: “ya es cierto en 1958, en lugar de 1968” (traducción).

El criterio para el ajedrez (vencer al campeón mundial en ejercicio en un enfrentamiento) fue establecido provisionalmente por este sitio.

Lo que se cree saberLo que suele decirse:Los primeros investigadores de IA hacían grandes afirmaciones sin fundamento
Según la fuente original:Ya entonces hubo críticas. Los propios autores explicaron que habían fijado plazos para permitir la comprobación e incluso señalaron ellos mismos el día de evaluación: alrededor del 1 de enero de 1968.

081958 · Demostración de la Marina

La marca de la tarjeta: derecha o izquierda

El día en que el periódico publicó grandes expectativas, ¿qué hizo realmente la máquina?

En julio de 1958, la Marina de Estados Unidos presentó una demostración a periodistas en Washington. Una simulación del perceptrón funcionó en la gran computadora IBM 704 de la Oficina Meteorológica (el organismo encargado del tiempo atmosférico). Tras unos 50 ensayos, aprendió a distinguir si la marca de una tarjeta estaba a la derecha o a la izquierda. La máquina específica aún no se había construido.

Al día siguiente, el titular de The New York Times fue (traducción). El artículo informó que la Marina esperaba que ese “embrión” llegara a ser “capaz de caminar, hablar, ver, escribir, reproducirse y ser consciente de su existencia” (traducción).

La figura de la derecha es un pequeño ejemplo que reproduce la demostración de aquel día; el tamaño de las tarjetas y las marcas fueron elegidos por este sitio. Al pulsar “50 tarjetas más”, el mapa de pesos desarrolla un patrón en el que la mitad derecha vota por la derecha y la mitad izquierda por la izquierda. La máquina aprendió únicamente qué casilla vota por qué lado. No conoce las palabras derecha e izquierda.

Lo que se cree saberLo que suele decirse:Rosenblatt dijo “El perceptrón caminará, hablará y tendrá conciencia”
Según la fuente original:El artículo atribuía esa expectativa a . Él también afirmó que “la máquina sería el primer dispositivo que pensara como el cerebro humano” (traducción), pero en su informe de 1961 criticó el tratamiento de la prensa, comparándolo con “una jauría de sabuesos felices” (traducción).

Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.

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

Tratar expresiones con paréntesis anidados

¿Cómo se puede calcular con las propias expresiones simbólicas en lugar de con números?

En el otoño de 1958, McCarthy y Minsky iniciaron en el MIT el (traducción). No escribieron una propuesta. Se cuenta que, cuando les preguntaron qué necesitaban, respondieron: 1 habitación, 2 programadores, 1 secretaria y 1 máquina para perforar tarjetas. Ese mismo otoño comenzaron a crear LISP (procesamiento de listas), un lenguaje de programación para manejar secuencias de símbolos.

En LISP, las expresiones se escriben con paréntesis anidados, como (TIMES X (PLUS X A) Y). La primera palabra indica qué hacer y el resto, sobre qué hacerlo. Las operaciones básicas son pocas: car toma el primer elemento, cdr toma el resto y cons añade un elemento al principio, entre otras. Un artículo de 1960 mostró cómo escribir la derivación de expresiones usando solo esas operaciones, bifurcaciones condicionales y funciones que se llaman a sí mismas.

En la figura de la derecha, al elegir “X(X+A)Y · Ejemplo del artículo”, desmarcar “Simplificar 1 y 0 (añadido del sitio)” y pulsar “Derivar respecto de X (DIFF)”, aparece en forma de árbol la misma respuesta que en el artículo. ONE, que representa 1, y ZERO, que representa 0, quedan sin cambios. Los lenguajes de la familia LISP ocuparon un lugar central en la investigación de IA durante mucho tiempo después.

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

′: derivada respecto de X. DIFF construye esta forma conservando los paréntesis anidados

Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.

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 · Sentido común

Deducir el primer paso para ir al aeropuerto

Si los hechos se escriben en frases, ¿puede una máquina deducir acciones a partir de ellos?

En noviembre de 1958 se celebró en el Laboratorio Nacional de Física de Inglaterra el congreso internacional (traducción). McCarthy presentó allí (traducción). Su idea, llamada Advice Taker, era escribir hechos y consejos en fórmulas lógicas y razonar a partir de ellos; si se obtenía una conclusión del tipo “hacer…”, se ejecutaría.

El ejemplo del artículo plantea el problema de ir al aeropuerto desde el escritorio de casa. A partir de 17 premisas, como at(I, desk) (estoy en el escritorio), at(car, home) (el automóvil está en casa), walkable(home) (se puede caminar dentro de la casa) y drivable(county) (se puede ir en automóvil dentro del condado), deduce 8 conclusiones en orden. La última es do(go(desk, car, walking)): primero, caminar hasta el automóvil.

En la figura de la derecha se puede pulsar “Deducir la siguiente”. Si se quita 1 premisa, ya no se encuentra el plan.

El artículo dice que no puede responder por completo cómo reunir las 17 premisas ni cómo hacer las deducciones. La figura sigue el orden en el que aparecen las conclusiones en el artículo.

Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.

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 · Reconocimiento de patrones

Reconocer letras con gritos de demonios

¿Se puede dividir el mecanismo de reconocimiento de letras en muchas piezas pequeñas?

En el mismo congreso, Selfridge presentó un mecanismo llamado (el lugar donde se reúnen todos los demonios). Los demonios de datos, en el nivel inferior, buscan cada uno una parte de la letra: una barra horizontal, una vertical, una curva, etc. Gritan más fuerte cuanto mayor es la certeza de haberla encontrado. Los demonios de reconocimiento, situados encima, reúnen los gritos que corresponden a su letra y gritan a su vez. El demonio de decisión, en el nivel superior, elige como respuesta la letra cuya voz es más fuerte.

También propuso un método de aprendizaje: variar poco a poco, desde fuera, el volumen de los megáfonos de los demonios, elegir el ajuste que más mejore el resultado y repetir el proceso (método de ascenso de colinas). En la figura de la derecha, al pulsar “Seguir ajustando”, el volumen parte de 0 y el porcentaje de aciertos va aumentando.

La estructura que extrae características y las combina multiplicándolas por pesos es la misma que la del perceptrón y las redes neuronales posteriores.

Voz del demonio de reconocimiento k＝Σ_i volumen_k,i × voz del demonio de datos i

volumen_k,i: peso con el que el demonio k escucha al demonio i (la parte que aprende)
respuesta: el k cuya voz es más fuerte

Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.

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

Elegir acciones que reduzcan las con la meta

¿Se puede crear un método de solución que sirva para cualquier problema?

Newell, Shaw y Simon crearon el a partir de Logic Theorist y lo presentaron en un informe preliminar para el congreso de París de junio de 1959 (el informe está fechado el 30 de diciembre de 1958). Lo llamaron general porque separaron el contenido del problema (lógica, álgebra, fórmulas trigonométricas, etc.) del método de solución.

El núcleo del método es el análisis de medios y fines. Se compara el estado actual con la meta, se identifica una diferencia y se elige una acción que reduzca esa diferencia. Si no se cumplen las condiciones para usar la acción, cumplirlas se convierte en una nueva meta más pequeña. Así se crean metas dentro de otras metas y el mismo procedimiento se aplica en varios niveles.

El primer problema de la figura de la derecha es preparar una tostada con mantequilla, un ejemplo creado por este sitio. Si se cambia la tabla que indica qué acción reduce qué diferencia, el mismo método de solución sirve para otro problema.

Uno de los objetivos del informe era acercar el comportamiento del programa a los registros de estudiantes universitarios que resolvían problemas de lógica pensando en voz alta. Los ejemplos del informe eran de lógica simbólica, álgebra elemental y fórmulas trigonométricas.

Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.

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 · Japón

Me gusta la música

¿Qué “máquinas pensantes” se construían entonces en Japón?

Alrededor del verano de 1958, el Laboratorio Electrotécnico inició el proyecto “Yamato”, una computadora específica para traducir del inglés al japonés. Como no disponían de una computadora con suficiente memoria para almacenar un diccionario, construyeron una máquina dedicada usando los circuitos de la computadora de transistores ETL Mark IV. El presupuesto era de 6 millones de yenes y la memoria, un tambor magnético de 820,000 bits. En febrero de 1959, al introducir una cinta de papel perforada con I like music, la máquina imprimió “ME GUSTA LA MÚSICA” (traducción).

Se eligió traducir del inglés al japonés para evitar las dificultades de introducir japonés (los caracteres kanji y la separación de las palabras). Aun así, había que trasladar el verbo al final de la frase, cambiar de lugar las preposiciones y añadir partículas como ga y o. Para los pronombres, I se convirtió en ware, you en nare y he en kare. En la figura de la derecha se puede avanzar por el procedimiento de traducción, paso a paso.

Hiroshi Wada, quien dirigió el proyecto, recordó que los 13 segundos hasta que la máquina comenzó a imprimir la primera traducción le parecieron muy largos. Los resultados se presentaron en junio de 1959 en el primer Congreso Internacional de Procesamiento de la Información, en París.

El diccionario y las reglas de la figura son un ejemplo creado por este sitio, salvo las traducciones de los pronombres. Las fuentes no indican cómo tradujo Yamato la frase I have some eggs in my hand., que se mostró en París.

Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.

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 · Aprendizaje automático

Corregir su propia forma de puntuar

¿Puede un programa jugar mejor que la persona que lo escribió?

Samuel, de IBM, continuó investigando cómo las computadoras aprenden de la experiencia mediante las damas (un juego en un tablero de 8×8 en el que las piezas se capturan saltando por encima de ellas). La versión que aprendía se demostró en televisión el 24 de febrero de 1956. El resumen de su artículo de 1959, (traducción), dice que, tras 8–10 horas de juego, el programa podía jugar mejor que la persona que lo había escrito.

La puntuación de una posición es la suma de características, como la diferencia en el número de piezas, la cantidad de movimientos disponibles o el control del centro, multiplicadas por sus pesos. El programa examina varias jugadas por adelantado y propaga las puntuaciones hacia arriba, suponiendo que elegirá la mayor para sí mismo y la menor para el rival (minimax). Uno de sus métodos de aprendizaje consiste en corregir los pesos para que la puntuación anterior a la búsqueda se acerque a la que se propaga tras examinar las jugadas futuras. En la figura de la derecha se puede pulsar “Aprender”.

El aprendizaje automático consiste en hacer que la máquina aprenda de ejemplos y de la experiencia, en lugar de escribir todo el procedimiento de solución.

w ← w＋η(puntuación propagada − puntuación antes de examinar jugadas futuras) × característica

w: peso
η: magnitud de la corrección
puntuación: suma de característica × peso (los números de la figura son un ejemplo creado por este sitio)

Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.

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

Cableado al azar y controles con motores

¿Qué ocurre si se construye una máquina que aprende como un aparato real, en lugar de un programa?

El 23 de junio de 1960 se presentó al público por primera vez Mark I, la máquina específica del perceptrón. Los pesos se ajustaban mediante (potenciómetros) girados por motores, y las conexiones se hacían en un gran panel de cables intercambiables. Según el informe de 1961, tenía 512 células A y 8 células R que daban la respuesta. Wightman y Martin se encargaron del montaje, y Hay, de los experimentos.

Su estructura tiene 3 niveles. Los puntos de la retina (S) se conectan a las células A mediante puntos elegidos al azar; esta parte no aprende. Solo se aprenden los pesos entre las células A y las células R. Siguiendo el experimento 1 del mismo informe, la figura de la derecha utiliza una retina que se cierra sobre sí misma, conectando arriba con abajo e izquierda con derecha, para distinguir barras horizontales de verticales.

Si la retina se conecta directamente, sin pasar por las células A, los errores no desaparecen por muchas veces que se repita el aprendizaje. Con cualquier conjunto de pesos, la puntuación media de todas las barras horizontales y la de todas las barras verticales son iguales. Al intercalar 80 células A aleatorias, algunas captan combinaciones de puntos y los errores llegan a 0 tras unos pocos recorridos.

El informe también registra un experimento en el que, aunque quien enseñaba daba respuestas incorrectas a propósito un 30% de las veces, la máquina aprendió a distinguir E de X con un 100% de aciertos. Se empleó un método distinto del aprendizaje por corrección de errores. Mark I se encuentra actualmente en la Institución Smithsonian.

Número de errores en cada recorrido (16 barras por recorrido)

Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.

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 · Personas y computadoras

Compartir 1 computadora entre todos

Antes de que las máquinas se encarguen de pensar en todo, ¿cómo deberían colaborar las personas y las computadoras?

En marzo de 1960, Licklider publicó el artículo (traducción). Como una higuera y el insecto que transporta su polen se ayudan mutuamente, imaginó una colaboración en la que las personas fijan los objetivos, plantean hipótesis, establecen criterios y evalúan, mientras la computadora se encarga de las tareas rutinarias. Al registrar su propio trabajo durante la primavera y el verano de 1957, encontró que alrededor del 85% del tiempo dedicado a pensar se empleaba en prepararse para hacerlo: buscar información, calcular, dibujar gráficos, etc.

Una de las tecnologías necesarias para ello es el tiempo compartido, un mecanismo que divide el tiempo de 1 computadora en pequeños intervalos para repartirlo entre muchas personas. Argumentó que las grandes computadoras de entonces eran demasiado rápidas y costosas para pensar junto con 1 sola persona, y que su tiempo de uso debía compartirse entre muchas. En la figura de la derecha se puede comparar este sistema con la espera por turnos. Aunque el tiempo total de procesamiento sea el mismo, la espera hasta la primera respuesta se reduce mucho.

Lo que se cree saberLo que suele decirse:Licklider predijo que las máquinas pensarían para 1980
Según la fuente original:El artículo decía “sería en 1980” (traducción) al presentar una estimación de un encuentro de la Fuerza Aérea. Él dejó un amplio margen para la duración de la época de colaboración entre personas y computadoras: “Los 15 podrían ser 10 o 500” (traducción).

171976 · Comprobación

4 colores: razonamiento humano y trabajo de la computadora

¿Cuándo se puede decir que una computadora ha demostrado un teorema?

La predicción afirmaba que una computadora “en un plazo de diez años… descubrirá y demostrará un nuevo teorema matemático importante” (traducción). No se encuentran registros de un acontecimiento que permita afirmarlo dentro de esos 10 años. En 1976, Appel y Haken demostraron el , el problema, planteado desde alrededor de 1852, de si cualquier mapa puede colorearse con 4 colores. Sin embargo, las personas construyeron el razonamiento de la demostración y el procedimiento para clasificar las formas. La computadora se encargó de examinar, una por una, cerca de 2,000 formas.

La figura de la derecha hace que una computadora coloree un mapa de ejemplo creado por este sitio. Colorea los países uno por uno y, cuando ya no queda ningún color posible, vuelve al paso anterior (retroceso o backtracking). A · B · C · D son todos vecinos entre sí, por lo que no pueden colorearse con 3 colores, por mucho que se intente. Una búsqueda que colorea un mapa y la demostración de un teorema válido para todos los mapas son cosas distintas.

En octubre de 1996, el programa de búsqueda de demostraciones EQP encontró automáticamente, en unos 8 días, una demostración de la , que seguía sin resolverse desde la década de 1930. En ambos casos, el propio problema ya había sido planteado por personas.

Lo que se cree saberLo que suele decirse:En 1976 una computadora demostró el teorema de los cuatro colores
Según la fuente original:Según el texto de la publicación, las personas construyeron a mano el procedimiento de clasificación, mientras la computadora examinó muchas formas una por una.

Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.

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))

La propuesta de verano que presentó la “inteligencia artificial”

Cómo fue el encuentro de un verano

Si se construyen todas las demostraciones

Buscar hacia atrás desde la respuesta

Corregir los pesos solo cuando hay errores

4 predicciones para “dentro de 10 años”

Fijaron ellos mismos el día de comprobación

La marca de la tarjeta: derecha o izquierda

Tratar expresiones con paréntesis anidados

Deducir el primer paso para ir al aeropuerto

Reconocer letras con gritos de demonios

Elegir acciones que reduzcan las “diferencias” con la meta

Me gusta la música

Corregir su propia forma de puntuar

Cableado al azar y controles con motores

Compartir 1 computadora entre todos

4 colores: razonamiento humano y trabajo de la computadora

Lo que aún no se sabe en este capítulo

La propuesta de verano que presentó la

Elegir acciones que reduzcan las con la meta