Навчання #22 — Лінійна алгебра та наука про дані

Лінійна алгебра — це мова сучасних обчислень. PageRank, стиснення зображень, рекомендаційні системи, фізичні симуляції, 3D-рендеринг і нейронні мережі — усе це, по суті, послідовності матричних операцій. Проте лінійну алгебру часто викладають як чисту маніпуляцію символами — рядки й стовпці без жодного геометричного змісту. Ця стаття йде протилежним шляхом: спочатку картинка, а вже потім — формула.

1. Матричні перетворення — що роблять матриці

Матриця 2×2 робить рівно одну річ: перетворює вектори на площині. Вона може розтягувати, обертати, віддзеркалювати, зсувати або згортати простір. Визначник — одне-єдине число — показує, як змінюється площа. Коли det = 0, матриця згортає площину в лінію або точку; інформація втрачається безповоротно.

Перетворення:  T(v) = Mv
  M = [[a, b], [c, d]]   відображає одиничний квадрат у паралелограм.

Визначник:  det(M) = ad − bc
  |det| = коефіцієнт зміни площі
  det > 0: орієнтація зберігається  |  det < 0: віддзеркалення
  det = 0: вироджена (сингулярна) матриця — відображає у простір нижчої розмірності

Власні вектори:  Mv = λv
  (M − λI)v = 0   ⟹  det(M − λI) = 0  (характеристичний многочлен)
  Власні значення λ₁,λ₂ показують коефіцієнти розтягу в особливих напрямках.

Для 2×2:  λ = (tr(M)/2) ± √((tr(M)/2)² − det(M))
  Дійсні власні значення: M має ортогональний власний базис (симетрична M)
  Комплексні власні значення: M містить компонент обертання

Слід = λ₁ + λ₂ = a + d
  (сума власних значень = сума діагональних елементів)

Спектральна теорема (симетрична M = Mᵀ):
  M = QΛQᵀ,   Q ортогональна,  Λ = diag(λ₁, λ₂)
  Кожну симетричну матрицю можна діагоналізувати — це основа PCA.

Симуляція матричних перетворень пропонує 8 готових перетворень — обертання, масштабування, зсув, віддзеркалення, проєкцію — плюс режим вільного редагування. Увімкніть одиничне коло, стрілки власних векторів і деформацію сітки, щоб побачити визначник як площу, а слід — як суму розтягів. Зверніть увагу на випадки одиничної та нільпотентної матриці: одна нічого не робить; інша згортає простір за два кроки.

2. Лінійна регресія — підбір прямих до зашумлених даних

Метод найменших квадратів (OLS) — найпростіша модель у статистиці й одна з найпоширеніших. Маючи n точок даних, потрібно знайти пряму, що мінімізує суму квадратів вертикальних відстаней. Розв'язок має чудову замкнену форму — і є окремим випадком нормальних рівнянь лінійної алгебри.

Мета:  мінімізувати SSE = Σ(yᵢ − ŷᵢ)² = ‖y − Xβ‖²

Нормальні рівняння:  (XᵀX)β = Xᵀy
  Розв'язок:  β̂ = (XᵀX)⁻¹Xᵀy  (єдиний, якщо X має повний ранг за стовпцями)

Для простої регресії (один предиктор + вільний член):
  β̂₁ = Σ(xᵢ−x̄)(yᵢ−ȳ) / Σ(xᵢ−x̄)²  = Cov(x,y)/Var(x)
  β̂₀ = ȳ − β̂₁x̄

Коефіцієнт детермінації:
  R² = 1 − SSE/SST = 1 − Σ(yᵢ−ŷᵢ)²/Σ(yᵢ−ȳ)²
  R² = r²  (для простої регресії r = кореляція Пірсона)

Кореляція Пірсона r:  r = Cov(x,y)/[σₓ σᵧ] ∈ [−1, 1]
  |r| = 0: лінійного зв'язку немає
  |r| = 1: ідеальний лінійний зв'язок

Геометрична інтерпретація:
  β̂ = (XᵀX)⁻¹Xᵀy — це ортогональна проєкція y на col(X).
  Вектор залишків e = y − Xβ̂ ⊥ col(X)  →  Xᵀe = 0  (завжди!)

Теорема Гаусса–Маркова:
  OLS є BLUE (найкращим лінійним незміщеним оцінювачем), коли
  похибки некорельовані, гомоскедастичні, з нульовим середнім.
  Порушення → гетероскедастичність, використовуйте WLS або GLS.

Клацніть на полотні діаграми розсіювання, щоб додати точки, і спостерігайте, як лінія регресії оновлюється миттєво. Лінії залишків (вертикальні відстані) показують саме те, що мінімізує OLS. Перетягніть пресет із викидом, щоб побачити важіль впливу — як одна екстремальна точка може повернути всю пряму — і зрозуміти, чому самого лише R² недостатньо для оцінки моделі (квартет Енскомба).

3. Баєсівський висновок — оновлення переконань за допомогою даних

Теорему Баєса можна висловити в кількох словах: апостеріорна ймовірність — це апріорна, помножена на правдоподібність і нормалізована. Якщо частотна статистика запитує «Яка ймовірність цих даних за умови нульової гіпотези?», то баєсівська статистика запитує «Яка ймовірність гіпотези за умови цих даних?» — набагато природніше питання для більшості наукових задач.

Теорема Баєса:  P(H|E) = P(E|H)·P(H) / P(E)
  H = гіпотеза,  E = свідчення (спостережені дані)
  P(H)   = апріорна ймовірність
  P(E|H) = правдоподібність
  P(E)   = маргінальна правдоподібність (нормалізаційна константа)
  P(H|E) = апостеріорна ймовірність

Форма шансів (уникає обчислення P(E)):
  Апостеріорні шанси = Апріорні шанси × коефіцієнт правдоподібності (фактор Баєса)
  BF = P(E|H₁)/P(E|H₀)   (BF > 10 → «сильний» доказ)

Спряжені апріорні розподіли (замкнена форма апостеріорної):
  Бета–Біноміальний:
    Апріорний: θ ~ Beta(α, β)
    Правдоподібність: k успіхів у n випробуваннях → Binomial(n, θ)
    Апостеріорний: θ | дані ~ Beta(α+k, β+n−k)

Приклад медичного тесту — базова частота має значення:
  Поширеність хвороби P(D) = 0.001 (1 з 1000)
  Чутливість тесту P(+|D) = 0.99
  Специфічність тесту P(−|¬D) = 0.99
  P(D|+) = 0.99×0.001 / [0.99×0.001 + 0.01×0.999] ≈ 0.09
  → 91% хибнопозитивних результатів навіть при точності тесту 99%!

Симуляція відтворює сценарій медичного тесту, дозволяючи налаштовувати поширеність, чутливість і специфічність. Результат — що позитивний тест на рідкісну хворобу зазвичай хибний — найважливіший і найконтрінтуїтивніший результат у прикладній теорії ймовірностей. Перемкніться на послідовне оновлення й додавайте спостереження одне за одним, щоб побачити, як апостеріорний розподіл загострюється з плаского апріорного.

4. Кластеризація K-Means — розбиття без міток

Навчання з учителем потребує розмічених даних — а це дорого. Кластеризація є навчанням без учителя: маючи нерозмічені точки, потрібно знайти природні групування. K-Means — найпростіший і найпоширеніший алгоритм кластеризації, що почергово призначає точки найближчому центроїду та переміщує кожен центроїд у середнє значення свого кластера.

Алгоритм Ллойда (K-Means):
  Ініціалізувати k центроїдів μ₁,…,μₖ  (випадково або через K-Means++)
  Повторювати до збіжності:
    1. Призначення:   zᵢ = argmin_j ‖xᵢ − μⱼ‖²  (найближчий центроїд)
    2. Оновлення:   μⱼ = (1/|Cⱼ|) Σ_{i∈Cⱼ} xᵢ  (середнє кластера)
  Цільова функція:  J = Σᵢ ‖xᵢ − μ_{z_i}‖²  (сума квадратів усередині кластера)

  Збіжність гарантована (J монотонно спадає)
  Але не глобальний оптимум — чутливий до ініціалізації!

K-Means++ (Arthur та Vassilvitskii, 2007):
  1. Обрати μ₁ рівномірно випадково.
  2. Для j = 2,…,k:
     Обрати μⱼ з імовірністю ∝ D(x)² = min_i ‖x − μᵢ‖²
  Очікуване J ≤ 8(ln k + 2) · J*   (гарантія наближення)

Вибір k — метод ліктя:
  Побудуйте графік J від k.  Шукайте «лікоть», де ∂J/∂k різко спадає.

Коефіцієнт силуету:   s(i) = (b(i) − a(i)) / max(a(i), b(i))
  a(i) = середня внутрішньокластерна відстань
  b(i) = середня відстань до найближчого кластера
  s ∈ [−1, 1]:  1 = ідеальна кластеризація, 0 = межа, −1 = неправильний кластер

Діаграма Вороного:   кожна комірка = {x : ‖x−μⱼ‖ ≤ ‖x−μₗ‖ ∀l≠j}
  Межі K-Means завжди лінійні (теселяція Вороного).

Симуляція відтворює повне розбиття Вороного піксель за пікселем за допомогою ImageData — кожен піксель забарвлюється відповідно до найближчого центроїда. Проходьте алгоритм Ллойда крок за кроком, щоб побачити збіжність, перемикайтеся на K-Means++, щоб порівняти якість ініціалізації, і використовуйте графік ліктя, щоб знайти «правильне» k для трьох різних синтетичних наборів даних.

5. Градієнтний спуск — навігація ландшафтами функції втрат

Майже кожну сучасну модель машинного навчання навчають за допомогою градієнтного спуску: багаторазово обчислюють градієнт функції втрат за параметрами, а потім роблять невеликий крок вниз по схилу. Варіанти — SGD, Momentum, RMSprop, Adam — відрізняються лише тим, як вони використовують історію градієнтів для адаптації розміру кроку.

Звичайний SGD:
  θ ← θ − α∇L(θ)   (α = швидкість навчання)
  Збіжність для опуклої L: O(1/√T) для негладкої, O(1/T) для гладкої

Momentum (Поляк, 1964):
  v ← βv − α∇L(θ)
  θ ← θ + v
  β ≈ 0.9.  Прискорює рух у напрямках стабільного градієнта.
  Варіант Нестерова: обчислює градієнт у θ + βv (з випередженням)

RMSprop (Хінтон, 2012, неопубліковано):
  s ← ρs + (1−ρ)(∇L)²
  θ ← θ − (α/√(s+ε))∇L
  Адаптує швидкість навчання окремо для кожного параметра — корисно для нестаціонарних цільових функцій

Adam (Кінгма і Ба, 2014):
  m ← β₁m + (1−β₁)∇L        (перший момент)
  v ← β₂v + (1−β₂)(∇L)²     (другий момент)
  m̂ = m/(1−β₁ᵗ),  v̂ = v/(1−β₂ᵗ)   (корекція зміщення)
  θ ← θ − α·m̂/(√v̂+ε)
  Значення за замовчуванням: α=1e-3, β₁=0.9, β₂=0.999, ε=1e-8
  Збіжність ≈ O(1/√T) для неопуклих цільових функцій

Функція Розенброка («банан»):
  f(x,y) = (1−x)² + 100(y−x²)²
  Глобальний мінімум у (1,1). Відома складністю: крута долина з пологим схилом.
  Adam ≈ 800 ітерацій до збіжності проти SGD ≈ 10 000+

Симуляція відтворює ландшафт функції втрат 60×60 у вигляді кольорової 3D-поверхні (алгоритм художника) і в реальному часі відстежує траєкторію оптимізатора. Запускайте всі чотири оптимізатори одночасно на функції Розенброка («банан») і багатомінімумній функції Гіммельблау. Візуальна різниця між зигзагом SGD, перерегулюванням Momentum і чистим спуском Adam пояснює, чому Adam став універсальним вибором за замовчуванням у глибокому навчанні.

6. Згорткові нейронні мережі — вилучення ознак за задумом

Повнозв'язна нейронна мережа, застосована до зображення 224×224, потребувала б понад 50 000 ваг на нейрон — обчислювально неможливо. Ідея, що лежить в основі CNN: сусідні пікселі корельовані, а та сама ознака (край, текстура) може з'явитися будь-де на зображенні. Заміна повних зв'язків локальними фільтрами та спільним використанням ваг зменшує кількість параметрів на порядки, водночас забезпечуючи інваріантність до зсуву.

Двовимірна дискретна згортка:
  (f * g)[i,j] = Σₘ Σₙ f[m,n]·g[i−m, j−n]
  У CNN g — це навчений фільтр (ядро) розміром k×k.

Розмір виходу (без доповнення):
  H_out = (H_in − k) / stride + 1

Обчислення карти ознак (для одного фільтра W, зсуву b):
  Z[i,j] = (X * W)[i,j] + b  (перед активацією)
  A[i,j] = ReLU(Z[i,j]) = max(0, Z[i,j])

Типові фільтри (створені вручну):
  Горизонтальний край:  [[-1,-1,-1],[0,0,0],[1,1,1]]
  Вертикальний край:    [[-1,0,1],[-1,0,1],[-1,0,1]]
  Різкість:             [[0,-1,0],[-1,5,-1],[0,-1,0]]
  Гаусове розмиття:     1/16 · [[1,2,1],[2,4,2],[1,2,1]]

Max pooling (2×2, крок 2):
  Зменшує просторові розміри вдвічі, залишає максимальну активацію.
  Забезпечує інваріантність до невеликих зсувів.

Зворотне поширення через згортку:
  ∂L/∂W = вхід * ∂L/∂Z  (кореляція, а не згортка)
  ∂L/∂X = повна згортка ∂L/∂Z з перевернутим W

Кількість параметрів (один згортковий шар, k=3, C_in каналів, C_out фільтрів):
  (k² · C_in + 1) · C_out  =  (9 · C_in + 1) · C_out
  проти повнозв'язного: H·W·C_in · H·W·C_out  (на порядки більше)

Оберіть одне з п'яти вхідних зображень 8×8 і перемикайтеся між чотирма вручну створеними фільтрами. Перемикайте вкладки шарів — вхід → Conv → ReLU → MaxPool → глибші шари — і спостерігайте, як анімована позиція сканування покроково вилучає ознаки. Панель архітектури відстежує просторові розміри та кількість параметрів, роблячи обчислювальну перевагу спільного використання ваг конкретною й наочною.

Єдність лінійної алгебри та науки про дані

Усі шість симуляцій — це різні прояви однієї й тієї самої геометричної структури. Лінійна регресія — це проєкція. K-Means розбиває простір діаграмою Вороного, межі якої є перпендикулярними бісектрисами, визначеними евклідовою метрикою. Градієнтний спуск слідує градієнту квадратичної форми, яка поблизу мінімуму завжди визначається матрицею Гессе та її власними значеннями. Згортковий шар — це структуроване розріджене матричне множення. Навіть теорема Баєса, застосована до гаусового апріорного розподілу й гаусової правдоподібності, дає гаусів апостеріорний розподіл, середнє якого є зваженим середнім — лінійною операцією.

Серія про машинне навчання продовжується деревами рішень (нелінійні розбиття) та навчанням з підкріпленням у Навчання #9 — Машинне навчання, а статистичні основи розглянуто в Навчання #15 — Імовірність і статистика. Про бік науки про дані, пов'язаний з обробкою сигналів — FFT, фільтри, спектрограми — читайте в Навчання #14 — Обробка сигналів.