Hacker News Digest

Стандартный алгоритм Ланцоса для вычисления матричных функций требует значительных ресурсов памяти: хранение n×k базисной матрицы, которая растёт с каждой итерацией. Для задачи с 500 000 переменными и 1000 итерациями это около 4 ГБ только для базиса. В статье представлен двухпроходной вариант алгоритма, требующий всего O(n) памяти ценой удвоения числа матрично-векторных произведений. При грамотной реализации этот подход не только экономит память, но и может работать быстрее для определённых задач.

Автор подробно описывает реализацию на Rust, включая шаги рекуррентного вычисления, итератор для управления состоянием, первый проход (вычисление разложения) и второй проход (восстановление решения). Интересно, что теоретические ожидания производительности не всегда подтверждаются на практике, особенно для средних по размеру матриц. Весь код доступен на GitHub, а технический отчёт с доказательствами и дополнительными экспериментами можно скачать отдельно.

• Обсуждение охватывает редкий случай, когда матрица и векторы помещаются в кэш, но базис не помещается, и показывает, что алгоритм Ланцоша может быть реализован без реортогонализации, что экономит O(n²) памяти и O(n²) FLOP в обмен на O(n) дополнительных итераций.
• Участники обсуждают точность двухпроходного подхода, влияние потери ортогональности на точность и применимость метода, а также то, что влияние на точность может быть меньше, чем погрешность самого алгоритма Ланцоша.
• Также обсуждается выбор языка для реализации алгоритма, причем участники делятся опытом и мнением о том, какие языки лучше всего подходят для высокопроизводительной численной линейной алгебры.
• В конце обсуждение сдвигается к тому, что автор может в будущем опубликовать расширенную версию статьи, и что читатели могут ожидать увидеть ее в будущем.

Матрицы — это мощный инструмент, а не просто набор чисел. Первые девять элементов матрицы представляют поворот объекта. Например, первые три элемента первой колонки (m[0], m[1], m[2]) — это направление оси X после преобразования. Аналогично, следующие три (m[4], m[5], m[6]) — это новая ось Y, и так далее.

Вместо того чтобы выполнять множество отдельных операций (вращение, масштабирование, перемещение), можно просто применить одну матрицу, которая объединяет все эти преобразования. Это эффективно: один вызов к glMultMatrixf() заменяет множество вызовов других функций.

Например, чтобы повернуть объект на 45 градусов вокруг оси Z и переместить его на 10 единиц по X и Y, можно использовать матрицу, где первые три элемента первых двух столбцов — это косинусы и синусы угла, а последние элементы первого и второго столбца — это координаты перемещения. Это не только проще мысленно, но и эффективнее для процессора.

Таким образом, матрицы — это не просто математическая абстракция, а практический инструмент для эффективного и интуитивного управления преобразованиями в 3D-графике.

• Обсуждение развернулось вокруг того, как именно представлять и обсуждать матрицы: какие обозначения и соглашения используются, как они влияют на понимание и как они связаны с тем, как мы привыкли думать о линейных преобразованиях.
• Участники обсуждали, что в разных областях (математика, компьютерная графика, машинное обучение) используются разные соглашения, что может вызывать путаницу.
• Обсуждались различия между подходами "row-major" и "column-major", а также то, как разные ПО и языки программирования (например, C vs. FORTRAN) влияют на то, как мы представляем и обсуждаем матрицы.
• Также обсудили, что важно различать матрицы как сетку чисел и как линейное преобразование, и как это влияет на то, как мы думаем о таких понятиях как повороты и масштабирование.

Линейная алгебра начинается с двух ключевых идей: метода Гаусса и концепции строкового и столбцового представления. На примере монет: уравнение 5x + y = 23 (где x — никели, y — пенни) имеет несколько решений, например, 4 никеля и 3 пенни или 23 пенни. Это линейное уравнение, так как его график — прямая.

Сложность возникает, когда переменных две, но нужно удовлетворить двум условиям. Например, в задаче о питании: молоко (1 г углеводов, 2 г белка) и хлеб (2 г углеводов, 1 г белка). Чтобы получить 5 г углеводов и 4 г белка, нужно решить систему из двух уравнений. Метод Гаусса позволяет найти такие x и y, которые одновременно удовлетворяют обоим уравнениям, демонстрируя переход от одной переменной к системам.

• Пользователи высоко оценили визуальный стиль и доступность объяснений в блоге, сравнивая его с другими популярными ресурсами.
• Было высказано пожелание начинать объяснение линейной алгебры с практической задачи и графической интерпретации, а не с абстрактного метода (как Gaussian elimination).
• Обсуждалась цель изучения линейной алгебры: для практического применения или глубокого теоретического понимания.
• Отмечены технические проблемы с отображением иллюстраций в тёмном режиме на iOS Safari.
• Упомянуты другие учебные материалы по теме и выражена благодарность автору за качественный контент.

Книга представляет собой структурированное введение в линейную алгебру, разбитое на пять глав, каждая из которых последовательно раскрывает ключевые концепции. Начинается с основ векторов и скаляров, включая операции над ними, скалярное произведение и проекции, затем переходит к матрицам и их свойствам, включая умножение, обратные матрицы и специальные типы вроде симметричных и диагональных. Третья глава посвящена системам линейных уравнений, методам исключения и LU-разложению, четвёртая — векторным пространствам, базисам и размерности, а пятая — линейным преобразованиям, их матричному представлению и свойствам вродя обратимости и проекций.

Особенность подхода — сочетание геометрической интуиции (векторы как стрелки, матрицы как преобразования) с алгебраической строгостью, что помогает глубже понять материал. Практические аспекты, такие как вычисление ранга или работа с координатными системами, подчёркивают прикладную ценность темы для машинного обучения, компьютерной графики и инженерии.

• Участники обсуждают учебные материалы по линейной алгебре, отмечая полезность книги "The Little Book of Linear Algebra" и её связи с практическими лабораторными работами.
• Возникает дискуссия о подходах к обучению: одни подчеркивают важность исполняемого кода для экспериментов, другие настаивают на необходимости изучения абстрактной теории с помощью математических учебников и ручных вычислений.
• Критикуются некоторые визуализации и определения в материалах (например, определение вектора), как вводящие в заблуждение или недостаточно строгие с математической точки зрения.
• Обсуждаются практические аспекты: применимость знаний для компьютерного зрения и машинного обучения, сравнение NumPy с другими инструментами (Octave, MATLAB) и важность интуитивного понимания.
• Автор книги отвечает на критику, поясняя свой подход и предлагая ссылки на дополнительные ресурсы (например, 3Blue1Brown) для лучшего визуального понимания.

План самообразования математика-чистяка (или статистика)

Этап 1

• школьная база
• дискретка, алгебра, анализ начального уровня

Этап 2

• линейная алгебра
• высшая алгебра
• вещественный и комплексный анализ
• диффуры, вероятность и статистика

Этап 3

• анализ, абстрактная алгебра, теория чисел
• топология, диффгеометрия
• по желанию: моделирование, статвывод, стохастика, вычислительная статистика

Этап 4

• фундамент: логика, множества, комбинаторика, криптография
• анализ: функциональный, мера, гармонический
• алгебра: группы, кольца, поля, гомологии
• числа: алгебраическая и аналитическая теория, эллиптические кривые
• геометрия и топология: алгебраическая, риманова, K-теория
• опционально: диффуры в частных, матфизика, вероятность на мере, многомерная статистика, байес, выживание, data mining

Этап 5

• читаем монографии и статьи, выбираем специализацию, делаем исследования

«Как пианист: сначала скучные этюды, потом — музыка» (Терри Тао).

• Классические «дорожные карты» по чистой математике часто выглядят как бесполезные списки книг без объяснения, зачем и в каком порядке их читать.
• Настоящий путь проще: крепкая линейная алгебра и анализ (Шилов, Рудин), дальше — основные учебники по геометрии, алгебре и анализу с доказательствами и наставником.
• Единственный способ стать математиком — публиковать исследования; маршрут любой, лишь бы вам было интересно и вы могли его пройти.
• Споры о «требуемом IQ 145» вызывают бурю критики: IQ не определяет креативность и усердие, а SAT/ACT лишь коррелируют с успехом, но не гарантируют его.
• Проверять стоит не коэффициент интеллекта, а свои реальные успехи в математике: умеете ли вы читать и писать доказательства, получаете ли удовольствие от процесса.

• Векторы и матрицы: LLM всё превращают в вектора; главное — скалярное произведение и умножение матриц.
• Softmax: превращает логиты в вероятности; температура регулирует «уверенность».
• Градиент и производная: показывают, как чуть изменить вес, чтобы ошибка уменьшилась.
• Цепное правило: позволяет распространить ошибку через слои; сердце backprop.
• Эмбеддинги: строки → векторы; чем ближе векторы, тем похожее значение.
• Attention: Q·K^T выделяет релевантные токены; V несёт смысл; маска прячет будущее.
• MLP в трансформере: два линейных слоя с ReLU; увеличивает выразительность.
• LayerNorm: стабилизирует распределение после каждого подслоя.
• Позиционное кодирование: добавляет «адрес» токену, иначе порядок теряется.
• Лосс (cross-entropy): средняя «удивлённость»; оптимизатор (Adam) крутит веса.

Дальше — только масштаб: больше слоёв, голов, данных и видеокарт.

• Физики и математики вспомнили, что знание тензорного исчисления, линалгебры и энтропии пригодилось для понимания backprop и LLM.
• Практика: «смотреть» Karpathy недостаточно — нужно кодить за ним; его курс даёт базы и уверенность копать дальше.
• Книга «Build a Large Language Model (from Scratch)» идёт шаг-за-шагом, но объясняет только вычисления, а не «почему это вообще работает»; explainability всё ещё исследуется.
• Путаница: эмбеддинги ≠ вся модель; они лишь вход для трансформера, внутри которого 1,8 трлн параметров и «чёрный ящик».
• LLM — логит-генераторы с неизбежной неопределённостью; цепочки моделей накапливают ошибку и быстро «ломаются» без человека-оркестратора.
• Для 99 % разработчиков хватает линалгебры, softmax, градиентов и PyTorch; остальное — инженерия данных, трюки и эксперименты.

Репозиторий the-litte-book-of/linear-algebra на GitHub.
Эпиграф Жана Дьёдонне: «Линейная алгебра — почти самая элементарная теория, хотя преподаватели и авторы учебников на протяжении поколений затемняли её простоту чудовищными выкладками с матрицами».

Меню навигации, вход, настройки внешнего вида, поиск и другие стандартные элементы GitHub опущены.

• Линейная алгебра считается глубокой и полезной, но базовая механика скучна.
• Многие советуют начинать с геометрической интуиции и визуализации (3Blue1Brown, «Wild Linear Algebra», mini-book photon_lines).
• Книга Axler «Linear Algebra Done Right» и курс Hefferon хвалятся за строгий, но понятный подход.
• Практика в графике/3D, экономике, машинном обучении и сжатии JPEG делает тему мотивирующей.
• Сообщество жалуется на плохое преподавание и просит больше визуальных объяснений, меньше «так надо».

Байес

$$P(A|B)=\frac{P(B|A)P(A)}{P(B)}$$ Обновляем вероятность гипотезы при новых данных.

def bayes(p_d, p_t_d, p_t_nd):
    p_t = p_t_d*p_d + p_t_nd*(1-p_d)
    return p_t_d*p_d / p_t

Энтропия

$$H(X)=-\sum_x P(x)\log P(x)$$ Измеряем неопределённость распределения.

import numpy as np
H = lambda p: -np.sum(p*np.log(p, where=p>0))

KL-дивергенция

$$D_{\text{KL}}(P|Q)=\sum_x P(x)\log\frac{P(x)}{Q(x)}$$ Сколько бит «лишних» нужно, если вместо истинного распределения $P$ использовать $Q$.

Кросс-энтропия

$$H(P,Q)=-\sum_x P(x)\log Q(x)$$ Используется как лосс в классификации.

Линейная алгебра

Линейное преобразование

$$\mathbf{y}=A\mathbf{x}$$ Матрица $A$ переводит вектор $\mathbf{x}$ в пространство признаков.

Собственные значения и векторы

$$A\mathbf{v}=\lambda\mathbf{v}$$ Направления, вдоль которых преобразование лишь растягивает/сжимает.

SVD

$$A=U\Sigma V^\top$$ Разложение на ортогональные и диагональные матрицы; основа PCA и рекомендательных систем.

Оптимизация

Градиентный спуск

$$\theta_{t+1}=\theta_t-\eta\nabla_\theta J(\theta)$$ Шагаем против градиента, чтобы минимизировать функцию потерь $J$.

Backprop

$$\frac{\partial L}{\partial W^{(l)}}=\delta^{(l)}(a^{(l-1)})^\top$$ Цепное правило для обучения нейросетей.

Функции потерь

MSE

$$\text{MSE}=\frac{1}{n}\sum_i (y_i-\hat y_i)^2$$ Классика регрессии.

Кросс-энтропия

$$L=-\sum_i y_i\log \hat y_i$$ Стандарт для классификации.

Продвинутые темы

Диффузия

$$q(x_t|x_{t-1})=\mathcal N(x_t;\sqrt{1-\beta_t}x_{t-1},\beta_t I)$$ Постепенное добавление шума и обратное восстановление.

Свертка

$$(f*g)[n]=\sum_m f[m]g[n-m]$$ Извлечение локальных паттернов в CNN.

Softmax

$$\text{softmax}(z_i)=\frac{e^{z_i}}{\sum_j e^{z_j}}$$ Превращает логиты в вероятности.

Attention

$$\text{Attention}(Q,K,V)=\text{softmax}\left(\frac{QK^\top}{\sqrt d_k}\right)V$$ Взвешенная сумма значений по релевантности запроса и ключей.

---

Краткий конспект ключевых уравнений ML: от вероятностей до трансформеров, с кодом и интуицией.

• @dkislyuk и @morleytj критикуют формат «списка формул» без связного объяснения и советуют читать оригинальную теорию Шеннона.
• @cl3misch нашёл баг в коде энтропии из-за неинициализированных значений и несоответствие формулы кросс-энтропии.
• @dawnofdusk и @cgadski хвалят полноту материала как удобную шпаргалку для быстрого погружения.
• @bee_rider и @calebkaiser обсуждают применение сингулярных чисел и собственных значений в LLM и LoRA.