WikiDer > Положительно определенное ядро

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 (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}}$ $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]

Navigation