Справочная математика Байесовские рассуждения смыс

A
Справочная математика
A.1 Линейная алгебра
A.1.1 Векторная алгебра
Пусть x обозначает n-мерный вектор-столбец с компонентами
Определение 116 (скалярное произведение). Скалярное произведение w · x определяется как:
и имеет естественную геометрическую интерпретацию как:
w · x = |w| |x| cos(;) (A.1.2)
где ; - угол между двумя векторами. Таким образом, если длины двух векторов фиксированы, то их внутреннее произведение является наибольшим при ; = 0, после чего один вектор является постоянным кратным другого. Если скалярное произведение xTy = 0, тогда x и y ортогональны (они находятся под прямым углом друг к другу).
Длина вектора обозначается |x|, квадрат длины задается как
Единичный вектор x имеет значение xTx= 1.
Определение 117 (линейная зависимость). Набор векторов x1 , ... , xn является линейно зависимым, если существует вектор xj, который может быть выражен как линейная комбинация других векторов. И наоборот, если единственное решение задачи
543 Линейная алгебра

Рисунок A.1: Разбиение вектора a на компоненты вдоль ортогональных направлений e и e; . Проекцией a на эти два направления являются длины ; и ; вдоль направлений e и e; .

то для всех ;i = 0, i = 1, . . . , n векторы x1 , . . . , xn линейно независимы.
A.1.2 Скалярное произведение как проекция
Предположим, что мы хотим разложить вектор a на его составляющие вдоль ортогональных направлений, заданных единичными векторами e и e;. То есть |e| = |e|; = 1 и e · e; = 0. Это показано на рисунке (A.1).  От нас требуется найти скалярные значения ; и ; такие, что
a = ;e + ;e; (A.1.5)
Из этого мы получаем
a · e = ; e · e + ;e; · e,
a · e; = ;e · e; + ;e; · e; (A.1.6)
Из-за ортогональности и единичных длин векторов e и e; это становится просто
;· e = ;,
; · e; = ; (A.1.7)
Набор векторов является ортонормированным, если они взаимно ортогональны и имеют единичную длину. Это означает, что мы можем записать вектор a в терминах ортонормированных компонент e и e; как
a = (a · e) e + (a · e; ) e; (A.1.8)
Таким образом, можно видеть, что скалярное произведение a и e проецирует вектор a на (единицу) направление e. Следовательно, проекция вектора a на направление, заданное параметром f , равна
А.1.3. Линии в пространстве
Линия в 2 (или более) измерениях может быть задана следующим образом. Вектор любой точки вдоль линии для некоторого значения s задается уравнением
p = a + su, s ; R. (A.1.10)
где u параллельна прямой, а прямая проходит через точку a, см. рис. (А.2). Это называется параметрическим представлением прямой. Альтернативную спецификацию можно дать, поняв, что все векторы вдоль прямой ортогональны нормали к прямой, n (u и n ортонормированы). То есть
(p ; a) · n = 0 ; p · n = a · n (A.1.11)
Если вектор n имеет единичную длину, то правая часть приведенного выше значения представляет собой кратчайшее расстояние от начала координат до линии, проведенной пунктирной линией на рис. (А.2) (поскольку это проекция a на нормальное направление).
Рисунок A.2: Линия может быть задана некоторым вектором положения на линии, a, и единичным вектором вдоль направления линии, u. В двух измерениях существует единственное направление, n, перпендикулярное прямой. В трех измерениях векторы, перпендикулярные направлению прямой, лежат в плоскости, вектор нормали которой направлен в направлении прямой, u.
ЧЕРНОВИК от 9 марта 2010 г. Линейная алгебра 544

Рисунок A.3. Плоскость может быть задана точкой на плоскости a и двумя непараллельными направлениями на плоскости u и v. Нормаль к плоскости уникальна и проходит в том же направлении, что и прямая, проходящая от начала координат до ближайшей точки на плоскости.
A.1.4 Плоскости и гиперплоскости
Прямая - это одномерная гиперплоскость. Для определения двумерной плоскости (в пространстве произвольной размерности) можно указать два вектора u и v, лежащих в плоскости (они не обязательно должны быть взаимно ортогональными), и a расположите вектор a на плоскости, см. рис. (A.3). Любой вектор p на плоскости можно записать в виде
p = a + su + tv,  (s, t) ; R. (A.1.12)
Альтернативное определение дано с учетом того, что любой вектор в плоскости должен быть ортогонален нормали к плоскости n.
(p ; a) · n = 0 ; p · n = a · n  (A.1.13).
Правая часть приведенного выше изображения представляет собой кратчайшее расстояние от начала координат до плоскости, обозначенное пунктирной линией на рис. (А.3). Преимущество этого представления в том, что оно имеет ту же форму, что и прямая. Действительно, это представление (гиперплоскостей) не зависит от размерности пространства. Кроме того, необходимо определить только два вектора – точку на плоскости a и нормаль к плоскости n.
A.1.5 Матрицы
Матрица A m ; n представляет собой набор скалярных значений m ; n, расположенных в прямоугольнике из m строк и n столбцов.
Вектор можно рассматривать как матрицу n ; 1. Если элемент i-й строки и j-го столбца равен Aij , то AT обозначает матрицу , в которой вместо Aji есть - транспонирование A. Например, A и его транспонирование являются :
Элемент i, j матрицы A может быть записан как Aij или, в случаях, когда требуется большая ясность, как [A]ij (для примера  [A-1]ij).
Определение 118 (транспонирование). Результатом преобразования BT матрицы B из n в m является матрица D из m в n с компонентами
B, (BT) T= B и (AB)T = BTAT . Если формы матриц A,B и C таковы, что имеет смысл вычислять произведение ABC, то
(ABC)T = CT BT AT (A.1.16)
Квадратная матрица A симметрична, если AT= A. Квадратная матрица называется эрмитовой, если
A = AT; (A.1.17)
где ; обозначает комплексно-сопряженный оператор. Для эрмитовых матриц собственные векторы образуют ортогональный набор с вещественными собственными значениями.
ЧЕРНОВИК от 9 марта 2010 г.
545 линейная алгебра
Определение 119 (Сложение матриц). Для двух матриц A и B одинакового размера,
[A + B]ij = [A]ij + [B]ij (A.1.18)
Определение 120 (Умножение матриц). Для l на n матриц A и n на m матриц B произведение
AB - это матрица l на m с элементами
Например
Обратите внимание, что даже если BA также определено, то есть если l = n, обычно BA не равно AB (когда они равны, мы говорим, что они коммутируют). Матрица I - это единичная матрица, обязательно квадратная, с единицами по диагонали и 0 везде. Для наглядности мы можем также записать Im для квадратной матрицы m ; m тождеств. Тогда для матрицы A   m ; n
ImA = AIn = A (A.1.21)
Единичная матрица содержит элементы [I]ij = ;ij, заданные с помощью дельты Кронекера:
Определение 121 (Трассировка).
трассировка \след, свертка\ (A)
, где ;i - собственные значения A.
A.1.6 Линейные преобразования
Вращения
Если мы предположим, что вращение двумерного вектора x = (x, y) T может быть выполнено с помощью матричного умножения Rx, то, поскольку матричное умножение является распределительным, нам нужно только выяснить, как единичные векторы осей i = (1, 0)T и j = (0, 1)T преобразуется с тех пор, как
Rx = xRi + yRj (A.1.24)
Единичные векторы i и j при повороте на ; градусов преобразуются в векторы
546
ЧЕРНОВИК от 9 марта 2010 года по линейной алгебре
Из этого можно просто прочитать значения элементов
A.1.7 Определяющие факторы \Детерминанты
Определение 122 (Определяющий фактор). Для квадратной матрицы A определяющим фактором является объем преобразования матрицы A (с точностью до изменения знака). То есть мы берем гиперкуб единичного объема и сопоставляем каждую вершину с преобразованием, а объем результирующего объекта определяется как определитель. Записываем [A]ij = aij ,

Определитель в случае (3 ; 3) имеет вид
Определитель (3 ; 3) матрицы A задается суммой слагаемых (-1)i+1 a1i det (Ai ), где Ai — это матрица (2 ; 2), сформированная из A путем удаления i-й строки и столбца. Эта форма определителя применима к любому измерению. То есть мы можем рекурсивно определить определитель как разложение по верхней строке определителей приведенных матриц. Абсолютным значением определителя является объем преобразования.
det( AT )= det (A) (A.1.30)
Для квадратных матриц A и B одинаковой размерности
det (AB) = det (A) det (B) ,
det (I) = 1 ; det A;1 = 1/det (A) (A.1.31)
Для любой матрицы A, которая сворачивает \разваливает\ измерения, объем преобразования равен нулю, как и определяющий фактор. Если определитель равен нулю, матрица не может быть обратимой, поскольку при любом векторе x, при заданной "проекции" y = Ax, мы не можем однозначно вычислить, какой вектор x был спроецирован на y – в общем случае будет бесконечное число решений.
Определение 123 (Ортогональная матрица). Квадратная матрица A ортогональна, если AAT = I = AT A. Таким образом, из свойств определителя мы видим, что ортогональная матрица имеет определитель ±1 и, следовательно соответствует преобразованию, сохраняющему объем, т.е. повороту.
Определение 124 (ранг матрицы). Для матрицы m ; n X с n столбцами, каждый из которых записан в виде m-вектора:
X = [x1 , . . . , xn] (A.1.32)
ранг X - это максимальное количество линейно независимых столбцов (или, что эквивалентно, строк). Квадратная матрица n ; n имеет полный ранг, если ранг равен n и матрица не является сингулярной. В противном случае матрица имеет пониженный ранг и является сингулярной.
ЧЕРНОВИК от 9 марта 2010 г. 547
Линейная алгебра
A.1.8 Обращение матрицы
Определение 125 (Обращение матрицы). Для квадратной матрицы A ее обратная величина удовлетворяет
A;1 A = I = AA;1 (A.1.33)
Не всегда возможно найти матрицу A;1, такую, что A;1 A = I. В этом случае мы называем матрицу сингулярной. Геометрически сингулярные матрицы соответствуют ‘проекциям’: если бы мы преобразовали каждую из вершин v бинарного гиперкуба Av, объем преобразованного гиперкуба был бы равен нулю. Если вам задан вектор y и сингулярное преобразование A, невозможно однозначно идентифицировать вектор x, для которого y = Ax - как правило, существует целое пространство возможностей.
При условии, что существуют обратные матрицы
(AB)-1 = B;1 A;1 (A.1.34)
Для неквадратной матрицы A, такой, что AAT обратима, тогда псевдообратная, определяемая как
A† = AT (AAT )-1 (A.1.35)
удовлетворяет AA† = I.
A.1.9 Вычисление обратной матрицы
Для матрицы 2 ; 2 в общем виде несложно вычислить в лоб явную форму обратной матрицы. Если матрица, обратную которой мы хотим найти, равна A = , тогда условие для обратной матрицы равно
Умножая левую часть, мы получаем четыре условия
Легко проверить, что решение этой системы из четырех линейных уравнений задается формулой
Величина ad ; bc является определителем A. Существует множество способов вычисления обратной общей матрицы, и мы отсылаем читателя к более специализированным текстам.

Обратите внимание, что, если требуется решить только линейную систему, хотя решение может быть получено с помощью обращения матрицы, это не следует использовать. Часто приходится решать линейные системы большого размера, состоящие из уравнения, и скорость становится проблемой. Эти уравнения можно решить гораздо точнее и быстрее, используя методы исключения, такие как исключение по Гауссу.
A.1.10 Собственные значения и векторы
Собственные векторы матрицы соответствуют естественной системе координат, в которой геометрическая трансформация, представленная символом A, может быть наиболее легко понята.
548 ЧЕРНОВИК от 9 марта 2010 года по линейной алгебре
Определение 126 (Собственные значения и собственные векторы). Для квадратной матрицы A, e является собственным вектором матрицы A с собственным значением ;, если
Следовательно, матрица является сингулярной, если она имеет нулевое собственное значение. Трассировка матрицы может быть выражена как
Для матрицы (n ; n) размерности существует (включая повторения) n собственных значений, каждое из которых имеет соответствующий собственный вектор. Мы можем преобразовать уравнение (A.1.39) в виде
(A ; ;I) e = 0 (A.1.42)
Это линейное уравнение, для которого собственный вектор e и собственное значение ; являются решением. Мы можем записать уравнение (A.1.42) в виде Be = 0, где B ; A ; ;I. Если B имеет обратную величину, то решением будет e = B;10 = 0, что тривиально удовлетворяет собственному уравнению. Следовательно, для любого нетривиального решения задачи Be = 0 нам нужно, чтобы B было необратимым. Это эквивалентно условию, что B имеет нулевой определитель. Следовательно, ; является собственным значением A, если
det (A ; ;I) = 0 (A.1.43)
Это называется характеристическим уравнением. Это определяющее уравнение будет представлять собой многочлен степени n, а результирующее уравнение известно как характеристический многочлен. Как только мы найдем собственное значение, можно найти соответствующий собственный вектор, подставив это значение вместо ; в уравнение (A.1.39) и решив линейные уравнения для e. Возможно, что для собственного значения ; собственный вектор не является уникальным и существует пространство соответствующих векторов. Геометрически собственные векторы представляют собой особые направления, такие, что результатом преобразования A вдоль направления e является простое масштабирование вектора e. Для матрицы вращения R, как правило, при вращении не будет сохраняться направление, так что собственные значения и векторы будут комплекснозначными (вот почему представление Фурье, которое соответствует представлению в повернутом базисе, обязательно является сложным \комплексным\).
Замечание 11 (Ортогональность собственных векторов симметричных матриц). Для действительной симметричной матрицы A = AT , и два его собственных вектора ei и ej из A ортогональны (ei )T ej = 0, если собственные значения ;i и ;j различны.
Вышесказанное можно продемонстрировать на:
Поскольку A симметрично, левая часть эквивалентна

Если ;i; ;j , это условие может быть выполнено только в том случае, если (ej )T ei = 0, а именно, если собственные векторы ортогональны.
ЧЕРНОВИК от 9 марта 2010 г.
549 Линейная алгебра
A.1.11 Матричные разложения
Наблюдение, что собственные векторы симметричной матрицы ортогональны, непосредственно приводит к приведенной ниже формуле спектрального разложения.
Определение 127 (Спектральное разложение). Симметричная матрица A имеет собственное разложение
, где ;i - собственное значение собственного вектора ei, а собственные векторы образуют ортогональный набор,
В матричной записи
где E - матрица собственных векторов, а ; - соответствующая диагональная матрица собственных значений. В более общем плане, для квадратного несимметричного неособого \несингулярного\  A мы можем записать
Определение 128 (разложение по сингулярным числам). SVD-разложение матрицы X n ; p имеет вид
где нет U = n;n при UT U = In . Также нет V = p;p при VT V = Ip . В матрице S нет S = n;p с нулями везде, кроме диагональных элементов. "Сингулярные значения" - это диагональные элементы [S]ii, и они положительны. Сингулярные значения упорядочены таким образом, что верхний левый диагональный элемент S содержит наибольшее одиночное значение.
Квадратичные формы
Определение 129 (Квадратичная форма).
xTAx + xTb (A.1.51)
Определение 130 (положительно определенная матрица). Симметричная матрица A, обладающая свойством, что xTAx ; 0 для любой вектор x называется неотрицательно определенным. Симметричная матрица A, обладающая свойством  xTAx > 0 для любого вектора x; 0, называется положительной. Положительно определенная матрица имеет полный ранг и, следовательно, обратима. Используя собственное разложение A,
, который больше нуля тогда и только тогда, когда все собственные значения положительны. Таким образом, A является положительным определением тогда и только тогда, когда все его собственные значения положительны.
550
ЧЕРНОВИК от 9 марта 2010 г. Многомерный анализ
A.2 Матричные тождества
Определение 131 (Формула трассировки-логарифмирования). Для положительно определенной матрицы A
Обратите внимание, что приведенный выше логарифм матрицы не является логарифмом по элементам. В MATLAB требуемая функция является logm. В общем случае для аналитической функции f (x), f (M) определяется с помощью разложения функции в степенной ряд. Справа, поскольку det (A) является скаляром, логарифм является стандартным логарифмом скаляра.
Определение 132 (лемма об обращении матрицы (формула Вудбери)). При условии наличия соответствующих инвестиций:
Собственные функции
С помощью аналогичного аргумента, который доказывает приведенную выше теорему линейной алгебры, собственные функции ортогональны вещественному симметричному ядру, K (x`, x) = K (x, x` ) ортогональны:
, где ; *(x) - комплексное сопряжение ; (x) 1 . Из предыдущих результатов мы знаем, что симметричная вещественная матрица K должна иметь разложение по собственным векторам с положительными вещественными собственными значениями. Поскольку это должно быть верно для любого измерения матрицы, это предполагает, что нам нужна сама (реальная симметричная) функция ядра чтобы получить разложение (при условии, что собственные значения являются счетными)
с тех пор
которое больше нуля, если все собственные значения положительны (поскольку для комплекса z, zz* ; ; 0). Если собственные значения неисчислимы (что происходит, когда область ядра неограничена), то соответствующее разложение имеет вид
A.3 Многомерный анализ
1Это определение внутреннего продукта полезно и особенно естественно в контексте ядер, инвариантных к трансляции. Мы вольны определять внутреннее произведение, но эта сопряженная форма часто является наиболее полезной.
ЧЕРНОВИК от 9 марта 2010 г.
551 многомерный анализ
Рисунок А.4: Интерпретация градиента. Эллипсы - это контуры с постоянным значением функции, f = const. В любой точке x вектор градиента ;f (x) направлен в направлении максимального увеличения функции.
Определение 133 (Частная производная). Рассмотрим функцию от n переменных, f (x1, x2,. . . xn) или f (x). То частная производная от f относительно x1 в точке x; определяется как следующий предел (если он существует)
Вектор градиента f будет обозначаться через ;f  или g
A.3.1. Интерпретация вектора градиента
Рассмотрим функцию f (x), которая зависит от вектора x. Нас интересует, как изменяется функция, когда вектор x изменяется на небольшую величину: x ; x + ;, где ; - вектор, длина которого очень мала. Согласно разложению Тейлора, функция ; изменится на
Мы можем интерпретировать приведенное выше суммирование как скалярное произведение вектора ;f с компонентами
и ;.

Градиент указывает на направление, в котором функция увеличивается наиболее быстро. Почему? Рассмотрим направление p (вектор единичной длины). Затем смещение на ; единиц в этом направлении изменяет значение функции на
f (x + ;;p) ; f (x) + ;;f (x) · ;p (A.3.5)
Направление ;p, для которого функция изменяется больше всего - это то, при котором перекрытие
где ; - угол между ;p и ;f (x). Перекрытие максимизируется, когда ; = 0, что дает ;p =
;f (x)/|;f (x)|. Следовательно, направление, в котором функция изменяется наиболее быстро, находится вдоль ;f (x).
A.3.2 Высшие производные
‘Первая производная" функции из n переменных представляет собой n-вектор; "вторая производная" функции из n переменных определяется n2 частными производными от n первых частных производных от n переменных
552  ПРОЕКТ от 9 марта 2010 г. Многомерный математический анализ
, который обычно записывается как
Если частные производные ;f/;xi , ;f /;xj и ; 2 f /;xi ;xj, которые являются непрерывными, то ; 2 f /;xi ;xj не существует и
Эти n2 вторых частных производных представлены квадратной симметричной матрицей, называемой матрицей Гессиан f (x).
А.3. Правило цепочки
Рассмотрим f (x1 , . . . , xn ). Теперь пусть каждый xj параметризуется u1 , . . . , um , т.е. xj = xj (u1 , . . . , um ). Что такое ;f /;u;?
члены более высокого порядка
члены более высокого порядка
Таким образом,
 члены более высокого порядка
Следовательно
Определение 134 (правило цепочки).
или в векторной записи
Определение 135 (Производная по направлению). Предположим, что f дифференцируема. Определим скалярную производную по направлению (Dv f )(x; ) от f в направлении v в точке x; . Пусть x = x; + hv, тогда
А.3.4 Матричное исчисление
ЧЕРНОВИК от 9 марта 2010 года 553
Неравенства
Определение 136 (Производная от следа матрицы). Для матриц A и B
Определение 137 (Производная от логарифмического определения (A)).
Так что
Определение 138 (Производная от обратной матрицы). Для обратимой матрицы A,
A.4 Неравенства
A.4.1 Выпуклость
Определение 139 (Выпуклая функция). Функция f (x) определяется как выпуклая, если для любых x, y и 0 ; ; ; 1
f (;x + (1 ; ;)y) ; ;f (x) + (1 ; ;)f (y) (A.4.1)
Если- f(x) выпуклая, то f (x) называется вогнутой.
Наглядное представление о выпуклой функции состоит в том, чтобы сначала рассмотреть величину ;x + (1 ; ;)y. Поскольку мы меняем от 0 до 1 эта трасса указывает на расстояние между x (; = 0) и y (; = 1). Итак, при ; = 0 мы начинаем с точки x, f (x) и по мере увеличения ; проводим прямую линию к точке y, f (y) при ; = 1. Выпуклость означает, что функция f всегда лежит ниже этой прямой. Геометрически это означает, что функция f (x) всегда увеличивается (никогда не становится неубывающей). Если d2 f (x)/dx2 > 0, то функция выпуклая.
Например, функция log x является вогнутой, поскольку ее вторая производная отрицательна:
A.4.2 Неравенство Дженсена
Для выпуклой функции f (x) непосредственно из определения выпуклости следует, что
для любого распределения p (x).
554 ЧЕРНОВИК от 9 марта 2010 г. Постепенный переход
A.5 Оптимизация
A.5.1 Критические точки
Когда все частные производные первого порядка в точке равны нулю (т. е.  ;f = 0), то точка называется стационарной или критической. Это может быть минимальная, максимальная или седловая точка.
Требуемое условие первого порядка для минимума
Существует минимум f при x *, если f (x;) ; f (x) для всех x, достаточно близких к x*. Пусть x = x; + hv для малых h и некоторое направление v. Затем с помощью разложения Тейлора для малого h,
f (x* + hv) = f (x*) + h ;fT v + O (h2) (A.5.1)
для минимального
h ;fT v + O(h2) ; 0 (A.5.2)
При выборе значения v равным-;f  условие становится
- h ;f T;f + o (h2) ; 0 (A.5.3)
и нарушается при малом положительном значении h, если только |;f|2 = ;f T ;f= 0. Таким образом, x *может быть локальным минимумом только в том случае, если
|;f (x;) | = 0, т.е. если каждый ;f (x *) = 0.
Требуемое условие второго порядка для минимума
В стационарной точке ;f = 0. Разложение Тейлора обеспечивается формулой
Таким образом, минимальное условие требует, чтобы vT Hf v ; 0, т.е. гессиан неотрицателен.
Определение 140 (Условия для минимума). Достаточными условиями для достижения минимума в точке x* являются (i) значение ;f(x; ) = 0 и (ii) значение ;f(x;) положительно.
Для квадратичной функции f (x) = 1/2xTAx ; bT x + c, при симметричном A выполняется необходимое условие ;f(x;) = 0 читает:
Ax *- b = 0 (A.5.5)
Если A обратимо, то это уравнение имеет единственное решение x* = = A-1b. Если A положительно, то x* является минимальным.
A.6 Градиентный спуск
Почти все методы поиска, которые мы рассматриваем, являются итеративными, т.е. мы движемся к минимуму x*, выполняя последовательность шагов. На k-м шаге мы делаем шаг длиной ;k в направлении pk ,
xk+1 = xk + ;k pk (A.6.1)
Длина шага может быть выбрана либо с использованием предварительных знаний, либо путем выполнения линейного поиска в направлении pk . Именно способ выбора pk отличает различные методы многомерной оптимизации, которые мы будем обсуждать.
ДРАФТ от 9 марта 2010 года 555
Градусный спуск
Мы будем предполагать, что можем аналитически оценить градиент f и часто будем использовать сокращенную запись
gk =  ;f (xk). (A.6.2)
Как правило, мы хотим выбрать pk, используя только информацию о градиенте; для больших задач вычисление гессиана может быть очень дорогостоящим, и это также может потребовать большого объема памяти.
Рассмотрим изменение переменных x = My. Тогда
g (y ) = f (x) = f (My) (A.6.3)
и
, так что
Тогда изменение g отличается от изменения f, хотя единственное различие между ними функции - это система координат. Эта досадная чувствительность к параметризации функции
частично устраняется в методах первого порядка, таких как градиентный спуск по естественному градиенту, в которых используется префактор, предназначенный для компенсации некоторой потери инвариантности. Мы отсылаем читателя к [7] для описания этого метода.
A.6.1 Градиентный спуск с фиксированным размером шага
Локально, если мы находимся в точке xk, мы можем уменьшить f (x), сделав шаг в направлении ;g(x). Если мы обновим уравнение
затем мы выполняем градиентный спуск с фиксированным размером шага ;. Если он не бесконечен, это всегда возможно, то есть мы перешагнем истинный минимум. Сильное уменьшение ; защищает от этого, но означает, что процесс оптимизации займет очень много времени, чтобы достичь минимума.
Чтобы понять, почему работает градиентный спуск, рассмотрим общее обновление
При малом ; мы можем разложить f около xk, используя теорему Тейлора:
При pk = - gk и при небольшом положительном значении ;k мы видим гарантированное уменьшение:
A.6.2 Градиентный спуск с использованием импульса
Простая идея, которая может улучшить сходимость градиентного спуска, заключается в том, чтобы на каждой итерации учитывать часть изменений по сравнению с предыдущей итерацией.  Используем
где ; - коэффициент импульса.
556 ЧЕРНОВИК от 9 марта 2010 г. Многомерная минимизация: квадратичные функции
Рисунок А.5: Оптимизация с использованием линейного поиска по направлениям наиболее крутого спуска. Бросившись вниз по самому крутому спуску из точки (и продолжая движение
в этом направлении в течение определенного времени), не всегда удается достичь дна самым быстрым способом!
A.6.3 Градиентный спуск с поиском по линиям
Идея градиентного спуска заключается в том, чтобы выбрать направление наиболее крутого спуска, обозначенное градиентом g, но при этом рассчитать величину шага, который в наибольшей степени уменьшает значение E при движении в этом направлении. Это включает в себя решение одномерной задачи минимизации E (xk-;gk ) относительно ; и называется линейным поиском. Затем выполняется этот шаг, и процесс повторяется снова.
Определение размера шага требует небольшой работы; например, вы можете найти три точки вдоль линии таким образом, чтобы ошибка в промежуточной точке была меньше, чем в двух других, чтобы существовал некоторый минимум вдоль линии, лежащей между первой и второй или между второй и третьей, и чтобы затем найти его, можно было бы использовать какой-то подход, сокращающий интервал вдвое. (Минимум, найденный таким образом, как и при использовании любого алгоритма градиентного спуска, может, конечно, не быть глобальным минимумом.) Существует несколько вариантов этой темы. Обратите внимание, что если размер шага выбран таким образом, чтобы максимально уменьшить E в этом направлении, то никаких можно добиться дальнейшего улучшения в E, двигаясь в этом направлении на данный момент. Таким образом, следующий шаг не будет иметь компонента в этом направлении; то есть следующий шаг будет проходить под прямым углом к только что сделанному. Это может привести к зигзагообразному поведению при оптимизации, см. рис. (A.5).
A.6.4 Точное условие поиска строки
На k-м шаге мы выбрали ;k для минимизации f (xk + ;k pk ). Итак, установив F (;) = f (xk + ;pk), на этом шаге мы решаем одномерную задачу минимизации для F (;). Таким образом, наш выбор ;k = ; * будет удовлетворять F` (;k ) = 0. Теперь
Таким образом, F` (;k ) = 0 означает, что производная по направлению поиска должна быть равна нулю в новой точке, и это дает точное условие поиска по линии:
Для квадратичной функции f (x) = 1/2 xT Ax;bT x + c, симметричной, мы можем использовать это условие для аналитического вычисления ;k . Поскольку ;f (xk+1 ) = Axk + ;k Apk ; b = ;f (xk ) +;k Apk , мы находим
A.7 Многомерная минимизация: квадратичные функции
Цель этого раздела - вывести эффективные алгоритмы минимизации многомерных квадратичных функций. Мы начнем с обобщения некоторых свойств квадратичных функций и в качестве побочного продукта получим эффективный метод проверки того, является ли симметричная матрица положительно определенной.
A.7.1 Минимизация квадратичных функций с помощью линейного поиска
Рассмотрим минимизацию квадратичной функции
ЧЕРНОВИК от 9 марта 2010 г. 557
Многомерное минимизирование: квадратичные функции
, где A положительно определено и симметрично. (Если A несимметрично, рассмотрим вместо этого симметричную матрицу (A + AT )/2, которая дает ту же функцию f ). Хотя мы знаем, где минимум этого функция заключается в том, что, просто используя линейную алгебру, мы хотим использовать эту функцию в качестве игрушечной модели для более сложных функций которые, однако, локально выглядят приблизительно квадратичными. Один из подходов заключается в поиске в определенном направлении p и нахождении минимума в этом направлении. Затем мы можем искать более глубокие минимумы, глядя в разных направлениях. То есть мы можем выполнять поиск вдоль линии x0 + ;p таким образом, чтобы функция достигала минимума. То есть производная по направлению равна нулю вдоль этой линии, что имеет решение,
Теперь мы нашли минимум вдоль линии, проходящей через x0 в направлении p. Но как нам выбрать направление поиска линии p? Казалось бы, разумно выбирать последовательные направления поиска по линии p в соответствии с pnew = ;;f (x; ), чтобы каждый раз минимизировать функцию вдоль линии наиболее крутого спуска. Однако это далеко не оптимальный выбор в случае минимизации квадратичных функций. Гораздо лучший набор направлений поиска - это те, которые определяются векторами, сопряженными с A.
Если матрица A диагональна, то минимизация является простой и может быть выполнена независимо для каждого измерения. Если бы мы могли найти обратимую матрицу P со свойством, что PT AP является диагональной, то решение было бы простым, поскольку для
при x = P;x мы можем вычислить минимум для каждого измерения ;x отдельно, а затем повторно преобразовать, чтобы найти x; = P;x; .
Определение 141 (Сопряженные векторы). Векторы pi , i = 1, . . . , k называются сопряженными с матрицей A тогда и только тогда, когда для i, j = 1, . . . , k и i; j:
Два условия гарантируют, что сопряженные векторы линейно независимы: Предположим, что
Теперь умножение слева на pT i A дает 0 = ;i pTi Api . Таким образом, ;i равно нулю, поскольку мы знаем, что pTi Api> 0. Поскольку мы можем использовать этот аргумент для любого i = 1, ... , k, все значения ;i должны быть равны нулю.
A.7.2 Построение сопряженных векторов по Граму-Шмидту
Пусть P = (p1 , p2 , . . . , pk ), где столбцы сформированы из A-сопряженных векторов, и обратите внимание, что мы начинаем с матрицы n на k, k ; n. Причина этого в том, что мы стремимся к процедуре прибавлений, где столбцы последовательно добавляются к P. Поскольку (PT AP)ij = pT i Apj матрица PT AP будет диагональной, если PTi AP j = 0 для i; j. Предположим, что у нас уже есть k сопряженных векторов p1 , . . . , pk , и пусть v - вектор, линейно независимый от p1 , . . . , pk . Затем мы устанавливаем
для которого ясно, что векторы p1 , . . . , pk+1 сопряжены, если A положительно определено. Используя процедуру Грама- Шмидта, мы можем построить n сопряженных векторов для положительно определенной матрицы следующим образом. Мы начинаем с n линейно независимых векторов u1 , ... , un , мы могли бы выбрать ui = ei , единичный вектор в 
558 ЧЕРНОВИК от 9 марта 2010 г. Многомерная минимизация: квадратичные функции
в i-м направлении. Затем мы устанавливаем p1 = u1 и используем (A.7.6) для вычисления p2 из p1 и v = u2 . Затем мы устанавливаем v = u3 и вычисляем p3 из p1 , p2 и v. Продолжая таким образом, мы получаем n сопряженных векторов. Обратите внимание, что на каждом этапе процедуры векторы u1 , . . . , uk охватывают то же подпространство, что и векторы p1 , . . . , pk . Что произойдет, если A не является положительно определенным? Если бы мы могли найти n сопряженных векторов, A было бы положительно определено, и поэтому в какой-то момент k процедура Грама-Шмидта должна завершиться. Этот произойдет, если PTk AP k  ; 0. Таким образом, опробовав процедуру Грама-Шмидта, мы действительно можем выяснить, является ли матрица положительно определенной.
A.7.3 Алгоритм сопряженных векторов
Предположим, что при минимизации f (x) = 1/2xT Ax ; bT x + c мы сначала строим n векторов p1 , ... , pn, сопряженных с A, которые мы используем в качестве направлений поиска. Таким образом,
На каждом шаге мы выбирали ;k путем точного линейного поиска, таким образом
Этот алгоритм сопряженных векторов имеет геометрическую интерпретацию, которая не только является производной направления- равный нулю в новой точке вдоль направления pk , он равен нулю во всех предыдущих направлениях поиска p1 , . . . , pk).
Теорема 1 (теорема Люэнбергера о расширяющемся подпространстве).
Пусть {pi }ni=1 ; последовательность векторов в Rn, сопряженных с (положительно определенной) матрицей A и f (x) = 1/2 xT Ax - bT x + c. Тогда для любого x1 последовательность {xk }, сгенерированная в соответствии с (A.7.7) и (A.7.8) обладает свойством, заключающимся в том, что производная от f по направлению pi обращается в нуль в точке xk+1, если i ; k; т.е. Dpi f (xk+1 ) = 0.
Доказательство: для i ; k мы можем записать xk+1 как:
Поскольку ;f (x) = Ax ; b , мы имеем
Так
Теперь (Dxi+1 f )(pi ) = 0 , поскольку точка xi+1 была получена путем точного линейного поиска в направлении pi . Но все члены в сумме по j также равны нулю, поскольку j > i и pTi Ap j = 0 в силу сопряженности. Таким образом, (Dpi f )(xk+1 ) = 0.
Теорема о подпространстве показывает, что, поскольку мы используем сопряженные векторы, оптимизирующиеся в направлении pk, это не нарушайте оптимальности по сравнению с предыдущими направлениями поиска. В частности, после выполнения n шагов алгоритма мы имеем (Dxn+1 f )(pi ) = ;f T (xn+1 )pi = 0, для i = 1, . . . , n. n уравнений можно записать в более компактной форме в виде:

ЧЕРНОВИК от 9 марта 2010 г.  559 Многомерная минимизация: квадратичные функции
Квадратная матрица P = (p1 , p2 , ... pn ) обратима, поскольку pi сопряжены, поэтому ;f (xn+1 ) = 0:  точка xn+1 является минимумом x; квадратичной функции f . Таким образом, в отличие от градиентного спуска, для квадратичная функция алгоритм сопряженных векторов сходится за конечное число шагов.
A.7.4 Алгоритм сопряженных градиентов
Алгоритм сопряженных градиентов является частным случаем алгоритма сопряженных векторов, в котором  процедура Грам-Шмидта становится очень простой. Мы не используем заранее определенный набор сопряженных векторов, а создаем их ‘на лету’. После k-шагов алгоритма сопряженных векторов нам нужно построить вектор pk+1, который сопряжен с p1 , . . . , pk . Это можно сделать, применив процедуру Грама-Шмидта к любому вектору v, линейно независимому от векторов p1 , . . . , pk . В алгоритме сопряженных градиентов выполняется специальный выбор v = ;;f (xk+1 ). Согласно теореме о подпространстве, градиент в новой точке xk+ 1 ортогонален pi , i = 1, . . . , k. Таким образом , ;f (xk+1 ) линейно не зависит от p1 , . . . , pk и является допустимым выбором для v, если только ;f (xk+1 ) = 0. В последнем случае xk+1 - это наш минимум, и мы закончили, и отныне будем считать, что ;f (xk+1 ) ; 0. Используя обозначение gk = ;f (xk ), уравнение для нового направления поиска, заданное процедурой Грама-Шмидта, выглядит следующим образом:
Поскольку gk + 1 ортогонально pi, i = 1, ... , k, то по теореме о подпространстве мы имеем pT
k + 1 gk + 1 = ;gk + 1 gk + 1 . Таким образом, ;k+1 можно записать как
и, в частности, ;k+1 ; 0. Теперь мы хотим показать, что, поскольку мы также использовали алгоритм сопряженных градиентов на предыдущих этапах, в уравнении (A.7.13) все члены, кроме последнего, в сумме по i равны нулю. Будем считать, что k > 0, поскольку на первом шаге (k = 0) мы просто установили p1 = ;g1 . Сначала обратите внимание, что
и поскольку ;k+1 ;0:
Таким образом, в уравнении (A.7.13):
Поскольку pi получено путем применения процедуры Грама-Шмидта к градиентам  gi, теорема подпространства gk + 1 T   pi =0 также подразумевает  gk + 1 T gi= 0 для i = 1, . . . , k. Это показывает, что
Следовательно, уравнение (A.7.13) упрощается до
Это можно представить в еще более простой форме, применив уравнение (A.7.14) к ;k:
Мы запишем это в виде
, где
560 ЧЕРНОВАЯ отметка 9 марта 2010г. Многомерная минимизация: квадратичные функции

Алгоритм  31 Сопряженного градиента для минимизации функции f (x)
2: Выбираем x1 .
пока gk 6= 0, выполните
ak = argmin f (xk + ak pk )
: Поиск по строке
10: конец, пока
Формула (A.7.21) для ;k предложена Флетчером и Ривзом. Поскольку градиенты ортогональны, ;k также можно записать в виде
это формула Полака-Рибьера. Выбор между двумя выражениями для ;k может иметь некоторое значение, если f не является квадратичным.
A.7.5 Метод Ньютона
Рассмотрим функцию f (x), минимум которой мы хотим найти. Есть разложения в ряд Тейлора до второго порядка дает
Матрица H является мешковиной\гессианом\. Дифференцируя правую часть относительно ; (или, что эквивалентно, завершая квадрат), мы обнаруживаем, что правая часть имеет наименьшее значение, когда
Следовательно, процедура оптимизации для минимизации E задается обновлением Newton
Преимущество метода Ньютона перед градиентным спуском заключается в том, что уменьшение целевой функции не зависит от линейного изменения координат, y = Mx.
A.7.6 Квазиньютоновские методы
Для крупномасштабных задач инверсия гессиана требует больших вычислительных затрат, особенно если матрица близка к сингулярной. Альтернативой является настройка итерации
Это очень общая форма; если Sk = A;1, то мы имеем метод Ньютона, в то время как если Sk = I, то мы имеем самый крутой спуск. В целом, казалось бы, было бы хорошей идеей выбрать  Sk в качестве приближения к обратному Гессиану. Также обратите внимание, что важно, чтобы  Sk был положительно определенным, чтобы для малых ;k мы получили метод спуска. Идея, лежащая в основе большинства квазиньютоновских методов, состоит в том, чтобы попытаться построить приблизительный обратный гессиан ~Hk, используя информацию, собранную по ходу спуска, и установить  Sk = ~Hk . Как мы видели, для задачи квадратичной оптимизации мы имеем соотношение
ЧЕРНОВИК от 9 марта 2010 561 Ограниченная оптимизация с использованием множителей Лагранжа
Алгоритм 32 Квазиньютон для минимизации функции f (x)
2: Выбираем x1
4: при gk 6= 0 делаем
 Поиск по строке
 и обновить Hk+1
10: конец, пока
Определение
мы видим, что уравнение A.7.27 принимает вид
Разумно требовать, чтобы
После n линейно независимых шагов мы получили бы ~Hn+1 = A;1 . При k < n существует бесконечное число решения для ~Hk+1, удовлетворяющие уравнению A.7.30. Популярным выбором является обновление Broyden-Fletcher-Goldfarb-Shanno \Бройден-Флетчер-Гольдфарб-Шано\ (или BFGS), предоставленное
Это поправка 2-го ранга к ~Hk, построенная из векторов sk и ~Hk yk .
Векторы направлений p1 , p2 , . . . , pk , pk = ;~Hk gk  , полученные с помощью алгоритма, подчиняются
Уравнение A.7.33 называется наследственным свойством. В нашем обозначении sk = ;k pk , и поскольку ; отлично от нуля, уравнение A.7.32 также можно записать в виде
Поскольку pk являются A-сопряженными и поскольку мы последовательно минимизируем f в этих направлениях, мы видим, что алгоритм BFGS является методом сопряженного направления; при выборе H1 = I это фактически метод сопряженного градиента. Обратите внимание, что требования к памяти для квазиньютоновских методов квадратично изменяются в зависимости от количества переменных и, следовательно, обычно используются для решения небольших задач. BFGS с ограниченной памятью сокращает объем памяти, используя только последние обновления l при вычислении приближенного обратного уравнения Гесса, уравнения (A.7.31). Напротив, требования к памяти для методов с чистым сопряженным градиентом масштабируются только линейно с размерностью x.
A.7 Ограниченная оптимизация с использованием множителей Лагранжа
Единственное ограничение
Рассмотрим сначала задачу минимизации f (x) при соблюдении единственного ограничения c (x) = 0. Представим, что мы уже определили x, который удовлетворяет ограничению, то есть c (x) = 0. Как мы можем определить, минимизирует ли это x
562 ЧЕРНОВИК от 9 марта 2010 г. Ограниченная оптимизация с использованием множителей Лагранжа
функция f ? Нам разрешено искать меньшие значения функции только вокруг этого x в направлениях, которые соответствуют ограничению. При небольшом изменении ; изменение ограничения равно


L(x, ;) = f (x) ; ;c(x)(A.7.4)
Следовательно, чтобы ограничение оставалось удовлетворенным, мы можем выполнять поиск только в таком направлении, при котором ; ·;c(x) = 0, то есть в направлениях ;, ортогональных ;c(x). Итак, давайте рассмотрим изменение f вдоль направления ;, где ; · ;c(x) = 0,
Поскольку мы ищем точку x, которая минимизирует функцию f , мы требуем, чтобы x была неподвижной точкой, ;f (x) · ; = 0. Таким образом, ; должно быть ортогонально как ;f (x), так и ;c(x). Поскольку мы хотим ограничить ; как можно меньше, наибольшая свобода обеспечивается за счет того, что ;f (x) должно быть параллельно ;c(x), так что
для некоторого ; ; R. Таким образом, для решения задачи оптимизации мы ищем точку x, такую, что ;f (x) = ;;c(x), для некоторого ;, и для которого c(x) = 0. Альтернативная формулировка этого двойного требования состоит в поиске x и ;, которые совместно минимизируют лагранжиан
Дифференцируя по x, мы получаем требование ;f (x) = ;;c(x), а дифференцируя по ;, мы получаем, что c(x) = 0.
Множество ограничений
Рассмотрим задачу оптимизации f (x) с учетом ограничений ci (x) = 0, i = 1, ... , r < n, где n - размерность пространства. Обозначим через S n ;r мерное подпространство x, которое подчиняется ограничениям. Предположим, что x; является таким оптимумом. Как и в неограниченном случае, мы рассматриваем возмущения от v до x;, но теперь такие, что v лежит в S
Пусть a;i = ;ci (x; ). Таким образом, чтобы возмущение оставалось в пределах S, мы требуем, чтобы vT a;i = 0 для всех i = 1, . . . , r. Пусть A; - матрица, столбцы которой равны a;1 , a;2 , . . . , a;r . Тогда это условие можно переписать как A; v = 0. Для локального оптимума мы также требуем, чтобы vT ;f = 0 для всех v в S. Мы видим, что ;f должно быть ортогонально v, а v должно быть ортогонально a;i ’-ым. Этого можно достичь, заставив ;f быть линейной комбинацией a;i, т.е.
Геометрически это означает, что вектор градиента перпендикулярен касательной к плоскости S в точке x;. Эти условия приводят к использованию метода множителей Лагранжа для задач оптимизации с ограничениями на равенство.  Метод требует нахождения x; и ;;, которые решают уравнения
Существует n + r уравнений и n + r неизвестных, поэтому система хорошо определена. Однако в целом система нелинейна (по x), и поэтому ее может быть нелегко решить. Мы можем переформулировать эти условия, введя функцию Лагранжа
Частные производные от L по x и ; воспроизводят уравнения A.7.7 и A.7.8. Следовательно, необходимым условием для локального минимизатора является то, что x; , ;; является стационарной точкой функции Лагранжа. Обратите внимание, что эта стационарная точка является не минимальной, а седловой, поскольку L линейно зависит от ;. Мы задали необходимые и достаточные условия первого порядка для локального оптимума. Чтобы показать, что этот оптимум является локальным минимумом, нам нужно было бы рассмотреть условия второго порядка, аналогичные положительной определенности Гессиана \ Гессена\ в неограниченном случае; это можно сделать, но здесь рассматриваться не будет.
ПРОЕКТ от 9 марта 2010 г. 563. Неограниченная оптимизация с использованием множителей Лагранжа
564
ЧЕРНОВИК от 9 марта 2010 г.
Библиография
[1] Л. Ф. Эббот, Дж. А. Варела, К. Сен и С. Б. Нельсон. Синаптическая депрессия и контроль усиления коры головного мозга. Science,
275: 220-223, 1997.
[2] Д. Х. Экли, Г. Э. Хинтон и Т. Дж. Сейновски. Алгоритм обучения для машин Больцмана. Мыслительный
Science, 9: 147-169, 1985.
[3] Р. П. Адамс и Д. Дж. К. Маккей. Байесовское онлайновое определение точки изменения. Кавендишская лаборатория, департамент
физический факультет Кембриджского университета, Кембридж, Великобритания, 2006. arXiv: 0710.3742v1 [stat.ML].
[4] Э. Айролди, Д. Блей, Э. Син и С. Файенберг. Модель скрытого смешанного членства для реляционных данных. В
LinkKDD ’05: Материалы 3-го международного семинара по обнаружению ссылок, стр. 82-89, Нью-Йорк, Нью-Йорк,
США, 2005. ACM.
[5] Э. М. Айролди, Д. М. Блей, С. Э. Файенберг и Э. П. Син. Стохастические блочные модели со смешанным членством. Журнал
исследований в области машинного обучения, 9: 1981-2014, 2008.
[6] Д. Л. Олспач и Х. У. Соренсон. Нелинейная байесовская оценка с использованием приближений суммы Гаусса.
Транзакции IEEE по автоматическому управлению, 17(4):439-448, 1972.
[7] S-i. Амари. Естественный градиент эффективно работает при обучении. Нейронные вычисления, 10(2):251-276, 1998.
[8] S-i. Амари. Естественное градиентное обучение для более или менее полных баз в ICA. Нейронные вычисления,
11: 1875-1883, 1999.
[9] И. Андруцопулос, Дж. Кутсиас, К. В. Чандринос и К. Д. Спиропулос. Экспериментальное сравнение
наивной байесовской и основанной на ключевых словах антиспам-фильтрации с личными сообщениями электронной почты. В ходе разбирательства по
23-я ежегодная международная конференция ACM SIGIR по исследованиям и разработкам в области поиска информации,
стр. 160-167, Нью-Йорк, Нью-Йорк, США, 2000. ACM.
[10] С. Арора и К. Лунд. Сложность аппроксимаций. В разделе Алгоритмы аппроксимации для NP-сложных задач, страницы
399–446. Издательство PWS Publishing Co., Бостон, Массачусетс, США, 1997.
[11] Ф. Р. Бах и М. И. Джордан. Тонкие деревья соединений. В работе Т. Г. Диттериха, С. Беккера и З. Гахрамани, редактор,
Достижения в области нейронных систем обработки информации (NIPS), номер 14, страницы 569-576, Кембридж, Массачусетс,
2001. Издательство Массачусетского технологического института.
[12] Ф. Р. Бах и М. И. Джордан. Вероятностная интерпретация канонического корреляционного анализа. компьютерная наука
Отдел и департамент статистики 688, Калифорнийский университет в Беркли, Беркли, США, 2005 год.
[13] Ю. Бар-Шалом и Сяо-Ронг Ли. Оценка и отслеживание: принципы, методы и программное обеспечение. Artech
Хаус, Норвуд, Массачусетс, 1998.
[14] Д. Барбер. Динамические байесовские сети с детерминированными таблицами. В работе С. Беккера, С. Труна и К. Обермайер,
редакторы, "Достижения в области нейронных систем обработки информации" (NIPS), номер 15, страницы 713-720, Кембридж,
Массачусетс, 2003. Издательство Массачусетского технологического института.
[15] Д. Барбер. Обучение с помощью импульсных нейронных сборок. У С. Беккера, С. Труна и К. Обермайер, редактор,
Достижения в области нейронных систем обработки информации (NIPS), номер 15, страницы 149-156, Кембридж, Массачусетс,
2003. Издательство Массачусетского технологического института.
565 БИБЛИОГРАФИЯ
библиография
[16] Д. Барбер. Работают ли два классификатора одинаково? Обработка с использованием байесовской проверки гипотез. IDIAP-
RR 57, IDIAP, улица Симплон, 4, Мартиньи, CH-1920, Швейцария, май 2004 г. IDIAP-RR 04-57.
[17] Д. Барбер. Коррекция математического ожидания для сглаживания при переключении линейных моделей пространства состояний по Гауссу. Журнал
of Machine Learning Research, 7: 2515-2540, 2006.
[18] Д. Барбер. Матрицы кликов для статистической декомпозиции графов и параметризации ограниченных положительных
Определенных матриц. В работе Д. А. Макаллестера и П. Миллимаки, редакторов, "Неопределенность в искусственном интеллекте",
номер 24, страницы 26-33, Корваллис, Орегон, США, 2008. AUAI press.
[19] Д. Барбер и Ф. В. Агаков. Изучение коррелированных последовательностей в сети пикирующих нейронов с использованием максимального
вероятность. Отчеты об исследованиях в области информатики EDI-INF-RR-0149, Эдинбургский университет, 2002.
[20] Д. Барбер и Ф.В. Агаков. Алгоритм IM: вариационный подход к максимизации информации. В
журнале Advances in Neural Information Processing Systems (NIPS), номер 16, 2004.
[21] Д. Барбер и К. М. Бишоп. Сравнение байесовских моделей методом Монте-Карло. В книге М. С. Мозера, М. И.
Джордана и Т. Петше "Достижения в области нейронных систем обработки информации" (NIPS), номер 9, страницы
333-339, Кембридж, Массачусетс, 1997. Издательство Массачусетского технологического института.
[22] Д. Барбер и К. М. Бишоп. Коллективное обучение в байесовских нейронных сетях. В книге "Нейронные сети и
машинное обучение", стр. 215-237. Springer, 1998.
[23] Д. Барбер и С. Чьяппа. Унифицированный вывод для вариационных байесовских линейных гауссовых моделей пространства состояний.
Платт и Т. Хоффман, редакторы журнала Advances in Neural Information Processing Systems (NIPS),
номер 19, страницы 81-88, Кембридж, Массачусетс, 2007. Издательство Массачусетского технологического института.
[24] Д. Барбер и У. Вигеринк. Доступные вариационные структуры для аппроксимации графических моделей. В M. S.
Кернс, С. А. Солла и Д. А. Кон, редакторы журнала "Достижения в области нейронных систем обработки информации" (NIPS),
номер 11, страницы 183-189, Кембридж, Массачусетс, 1999. Издательство Массачусетского технологического института.
[25] Д. Барбер и К. К. И. Уильямс. Гауссовские процессы для байесовской классификации с помощью гибридного метода Монте-Карло. В
книге М. С. Мозера, М. И. Джордана и Т. Петше, редакторов, "Достижения в области нейронных систем обработки информации", NIPS
9, стр. 340-346, Кембридж, Массачусетс, 1997. Издательство Массачусетского технологического института.
[26] Р. Дж. Бакстер. Точно решаемые модели в статистической механике. Academic Press, 1982.
[27] М. Дж. Бил, Ф. Фальчиани, З. Гахрамани, К. Рангел и Д. Л. Уайлд. Байесовский подход к реконструкции
генетических регуляторных сетей со скрытыми факторами. Биоинформатика, (21): 349-356, 2005.
[28] А. Беккер и Д. Гейгер. Достаточно быстрый алгоритм для нахождения деревьев клик, близких к оптимальным. Искусственный
Интеллект, 125(1-2):3-17, 2001.
[29] А. Дж. Белл и Т. Дж. Сейновски. Основанный на максимизации информации подход к слепому разделению и слепой
Деконволюция. Нейронные вычисления, 7(6):1129-1159, 1995.

[30] Р. Э. Беллман. Динамическое программирование. Издательство Принстонского университета, Принстон, Нью-Джерси, 1957. Издание
в мягкой обложке издательством Dover Publications (2003).
[31] Й. Бенгио и П. Фраскони. HMMS ввода-вывода для обработки последовательностей. IEEE Trans. Нейронные сети,
(7): 1231-1249, 1996.
[32] А. Л. Бергер, С. Д. Делла Пьетра и В. Дж. Д. Делла Пьетра. Подход с максимальной энтропией к
обработке естественного языка. Компьютерная лингвистика, 22(1):39-71, 1996.
[33] Дж. О. Бергер. Теория статистических решений и байесовский анализ. Springer, второе издание, 1985.
[34] Д. П. Берцекас. Динамическое программирование и оптимальное управление. Athena Scientific, второе издание, 2000.
[35] Дж. Бесаг. Пространственные взаимодействия и статистический анализ решетчатых систем. Журнал Королевского статистического
Общество, Серия В, 36(2):192-236, 1974.
[36] Дж. Бесаг. О статистическом анализе грязных фотографий. Журнал Королевского статистического общества, Серия В,
48: 259-302, 1986.
[37] Дж. Бесаг и П. Грин. Пространственная статистика и байесовские вычисления. Журнал Королевского статистического общества,
серия В, 55: 25-37, 1993.
566
ЧЕРНОВИК БИБЛИИ от 9 марта 2010 года
библиография
Бирман. Обновление измерений с использованием U-D факторизации. Automatica, 12: 375-382, 1976.
[39] Н. Л. Биггс. Дискретная математика. Издательство Оксфордского университета, 1990.
[40] К. Биндер и А. П. Янг. Вращающиеся очки: экспериментальные факты, теоретические концепции и открытые вопросы.
Перераб. Phys., 58 (4): 801-976, октябрь 1986 г.
[41] К. М. Бишоп. Нейронные сети для распознавания образов. Издательство Оксфордского университета, 1995.
[42] К. М. Бишоп. Распознавание образов и машинное обучение. Спрингер, 2006.
[43] К. М. Бишоп и М. Свенсен. Байесовские иерархические комбинации экспертов. В книге У. Кьерульфа и К. Мика, редакторов,
Труды Девятнадцатой конференции по неопределенности в искусственном интеллекте, страницы 57-64. Морган Кауфманн,
2003.
[44] Д. Блей, А. Нг и М. Джордан. Скрытое распределение Дирихле. Журнал исследований в области машинного обучения, (3): 993–
1022, 2003.
[45] Р. Р. Букерт. Байесовские сети убеждений: от построения к логическому выводу. Докторская диссертация, Университет Утрехта,
1995.
[46] С. Бойд и Л. Ванденберг. Выпуклая оптимизация. Издательство Кембриджского университета, 2004.
[47] Ю. Бойков и В. Колмогоров. Экспериментальное сравнение алгоритмов минимального сокращения/максимального расхода для
минимизации энергии в зрении. IEEE Trans. Анализ шаблонов. Мах. Интеллект., 26(9):1124-1137, 2004.
[48] Ю. Бойков, О. Векслер и Р. Забих. Быстрая приближенная минимизация энергии с помощью графических разрезов. Перевод IEEE.
Анализ шаблонов. Мах. Intell., 23: 1222-1239, 2001.
[49] М. Бранд. Инкрементная сингулярная декомпозиция неопределенных данных с пропущенными значениями. На европейском
Конференция по компьютерному зрению (ECCV), страницы 707-720, 2002.
[50] Дж. Бризе и Д. Хекерман. Поиск и устранение неисправностей на основе теории принятия решений: основа для ремонта и эксперимента.
В книге Э. Хорвица и Ф. Дженсена, редакторов, Неопределенность в искусственном интеллекте, номер 12, страницы 124-132, Сан-Франциско.
Франциско, Калифорния, 1996 год. Морган Кауфманн.
[51] Х. Бунке и Т. Целли. Скрытые марковские модели: применение в компьютерном зрении. Машинное восприятие и
искусственный интеллект. World Scientific Publishing Co., Inc., Ривер-Эдж, Нью-Джерси, США, 2001.
[52] У. Бунтайн. Уточнение теории на основе байесовских сетей. В книге "Неопределенность в искусственном интеллекте", номер 7,
страницы 52-60, Сан-Франциско, Калифорния, 1991. Морган Кауфманн.
[53] А. Кано и С. Мораль. Достижения в области интеллектуальных вычислений – IPMU, 1994, глава "Эвристические алгоритмы для
триангуляции графов", страницы 98-107. Номер 945 в "Конспектах лекций по компьютерным наукам". Springer-Verlag,
1995.
[54] О. Каппе, Э. Мулин и Т. Райден. Логический вывод в скрытых марковских моделях. Спрингер, Нью-Йорк, 2005.
[55] Э. Кастильо, Дж. М. Гутьеррес и А. С. Хади. Экспертные системы и вероятностные сетевые модели. Springer,
1997.
[56] А. Т. Джемгил. Байесовский вывод в моделях неотрицательной матричной факторизации. Технический отчет CUED/F-
INFENG/TR.609, Кембриджский университет, июль 2008.
[57] А. Т. Джемгил, Б. Каппен и Д. Барбер. Генеративная модель музыкальной транскрипции. Транзакции IEEE
по обработке аудио, речи и языка., 14(2):679-694, 2006.
[58] Х. С. Чанг, М. К. Фу, Дж. Ху и С. И. Маркус. Алгоритмы, основанные на моделировании марковских процессов принятия решений.
Спрингер, 2007.
[59] С. Чьяппа и Д. Барбер. Байесовские линейные гауссовы модели пространства состояний для декомпозиции биосигнала. Сигнал
Обработка писем, 14(4):267-270, 2007.
[60] С. Чиб и М. Дюкер. Немарковское переключение режимов с эндогенными состояниями и изменяющимся во времени состоянием
Сильные стороны. 600 летних встреч Эконометрического общества Северной Америки 2004 года, Эконометрическое общество, август
2004.
[61] С. К. Чоу и С. Н. Лю. Аппроксимация дискретных распределений вероятностей с помощью деревьев зависимостей. IEEE
Труды по теории информации, 14(3):462-467, 1968.
ПРОЕКТ от 9 марта 2010 г.
567 БИБЛИОГРАФИЯ
библиография
[62] П. С. Черчленд и Т. Дж. Сейновски. Вычислительный мозг. Издательство Массачусетского технологического института, Кембридж, Массачусетс, США, 1994.
[63] Д. Кон и Х. Чанг. Учимся вероятностно идентифицировать авторитетные документы. П. Лэнгли, редактор,
Международная конференция по машинному обучению, номер 17, стр. 167-174. Морган Кауфманн, 2000.
[64] Д. Кон и Т. Хофманн. Недостающее звено - вероятностная модель содержания документа и гипертекста.
Связь. Номер 13, страницы 430-436, Кембридж, Массачусетс, 2001. Издательство Массачусетского технологического института.
[65] А. С. С. Кулен, Р. Кюн и П. Соллих. Теория нейронных систем обработки информации. Оксфордский университет
Издательство, 2005.
[66] Г. Ф. Купер и Э. Херсковиц. Байесовский метод построения вероятностных сетей на основе данных.
Машинное обучение, 9(4):309-347, 1992.
[67] А. Кордуняну и К. М. Бишоп. Выбор вариационной байесовской модели для смешанных распределений. В
Т. Яаккола и Т. Ричардсон, редакторы, Искусственный интеллект и статистика, стр. 27-34. Морган Кауфманн,
2001.
[68] М. Т. Кавер и Дж. А. Томас. Элементы теории информации. Уайли, 1991.
[69] Р. Г. Коуэлл, А. П. Дэвид, С. Л. Лауритцен и Д. Дж. Шпигельхальтер. Вероятностные сети и экспертные системы.
Springer, 1999.
[70] Д. Р. Кокс и Н. Вермут. Многомерные зависимости. Чепмен и Холл, 1996.
[71] Н. Кристианини и Дж. Шоу-Тейлор. Введение в методы опорных векторов. Кембриджский университет
Издательство, 2000.
[72] П. Данготье, Р. Хербрих, Т. Минка и Т. Грэпел. Истинное мастерство сквозь время: возвращение к истории
шахмат. Платт и Т. Хоффман, редакторы, "Достижения в области нейронных систем обработки информации"
(NIPS), номер 19, страницы 569-576, Кембридж, Массачусетс, 2007. Издательство Массачусетского технологического института.
[73] Х. А. Дэвид. Метод парных сравнений. Издательство Оксфордского университета, Нью-Йорк, 1988.
[74] А. П. Давид. Диаграммы влияния для причинно-следственного моделирования и логических выводов. Международный статистический обзор, 70:161–
189, 2002.
[75] А. П. Давид и С. Л. Лауритцен. Гипермарковские законы в статистическом анализе разложимых графических
Модели. Анналы статистики, 21(3):1272-1317, 1993.
[76] П. Дайан и Л.Ф. Эббот. Теоретическая неврология. Издательство Массачусетского технологического института, 2001.
[77] П. Даян и Г. Э. Хинтон. Использование максимизации математического ожидания для обучения с подкреплением. Нейронные вычисления
, 9: 271-278, 1997.
[78] Т. Де Би, Н. Кристианини и Р. Росипал. Справочник по геометрическим вычислениям: приложения в моделировании
Распознавание, компьютерное зрение, нейронные вычисления и робототехника, глава "Собственные проблемы распознавания образов".
Springer-Verlag, 2005.

[79] Р. Дехтер. Исключение ошибок: объединяющая структура для алгоритмов вероятностного вывода. В книге Э. Хорвица
и Ф. Дженсена, редакторов, "Неопределенность в искусственном интеллекте", стр. 211-219, Сан-Франциско, Калифорния, 1996 г. Морган
Кауфманн.
[80] С. Дидерих и М. Оппер. Изучение коррелированных паттернов в сетях спинового стекла с помощью локальных правил обучения.
Physical Review Letters, 58(9):949-952, 1986.
[81] Р. Дизель. Теория графов. Springer, 2005.
[82] А. Дусе и А. М. Йохансен. Учебное пособие по фильтрации частиц и сглаживанию: пятнадцать лет спустя. В
Д. Крисан и Б. Розовски, редакторы Оксфордского справочника по нелинейной фильтрации. Издательство Оксфордского университета, 2009.
[83] Р. О. Дуда, П. Э. Харт и Д. Г. Сторк. Классификация паттернов. Wiley-Interscience Publication, 2000.
[84] Р. Дурбин, С. Р. Эдди, А. Крог и Г. Митчисон. Анализ биологических последовательностей: вероятностные модели
белков и нуклеиновых кислот. Издательство Кембриджского университета, 1999.
[85] А. Дюринг, А. С. С. Кулен и Д. Шеррингтон. Фазовая диаграмма и емкость
памяти нейронных сетей, обрабатывающих последовательности. Журнал физики A, 31: 8607-8621, 1998.
568
ЧЕРНОВИК БИБЛИИ от 9 марта 2010 года
библиография
[86] Дж. М. Гутьеррес, Э. Кастильо и А. С. Хади. Экспертные системы и вероятностные сетевые модели. Springer Verlag,
1997.
[87] Дж. Эдмондс и Р. М. Карп. Теоретические усовершенствования алгоритмической эффективности для задач сетевого потока.
Журнал ACM, 19(2):248-264, 1972.
[88] Р. Эдвардс и А. Сокал. Обобщение представления Фортиума-Кастелейна-Свендсона-Вана и
алгоритма Монте-Карло. Physical Review, D, 38: 2009-2012, 1988.
[89] А. Э. Эло. Рейтинг шахматистов прошлого и настоящего. Арко, Нью-Йорк, второе издание, 1986.
[90] Ю. Эфраим и У. Дж. Дж. Робертс. Возвращаясь к авторегрессионному скрытому марковскому моделированию речевых сигналов. IEEE
Письма по обработке сигналов, 12 (2): 166-169, февраль 2005.
[91] Е. Ерошева, С. Файнберг и Дж. Лафферти. Модели смешанного членства в научных публикациях. В Трудах
Национальной академии наук, том 101, страницы 5220-5227, 2004.
[92] Р-Э. Фан, П-Х. Чен и Си Джей Лин. Выбор рабочего набора с использованием информации второго порядка для обучения
Методы опорных векторов. Журнал исследований машинного обучения, 6: 1889-1918, 2005.
[93] П. Фернхед. Точный и эффективный байесовский вывод для задач с несколькими точками изменения. Технический отчет,
факультет математики и статистики Ланкастерского университета, 2003.
[94] Г. Х. Фишер и И. В. Моленаар. Модели Раша: основы, последние разработки и приложения.
Спрингер, Нью-Йорк, 1995.
[95] М. Э. Фишер. Статистическая механика димеров на плоской решетке. Physical Review, 124: 1664-1672, 1961.
[96] Б. Фрей. Расширение факторных графов для объединения направленных и ненаправленных графических моделей. В С. Кротком и
У. Кьерульф, редактор, Неопределенность в искусственном интеллекте, номер 19, страницы 257-264. Морган Кауфман,
2003.
[97] Н. Фридман, Д. Гейгер и М. Голдшмидт. Байесовские сетевые классификаторы. Машинное обучение, 29: 131-163,
1997.
[98] С. Фрювирт-Шнаттер. Модели конечной смеси и марковского переключения. Спрингер, 2006.
[99] М. Фриденберг. Свойство Маркова цепного графа. Scandanavian Journal of Statistics, 17: 333-353, 1990.
[100] Т. Фермстон и Д. Барбер. Решение задач детерминированной политики (PO) с использованием максимизации ожиданий и
Антифриз. В статье Э. Сузуки и М. Себага, редакторов Европейской конференции по машинному обучению и принципам
и практике поиска знаний в базах данных, сентябрь 2009 г. Семинар по обучению и интеллектуальному анализу данных
для робототехники.
[101] А. Галка, О. Ямашита, Т. Одзаки, Р. Бискай и П. Вальдес-Соса. Решение динамической обратной задачи
генерации ЭЭГ с использованием пространственно-временной фильтрации Калмана. NeuroImage, (23): 435-453, 2004.
[102] П. Ганди, Ф. Бромберг и Д. Маргаритис. Изучение структуры сети Маркова с использованием нескольких тестов на независимость.
В материалах Международной конференции SIAM по интеллектуальному анализу данных, стр. 680-691, 2008.
[103] М. Р. Гэри и Д. С. Джонсон. Компьютеры и неразрешимость, Руководство по теории NP-полноты.
У.Х. Фриман и компания, Нью-Йорк, 1979.
[104] А. Гелб. Прикладная оптимальная оценка. Издательство Массачусетского технологического института, 1974.
[105] А. Гельман, Г. О. Робертс и У. Р. Гилкс. Эффективные правила прыжков в Метрополию. В книге Дж. О. Бернардо, Дж
. М. Бергера, А. П. Давида и А. Ф. М. Смита, редакторы, Байесовская статистика, том 5, страницы 599-607. Оксфорд
Издательство университета, 1996.
[106] С. Геман и Д. Геман. Стохастическая релаксация, распределения Гиббса и байесовское восстановление изображений. В
книге "Чтения в неуверенных рассуждениях", стр. 452-472, Сан-Франциско, Калифорния, США, 1990. Издательство Моргана Кауфмана
Инк.
[107] М. Г. Гентон. Классы ядер для машинного обучения: обзор статистики. Журнал машинного обучения
Research, 2: 299-312, 2001.
[108] У. Герстнер и У. М. Кистлер. Модели пиковых нейронов. Издательство Кембриджского университета, 2002.
ЧЕРНОВИК от 9 марта 2010 г.
569 БИБЛИОГРАФИЯ
библиография
[109] З. Гахрамани и М. Дж. Бил. Вариационный вывод для байесовских комбинаций факторных анализаторов. В соавторстве
Солла, Т. К. Лин и К-Р. Мюллер, редактор, Достижения в области нейронных систем обработки информации (NIPS),
номер 12, страницы 449-455, Кембридж, Массачусетс, 2000. Издательство Массачусетского технологического института.
[110] З. Гахрамани и Г. Э. Хинтон. Вариационное обучение для переключения моделей пространства состояний. Нейронные вычисления,
12(4):963-996, 1998.
[111] А. Гиббонс. Алгоритмическая теория графов. Издательство Кембриджского университета, 1991.
[112] У. Р. Джилкс, С. Ричардсон и Д. Дж. Шпигельхальтер. Марковская цепочка Монте-Карло на практике. Chapman & Hall,
1996.
[113] М. Джиролами и А. Кабан. Об эквивалентности между PLSI и LDA. В материалах 26-й ежегодной
международной конференции ACM SIGIR по исследованиям и разработкам в области поиска информации, стр. 433-434,
Нью-Йорк, Нью-Йорк, США, 2003. ACM Press.
[114] М. Э. Гликман. Оценка параметров в больших экспериментах по динамическому парному сравнению. Прикладная статистика,
48: 377-394, 1999.
[115] А. Глоберсон и Т. Яаккола. Приближенный вывод с использованием декомпозиции плоского графа. В статье Б. Шелкопфа,
Дж. Платта и Т. Хоффмана, редакторов журнала "Достижения в области нейронных систем обработки информации" (NIPS), номер 19,
страницы 473-480, Кембридж, Массачусетс, 2007. Издательство Массачусетского технологического института.
[116] Д. Голдберг, Д. Николс, Б. М. Оки и Д. Терри. Использование коллаборативной фильтрации для
создания информационного гобелена. Communications ACM, 35: 61-70, 1992.
[117] Г. Х. Голуб и К. Ф. ван Лоан. Матричные вычисления. Издательство Университета Джона Хопкинса, 3-е издание, 1996.
[118] М. К. Голумбич и И. Бен-Арройо Хартман. Теория графов, комбинаторика и алгоритмы. Springer-Verlag,
2005.
[119] К. Гутис. Графический метод для решения задачи анализа принятия решений. Труды IEEE по системам, человеку
и кибернетике, 25: 1181-1193, 1995.
[120] П. Дж. Грин и Б. У. Сильверман. Непараметрическая регрессия и обобщенные линейные модели, том 58
монографий по статистике и прикладной теории вероятностей. Чепмен и Холл, 1994.
[121] Д. М. Грейг, Б. Т. Портеус и А. Х. Сехольт. Точная максимальная апостериорная оценка для бинарных изображений.
Журнал Королевского статистического общества, Серия В, 2: 271-279, 1989.
[122] Г. Гримметт и Д. Стирзакер. Вероятность и случайные процессы. Издательство Оксфордского университета, второе издание,
1992.