Положительно определенное ядро - Positive-definite kernel

В теория операторов, раздел математики, положительно определенное ядро является обобщением положительно определенная функция или положительно определенная матрица. Впервые он был представлен Джеймс Мерсер в начале ХХ века в контексте решения интегральные операторные уравнения. С тех пор положительно определенные функции и их различные аналоги и обобщения возникли в различных разделах математики. Они встречаются в природе в Анализ Фурье, теория вероятности, теория операторов, комплексная теория функций, момент проблемы, интегральные уравнения, краевые задачи за уравнения в частных производных, машинное обучение, проблема встраивания, теория информации, и другие области.

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

Определение

Позволять ${displaystyle {mathcal {X}}}$ быть непустым набором, иногда называемым набором индексов. А симметричная функция ${displaystyle K: {mathcal {X}} imes {mathcal {X}} o mathbb {R}}$ называется положительно определенным (п.о.) ядром на ${displaystyle {mathcal {X}}}$ если

${displaystyle sum _ {i = 1} ^ {n} sum _ {j = 1} ^ {n} c_ {i} c_ {j} K (x_ {i}, x_ {j}) geq 0quad quad quad quad ( 1.1)}$

справедливо для любого ${displaystyle x_ {1}, точки, x_ {n} в {mathcal {X}}}$, данный ${displaystyle nin mathbb {N}, c_ {1}, dots, c_ {n} in mathbb {R}}$.

В теории вероятностей иногда различают положительно определенные ядра, для которых равенство в (1.1) влечет ${displaystyle c_ {i} = 0; (для всех i)}$, и положительные полуопределенные (p.s.d.) ядра, которые не накладывают этого условия. Обратите внимание, что это эквивалентно требованию, чтобы любая конечная матрица, построенная путем попарного вычисления, ${displaystyle mathbf {K} _ {ij} = K (x_ {i}, x_ {j})}$, имеет либо полностью положительный (p.d.), либо неотрицательный (p.s.d.) собственные значения.

В математической литературе ядра обычно представляют собой комплексные функции, но в этой статье мы предполагаем, что функции действительны, что является обычной практикой в ​​приложениях p.d. ядра.

Некоторые общие свойства

• Для семьи п.д. ядра ${displaystyle (K_ {i}) _ {iin mathbb {N}}, K_ {i}: {mathcal {X}} имеет {mathcal {X}} o mathbb {R}}$
  • Сумма ${displaystyle sum _ {i = 1} ^ {n} lambda _ {i} K_ {i}}$ это p.d., учитывая ${displaystyle lambda _ {1}, dots, lambda _ {n} geq 0}$
  • Продукт ${displaystyle K_ {1} ^ {a_ {1}} точки K_ {n} ^ {a_ {n}}}$ это p.d., учитывая ${displaystyle a_ {1}, dots, a_ {n} в mathbb {N}}$
  • Лимит ${displaystyle K = lim _ {нет информации} K_ {n}}$ это p.d. если предел существует.
• Если ${displaystyle ({mathcal {X}} _ {i}) _ {i = 1} ^ {n}}$ - последовательность множеств, а ${displaystyle (K_ {i}) _ {i = 1} ^ {n}, K_ {i}: {mathcal {X}} _ {i} imes {mathcal {X}} _ {i} o mathbb {R} }$ последовательность п.о. ядра, затем оба

${displaystyle K ((x_ {1}, точки, x_ {n}), (y_ {1}, dots, y_ {n})) = prod _ {i = 1} ^ {n} K_ {i} (x_ {i}, y_ {i})}$ и

${displaystyle K ((x_ {1}, точки, x_ {n}), (y_ {1}, dots, y_ {n})) = сумма _ {i = 1} ^ {n} K_ {i} (x_ {i}, y_ {i})}$

являются p.d. ядра на ${displaystyle {mathcal {X}} = {mathcal {X}} _ {1} imes dots imes {mathcal {X}} _ {n}}$.

• Позволять ${displaystyle {mathcal {X}} _ {0} subset {mathcal {X}}}$. Тогда ограничение ${displaystyle K_ {0}}$ из ${displaystyle K}$ к ${displaystyle {mathcal {X}} _ {0} imes {mathcal {X}} _ {0}}$ также п.д. ядро.

Примеры p.d. ядра

• Распространенные примеры p.d. ядра, определенные на евклидовом пространстве ${displaystyle mathbb {R} ^ {d}}$ включают:
  • Линейное ядро: ${displaystyle K (mathbf {x}, mathbf {y}) = mathbf {x} ^ {T} mathbf {y}, quad mathbf {x}, mathbf {y} в mathbb {R} ^ {d}}$.
  • Полиномиальное ядро: ${displaystyle K (mathbf {x}, mathbf {y}) = (mathbf {x} ^ {T} mathbf {y} + r) ^ {n}, quad mathbf {x}, mathbf {y} в mathbb {R } ^ {d}, rgeq 0, ngeq 1}$.
  • Гауссово ядро ​​(Ядро RBF ): ${displaystyle K (mathbf {x}, mathbf {y}) = e ^ {- {frac {| mathbf {x} -mathbf {y} | ^ {2}} {2sigma ^ {2}}}}, quad mathbf {x}, mathbf {y} в mathbb {R} ^ {d}, sigma> 0}$.
  • Ядро лапласа: ${displaystyle K (mathbf {x}, mathbf {y}) = e ^ {- alpha | mathbf {x} -mathbf {y} |}, quad mathbf {x}, mathbf {y} в mathbb {R} ^ { d}, альфа> 0}$.
  • Ядро Абеля: ${displaystyle K (x, y) = e ^ {- alpha | x-y |}, x, yquad в mathbb {R}, alpha> 0}$.
  • ядро, генерирующее Соболевские пространства ${displaystyle W_ {2} ^ {k} (mathbb {R} ^ {d})}$: ${displaystyle K (x, y) = | xy | _ {2} ^ {k- {frac {d} {2}}} B_ {k- {frac {d} {2}}} (| xy | _ { 2})}$, куда ${displaystyle B_ {u}}$ - функция Бесселя третьего рода.
  • ядро, генерирующее пространство Пэли-Винера: ${displaystyle K (x, y) = {mbox {sinc}} (alpha (x-y)), x, yin mathbb {R}, alpha> 0}$.
• Если ${displaystyle H}$ это Гильбертово пространство, то соответствующий ему внутренний продукт ${displaystyle (cdot, cdot) _ {H}: H imes H o mathbb {R}}$ п.д. ядро. Действительно, у нас есть

${displaystyle sum _ {i, j = 1} ^ {n} c_ {i} c_ {j} (x_ {i}, x_ {j}) _ {H} = left (sum _ {i = 1} ^ { n} c_ {i} x_ {i}, sum _ {j = 1} ^ {n} c_ {j} x_ {j} ight) _ {H} = left | sum _ {i = 1} ^ {n} c_ {i} x_ {i} ight | _ {H} ^ {2} geq 0}$

• Ядра определены на ${displaystyle mathbb {R} _ {+} ^ {d}}$ и гистограммы: гистограммы часто встречаются при решении реальных задач. Большинство наблюдений обычно доступны в виде неотрицательных векторов подсчетов, которые, если нормализовать, дают гистограммы частот. Было показано ^[1] что следующее семейство квадратов метрик, соответственно дивергенции Дженсена, ${displaystyle chi}$-квадрат, общая вариация и два варианта расстояния Хеллингера:

${displaystyle psi _ {JD} = Hleft ({frac {heta + heta '} {2}} ight) - {frac {H (heta) + H (heta')} {2}},}$

${displaystyle psi _ {chi ^ {2}} = sum _ {i} {frac {(heta _ {i} - heta _ {i} ') ^ {2}} {heta _ {i} + heta _ {i } '}}, quad psi _ {TV} = sum _ {i} | heta _ {i} - heta _ {i} '|,}$

${displaystyle psi _ {H_ {1}} = sum _ {i} | {sqrt {heta _ {i}}} - {sqrt {heta _ {i} '}} |, psi _ {H_ {2}} = сумма _ {i} | {sqrt {heta _ {i}}} - {sqrt {heta _ {i} '}} | ^ {2},}$

может использоваться для определения p.d. ядра по следующей формуле

${displaystyle K (heta, heta ') = e ^ {- альфа psi (heta, heta')}, alpha> 0.}$

История

Положительно определенные ядра, как они определены в (1.1), впервые появились в 1909 г. в статье Джеймса Мерсера об интегральных уравнениях.^[2] Несколько других авторов использовали эту концепцию в следующие два десятилетия, но ни один из них явно не использовал ядра. ${displaystyle K (x, y) = f (x-y)}$, т.е. p.d. функции (действительно, М. Матиас и С. Бохнер похоже, не знал об исследовании p.d. ядра). Работа Мерсера возникла из статьи Гильберта 1904 года. ^[3] на Интегральные уравнения Фредгольма второго вида:

${displaystyle f (s) = phi (s) -lambda int _ {a} ^ {b} K (s, t) phi (t) mathrm {d} t.qquad qquad (1.2)}$

В частности, Гильберт показал, что

${displaystyle int _ {a} ^ {b} int _ {a} ^ {b} K (s, t) x (s) x (t) mathrm {d} smathrm {d} t = sum {frac {1} {lambda _ {n}}} влево [int _ {a} ^ {b} psi _ {n} (s) x (s) mathrm {d} прицел] ^ {2}, qquad qquad (1.3)}$

куда ${displaystyle K}$ - непрерывное вещественное симметричное ядро, ${displaystyle x}$ непрерывно, ${displaystyle {psi _ {n}}}$ это полная система ортонормированные собственные функции, и ${displaystyle lambda _ {n}}$Соответствующие собственные значения из (1.2). Гильберт определил «определенное» ядро ​​как ядро, для которого двойной интеграл

${displaystyle J (x) = int _ {a} ^ {b} int _ {a} ^ {b} K (s, t) x (s) x (t) mathrm {d} s; mathrm {d} t }$

удовлетворяет ${displaystyle J (x)> 0}$ кроме ${displaystyle x (t) = 0}$. Первоначальной целью статьи Мерсера было охарактеризовать ядра, определенные в смысле Гильберта, но Мерсер вскоре обнаружил, что класс таких функций слишком ограничен, чтобы характеризовать их в терминах определителей. Поэтому он определил непрерывное вещественное симметричное ядро ${displaystyle K (s, t)}$ быть положительным типом (т.е. положительно определенным), если ${displaystyle J (x) geq 0}$ для всех реальных непрерывных функций ${displaystyle x}$ на ${displaystyle [a, b]}$, и он доказал, что (1.1) является необходимым и достаточным условием положительного типа ядра. Затем Мерсер доказал, что для любого непрерывного п.о. ядро расширение

${displaystyle K (s, t) = sum {frac {psi _ {n} (s) psi _ {n} (t)} {lambda _ {n}}}}$

держится абсолютно и равномерно.

Примерно в то же время У. Х. Янг,^[4] мотивированный другим вопросом теории интегральных уравнений, показал, что для непрерывных ядер условие (1.1) эквивалентно ${displaystyle J (x) geq 0}$ для всех ${displaystyle xin L ^ {1} [a, b]}$.

E.H. Мур ^[5][6] инициировал изучение очень общего вида п.о. ядро. Если ${displaystyle E}$ это абстрактный набор, он вызывает функции ${displaystyle K (x, y)}$ определено на ${displaystyle E imes E}$ «Положительные эрмитовы матрицы», если они удовлетворяют (1.1) для всех ${displaystyle x_ {i} in E}$. Мур интересовался обобщением интегральных уравнений и показал, что для каждого такого ${displaystyle K}$ есть гильбертово пространство ${displaystyle H}$ таких функций, что для каждой ${displaystyle fin H, f (y) = (f, K (cdot, y)) _ {H}}$. Это свойство называется воспроизводящим свойством ядра и оказывается важным при решении краевых задач для эллиптических уравнений в частных производных.

Еще одно направление развития, в котором п.д. ядра сыграли большую роль в теории гармоник на однородных пространствах, начатой Э. Картан в 1929 г. и продолжил Х. Вейль и С. Ито. Самая полная теория п.д. ядра в однородных пространствах - это ядро М. Крейн^[7] который включает как частные случаи работы над p.d. функции и неприводимые унитарные представления локально компактных групп.

В теории вероятностей п.о. ядра возникают как ядра ковариации случайных процессов.^[8]

Связь с воспроизводящим ядром Гильбертовы пространства и карты характеристик

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

Позволять ${displaystyle X}$ быть набором, ${displaystyle H}$ гильбертово пространство функций ${displaystyle f: X o mathbb {R}}$, и ${displaystyle (cdot, cdot) _ {H}: H imes H o mathbb {R}}$ соответствующий внутренний продукт на ${displaystyle H}$. Для любого ${displaystyle xin X}$ Функционал оценки ${displaystyle e_ {x}: H o mathbb {R}}$ определяется ${displaystyle fmapsto e_ {x} (f) = f (x)}$. Сначала определим воспроизводящее ядро ​​гильбертова пространство (RKHS):

Определение: Космос ${displaystyle H}$ называется гильбертовым пространством воспроизводящего ядра, если функционалы вычисления непрерывны.

С каждым RKHS связана специальная функция, а именно воспроизводящее ядро:

Определение: Воспроизведение ядра - это функция ${displaystyle K: X imes X o mathbb {R}}$ такой, что

1) ${displaystyle K_ {x} (cdot) в H, для всех xin X}$, и

2) ${displaystyle (f, K_ {x}) = f (x)}$, для всех ${displaystyle fin H}$ и ${displaystyle xin X}$.

Последнее свойство называется воспроизводящим свойством.

Следующий результат показывает эквивалентность RKHS и воспроизводящих ядер:

Теорема: Каждое воспроизводящее ядро ${displaystyle K}$ индуцирует уникальный RKHS, и каждый RKHS имеет уникальное воспроизводящее ядро.

Теперь связь между p.d. ядра и RKHS дается следующей теоремой

Теорема: Каждое воспроизводящее ядро ​​положительно определено, и каждый p.d. Ядро определяет уникальный RKHS, единственное воспроизводящее ядро ​​которого.

Таким образом, для положительно определенного ядра ${displaystyle K}$, можно построить связанный RKHS с ${displaystyle K}$ как воспроизводящее ядро.

Как было сказано ранее, p.d. ядра могут быть построены из внутренних продуктов. Этот факт можно использовать для подключения п.о. ядра с другим интересным объектом, который возникает в приложениях машинного обучения, а именно картой функций. Позволять ${displaystyle F}$ - гильбертово пространство, и ${displaystyle (cdot, cdot) _ {F}}$ соответствующий внутренний продукт. Любая карта ${displaystyle Phi: X o F}$ называется картой характеристик. В этом случае мы называем ${displaystyle F}$ пространство функций. Легко увидеть ^[9] что каждая карта функций определяет уникальный p.d. ядро

${displaystyle K (x, y) = (Phi (x), Phi (y)) _ {F}.}$

Действительно, положительная определенность ${displaystyle K}$ следует из п.о. свойство внутреннего продукта. С другой стороны, каждый p.d. Ядро и соответствующий ему RKHS имеют много связанных карт функций. Например: пусть ${displaystyle F = H}$, и ${displaystyle Phi (x) = K_ {x}}$ для всех ${displaystyle xin X}$. потом ${displaystyle (Phi (x), Phi (y)) _ {F} = (K_ {x}, K_ {y}) _ {H} = K (x, y)}$, благодаря свойству воспроизведения, что позволяет по-новому взглянуть на p.d. ядра как скалярные произведения в соответствующих гильбертовых пространствах, или, другими словами, p.d. ядра можно рассматривать как карты сходства, которые эффективно количественно определяют, насколько похожие две точки ${displaystyle x}$ и ${displaystyle y}$ через ценность ${displaystyle K (x, y)}$. Более того, в силу эквивалентности p.d. ядра и соответствующий RKHS, каждая карта функций может быть использована для построения RKHS.

Ядра и расстояния

Методы ядра часто сравнивают с методами, основанными на расстоянии, такими как ближайшие соседи. В этом разделе мы обсуждаем параллели между их двумя соответствующими ингредиентами, а именно ядрами. ${displaystyle K}$ и расстояния ${displaystyle d}$.

Здесь функцией расстояния между каждой парой элементов некоторого множества ${displaystyle X}$, мы имеем в виду метрика определенная на этом множестве, т.е. любая неотрицательная функция ${displaystyle d}$ на ${displaystyle {mathcal {X}} imes {mathcal {X}}}$ что удовлетворяет

• ${displaystyle d (x, y) geq 0}$, и ${displaystyle d (x, y) = 0}$ если и только если ${displaystyle x = y}$,
• ${displaystyle d (x, y) = d (y, x)}$,
• ${displaystyle d (x, z) leq d (x, y) + d (y, z)}$.

Одно звено между расстояниями и п.д. Ядра задаются определенным типом ядра, называемым отрицательно определенным ядром, и определяются следующим образом

Определение: Симметричная функция ${displaystyle psi: {mathcal {X}} imes {mathcal {X}} o mathbb {R}}$ называется отрицательно определенным (н.о.) ядром на ${displaystyle {mathcal {X}}}$ если

${displaystyle sum _ {i, j = 1} ^ {n} c_ {i} c_ {j} psi (x_ {i}, x_ {j}) leq 0quad quad quad quad (1.4)}$

справедливо для любого ${displaystyle nin mathbb {N}, x_ {1}, dots, x_ {n} in {mathcal {X}},}$ и ${displaystyle c_ {1}, dots, c_ {n} в mathbb {R}}$ такой, что${displaystyle sum _ {i = 1} ^ {n} c_ {i} = 0}$.

Параллель между n.d. ядра и расстояния в следующем: всякий раз, когда н.д. ядро исчезает на множестве ${displaystyle {(x, x): xin {mathcal {X}}}}$, и равен нулю только на этом множестве, то его квадратный корень - это расстояние для ${displaystyle {mathcal {X}}}$.^[10] В то же время каждое расстояние не обязательно соответствует н.о. ядро. Это верно только для гильбертовских расстояний, где расстояние ${displaystyle d}$ называется гильбертовым, если можно вложить метрическое пространство ${displaystyle ({mathcal {X}}, d)}$ изометрически в какое-то гильбертово пространство.

С другой стороны, n.d. ядра можно идентифицировать с подсемейством p.d. ядра, известные как безгранично делимые ядра. Неотрицательное ядро ${displaystyle K}$ называется безгранично делимым, если для каждого ${displaystyle nin mathbb {N}}$ существует положительно определенное ядро ${displaystyle K_ {n}}$ такой, что ${displaystyle K = (K_ {n}) ^ {n}}$.

Еще одна ссылка - п.д. ядро индуцирует псевдометрический, где первое ограничение на функцию расстояния ослаблено, чтобы позволить ${displaystyle d (x, y) = 0}$ за ${displaystyle xeq y}$. Для положительно определенного ядра ${displaystyle K}$, мы можем определить функцию расстояния как:

${displaystyle d (x, y) = {sqrt {K (x, x) -2K (x, y) + K (y, y)}}}$

Некоторые приложения

Ядра в машинном обучении

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

Ядра в вероятностных моделях

В теории вероятностей ядра возникают по-разному.

• Недетерминированные проблемы восстановления: предположим, что мы хотим найти ответ ${displaystyle f (x)}$ неизвестной модельной функции ${displaystyle f}$ в новой точке ${displaystyle x}$ набора ${displaystyle {mathcal {X}}}$, при условии, что у нас есть образец пар вход-ответ ${displaystyle (x_ {i}, f_ {i}) = (x_ {i}, f (x_ {i}))}$ дано наблюдением или экспериментом. Ответ ${displaystyle f_ {i}}$ в ${displaystyle x_ {i}}$ не является фиксированной функцией ${displaystyle x_ {i}}$ а скорее реализация действительной случайной величины ${displaystyle Z (x_ {i})}$. Цель - получить информацию о функции ${displaystyle E [Z (x_ {i})]}$ который заменяет ${displaystyle f}$ в детерминированной обстановке. Для двух элементов ${displaystyle x, yin {mathcal {X}}}$ случайные величины ${displaystyle Z (x)}$ и ${displaystyle Z (y)}$ не будет некоррелированным, потому что если ${displaystyle x}$ слишком близко к ${displaystyle y}$ случайные эксперименты, описанные ${displaystyle Z (x)}$ и ${displaystyle Z (y)}$ часто будет демонстрировать подобное поведение. Это описывается ядром ковариации ${displaystyle K (x, y) = E [Z (x) cdot Z (y)]}$. Такое ядро ​​существует и положительно определено при слабых дополнительных предположениях. Теперь хорошая оценка для ${displaystyle Z (x)}$ может быть получен с помощью интерполяции ядра с ядром ковариации, полностью игнорируя вероятностный фон.

Предположим теперь, что шумовая переменная ${displaystyle epsilon (x)}$, с нулевым средним и дисперсией ${displaystyle sigma ^ {2}}$, добавляется к ${displaystyle x}$, такая, что шум независим для разных ${displaystyle x}$ и независимо от ${displaystyle Z}$ там тогда проблема нахождения хорошей оценки для ${displaystyle f}$ идентичен приведенному выше, но с модифицированным ядром, заданным ${displaystyle K (x, y) = E [Z (x) cdot Z (y)] + сигма ^ {2} дельта _ {xy}}$.

• Оценка плотности по ядрам: проблема в том, чтобы восстановить плотность ${displaystyle f}$ многомерного распределения по домену ${displaystyle {mathcal {X}}}$, из большой выборки ${displaystyle x_ {1}, точки, x_ {n} в {mathcal {X}}}$ включая повторы. Там, где точки выборки расположены плотно, функция истинной плотности должна принимать большие значения. Простая оценка плотности возможна путем подсчета количества выборок в каждой ячейке сетки и построения результирующей гистограммы, которая дает кусочно-постоянную оценку плотности. Более точную оценку можно получить, используя ядро, инвариантное по отношению к сдвигу. ${displaystyle K}$, с полным интегралом, равным единице, и определим

${displaystyle f (x) = {frac {1} {n}} sum _ {i = 1} ^ {n} Kleft ({frac {x-x_ {i}} {h}} ight)}$

как гладкая оценка.

Численное решение уравнений в частных производных

Одна из самых больших областей применения так называемых бессеточные методы находится в численном решении PDEs. Некоторые из популярных методов без сетки тесно связаны с положительно определенными ядрами (например, бессеточный местный Петров Галёркин (МЛПГ), Воспроизведение метода ядерных частиц (RKPM) и гидродинамика сглаженных частиц (SPH) ). Эти методы используют радиальное базисное ядро ​​для словосочетание.^[11]

Теорема Стайнспринга о расширении

Другие приложения

В литературе по компьютерным экспериментам ^[12] и других инженерных экспериментов все чаще встречаются модели, основанные на p.d. ядра, RBF или кригинг. Одна из таких тем - моделирование поверхности отклика. Другие типы приложений, которые сводятся к подгонке данных: быстрое прототипирование и компьютерная графика. Здесь часто используются неявные модели поверхности для аппроксимации или интерполяции данных облака точек.

Приложения p.d. ядра в различных других разделах математики находятся в многомерной интеграции, многомерной оптимизации, а также в численном анализе и научных вычислениях, где изучаются быстрые, точные и адаптивные алгоритмы, идеально реализованные в высокопроизводительных вычислительных средах.^[13]

Смотрите также

• Интегральное уравнение
• Интегральное преобразование
• Положительно определенная функция на группе
• Воспроизведение ядра гильбертова пространства
• Метод ядра

Рекомендации