Один, мы здесь

Вы можете прочитать обзор курса численной линейной алгебры по материалам блога fast.ai. Курс изначально преподавался в рамках исследовательского проекта по науке о данных в Университете Сан-Франциско. Видеозаписи курса доступны на YouTube (обратите внимание, что кодировка записок и номера видео не совпадают, поскольку некоторым запискам требуется более одного видео для покрытия).

Вы можете задать вопросы по курсу на нашем форуме fast.ai.

Примечание: В будущих курсах будет больше кода.

Зачем изучать численную линейную алгебру?

Ключевой вопрос этого курса: как мы можем выполнять матричные вычисления с приемлемой скоростью и приемлемой точностью?

Список десяти самых важных научных и инженерных алгоритмов 20-го века включает методы разложения матриц. Он также включает QR-алгоритм, который мы рассмотрим, и пример итерационного метода Крылова (см. здесь).

Источник: Десять алгоритмов

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

• использование памяти;
• скорость;
• точность;
• расширяемость / параллелизм.

Обычно приходится искать компромисс между этими категориями.

Мотивация

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

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

Понимание того, как на самом деле работают алгоритмы. Помогает при отладке и ускорении решений.

Матричные вычисления

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

• умножение матриц и тензоров;
• разложение матриц.

Таким образом, в основном мы будем комбинировать матрицы, а затем снова разделять их!

Умножение матриц и векторов

Ниже приведена матрица, которая показывает вероятность перехода из одного состояния здоровья в другое за один год. Если текущее состояние здоровья группы составляет:

• 85% без симптомов;
• 10% с симптомами;
• 5% больных СПИДом;
• 0% смертей.

Каков процент каждого состояния здоровья через год?

Источник: Концепции марковских цепей

Ответ

import numpy as np

# Упражнение: используйте Numpy для вычисления ответа на вышеизложенное

# array([[ 0.765 ,  0.1525,  0.0645,  0.018 ]])

Умножение матриц на матрицы

Источник: Простые приложения линейной алгебры в реальном мире [https://www.mff.cuni.cz/veda/konference/wds/proc/pdf06/WDS06_106_m8_Ulrychova.pdf]

Ответ

# Упражнение: Используйте Numpy для выполнения вычислений, указанных выше

'''
array([[ 50. ,  49. ],
       [ 58.5,  61. ],
       [ 43.5,  43.5]])
'''

Изображения данных

Изображения можно представить в виде матриц.

Источник: Адам Гейтгей [https://medium.com/@ageitgey/machine-learning-is-fun-part-3-deep-learning-and-convolutional-neural-networks-f40359318721]

Свёрточные нейронные сети

Свёрточные нейронные сети (CNN) являются основой глубокого обучения, которое привело к огромному прогрессу в распознавании изображений за последние несколько лет. В настоящее время они также всё чаще используются для обработки речи, например, перевод речи Facebook AI в девять раз быстрее, чем RNN (в настоящее время наиболее распространённый метод перевода речи).

Теперь компьютеры точнее людей в распознавании изображений.

Источники: https://blogs.nvidia.com/blog/2014/09/07/imagenet/, https://nbviewer.jupyter.org/github/fastai/numerical-linear-algebra-v2/blob/master/nbs/convolution-intro.ipynb

Вы можете рассматривать свёртку как особый вид умножения матриц. Ниже приведены три изображения из отличной статьи блога «Различные точки зрения на CNN» [https://medium.com/impactai/cnns-from-different-viewpoints-fab7f52d159c], написанной студентами fast.ai:

Свёртка применяет фильтр к каждой части изображения:

Точка зрения нейронной сети:

Точки зрения умножения матриц:

Давайте посмотрим в этом ноутбуке [https://nbviewer.jupyter.org/github/fastai/numerical-linear-algebra-v2/blob/master/nbs/convolution-intro.ipynb], как использовать свёртку для обнаружения границ (первоначально из курса глубокого обучения fast.ai [http://course.fast.ai/] ).

Разложение матриц

Мы обсудим матричное разложение на каждом занятии этого курса и рассмотрим следующие примеры в будущих занятиях:

Моделирование тем (NMF и SVD, SVD использует QR) набор документов может быть представлен в виде матрицы терминов документа.

Источник: Введение в поиск информации [http://player.slideplayer.com/15/4528582/#]

Удаление фона (сокращение SVD):

Источник: Учебник NMF [http://perso.telecom-paristech.fr/~essid/teach/NMF_tutorial_ICME-2014.pdf]

Снижение шума (робастное PCA, использующее SVD):

Этот пример взят из блога Жана Коссаифи [http://jeankossaifi.com/blog/rpca.html].

Алгоритм PageRank Google (разложение по собственным значениям):

Источник: Что такое PageRank? [http://computationalculture.net/article/what_is_in_pagerank]

Другие списки факторизации и приложений [https://sites.google.com/site/igorcarron2/matrixfactorizations].

Точность

Арифметика с плавающей точкой

Чтобы понять точность, нам сначала нужно понять, как компьютер (конечный и дискретный) хранит числа (бесконечные и непрерывные). Проблема: математика непрерывна и бесконечна, а компьютеры дискретны и конечны

Компьютеры имеют два ограничения в представлении чисел:

• они не могут быть произвольно большими;
• между ними обязательно есть разница.

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

Как компьютер хранит числа:

IEEE двойная точность арифметики:

числа могут достигать 1,79 * 10^308, а наименьшие — 2,23 * 10^-308.

Интервал [1, 2] представлен дискретным подмножеством:

Интервал [2, 4] представляется как:

Масштаб с плавающей точкой не является равномерно распределённым.

Источник: «Вы никогда не думали, что вам нужно знать о плавающих точках, но вы будете вынуждены это сделать» (http://www.volkerschatz.com/science/float.html).

Машина ε — половина расстояния между двумя ближайшими числами. Это может варьироваться в зависимости от компьютера. В соответствии со стандартом IEEE двойной точности:

Два важных свойства операций с плавающими точками:

Для любого числа x и его ближайшего приближённого значения с плавающей точкой fl(x) разность между ними всегда меньше, чем машина ε относительно. Для некоторых ε, где:

Для любой операции (* обозначает любую операцию +, -, *, /), ⊛ — её приближение с плавающей точкой, для некоторых ε, где:

Это означает, что каждая операция с плавающей точкой точна до максимальной относительной ошибки, равной машине ε.

История

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

• фиксированная точка арифметики;
• логарифмические и полулогарифмические системы счисления;
• непрерывные дроби;
• рациональные числа;
• потенциально бесконечные строки рациональных чисел;
• индексные системы уровня;
• системы с фиксированной и плавающей косой чертой;
• 2-адические числа.

Для справки см. главу 1 «Руководства по операциям с плавающей точкой» (https://perso.ens-lyon.fr/jean-michel.muller/chapitre1.pdf) (бесплатно). Да, есть книга о плавающей точке из 16 глав!

Хронология операций с плавающей точкой

• До н. э. 1600: система вавилонских шестидесятичных чисел была самой ранней системой с плавающей точкой (Дональд Кнут). Использовалась шестидесятеричная система счисления для представления дробной части (если отношение двух чисел было степенью 60, они считались одинаковыми).
• 1630: правила скольжения. Работа только с мантиссой (основание 10).
• 1914: Леонардо Торрес и Кеведо использовали операции с плавающей точкой для описания электромеханической реализации аналитической машины Бэббиджа.
• 1941: первая настоящая современная реализация. Z3, компьютер Конрада Цузе. Использовал основание 2 с 14 битами мантиссы, 7 битами экспоненты и одним знаковым битом.
• 1985: опубликован стандарт двоичной арифметики с плавающей точкой IEEE 754-1985. Повышена точность, надёжность и портативность. Под руководством Уильяма Кахана.

«Было введено много разных методов для аппроксимации действительных чисел на компьютерах. Однако операции с плавающей точкой остаются наиболее часто используемым методом представления действительных чисел в современных компьютерах. Моделирование бесконечного непрерывного множества (действительные числа) с помощью конечного набора („машинных чисел“) — непростая задача: необходимо найти разумный компромисс между скоростью, точностью, динамическим диапазоном, удобством использования, реализацией и памятью. При правильном выборе параметров (основания, точности, экстремальных значений и т. д.) операции с плавающей точкой представляются очень хорошим компромиссом для большинства числовых приложений».

Хотя основание 2 (двоичное) кажется явным победителем для компьютеров, в разное время использовались различные основания:

• ранние машины PDP-10, Burroughs 570 и 6700 использовали основание 8;
• IBM FORTRAN использовал основание 16 для FORTRAN IV и FORTRAN 66;
• основание 10 использовалось для финансовых расчётов, карманных калькуляторов и Maple;
• SETUN, советский компьютер 1958 года, использовал основание 3 (преимущество: минимизация βxp для фиксированного максимального представимого числа β^p — 1, округление равно усечению).
• Основание 2 является наиболее распространённым. Причина: простота реализации. Исследования показывают (с неявным лидирующим битом), что это даёт лучшую наихудшую или среднюю точность по сравнению со всеми другими основаниями.

Условное действие и стабильность

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

«Стабильный алгоритм может дать правильный ответ почти для всех правильных задач». — Трефетен.

Условное воздействие: поведение возмущений математической задачи (например, метод наименьших квадратов).

Стабильность: поведение алгоритма, используемого для решения проблемы на компьютере (например, алгоритм наименьших квадратов, хаусхолдер, обратное замещение, гауссово исключение).

Пример: собственные значения матрицы:

import scipy.linalg as la

A = np.array([[1., 1000], [0, 1]])
B = np.array([[1, 1000], [0.001, 1]])

print(A)

print(B)

'''
[[    1.  1000.]
 [    0.     1.]]
[[  1.00000000e+00   1.00000000e+03]
 [  1.00000000e-03   1.00000000e+00]]
'''

np.set_printoptions(suppress=True, precision=4)

wA, vrA = la.eig(A)
wB, vrB = la.eig(B)

wA, wB
'''
(array([ 1.+0.j,  1.+0.j]), array([ 2.+0.j,  0.+0.j]))
'''

Обратите внимание: два свойства операций с плавающей точкой

Разница между действительным числом x и его ближайшим приближением с плавающей точкой fl (x) всегда меньше машины ε относительно.

Каждая операция с плавающей точкой +, -, ×, / имеет максимальную относительную погрешность, равную машине ε.

Мы увидим примеры:

• классический и исправленный Грамм-Шмидт для точности;
• Грамм-Шмидт против Хаусхолдера (два разных способа вычисления QR-разложения, ортогональность ответов);
• условия уравнения.

Приблизительная точность

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

Во многих случаях входные данные также могут быть не такими точными, поэтому использование входных данных и вычислений для поиска более высокой точности не имеет смысла.

Примеры:

• случайные структуры данных;
• фильтры Блума;
• HyperLogLog;
• локально чувствительное хеширование;
• пропустить списки;
• минимальные графики;
• минимальное хеширование.

Пример: фильтр Блума может использовать менее 10 бит каждого элемента для проверки членства в наборе с вероятностью ложного срабатывания 1%. Это обычно представляет собой сокращение использования памяти в тысячи раз.

|     |
| B   |
|____|

Ложноположительные результаты легко обрабатываются путём выполнения второго этапа (точного) тестирования для всех возвращённых элементов. Это особенно эффективно для редких элементов, так как может быть очень эффективным. Например, многие веб-браузеры используют фильтры Блума для создания списка заблокированных страниц (например, страницы с вирусами), поскольку заблокированные страницы составляют лишь небольшую часть всего Интернета. Ложноположительные элементы можно легко обработать, получив любой контент, возвращаемый фильтром Блума, и проверив его по полному точному списку с веб-сервиса. Случайные алгоритмы

• Алгоритм Каргера (минимальное разрезание графа)
• Случайный регрессионный анализ
• Метод Монте-Карло
• Случайное LU-разложение (метод Гаусса)
• Случайный SVD

Если мы готовы смириться с некоторой потерей точности, то обычно можем ускорить процесс в несколько раз или даже порядков за счёт использования приближённых алгоритмов. Эти алгоритмы обычно дают правильный ответ с определённой вероятностью. Если вы будете запускать алгоритм повторно, то сможете увеличить эту вероятность!

Дорогостоящие ошибки

Примером может служить случай с Европейским космическим агентством, которое потратило 700 миллионов долларов на ракету «Ариан-5» из-за ошибки, которая произошла в 1994 году и была связана с процессорами Intel Pentium. Ошибка заключалась в том, что при попытке поместить 64-битное число в 16-битный регистр происходило переполнение, что приводило к неправильным результатам вычислений.

Ещё один пример — ошибка в процессорах Intel Pentium, связанная с плавающей точкой, которая обошлась в 4,75 миллиарда фунтов стерлингов. Статья об этом вышла в газете The New York Times 24 ноября 1994 года.

Подробнее о случайных ошибках и их причинах можно узнать из книг Трефетена и Бауэра (глава 13) и Гринбаума и Шартье (глава 5).

Использование памяти

Разреженные и плотные матрицы

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

На рисунке ниже показана разреженная матрица, взятая из примера задачи из области механики твёрдого тела (например, моделирование воздушного потока вокруг плоскости). Чёрным цветом обозначены ненулевые элементы, белым — нулевые.

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

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

Скорость

Скорость зависит от многих факторов, таких как сложность вычислений, векторизация, расширение до нескольких ядер и узлов, локальность данных.

Сложность вычислений

Сложность алгоритмов обычно измеряется в терминах количества операций, необходимых для выполнения задачи. Например, алгоритм может иметь сложность O(n^2 m), где n и m — размеры входных данных.

Понимание и применение концепции сложности вычислений важно для понимания производительности алгоритмов. Вы можете изучить эту тему на сайтах Interview Cake, Codecademy и HackerRank.

Векторизация

Современные процессоры и графические процессоры могут выполнять операции над несколькими элементами одновременно. Например, можно вычислить экспоненту для четырёх чисел с плавающей запятой одновременно. Этот подход называется SIMD (одна инструкция — множество данных). Обычно вы не пишете код для SIMD напрямую, а используете векторизованные операции в библиотеках, таких как NumPy, которые используют специализированные векторизованные функции BLAS и LAPACK.

BLAS (подпрограммы базовой линейной алгебры) — это набор функций для выполнения основных арифметических операций с матрицами и векторами. Примеры библиотек BLAS включают AMD Core Math Library (ACML), ATLAS, Intel Math Kernel Library (MKL) и OpenBLAS.

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

Цель LAPACK — обеспечить эффективную работу LINPACK и EISPACK на компьютерах с общей памятью и параллельными процессорами, используя преимущества кэширования (впервые выпущен в 1992 году). LINPACK и EISPACK не учитывали многоуровневую архитектуру памяти, и перемещение данных занимало слишком много времени.

Локальность данных

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

Вот некоторые цифры, которые должен знать каждый (по Джеффу Дину):

Эти цифры показывают, что каждый последующий уровень памяти медленнее предыдущего на порядок. Доступ к жёсткому диску очень медленный.

Видео показывает различные методы размытия фотографий и сравнивает их. Хотя видео посвящено языку Halide, оно иллюстрирует проблемы, связанные с локальностью данных, которые актуальны для всех языков программирования.

Хотя видео посвящено новому языку программирования Halide, оно хорошо иллюстрирует проблему локальности данных, которая актуальна для всех языков. В видео рассматриваются различные подходы к размытию фотографий и проводится их сравнение. Рекомендуется посмотреть видео с 1 по 13 минуту.

Локальность данных трудно реализовать. Необходимо найти баланс между сохранением данных для экономии памяти и повторным использованием данных для повышения производительности.

Временность

Временность возникает, когда результаты вычислений сохраняются во временных переменных в оперативной памяти, а затем эти переменные используются для дальнейших вычислений. Это значительно медленнее, чем сохранение результатов в регистрах или кэше процессора и выполнение всех необходимых вычислений перед сохранением окончательного результата в оперативной памяти. Для нас это особенно актуально, так как NumPy часто создаёт временные переменные для каждой операции или функции. Например, выражение a = b * c^2 + ln(d) создаст четыре временные переменные, так как в нём есть четыре операции и функции.

Расширение до нескольких ядер и узлов

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