Към съдържанието
wannacode

Цифрите от касовата бележка

Накратко: Разпознаването на цифри с невронна мрежа превръща картинката в пиксели като признаци, а мрежа с по един неврон за цифра се учи да казва коя цифра е.

Проблем

Сумата от снимката

При връщане на стока клиентът праща снимка на касовата бележка, а системата трябва да прочете сумата. Касата печата цифрите с един и същ шрифт, затова изглежда лесно: сравни пикселите с шрифта и готово.

Но хартията се мачка, мастилото избелява, а по снимката има петна. Ето седмицата от шрифта и три седмици от истински бележки:

printSide([show(pixels(DIGITS[7])), show(trainX[7]), show(trainX[17]), show(trainX[27])]);
Изход
#####   #####   #####   #####
....#   ....#   ....#   ....#
...#.   ...##   .....   ...#.
..#..   ..#..   #.#..   ..##.
..#..   ..#..   ..#..   #.##.

Третата седмица е без пиксел на средния ред, четвъртата има излишно мастило долу. Правило „7 е, ако тези 9 пиксела са мастило“ се чупи от първото петно. А правило за всяко възможно петно не можеш да напишеш.

Идеята

Пикселите са признаци

Картинката 5 × 5 са 25 пиксела. Подреди ги ред по ред и имаш 25 числа: 1 за мастило, 0 за празно. Това са признаците, точно както разстоянието и теглото на поръчка. Разпознаването на картинка е класификация с 25 признака и 10 класа, цифрите от 0 до 9. Това е разпознаване на картинка (image classification).

Мрежата е слой от 10 неврона, по един за цифра. Всеки неврон има по едно тегло за всеки пиксел: сборът му е голям, когато мастилото е там, където неговата цифра има мастило.

Десетте сбора стават вероятности със softmax: всеки сбор става eˢ, после всяко число се дели на сбора на всички. Числата са положителни и общо 1. Най-голямото е отговорът, а големината му е колко е сигурна мрежата.

Обучението е цикълът от предишния урок: епохи, разбъркване, партиди, стъпка. Грешката за една картинка е −ln(p) на верната цифра: 0, ако мрежата дава 100% на верния отговор, и голяма, ако му дава малко.

Данните: 60 цифри за обучение (по 6 от всяка) и 30 за тест (по 3), всичките от шрифта с петна. Всеки пиксел се обръща с вероятност 8%, средно два пиксела на цифра.

Виж го

Данните и мрежата

Шрифтът е записан в кода като текст, # е мастило:

// цифрите от шрифта на касата: 5 × 5 пиксела, # е мастило
const DIGITS = [
  [".###.", "#...#", "#...#", "#...#", ".###."],
  ["..#..", ".##..", "..#..", "..#..", ".###."],
  [".###.", "#...#", "..##.", ".#...", "#####"],
  ["####.", "....#", ".###.", "....#", "####."],
  ["#..#.", "#..#.", "#####", "...#.", "...#."],
  ["#####", "#....", "####.", "....#", "####."],
  [".###.", "#....", "####.", "#...#", ".###."],
  ["#####", "....#", "...#.", "..#..", "..#.."],
  [".###.", "#...#", ".###.", "#...#", ".###."],
  [".###.", "#...#", ".####", "....#", ".###."],
];

Картинката става признаци, петната се правят с генератора, а признаците стават обратно картинка, за да ги печатаме:

// картинката като 25 признака: ред по ред, 1 за мастило, 0 за празно
function pixels(rows) {
  const x = [];
  for (let r = 0; r < 5; r++)
    for (let c = 0; c < 5; c++) x.push(rows[r][c] === "#" ? 1 : 0);
  return x;
}


// петно или избеляло мастило: всеки пиксел се обръща с вероятност 8%
const smudge = (x, rng) => x.map((v) => (rng.next() < 0.08 ? 1 - v : v));


// признаците обратно като картинка
const show = (x) =>
  [0, 1, 2, 3, 4].map((r) => x.slice(r * 5, r * 5 + 5).map((v) => (v > 0.5 ? "#" : ".")).join(""));


// няколко картинки една до друга
function printSide(pics) {
  for (let r = 0; r < 5; r++) console.log(pics.map((pic) => pic[r]).join("   "));
}

Генераторът е от предишния урок, със семе 7. Първо се правят 60-те цифри за обучение, после 30-те за тест:

class Rng {
  constructor(seed) {
    this.state = seed;
  }


  // следващото число между 0 и 1; едно семе дава едни и същи числа
  next() {
    this.state = (this.state * 48271) % 2147483647;
    return this.state / 2147483647;
  }
}
const rng = new Rng(7);
const trainY = Array.from({ length: 60 }, (_, n) => n % 10);
const trainX = trainY.map((d) => smudge(pixels(DIGITS[d]), rng));
const testY = Array.from({ length: 30 }, (_, n) => n % 10);
const testX = testY.map((d) => smudge(pixels(DIGITS[d]), rng));

Мрежата: 10 × 25 тегла и 10 отмествания. predict смята десетте сбора и ги прави вероятности. Преди exp от всеки сбор се вади най-големият: резултатът е същият, но exp не прелива при големи сборове. В step наклонът на неврон k по сбора му е p[k] − 1 за верната цифра и p[k] за другите: верният неврон се бута нагоре, а другите надолу, толкова, колкото са сгрешили.

class Net {
  // малки случайни тегла; отместванията остават 0
  constructor(rng) {
    this.w = Array.from({ length: 10 }, () =>
      Array.from({ length: 25 }, () => (rng.next() * 2 - 1) * 0.1)); // тегло на всеки пиксел за всеки от 10-те неврона
    this.b = new Array(10).fill(0);
  }


  // десетте вероятности (softmax): сборът им е 1
  predict(x) {
    const p = [];
    for (let k = 0; k < 10; k++) {
      let s = this.b[k];
      for (let i = 0; i < 25; i++) s += this.w[k][i] * x[i];
      p.push(s);
    }
    const top = Math.max(...p);
    let total = 0;
    for (let k = 0; k < 10; k++) {
      p[k] = Math.exp(p[k] - top);
      total += p[k];
    }
    for (let k = 0; k < 10; k++) p[k] /= total;
    return p;
  }


  // грешката: средното −ln(p) на верния отговор
  loss(xs, ys) {
    let total = 0;
    for (let n = 0; n < xs.length; n++) total -= Math.log(this.predict(xs[n])[ys[n]]);
    return total / xs.length;
  }


  // стъпка по партида: наклонът на неврон k е p[k] − 1 за верната цифра, p[k] за другите
  step(xs, ys, batch, rate) {
    const gw = Array.from({ length: 10 }, () => new Array(25).fill(0));
    const gb = new Array(10).fill(0);
    for (const n of batch) {
      const p = this.predict(xs[n]);
      for (let k = 0; k < 10; k++) {
        const d = p[k] - (k === ys[n] ? 1 : 0);
        gb[k] += d;
        for (let i = 0; i < 25; i++) gw[k][i] += d * xs[n][i];
      }
    }
    for (let k = 0; k < 10; k++) {
      this.b[k] -= (rate * gb[k]) / batch.length;
      for (let i = 0; i < 25; i++) this.w[k][i] -= (rate * gw[k][i]) / batch.length;
    }
  }
}

Пробвай

Предвиди изхода

Какво печата програмата? x[r * 5 + 2] е пикселът в ред r и колона 2 (броим от 0).

const x = pixels(DIGITS[7]);
console.log([0, 1, 2, 3, 4].map((r) => x[r * 5 + 2]).join(" "));
Отговор

Виж го

Обучението и една цифра отблизо

60 епохи, партиди по 10, скорост 0,5. На всеки 10 епохи програмата печата грешката и колко цифри са познати от обучението и от теста:

const net = new Net(rng);
const order = [...trainX.keys()];
console.log("епоха  грешка  обучение  тест");
for (let epoch = 1; epoch <= 60; epoch++) {
  shuffle(order, rng);
  for (let start = 0; start < order.length; start += 10)
    net.step(trainX, trainY, order.slice(start, start + 10), 0.5);
  if (epoch % 10 === 0) {
    const right = `${correct(net, trainX, trainY)}/${trainX.length}`;
    const test = `${correct(net, testX, testY)}/${testX.length}`;
    const loss = net.loss(trainX, trainY).toFixed(3);
    console.log(String(epoch).padStart(5) + loss.padStart(8) + right.padStart(10) + test.padStart(6));
  }
}
Изход
епоха  грешка  обучение  тест
   10   0.268     59/60 28/30
   20   0.128     60/60 29/30
   30   0.084     60/60 29/30
   40   0.063     60/60 29/30
   50   0.050     60/60 29/30
   60   0.042     60/60 29/30

След 20 епохи мрежата познава всичките 60 цифри за обучение и 29 от 30 в теста. Грешката продължава да пада, защото мрежата става по-сигурна, но цифрата от теста, която греши, остава същата.

Ето какво става с една цифра. Пикселите влизат, всеки неврон сбира теглата си по тях, а softmax прави сборовете вероятности:

// десетте вероятности (softmax): сборът им е 1
predict(x) {
  const p = [];
  for (let k = 0; k < 10; k++) {
    let s = this.b[k];
    for (let i = 0; i < 25; i++) s += this.w[k][i] * x[i];
    p.push(s);
  }
  const top = Math.max(...p);
  let total = 0;
  for (let k = 0; k < 10; k++) {
    p[k] = Math.exp(p[k] - top);
    total += p[k];
  }
  for (let k = 0; k < 10; k++) p[k] /= total;
  return p;
}


const net = train(trainX, trainY, rng);
const shifted = pixels(shift(DIGITS[1]));
for (const x of [testX[17], shifted]) {
  printSide([show(x)]);
  const p = net.predict(x);
  for (let k = 0; k < 10; k++) {
    const bar = "█".repeat(Math.round(p[k] * 20));
    const pct = (p[k] * 100).toFixed(1).padStart(5);
    console.log(`${k} ${bar.padEnd(20)} ${pct}%`);
  }
  console.log(`→ ${best(p)}`);
}
Стъпка по стъпка, с думи
  1. Седмица от теста, с петно долу вляво. За мрежата тя е 25 числа: 1 за мастило, 0 за празно.
  2. Всеки от 10-те неврона сбира теглата си по пикселите с мастило. Невронът на 7 има най-голям сбор: 6,68.
  3. Softmax: e на степен всеки сбор, делено на общото. Десетте ленти са общо 100%.
  4. Най-голямата лента е отговорът: 7 с 98,4%. Петното не попречи.
  5. Единицата от шрифта, без петно, отпечатана с един пиксел надясно. Мастилото ѝ е в четвъртата колона.
  6. Мрежата казва 4 с 57,1%, а 1 получава само 4,4%. Теглата на 4 чакат мастило точно в тази колона.
  7. Всяко тегло е вързано за един пиксел. Петната мрежата се научи да пренебрегва, а отместване не е виждала.
const net = train(trainX, trainY, rng);
const shifted = pixels(shift(DIGITS[1]));
for (const x of [testX[17], shifted]) {
  printSide([show(x)]);
  const p = net.predict(x);
  for (let k = 0; k < 10; k++) {
    const bar = "█".repeat(Math.round(p[k] * 20));
    const pct = (p[k] * 100).toFixed(1).padStart(5);
    console.log(`${k} ${bar.padEnd(20)} ${pct}%`);
  }
  console.log(`→ ${best(p)}`);
}
Изход
#####
....#
...#.
..#..
#.#..
0                        0.1%
1                        0.0%
2                        0.2%
3                        0.4%
4                        0.0%
5                        0.7%
6                        0.0%
7 ████████████████████  98.4%
8                        0.1%
9                        0.1%
→ 7
...#.
..##.
...#.
...#.
..###
0                        0.2%
1 █                      4.4%
2 ███                   15.4%
3                        2.3%
4 ███████████           57.1%
5                        0.6%
6 █                      5.0%
7 █                      7.1%
8 █                      2.9%
9 █                      5.0%
→ 4

Седмицата от теста е с петно долу вляво, и мрежата пак казва 7 с 98,4%. Втората картинка е единицата от шрифта, отпечатана с един пиксел надясно. Без нито едно петно, и мрежата казва 4 с 57,1%. Към нея ще се върнем.

Идеята

Какво гледа всеки неврон

Всеки неврон има 25 тегла, по едно за пиксел, затова теглата му също са картинка 5 × 5. Голямо положително тегло значи „мастилото тук е за мен“, голямо отрицателно значи „мастилото тук е против мен“:

// # силно „да“, + „да“, . все едно, - „не“, = силно „не“
function symbol(v) {
  if (v > 0.8) return "#";
  if (v > 0.25) return "+";
  if (v < -0.8) return "=";
  if (v < -0.25) return "-";
  return ".";
}


const weightMap = (weights) =>
  [0, 1, 2, 3, 4].map((r) => weights.slice(r * 5, r * 5 + 5).map(symbol).join(""));
const net = train(trainX, trainY, rng);
console.log("  0       1       7  ");
printSide([0, 1, 7].map((d) => weightMap(net.w[d])));
Изход
  0       1       7
.+.--   .-+=.   #+++#
+.-.#   -##.-   -.--+
#===#   --+=-   -==+.
#--.+   -+#.-   ..#.-
.+.--   -+.+-   -=+-.

Невронът на 0 иска мастило в двете крайни колони и е силно против мастило в средата на третия ред: там 0 е празна, а 8, 3 и 2 имат мастило. Невронът на 7 иска целия горен ред и третата колона долу. Невронът на 1 иска двата пиксела в горната средна част (.##.), а е против долния ляв ъгъл, където 2 и 5 имат мастило.

Никой не е казал на мрежата къде е чертата на седмицата. Теглата са намерени само от примерите. Те не са копие на цифрата: невронът гледа и къде неговата цифра се различава от другите.

Пробвай

Попълни

Последните редове на softmax. На какво се дели всяко число, за да са десетте общо 1?

for (let k = 0; k < 10; k++) p[k] /= ;

Идеята

Един пиксел встрани

Касата понякога печата цифрата малко встрани, а снимката е под ъгъл. Ето три цифри от шрифта, без петна, отместени с един пиксел надясно:

// същата цифра, отпечатана с един пиксел надясно
const shift = (rows) => rows.map((row) => "." + row.slice(0, 4));
const net = train(trainX, trainY, rng);
const digits = [1, 3, 7];
printSide(digits.map((d) => shift(DIGITS[d])));
for (const d of digits) {
  const p = net.predict(pixels(shift(DIGITS[d])));
  console.log(`${d} → ${best(p)} (${(p[best(p)] * 100).toFixed(1)}%)`);
}
Изход
...#.   .####   .####
..##.   .....   .....
...#.   ..###   ....#
...#.   .....   ...#.
..###   .####   ...#.
1 → 4 (57.1%)
3 → 9 (77.7%)
7 → 9 (39.0%)

Мрежата, която познава 29 от 30 цифри с петна, греши и трите. От всичките десет отместени цифри само деветката излиза вярна, и то с 53,8%.

Причината е в теглата. Всяко тегло е вързано за един пиксел на едно място. Невронът на 1 очаква мастило в средната колона. Отместената единица е в четвъртата колона, а там мастило очаква невронът на 4. За мрежата същата форма на друго място е друга картинка: тя не знае, че е видяла „чертичка“, знае само кои пиксели са мастило.

Затова данните за обучение трябва да са като истинските. Ако на снимките цифрите се местят, примерите за обучение трябва също да се местят. Или мрежата трябва да е от друг вид, която търси формата навсякъде (виж „По-точно“).

Пробвай

Намери грешката

Колега пише отчет за точността на мрежата и пише „100%“. На бележките от клиенти мрежата греши. На кой ред е грешката?

Избери реда с грешката.

Идеята

Кога вреди

  • Уверено грешна. Единствената грешка в теста е тройка с петно в средата, която мрежата чете като 9 с 91,2%. Вероятността е колко е сигурна мрежата, не колко е права. Когато грешката струва пари, прагът за „сигурно“ се проверява на тест, а съмнителните цифри ги гледа човек.
  • Всичко, което не е видяла. Отместване, друг шрифт, наклонена снимка, цифра, написана на ръка: мрежата е виждала само шрифта с петна и не знае нищо друго. За нея всяка картинка е някоя от десетте цифри, дори празен квадрат или буква.
  • Малко данни. 60 картинки стигат, защото шрифтът е един и цифрите са 5 × 5. За снимка на истинска бележка трябват хиляди примери и по-голяма мрежа.
  • Не е нужна мрежа. Ако касата праща сумата и като текст или QR код на бележката, прочети нея. Разпознаването е за случаите, когато друг път няма.
По-точно, за любопитните

Softmax с формула. Сборовете на десетте неврона са s₀ … s₉. Вероятността за цифра k е:

p[k] = e^(s[k]) / (e^(s₀) + e^(s₁) + … + e^(s₉))

С думи: направи всеки сбор положителен с e на степен сбора, после раздели на общото. При две цифри това е сигмоидата от логистичната регресия: softmax е нейното продължение за повече класове. Изваждането на най-големия сбор не сменя резултата, защото e^(s − m) = e^s / e^m, а e^m се съкращава.

Защо наклонът е p[k] − 1. Грешката за една картинка е L = −ln(p[y]), където y е верната цифра (cross-entropy). Наклонът ѝ по сбора на неврон k излиза много прост: p[k] − 1 за k = y и p[k] за другите. Ако мрежата дава 98% на верния отговор, бутането е само −0,02. Ако му дава 10%, е −0,9. Оттам backprop продължава към теглата като в предишните уроци: наклонът по тегло i е наклонът по сбора, умножен по пиксел i.

Защо няма скрит слой. С 10 неврона направо от пикселите всяко тегло е за един пиксел и една цифра, затова картата на теглата се чете. Със скрит слой мрежата познава повече, но картите на скритите неврони са смес от части на няколко цифри и трудно се четат. Опитай в упражненията.

Мрежите за картинки. Истинските мрежи за картинки са конволюционни (CNN): малък прозорец от тегла, например 3 × 3, се плъзга по цялата картинка и търси една и съща форма навсякъде. Чертичката е чертичка и вляво, и вдясно, затова отместването почти не им пречи. Класическият пример е MNIST: 70 000 цифри, писани на ръка, 28 × 28 пиксела. В PyTorch прозорецът е nn.Conv2d.

Еднакви числа на четирите езика. Програмите печатат вероятностите с един знак след запетаята, а лентите са закръглени до 20 части. Урокът проверява, че нито една лента и нито едно тегло не стоят точно на границата на закръгляне, затова изходът е един и същ на Java, C#, Python и JavaScript.

Упражнение

Сумата от бележката

Реши задачата в редактора си.

Сумата на бележката е 12,90 €: цифрите 1, 2, 9 и 0. Касата е отпечатала последната цифра с един пиксел надясно, а по снимката има петна. Направи четирите картинки (последната отместена, всичките с петна от същия генератор, след обучението), разпознай всяка и отпечатай цифрата и вероятността ѝ. Ако вероятността е под 90%, отбележи цифрата за проверка на ръка и сложи ? на мястото ѝ в сумата.

Изход
цифра 1: 1 (97.0%)
цифра 2: 2 (94.4%)
цифра 3: 9 (90.5%)
цифра 4: 7 (37.4%) → провери на ръка
сума: 12,9? € → провери на ръка

Отместената нула става 7, но само с 37,4%, и прагът я хваща. Деветката минава с 90,5%, на косъм над прага. Прагът не прави мрежата по-умна, той казва кога да не ѝ вярваш. Бележка с ? отива при човек, а не в счетоводството.

Още задачи

  • Отместени примери. Добави към данните за обучение всяка цифра от шрифта, отместена с един пиксел наляво и надясно, и обучи наново. Колко от десетте отместени цифри познава сега? А колко от теста?
  • Скрит слой. Сложи скрит слой от 16 неврона със сигмоида между пикселите и softmax. Отпечатай теглата на два скрити неврона като картинка. Прилича ли някой на цифра?

Тест

Провери се

1. Как мрежата вижда картинка 5 × 5?
2. Мрежата дава 98,4% за 7 и малки числа за другите цифри. Колко е сборът на десетте вероятности?
3. Единицата е отпечатана с един пиксел надясно, и мрежата казва 4 с 57,1%. Защо?
4. Колегата отчита 100% точност, мерена на 60-те цифри, с които мрежата се е учила. Какво казва това за нови бележки?
5. Една тройка от теста мрежата чете като 9 с 91,2%. Какво следва от това?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·