Разбираемся в ML без воды: от базы до Attention. Часть 12: Понижение размерности и PCA

Все публикации подряд на Хабре

Ловим музу за клавиатуру: как айтишнику стать автором Что умеет Midjourney в 2026? Мой немного грустный разбор этого шикарного инструмента Никто не любит писать тесты, но ИИ может исправить это IPv8 выглядит как мечта. Поэтому почти наверняка не взлетит Производители вернули в продажу материнки с DDR3. Что происходит? Управление агентом с телефона через Telegram теперь в KodaCode От координации к лидерству: как меняется роль руководителя разработки Я сделала родителям бизнес вместо пенсии: зарабатываем 70 тысяч, мама не даёт продать В три раза быстрее приемка товара и оптимизация трудозатрат на 73%: как «РСТ-Инвент» помог Gulliver Group ИИ-шечный мир победил? О влиянии искусственного интеллекта на игропром Кремль снижает давление на Телеграмм пока Европа строит интернет по паспорту Как CEO, CTO и CIO за 8 часов собрали ИИ-директора, который умеет держать позицию под давлением Как (не) потерять домен за выходные Вместо 8 разных VPS: как я организовал практику студентам на одном сервере Почему твой Open Source проект не замечают? R&D: искусство управления неопределенностью в разработке AI-дефляция: вакансий для разработчиков больше, а рост зарплат — худший за 15 лет Мы отдали управление роботами OpenClaw. Что из этого вышло Галактический ID: система идентификации для всех форм разумной жизни Шесть основ бизнес-анализа: начинаем с вопроса «Кто в игре?» Код-ревью, в котором дело не в коде Данные переехали. Команда — нет Системной подход к сдаче OSWE в 2025 Почему комната управления реактором покрашена в цвет морской пены 4 YAML-файла вместо PySpark: как аналитикам строить пайплайны без разработчиков LLM-агент для поиска свободных доменов: автоматизируем подбор Когда, зачем и как правильно начинать новую сессию в Claude Code? Как я заставил нейросеть писать макросы для FreeCAD Анатомия ИИ‑агента для подбора персонала. От тысячи резюме к топ‑10 за минуты Опыт разработчика как экономика внимания Автономность как точка невозврата: кто будет субъектом в цифровом будущем Обучение ИИ в «диких» условиях: как рутинные действия превращаются в датасеты Как измерить LLM для задач кибербеза: обзор открытых бенчмарков Где хранить код? Сравнение GitHub, GitLab и Bitbucket Математика объясняет, почему нормальное распределение встречается повсюду Почему ваш FinOps не работает: 12 тезисов от практиков Как подписать проектную документацию УКЭП с использованием бесплатных лицензий Pilot Адаптивное администрирование Sigla Vision Я грузил уран в бочки, а потом 20 лет строил ИТ в атомной отрасли Чем позвонить с Эвереста? История и обзор спутниковой связи. Часть 2 Как языковая модель помогает контролировать качество инструктажей по охране труда в металлургии Как не передать на desktop свой IP в РКН Анатомия SAP Privileges: как устроено управление правами в macOS MoneyDev: Сказка про три главных слова Обновлённый токенизатор видео K-VAE 2.0 от Сбера Как сделать диспетчеризацию дома на 1284 квартиры почти бесплатно Как мы разогнали железную дорогу Мы дали агентам рутину. Теперь надо решить — что делать с освободившимся временем Токсичный контент, промпт-хакинг и защита ИИ — всё о Guardrails для LLM Умный город начинается с точного взгляда: как «Фалькон Тех» меняет пространство к лучшему Навайбкодил приложение для анализа графов Почему Дюну так интересно читать? Упрощаем работу с рутиной или как стать Гендальфом Белым Деконструкция Go: CPU, RAM и что там происходит. Go Assembler база. Часть 1.1 Какие профессии исчезнут из-за ИИ, а какие появятся? И что с этим делать Как мы построили IT-отдел, где хочется расти: архитектурные встречи, прозрачные метрики и книжные подарки Rufler: Делаем из Claude Code автономный рой через один YAML-конфиг Sing-box и белый список приложений Как построить надёжный обмен сообщениями в микросервисах: лучшие практики для enterprise OpenAI строит MLM-пирамиду, а McKinsey и Accenture помогают ей в этом Дом, который не построил Фишер (Часть 2) «Сверхзвуковой математик» против «Вдумчивого логиста»: битва алгоритмов 3D-упаковки Мультимодальные модели – грубый и дорогой инструмент Разговоры ничего не стоят. Код тоже Проверки физических лиц: с кого начнет ФНС Топ-10 бесплатных нейросетей для создания видео в 2026 году Первые слои кода: как наши решения сегодня определяют архитектуру ИИ на десятилетия Разработка нового статического анализатора: PVS-Studio JavaScript Поиск уязвимостей ПО: базовый минимум или роскошный максимум Почему оценка персонала не работает как инструмент управления Как мы разработали ИИ-ассистента и сократили рутину продуктовой команды на 50% Как я ушел из найма, нажарил косточек и продал на маркетплейсах на 168 млн в год Когда 1С:ERP уже внедрена, а нормального производственного плана всё ещё нет Как я сделал Claude мультимодальным, подключив к нему Qwen Omni Как приглашение на вакансию мечты превращается в атаку Infrastructure as Code: философия и лучшие практики IaC Тестируем Yandex Code Assistant на задаче, в которой нужно хранить секреты nxs-universal-chart v3.0: новое поколение универсального Helm-чарта Callback Injection: Техника, которая отправила Microsoft Defender в глухой нокаут «Все идеи на стол»: митап как способ вывести проект из тупика Сегодня я узнал нечто новое о GPU благодаря багу в своей игре Как заставить LLM ̶ ̶г̶а̶л̶л̶ю̶ ̶ эволюционировать Карта событий как фундамент аналитики: практический кейс для E-commerce Что выбрать для AI: x86, ARM или RISC-V? Дайджест железа за март Роль соматических мутаций в развитии аутоиммунных заболеваний: путь к избирательной терапии Mythos от Anthropic — тревожный сигнал для всех, а не только для банков Guardrails для LLM на Java: как приручить промпт‑инъекции и токсичные ответы Green-VLA: как мы собрали VLA-модель для реального антропоморфного робота и не потеряли обобщение Финансовая гонка вооружений: почему умные люди добровольно в ней участвуют Эра ИИ-агентов наступила: выбираем лучшего цифрового сотрудника # Практический опыт внедрения WinCC Redundancy на производственном предприятии Сделал MVP за 3 дня, а потом неделю прикручивал оплату. Оно того стоило? Физика против Маска: почему Starship V3 может оказаться ещё одной катастрофой Нефть Венесуэлы: крупнейшие запасы в мире, но не крупнейшая нефтяная держава JPA 4. Переосмысление Hibernate Почему зеркальная фотокамера Nikon D5 десятилетней давности идеально подошла для миссии «Артемида-2» Проект «Уровень-Спутник» или как мы сделали платформу для гидрологов «Замедлиться, чтобы ускориться»: почему ИИ повышает цену ошибок в требованиях и архитектуре Как с нуля поднять трафик IT-компании на 1657% при бюджете 55 тыс. и выжить Pixel-perfect Downsampling — идеальная отрисовка 50 миллионов точек без потерь

ysrgsyn · 2026-06-23 · via Все публикации подряд на Хабре

Средний

8 мин

В предыдущей части мы разобрали градиентный бустинг — финального босса в классическом обучении с учителем. Мы научились строить мощные ансамбли, которые выжимают максимум из табличных данных. Кажется, что на этом можно ставить точку и прыгать в современный мир нейросетей и Deep Learning.

Но до этого момента мы жили в идеальной теплице: у нас всегда была разметка (тот самый target, который нужно предсказать), а количество признаков в таблицах было разумным. В реальности все иначе. Данных часто слишком много, в них куча шума, а правильных ответов никто не разметил.

В этой части мы закроем очередную проблему в классическом ML — столкнемся лицом к лицу с проклятием размерности (curse of dimensionality). Поймем, как сжимать многомерные пространства, не теряя важный смысл, и как заставить машину самостоятельно группировать объекты в кластеры, вообще не имея готовых классов.

Проклятие размерности

Хорошо ли иметь много столбцов в датасете? На первый взгляд, кажется, да. Чем больше признаков, тем больше потенциально полезной информации может содержаться в данных. Закономерностей найдется больше, модель (хоть дерево, хоть линейная регрессия) получит больше информации для поиска закономерностей. Одним словом — профит. И это, в целом, истина.

Но у монетки есть и обратная сторона, по имени проклятием размерности (Curse of Dimensionality). Этот термин придумал математик Ричард Беллман для динамического программирования, но он идеально вписался и в мире машинного обучения. Разберем в чем его суть:

При увеличении количества признаков возникают несколько неприятных моментов.

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

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

Во-вторых, данные становятся "редкими": представьте квадрат со стороной 1.

В 1D это отрезок длины 1.
В 2D — квадрат площадью 1.
В 10D — гиперкуб объёма 1.

Теперь возьмём маленькую область со стороной 0.1.

В 1D её "объём" равен 0.1, или 10% от всего пространства;
В 2D: 0.01, или же 1%;
В 10D: 10 $^{-10}$ , то есть 0....01%.

Получается, общее пространство вокруг разрастается до гигантских масштабов, а область с нашими данными превращается в микроскопическую точку. Вокруг остается один пустой "воздух". Чтобы заполнить этот 10-мерный куб данными с той же плотностью, что и обычный отрезок, нам понадобится экспоненциально больше строк в датасете. Откуда найти столько данных? — непонятно.

Из этого вытекает третья проблема: расстояния теряют свой смысл.

В предыдущих статьях мы уже разбирали несколько моделей, которые напрямую используют понятие геометрической близости (например, KNN или SVM). Но в высокой размерности появляется концентрация расстояний:

$\frac{d_{\max}-d_{\min}}{d_{\min}}\to 0$

Самая дальняя точка оказывается почти на таком же расстоянии, как и самая близкая. То есть понятие "сосед" становится менее информативным.

Также, есть и четвертая проблема: возможность переобучения:

Если признаков много, модель получает огромную свободу.

Например у нас 100 объектов и 100500 признаков. Модель может найти гиперплоскость, которая идеально разделит обучающую выборку, но на новых данных всё развалится.

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

Понижение размерности

Как мы увидели, проблем у высокой размерности достаточно много. И один из классических способов борьбы с ними звучит почти гениально: раз высокая размерность создаёт проблемы, давайте её понизим.

Однако делать это нужно со вкусом. Самый грубый подход иногда действительно работает: мы можем без сожалений удалить столбец с группой крови предыдущих владельцев из датасета, который используем для предсказания цен на дома. Иными словами, можно и нужно избавляться от признаков, которые вообще не связаны с поставленной задачей.

И да, формально это тоже является понижением размерности, активно используется на практике и называется отбором признаков (feature selection). Минус такого подхода заключается в том, что в конечном счёте мы своими руками избавляемся от части информации.

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

Посмотрим как это работает, на примере ветерана машинного обучения — метода PCA.

Principal component analysis (PCA)

Итак, Метод главных компонент (Principal component analysis, PCA) — это способ преобразовать исходные признаки так, чтобы получить новое пространство, в котором информация "упакована" более компактно.

Возьмем датасет с автомобилями. Если у всех машин пробег равен ровно 100500 км, этот признак, очевидно, бесполезен. Но если пробег варьируется от 5000 до 100000 км, разброс огромен, и этот признак уже может быть информативным. PCA ищет такие направления в данных, вдоль которых этот разброс максимален, и объявляет их новыми осями — главными компонентами.

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

Посмотрим как это работает с математической точки зрения.

Возьмем датасет (матрицу) размерности $n \times d$ , где n — количество объектов (строк), а — количество признаков (столбцов).

Как мы уже поняли, речь будет пойти о дисперсии. Потому, изначально хочется центрировать данные (вычесть из каждого признака его среднее значение по выборке). Делается это крайне просто: для каждого признака вычисляем среднее

$\mu_{j} = \frac{1}{n}\sum_{i=1}^{n}x_{ij}$

И отнимаем её от всех значений $x_j := x_j - \mu_j$ . Тем самым центр превращается в начало координат. Теперь надо думать на какую прямую лучше всего спроецировать наши точки. Чтобы не путаться в обозначениях, напишем полученное как , где — центрированное.

Итак, прямую можно задать единичным вектором $||\omega|| = 1, \ \omega \in \mathbb{R}^d$ . А проекции точки на прямую имеют вид $z_i = x_{i}\omega$ , где $i = 1, \dots, n$ . А мы хотим найти такое направление, при котором разброс этих проекций был максимальным, то есть задача выглядит так:

$\max_{||\omega||=1}\text{Var}(z)$

И вот здесь нам как раз пригодится центрирование, ибо дисперсия $\text{Var}(z)$ раскроется просто как

$\text{Var}(z) = \frac{1}{n}\sum_{i=1}^{n}z_i^2 = \frac{1}{n} z^Tz$

Подставляя $z = X_c\omega$ , получим

$\text{Var}(z) = \frac{1}{n}(X_c\omega)^TX_c\omega = \frac{1}{n}\omega^TX_c^TX_c\omega$

Вспоминаем ковариационную матрицу: $\Sigma = X^TX$ . Получаем итоговую задачу PCA:

$\max_{||\omega||=1}\omega^T\Sigma\omega.$

Дальше все достаточно естественно — люди мы простые, видим условную задачу, вводим Лагранжиан (подробнее об этом было в части 8).

$\mathcal{L}(\omega, \lambda) = \omega^T\Sigma\omega - \lambda(\omega^T\omega - 1)$

По стандартному методу, берем производную по $\omega$ , приравниваем к нулю:

$2\Sigma\omega - 2\lambda\omega = 0$

Отсюда получаем $\Sigma\omega = \lambda\omega$ . И это не просто уравнение, это классическое определение собственного вектора. Получается, что $\omega$ собственный вектор матрицы $\Sigma$ , а $\lambda$ — собственное значение.

Теперь мы получили главную идею: $\omega^T\Sigma\omega = \lambda$ , если $\omega$ — собственный вектор. А значит для задачи максимизации мы просто берем собственный вектор с наибольшим собственным значением.

То есть, весь PCA это:

Вычислить ковариационную матрицу для центрированных данных;
Найти собственные векторы ковариационной матрицы;
Отсортировать их по собственным значениям;
Взять первые (число компонент);
Умножать данные на эти векторы и получить сжатый датасет размера $\mathbb{R}^{n \times k}$ .

Казалось бы, всё отлично, но раз мы занимаемся понижением размерности, то фич у нас многовато. А из этого следует, что ковариационная матрица будет огромной. Именно поэтому, на практике почти всегда обходятся без вычисления ковариационной матрицы, а используют метод под названием SVD.

Singular Value Decomposition / Сингулярное разложение

Суть SVD заключается в том, что мы можем разложить матрицу на вращение, сжатие и на ещё одно вращение.

Где

Если подставить такое разложение в ковариационную матрицу $\Sigma = X^TX$ , получим

$\Sigma = (USV^T)^T(USV^T) = VS^TU^TUSV^T$

Вспомним, что матрица называется ортогональной, если , где — единичная матрица. Поэтому,

$\Sigma = VS^TISV^T = VS^TSV^T$

Так как матрица диагональная, то , а само произведение дает нам диагональную матрицу, с элементами $s_{ij} = \lambda_{i}$ , при , и $s_{ij} = 0$ , при $i\ne j$ . Обозначим эту матрицу собственных значений как $\Lambda$ . Стало быть,

$\Sigma = V\Lambda V^T$

Остается финальный шаг: умножим обе части этого равенства на матрицу справа:

$\Sigma V=V\Lambda V^{T}V$

Так как матрица V ортогональна, то и , а значит

$\Sigma V= V \Lambda$

Фактически, это то же самое уравнение $\Sigma \omega = \lambda \omega$ , к которому мы пришли через Лагранжиан.

Матрица , которую SVD берет напрямую из наших центрированных данных $X_{c}$ , состоит из тех самых собственных векторов ковариационной матрицы, которые мы искали для максимизации дисперсии. То есть таким образом мы пропустили вычисление $X^{T}X$ .

Посмотрим на разницу:

Метод	Сложность по времени	Сложность по памяти	Проблема
1. Через ковариацию	$O(n \cdot d^2 + d^3)$		Кубическая сложность
2. Полный SVD	$O(n \cdot d^2)$		Часто большое

Как говорится, хрен редьки не слаще. Однако, всё это время мы брали все собственные вектора, а затем оставили из них первые . Для решения этой проблемы существует метод Ланцоша.

Метод Ланцоша

В чем суть? Раз мы не обязаны найти все собственные векторы огромной матрицы, мы можем спроецировать её на подпространство гораздо меньшей размерности k, где и найдем нужное нам количество.

Пусть у нас есть гигантская ковариационная матрица $\Sigma = X_c^T X_c$ размера $d \times d$ . Мы физически не можем её вычислить и хранить в памяти. Наша цель — найти её первый собственный вектор $\omega _{1}$ (главную компоненту).

Возьмем случайный единичный вектор размера и умножим его на ковариационную матрицу справа. Назовем результат как.

$v = \Sigma q = X^T_c(X_cq_1)$

Пока что произошли две быстрые умножения, т.е. компьютер не вычислил матрицу $\Sigma$ .

Теперь измерим, какая часть от вектора $\Sigma q_1$ сонаправлена с нашим исходным вектором ․ Для этого найдем их скалярное произведение и обозначим полученное число как $\alpha_{1}$ :

$\alpha_1 = q_1^T\Sigma q_1$

Также вычтем из $\Sigma q_1$ его проекцию на $q_{1}$ , чтобы получить строго перпендикулярный остаток. Назовем этот остаток вектором $r_{1}$ :

$r_1 = \Sigma q_1 - \alpha_1q_1$

Посмотрим на следующее произведение:

$q_1^Tr_1 = q_1^T(\Sigma q_1 - \alpha_1q_1) = q_1^T\Sigma q_1 - \alpha_1(q_1^Tq_1)$

Так как $q_{1}$ единичный (), а $q_1^T \Sigma q_1 = \alpha_1$ , то получаем:

$q_1^Tr_1 = \alpha_1 - \alpha_1 = 0$

Как и ожидалось, вектор $r_{1}$ перпендикулярен $q_{1}$ .

Обозначим длину вектора $r_{1}$ как $\beta_1$ ( $\beta_1 = \Vert r_1 \Vert\$ ). Отнормируем его, чтобы получить второй единичный вектор:

$q_{2}=\frac{r_{1}}{\beta_{1}}\implies r_{1}=\beta_{1}q_{2}$

Подставим это обратно в наше уравнение:

$\beta_{1}q_{2}=\Sigma q_{1}-\alpha_{1}q_{1}\implies \Sigma q_{1}=\alpha_{1}q_{1}+\beta_{1}q_{2}$

Теперь у нас есть два взаимно перпендикулярных вектора $q_{1}$ и $q_{2}$ . Умножим матрицу $\Sigma$ на наш новый вектор $q_{2}$ : $\Sigma q_{2}$

Аналогично предыдущему шагу, этот вектор будет как-то проецироваться на уже имеющиеся у нас направления $q_{1}$ и $q_{2}$ . Найдем эти проекции:

Проекция на $q_{2}$ : $\alpha_2 = q_2^T \Sigma q_2$
Проекция на $q_{1}$ : $q_1^T \Sigma q_2$

По свойствам транспонирования $q_1^T \Sigma q_2 = (\Sigma q_1)^T q_2$ . Подставим сюда найденное нами выражение для $\Sigma q_1$ :

$(\Sigma q_{1})^{T}q_{2}=(\alpha_{1}q_{1}+\beta_{1}q_{2})^{T}q_{2}=\alpha_{1}(q_{1}^{T}q_{2})+\beta_{1}(q_{2}^{T}q_{2})$

Итак, $q_{1}$ и $q_{2}$ перпендикулярны, длина $q_{2}$ равна 1. Нетрудно заметить, что наше выражение превращается просто в число $\beta_{1}$ .

Красота симметрии: проекция нового вектора $\Sigma q_2$ на самый первый вектор $q_{1}$ оказалась в точности равна числу $\beta _{1}$ , которое мы посчитали на прошлом шаге!

Теперь снова вычтем из $\Sigma q_2$ обе эти проекции, чтобы получить следующий перпендикулярный остаток $r_{2}$ :

$r_{2}=\Sigma q_{2}-\alpha_{2}q_{2}-\beta_{1}q_{1}$

Измеряем длину остатка $\beta_2 = \Vert r_2 \Vert$ и находим следующий единичный вектор :

$q_3 = \frac{r_2}{\beta_2} \implies r_2 = \beta_2q_3$

Отсюда получим

$\Sigma q_2 = \beta_1q_1 + \alpha_2q_2 + \beta_2q_3$

Аналогично для :

$\Sigma q_n = \beta_{n-1}q_{n-1} + \alpha_nq_n + \beta_{n}q_{n+1}$

То есть вектор $\Sigma q_n$ зависит только от $q_{n-1}$ и $q_{n+1}$ .

Запишем систему уравнений в общем виде для векторов. Соберем векторы $q_1, \dots, q_k$ в прямоугольную матрицу $Q_{k}$ размера $d \times k$ .

Тогда всю эту цепочку уравнений можно записать как одно матричное равенство:

$\Sigma Q_{k}=Q_{k}T_{k}$

Матрица $T_{k}$ заполняется нашими числами $\alpha$ и $\beta$ согласно уравнению. Поскольку каждый шаг зависит только от двух соседей, числа ложатся строго по трем диагоналям, а все остальные элементы матрицы нулевые:

$T_{k}=\left(\begin{matrix}\alpha {1}&\beta {1}&0&0\\ \beta {1}&\alpha {2}&\beta {2}&0\\ 0&\beta {2}&\alpha {3}&\beta {3}\\ 0&0&\beta {3}&\alpha {4}\end{matrix}\right)$

Умножим уравнение $\Sigma Q_k = Q_k T_k$ на $Q_{k}^{T}$ слева. Так как все векторы строго перпендикулярны друг другу, то (единичная матрица размера $k \times k$ ). Получаем:

$Q_{k}^{T}\Sigma Q_{k}=T_{k}$

Мы с нуля вывели, как превратить гигантскую ковариационную матрицу в крошечную трехдиагональную матрицу размера $k \times k$ .

Теперь компьютеру не составит труда собственные векторы $s_{i}$ этой матрицы $T_{k}$ :

$T_{k}s_{i}=\theta_{i}s_{i}$

Но давайте поймем куда делись наши "омеги и лямбды".

Подставим вместо $T_{k}$ выражение $Q_k^T \Sigma Q_k$ :

$(Q_{k}^{T}\Sigma Q_{k})s_{i}=\theta_{i}s_{i}$

Умножим на $Q_{k}$ слева:

$Q_k Q_k^T \Sigma Q_k s_i = \theta_i Q_k s_i$

Поскольку вектор $\Sigma Q_k s_i$ по определению метода Ланцоша целиком лежит внутри нашего подпространства $Q_{k}$ , операция проекции $Q_{k}Q_{k}^{T}$ оставляет его неизменным и полностью исчезает. Получим:

$\Sigma (Q_{k}s_{i})=\theta_{i}(Q_{k}s_{i})$

Сравниваем это с нашим Лагранжианом $\Sigma \omega = \lambda \omega$ :

Наши искомые омеги (собственные векторы) — это просто $\omega_i = Q_k s_i$ .
Наши лямбды (собственные значения) — это $\lambda_i = \theta _{i}$ .

Заключение

Напоследок, добавим этот метод в нашу таблицу для сравнения.

Метод	Сложность по времени	Сложность по памяти
1. Через ковариацию	$O(n \cdot d^2 + d^3)$
2. Полный SVD	$O(n \cdot d^2)$
3. Метод Ланцоша	$O(n \cdot d \cdot k)$	$O(n \cdot k + d \cdot k)$

Думаю, комментарии излишни.

На если запустить алгоритм в таком виде, то через 3–4 шага из-за микроскопических погрешностей в вычислениях свойство ортогональности векторов начинает теряться (в численных методах это называют loss of orthogonality). Новые векторы перестают быть перпендикулярными самым первым, и алгоритм ломается.

Именно поэтому на практике (включая тот же scikit-learn и с его ARPACK) никто не запускает метод Ланцоша "в лоб". К нему обязательно прикручивают так называемую процедуру переортогонализации.

Её смысл в том, что алгоритм заставляют принудительно проверять и выравнивать перпендикулярность нового вектора не только по отношению к двум соседям, а вообще ко всем ранее найденным векторам.

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

На практике встречаются и другие методы, но мы пока остановимся на этих. А также существуют и другие методы понижения размерности в целом. О них и поговорим в дальнейшем!

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

Все публикации подряд на Хабре

Проклятие размерности

Понижение размерности

Principal component analysis (PCA)

Singular Value Decomposition / Сингулярное разложение

Метод Ланцоша

Заключение