# Джелани Нельсон: «Почему алгоритмы из 70-х актуальны для ИИ?»

Источник: https://www.youtube.com/watch?v=sN_t0Nm6Rmk
Канал: The TWIML AI Podcast
Опубликовано: 15.04.2021

---

## Теория вычислений как искусство: беседа с Джелани Нельсоном
[[JUMP:0:00]]

Джелани Нельсон — профессор группы теории вычислительных систем в Калифорнийском университете в Беркли — в рамках подкаста The TWIML AI Podcast обсудил роль теоретической информатики в современном мире. Ученый рассказал о своем пути в науку, применении алгоритмов сжатия данных в машинном обучении и важности образовательных инициатив в Эфиопии.

### 🧠 От видеоигр к алгоритмической теории
[[JUMP:0:37]]

Интерес Нельсона к информатике начался в детстве с видеоигр: на свой четвертый день рождения он получил Nintendo Entertainment System. В средней школе он самостоятельно изучил HTML, а в старших классах — C++ и основы программирования.

*   **Академический путь:** Будучи студентом MIT, он решил получить двойную специализацию по математике и CS.
*   **Спортивное программирование:** Настоящий интерес к теоретической информатике пробудился у Нельсона во время участия в соревнованиях типа TopCoder. В студенческие годы он мог посвящать решению алгоритмических задач по 8–10 часов в день.
*   **Специализация:** После получения степени магистра в MIT он остался там же для работы над PhD, сосредоточившись на алгоритмах, скетчинге (sketching) и потоковой обработке данных (streaming).

### 📉 Скетчинг, стриминг и dimensionality reduction
[[JUMP:4:09]]

Работа Нельсона лежит на стыке теории и практического машинного обучения. Он специализируется на создании алгоритмов, которые позволяют эффективно работать с огромными объемами данных при ограниченных ресурсах.

*   **Скетчинг:** Это способ сжатого представления данных, позволяющий отвечать на запросы с использованием сублинейного объема памяти. По словам ученого, для многих задач потоковой обработки использование рандомизированных (вероятностных) алгоритмов является единственным способом достичь высокой эффективности.
*   **Пример: приближенный счетчик Морриса:** Алгоритм, разработанный Робертом Моррисом в 1970-х годах для Unix, позволяет хранить значения счетчиков с высокой точностью, используя логарифмический объем памяти. Сегодня этот подход применяется в Redis для политик вытеснения кэша (least frequently used).
*   **Снижение размерности (Johnson-Lindenstrauss Lemma):** Лемма Джонсона-Линденштрасса (1984) утверждает, что $n$ векторов в высокоразмерном пространстве можно отобразить в пространство меньшей размерности, сохранив при этом попарные евклидовы расстояния с заданной точностью. Это критически важно для ускорения обучения классификаторов, кластеризации и аппроксимации PCA.

### 🎓 Образование: Aiti и алгоритмическое мышление
[[JUMP:27:41]]

Нельсон является одним из основателей некоммерческой программы (летний лагерь) для одаренных школьников в Эфиопии. Программа направлена на обучение алгоритмам студентов, у которых ранее не было доступа к академическому CS.

*   **Эффективность программы:** С 2011 года выпускники программы поступают в ведущие мировые вузы, включая MIT, Гарвард и Стэнфорд. Многие из них продолжают обучение в аспирантуре или работают в крупных IT-компаниях, таких как Google и Facebook.
*   **Педагогический подход:** Ученый утверждает, что лучший способ увлечь детей — это показать им неочевидность простых вещей. Например, он демонстрирует, что привычный «школьный» метод умножения чисел не является оптимальным, и знакомит учеников с алгоритмом Карацубы, имеющим меньшую вычислительную сложность.

По мнению Нельсона, даже если практикующим специалистам не всегда нужны глубокие теоретические знания для написания кода, понимание основ — таких как динамическое программирование или алгоритмы скетчинга — значительно расширяет их возможности при решении сложных оптимизационных задач.