Недавно я помогал вести курс по линейной алгебре, который организовали Тай-Даная Брэдли и Джек Хидари. Одним из вопросов, который периодически возникал у слушателей курса, был вопрос о том, почему программистов должна заботить тема линейной комбинации векторов.
Если кто не знает о том, что это такое — поясню. Предположим, имеются векторы
. Их линейной комбинацией называется выражение вида 
, представляющее собой сумму произведений векторов на коэффициенты 
.
Должен признать, что книги по математике оказывают своим читателям медвежью услугу, представляя концепцию линейной комбинации векторов не более чем теоретической идеей. В результате создаётся впечатление того, что эта концепция нужна лишь для математических доказательств, что самое ценное для практика — это умножение матриц и векторные произведения. Но, на самом деле, это не так. Линейная комбинация векторов лежит в самом сердце многих вариантов практического применения математических идей.
В некоторых случаях главной целью применения некоего алгоритма является лишь поиск «приемлемой» линейной комбинации набора векторов. Векторы — это строительные блоки (часто являющиеся базисом векторного пространства или подпространства), а набор линейных комбинаций векторов представляет собой законный способ комбинирования этих блоков. Более простые блоки допускают применение более простых и более эффективных алгоритмов, но их линейные комбинации менее выразительны. Вследствие этого и возникает компромисс.
Конкретный пример этого — регрессия. Большинство людей, говоря о регрессии, имеют в виду линейную регрессию. Речь идёт о поиске линейной функции, вроде
, которая хорошо аппроксимирует некие данные. В случае с функцией от нескольких переменных имеется, например, 
в роли вектора входных переменных, и 
в роли вектора коэффициентов или весов. А сама функция тогда выглядит как 
.
Для того чтобы избежать сдвига функции на
(что делает функцию аффинной, а не чисто линейной; с формулами чисто линейных функций проще работать, так как сдвиг функции напоминает неприятный частный случай, который нужно постоянно принимать во внимание) авторы часто добавляют к вектору входных переменных фиктивную переменную 
, значение которой никогда не меняется и составляет 1, и переименовывают в 
для того чтобы формула приобрела бы окончательный вид 
. В результате задача оптимизации, которую нужно решить, учитывая то, что
— это набор данных для аппроксимации, выглядит так:
В данном случае оптимизируемая функция, представляющая собой результат работы регрессии, не похожа на линейную комбинацию векторов. Но с технической точки зрения это — линейная комбинация векторов, хотя выполнена она с использованием не слишком интересного способа.
Более очевидной связь подобных задач с линейной комбинацией векторов становится тогда, когда пытаются моделировать нелинейные системы. Суть тут в том, чтобы определить класс функций, называемых базисными функциями
, и допустить, чтобы аппроксимация представляла бы собой любую линейную комбинацию функций в 
, то есть — любую функцию в пределах :
Опять же, вместо того, чтобы умножать каждую координату входного вектора на коэффициент
, мы «взвешиваем» вклад каждой базисной функции (когда нам дан весь входной вектор) в выходные данные. Если базисные функции должны дать нам единственную координату — ( 
), это значит, что мы возвращаемся к линейной регрессии.
В результате задача оптимизации будет заключаться в том, чтобы выбрать коэффициенты, минимизирующие ошибку аппроксимации:
Рассмотрим пример. Предположим, что нам нужно выполнить регрессию на базисных функциях, представленных квадратичными полиномами. Базис для трёх входных переменных может выглядеть так:
Любой квадратичный полином от трёх переменных может быть представлен в виде линейной комбинации этих базисных функций. Кроме того, обратить внимание на то, что если рассматривать это как базис векторного пространства, тогда вектор будет представлен набором из 10 чисел — из десяти коэффициентов полинома. Это — то же самое, что
, но с другой интерпретацией того, какой смысл имеют компоненты векторов. Учитывая это, мы теперь знаем о том, как находить скалярные произведения векторов, проекции векторов, и много чего ещё, хотя всё это может и не иметь такого же геометрического смысла.
Это — не те функции, которые обычно, на практике, используются в качестве базисных функций для полиномиальной регрессии (подробнее об этом смотрите в примечаниях, приведённых в конце статьи), но благодаря этим знаниям мы уже можем сделать кое-что полезное при реализации регрессионных алгоритмов.
Хотя существуют аналитические решения многих регрессионных задач (включая задачу квадратичной регрессии, хотя и с небольшим изменением), градиентный спуск — это достаточно простое решение, позволяющее продемонстрировать то, как оптимизатор может находить «приемлемые» линейные комбинации векторов. Нижеприведённый код написан на Python 3.9, этот код можно найти на GitHub.
Начнём с объявления нескольких полезных псевдонимов типов:
Затем объявим простой класс-обёртку для базисных функций:
Функция
Сейчас можно определить градиент функции ошибки по отношению к весам и к одной точке данных. Вспомним о том, что функция ошибок выглядит так:
Здесь
— это линейная комбинация базисных функций:
Так как мы реализуем алгоритм стохастического градиентного спуска, формула вычисления ошибки немного упрощается. Мы вычисляем её не для всего набора данных, а только для одного, случайным образом выбранного элемента за раз. В результате функция ошибки будет выглядеть так:
Затем мы вычисляем градиент применительно к отдельным компонентам
, используя правило дифференцирования сложной функции, и учитывая, что единственный компонент линейной комбинации векторов, отличающийся ненулевым влиянием на градиент для 
— это компонент, содержащий . Это — один из главных плюсов использования линейной комбинации векторов, который заключается в простоте вычисления градиента:
Ещё одна сильная сторона линейности заключается в том, что этой формуле безразлично содержимое исходных базисных функций. Это будет так до тех пор, пока веса не появятся в формуле для базисных функций. Попробуйте, в качестве упражнения, изменить эту реализацию так, чтобы в каждой из точек данных применялась бы собственная радиальная базисная функция (в конце статьи есть примечание о том, почему это, в реальной жизни, может быть непросто).
И, наконец, реализуем ядро алгоритма градиентного спуска, в которое входят механизмы, упрощающие отладку кода:
Сгенерируем какой-нибудь простой набор данных и запустим оптимизацию:
Алгоритму на то, чтобы сойтись, может понадобиться несколько тысяч шагов. Сколько именно — зависит от того, как отработал генератор случайных чисел при подготовке данных. Но обычно алгоритм сходится к решению, дающему ошибку меньше 1. Вот график, на котором показана связь ошибки и шагов алгоритма градиентного спуска для задачи квадратичной регрессии.
Ошибка и шаги алгоритма
Я завершу этот материал пояснениями, на которые ссылался в статье.
Настоящее полиномиальное ядро. Мы решили использовать простой набор полиномиальных функций. Это тесно связано с концепцией «ядра», но «настоящее» полиномиальное ядро использует немного другие базисные функции. Оно масштабирует некоторые из базисных функций, используя
. Но зачем это делать? Ответ сводится к технике повышения эффективности вычислений, называемой «ядерным трюком». Этот «трюк», если кратко его описать, позволяет вычислять скалярное произведение двух линейных комбинаций векторов в векторном пространстве без вычисления координат данных в пространстве. Если в реализации используемого алгоритма регрессии используются только скалярные произведения векторов (что справедливо для аналитических решений регрессионных задач), то в нашем распоряжении оказываются сильные стороны нелинейного моделирования признаков и нам, при этом, не нужно тратить ресурсы на непосредственное вычисление признаков. В этой связи уместно будет обсудить гораздо больше теоретических математических вопросов (см. также: Reproducing Kernel Hilbert Space), но тут я не буду углубляться в эту тему.
Что не так с упражнением про радиальные базисные функции? В этом упражнении я предложил вам создать семейство базисных функций, по одной функции для каждой точки данных. Проблема тут заключается в том, что наличие настолько большого количества базисных функций делает пространство линейной комбинации векторов слишком выразительным. В ходе оптимизации произойдёт переобучение модели. В результате получится нечто, напоминающее справочную таблицу: каждой точке данных соответствует отдельная запись. При этом такая модель редко показывает хорошие результаты при обработке новых точек данных, которых не было в учебном наборе. Дело в том, что этих точек нет в найденной алгоритмом оптимизации «справочной таблице». На практике, для того чтобы справиться с этой проблемой, обычно, при расчёте ошибки, используют дополнительный компонент, соответствующий метрикам L1 или L2 вектора весовых коэффициентов. Это позволяет обеспечить то, что общий размер весов будет небольшим, то, что большинство весов, в случае с применением метрики L1, будут нулевыми, и то, что лишь немногие веса (самые важные) будут ненулевыми. Процесс введения «штрафов» за «размеры» линейных комбинаций векторов называют регуляризацией.
Что вы посоветовали бы почитать программистам, которые хотят с нуля освоить линейную алгебру?
Если кто не знает о том, что это такое — поясню. Предположим, имеются векторы
. Их линейной комбинацией называется выражение вида 
, представляющее собой сумму произведений векторов на коэффициенты 
.Должен признать, что книги по математике оказывают своим читателям медвежью услугу, представляя концепцию линейной комбинации векторов не более чем теоретической идеей. В результате создаётся впечатление того, что эта концепция нужна лишь для математических доказательств, что самое ценное для практика — это умножение матриц и векторные произведения. Но, на самом деле, это не так. Линейная комбинация векторов лежит в самом сердце многих вариантов практического применения математических идей.
В некоторых случаях главной целью применения некоего алгоритма является лишь поиск «приемлемой» линейной комбинации набора векторов. Векторы — это строительные блоки (часто являющиеся базисом векторного пространства или подпространства), а набор линейных комбинаций векторов представляет собой законный способ комбинирования этих блоков. Более простые блоки допускают применение более простых и более эффективных алгоритмов, но их линейные комбинации менее выразительны. Вследствие этого и возникает компромисс.
Конкретный пример этого — регрессия. Большинство людей, говоря о регрессии, имеют в виду линейную регрессию. Речь идёт о поиске линейной функции, вроде
, которая хорошо аппроксимирует некие данные. В случае с функцией от нескольких переменных имеется, например, 
в роли вектора входных переменных, и 
в роли вектора коэффициентов или весов. А сама функция тогда выглядит как 
.Для того чтобы избежать сдвига функции на
(что делает функцию аффинной, а не чисто линейной; с формулами чисто линейных функций проще работать, так как сдвиг функции напоминает неприятный частный случай, который нужно постоянно принимать во внимание) авторы часто добавляют к вектору входных переменных фиктивную переменную 
, значение которой никогда не меняется и составляет 1, и переименовывают в 
для того чтобы формула приобрела бы окончательный вид 
. В результате задача оптимизации, которую нужно решить, учитывая то, что
— это набор данных для аппроксимации, выглядит так:
В данном случае оптимизируемая функция, представляющая собой результат работы регрессии, не похожа на линейную комбинацию векторов. Но с технической точки зрения это — линейная комбинация векторов, хотя выполнена она с использованием не слишком интересного способа.
Более очевидной связь подобных задач с линейной комбинацией векторов становится тогда, когда пытаются моделировать нелинейные системы. Суть тут в том, чтобы определить класс функций, называемых базисными функциями
, и допустить, чтобы аппроксимация представляла бы собой любую линейную комбинацию функций в 
, то есть — любую функцию в пределах :
Опять же, вместо того, чтобы умножать каждую координату входного вектора на коэффициент
, мы «взвешиваем» вклад каждой базисной функции (когда нам дан весь входной вектор) в выходные данные. Если базисные функции должны дать нам единственную координату — ( 
), это значит, что мы возвращаемся к линейной регрессии.
В результате задача оптимизации будет заключаться в том, чтобы выбрать коэффициенты, минимизирующие ошибку аппроксимации:
Рассмотрим пример. Предположим, что нам нужно выполнить регрессию на базисных функциях, представленных квадратичными полиномами. Базис для трёх входных переменных может выглядеть так:
Любой квадратичный полином от трёх переменных может быть представлен в виде линейной комбинации этих базисных функций. Кроме того, обратить внимание на то, что если рассматривать это как базис векторного пространства, тогда вектор будет представлен набором из 10 чисел — из десяти коэффициентов полинома. Это — то же самое, что
, но с другой интерпретацией того, какой смысл имеют компоненты векторов. Учитывая это, мы теперь знаем о том, как находить скалярные произведения векторов, проекции векторов, и много чего ещё, хотя всё это может и не иметь такого же геометрического смысла.Это — не те функции, которые обычно, на практике, используются в качестве базисных функций для полиномиальной регрессии (подробнее об этом смотрите в примечаниях, приведённых в конце статьи), но благодаря этим знаниям мы уже можем сделать кое-что полезное при реализации регрессионных алгоритмов.
Простой стохастический градиентный спуск
Хотя существуют аналитические решения многих регрессионных задач (включая задачу квадратичной регрессии, хотя и с небольшим изменением), градиентный спуск — это достаточно простое решение, позволяющее продемонстрировать то, как оптимизатор может находить «приемлемые» линейные комбинации векторов. Нижеприведённый код написан на Python 3.9, этот код можно найти на GitHub.
Начнём с объявления нескольких полезных псевдонимов типов:
from typing import Callable, Tuple, List
Input = Tuple[float, float, float]
Coefficients = List[float]
Gradient = List[float]
Hypothesis = Callable[[Input], float]
Dataset = List[Tuple[Input, float]]
Затем объявим простой класс-обёртку для базисных функций:
class QuadraticBasisPolynomials:
def __init__(self):
self.basis_functions = [
lambda x: 1,
lambda x: x[0],
lambda x: x[1],
lambda x: x[2],
lambda x: x[0] * x[1],
lambda x: x[0] * x[2],
lambda x: x[1] * x[2],
lambda x: x[0] * x[0],
lambda x: x[1] * x[1],
lambda x: x[2] * x[2],
]
def __getitem__(self, index):
return self.basis_functions[index]
def __len__(self):
return len(self.basis_functions)
def linear_combination(self, weights: Coefficients) -> Hypothesis:
def combined_function(x: Input) -> float:
return sum(
w * f(x)
for (w, f) in zip(weights, self.basis_functions)
)
return combined_function
basis = QuadraticBasisPolynomials()
Функция
linear_combination возвращает функцию, которая вычисляет взвешенную сумму базисных функций. Теперь мы можем описать функции, вычисляющие ошибку для всего набора данных и для одной точки данных:def total_error(weights: Coefficients, data: Dataset) -> float:
hypothesis = basis.linear_combination(weights)
return sum(
(actual_output - hypothesis(example)) ** 2
for (example, actual_output) in data
)
def single_point_error(
weights: Coefficients, point: Tuple[Input, float]) -> float:
return point[1] - basis.linear_combination(weights)(point[0])
Сейчас можно определить градиент функции ошибки по отношению к весам и к одной точке данных. Вспомним о том, что функция ошибок выглядит так:
Здесь
— это линейная комбинация базисных функций:
Так как мы реализуем алгоритм стохастического градиентного спуска, формула вычисления ошибки немного упрощается. Мы вычисляем её не для всего набора данных, а только для одного, случайным образом выбранного элемента за раз. В результате функция ошибки будет выглядеть так:
Затем мы вычисляем градиент применительно к отдельным компонентам
, используя правило дифференцирования сложной функции, и учитывая, что единственный компонент линейной комбинации векторов, отличающийся ненулевым влиянием на градиент для 
— это компонент, содержащий . Это — один из главных плюсов использования линейной комбинации векторов, который заключается в простоте вычисления градиента:
Ещё одна сильная сторона линейности заключается в том, что этой формуле безразлично содержимое исходных базисных функций. Это будет так до тех пор, пока веса не появятся в формуле для базисных функций. Попробуйте, в качестве упражнения, изменить эту реализацию так, чтобы в каждой из точек данных применялась бы собственная радиальная базисная функция (в конце статьи есть примечание о том, почему это, в реальной жизни, может быть непросто).
def gradient(weights: Coefficients, data_point: Tuple[Input, float]) -> Gradient:
error = single_point_error(weights, data_point)
dE_dw = [0] * len(weights)
for i, w in enumerate(weights):
dE_dw[i] = -2 * error * basis[i](data_point[0])
return dE_dw
И, наконец, реализуем ядро алгоритма градиентного спуска, в которое входят механизмы, упрощающие отладку кода:
import random
def print_debug_info(step, grad_norm, error, progress):
print(f"{step}, {progress:.4f}, {error:.4f}, {grad_norm:.4f}")
def gradient_descent(
data: Dataset,
learning_rate: float,
tolerance: float,
training_callback = None,
) -> Hypothesis:
weights = [random.random() * 2 - 1 for i in range(len(basis))]
last_error = total_error(weights, data)
step = 0
progress = tolerance * 2
grad_norm = 1.0
if training_callback:
training_callback(step, 0.0, last_error, 0.0)
while abs(progress) > tolerance or grad_norm > tolerance:
grad = gradient(weights, random.choice(data))
grad_norm = sum(x**2 for x in grad)
for i in range(len(weights)):
weights[i] -= learning_rate * grad[i]
error = total_error(weights, data)
progress = error - last_error
last_error = error
step += 1
if training_callback:
training_callback(step, grad_norm, error, progress)
return basis.linear_combination(weights)
Сгенерируем какой-нибудь простой набор данных и запустим оптимизацию:
def example_quadratic_data(num_points: int):
def fn(x, y, z):
return 2 - 4*x*y + z + z**2
data = []
for i in range(num_points):
x, y, z = random.random(), random.random(), random.random()
data.append(((x, y, z), fn(x, y, z)))
return data
if __name__ == "__main__":
data = example_quadratic_data(30)
gradient_descent(
data,
learning_rate=0.01,
tolerance=1e-06,
training_callback=print_debug_info
)
Алгоритму на то, чтобы сойтись, может понадобиться несколько тысяч шагов. Сколько именно — зависит от того, как отработал генератор случайных чисел при подготовке данных. Но обычно алгоритм сходится к решению, дающему ошибку меньше 1. Вот график, на котором показана связь ошибки и шагов алгоритма градиентного спуска для задачи квадратичной регрессии.
Ошибка и шаги алгоритма
Ядра и регуляризация
Я завершу этот материал пояснениями, на которые ссылался в статье.
Настоящее полиномиальное ядро. Мы решили использовать простой набор полиномиальных функций. Это тесно связано с концепцией «ядра», но «настоящее» полиномиальное ядро использует немного другие базисные функции. Оно масштабирует некоторые из базисных функций, используя
. Но зачем это делать? Ответ сводится к технике повышения эффективности вычислений, называемой «ядерным трюком». Этот «трюк», если кратко его описать, позволяет вычислять скалярное произведение двух линейных комбинаций векторов в векторном пространстве без вычисления координат данных в пространстве. Если в реализации используемого алгоритма регрессии используются только скалярные произведения векторов (что справедливо для аналитических решений регрессионных задач), то в нашем распоряжении оказываются сильные стороны нелинейного моделирования признаков и нам, при этом, не нужно тратить ресурсы на непосредственное вычисление признаков. В этой связи уместно будет обсудить гораздо больше теоретических математических вопросов (см. также: Reproducing Kernel Hilbert Space), но тут я не буду углубляться в эту тему.Что не так с упражнением про радиальные базисные функции? В этом упражнении я предложил вам создать семейство базисных функций, по одной функции для каждой точки данных. Проблема тут заключается в том, что наличие настолько большого количества базисных функций делает пространство линейной комбинации векторов слишком выразительным. В ходе оптимизации произойдёт переобучение модели. В результате получится нечто, напоминающее справочную таблицу: каждой точке данных соответствует отдельная запись. При этом такая модель редко показывает хорошие результаты при обработке новых точек данных, которых не было в учебном наборе. Дело в том, что этих точек нет в найденной алгоритмом оптимизации «справочной таблице». На практике, для того чтобы справиться с этой проблемой, обычно, при расчёте ошибки, используют дополнительный компонент, соответствующий метрикам L1 или L2 вектора весовых коэффициентов. Это позволяет обеспечить то, что общий размер весов будет небольшим, то, что большинство весов, в случае с применением метрики L1, будут нулевыми, и то, что лишь немногие веса (самые важные) будут ненулевыми. Процесс введения «штрафов» за «размеры» линейных комбинаций векторов называют регуляризацией.
Что вы посоветовали бы почитать программистам, которые хотят с нуля освоить линейную алгебру?
