Деревья инкрементной иерархической дискриминантной регрессии (IHDR) | Перевод и примечания

Зачем переводить эту старую статью, опубликованную в 2007 году? Есть четыре основные причины:

(1) В этой статье четко представлена ​​концепция поэтапного обучения. (2) Диссертация имеет определенную теоретическую и прикладную ценность. (3) Авторы статьи все еще активны, и чтение предыдущей работы помогает понять последнюю работу. (4) После цикла изменений я чувствую себя ближе, и мне легче понять текст, который я перевел. Ниже приводится перевод, а примечания выделены курсивом.

---

[1] Дж. Уэнг, «Инкрементная иерархическая дискриминантная регрессия», стр. 28, 2007.

Резюме

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

keywords : online learning, incremental learning, cortical development, discrimenant analysis, local invariance, plasticity, decision trees, high dimensional data, classification, regression, and autonomus development.

введение

Кора головного мозга представляет собой регрессионную модель, которая выполняет числовой ввод для вывода данных. В подходящей временной шкале частота активации нейронов была смоделирована как основной источник информации, передаваемой нейронными аксонами. Область коры постепенно развивается (адаптируется и самоорганизуется) с опытом обработки сигналов. Мозг человека имеет четыре типа коры: первичную, ассоциативную (ассоциативную), мультимодальную и паракортикальную. Ассоциативная кора находится между первичной корой и моторной зоной. Математическая модель, построенная в данной работе, может рассматриваться как грубая аппроксимационная вычислительная модель развития ассоциативной коры головного мозга. На самом деле в мозгу человека еще много неизвестных мест. Таким образом, вычислительная модель, представленная в этой статье, не предназначена для полного соответствия тому, что описано в биологии.

Деревья классификации (выводятся в виде меток классов) и деревья регрессии (выводятся в виде числовых векторов) служат двум целям: индексация и предсказание. Деревья индексов, такие как деревья K-D и R-деревья, широко использовались для извлечения известных данных дерева из наборов данных в качестве эффективной структуры хранения данных для уменьшения временной сложности поиска.$\log{(n)}$). Деревья прогнозов, также известные как деревья решений, широко используются в машинном обучении для создания набора правил прогнозирования на основе дерева. Поскольку построенные деревья решений обычно неглубокие, временная сложность не является проблемой для деревьев решений. Кроме того, для этой статьи требуется система искусственной нейронной сети с добавочным обучением в режиме реального времени. Поэтому мы рассматриваем эффективность времени и важную производительность обобщения. Кроме того, нам нужно строить дерево постепенно, чтобы его можно было использовать для обработки постепенно поступающих данных. Например, ввод видеоинформации об окружающей среде в роботизированную систему в режиме реального времени.

Традиционное дерево классификации или регрессии использует одну переменную для разделения ее на каждом внутреннем узле для построения дерева, например CART, C5.0 и многие другие методы дерева. Это означает, что гиперплоскость, используемая для разделения входного пространства в узле, ортогональна одной из осей пространства. Многомерное линейное разбиение не обязательно должно быть ортогональным к какой-либо оси координат, поэтому оно может правильно разделить пространство вдоль границы решения, что приводит к лучшему прогнозированию и обобщению. Дерево, построенное с несколькими переменными, называетсяoblique trees.

Существующие наклонные деревья включают OC1, SHOSLIF. OC1 использует рекурсивный поиск разделенной плоскости. SHOSLIF использует PCA и LDA для прямого вычисления разделения. SHOSLIF использует многомерное нелинейное разделение (поверхности, разделяющие поверхности в произвольной ориентации). Почему LDA важен, потому чтоLDA использует информацию из выходного пространствадля разделения входного пространства. PCA использует только информацию из входного пространства. Следствием этого является то, что переменные во входном пространстве, которые не связаны с выходными данными (например, шумовые компоненты), также захватываются PCA. Включение методов дискриминантного анализа, таких как LDA, может игнорировать входные компоненты, которые не имеют отношения к выходным данным.

Проблема усложняется, когда выход представляет собой многомерный аналоговый сигнал (например, сигнал управления движением робота в реальном времени). Метки классов трудно найти, поэтому методы LDA нельзя применять напрямую. Иерархическая дискриминантная регрессия (HDR) выполняет операции кластеризации как во входном, так и в выходном пространстве, а кластеризация в выходном пространстве предоставляет виртуальные метки для направления кластеризации во входном пространстве. В этом документе предлагается инкрементная версия HDR, IHDR.

Инкрементная регрессия

Полностью поэтапное обучение — очень сложная задача. Полное инкрементное обучение означает, что дерево должно обновлять дерево (модель) для каждого входного вектора. Вполне разумно предположить, что мозг является полностью инкрементным мозгом, который должен работать и обновляться при каждом сенсорном вводе. В системе инкрементного обучения кадры данных поступают последовательно в последовательности. каждый кадр$x(t)$Векторы данных меняют мир во времени$t$Образец (снимок) файла . Поскольку поток данных наблюдений может продолжаться в течение длительного времени или даже никогда не прекращаться, система должна иметь возможность каждый раз обновлять систему текущими данными. После того, как каждый кадр данных используется для обновления, он отбрасывается. Основные причины последовательного обучения включают: (а) невозможность хранения всех входящих данных; (б) пакетная обработка (включая обучение в последовательностях, разбитых на фрагменты) требует времени и вносит временные задержки, начиная с первого пакета данных. следующая партия поступающих данных значительна; (c) обновление дерева происходит очень быстро, но для построения полного дерева требуется больше времени. Следовательно, эффект задержки обновления дерева одним кадром данных короче.

Преимущества поэтапного обучения

(a) Выполнить во время строительства. IHDR может работать до завершения сборки (для прогнозирования); (b) Сосредоточьтесь на трудных частях исследования. Будут ли собираться более поздние обучающие выборки, зависит от производительности текущего дерева, что позволяет использовать более эффективные обучающие выборки для обучения труднообучаемых частей; (c) Количество обучающих выборок определяется динамически. Учитывая задачу классификации или регрессии, трудно определить, сколько обучающих выборок требуется для этой задачи. Инкрементное обучение позволяет роботу динамически определять необходимые данные обучающей выборки в соответствии с текущей производительностью системы; (d) Эти выборки (микрокластеры, присутствующие в листовых узлах в IHDR) принимаются в разное время и могут храниться в разных местах дерева, что может повысить производительность.

По сравнению с другими методами дополнительного обучения IHDR имеет следующие характеристики:

• Долговременная и кратковременная память с систематической организацией. Долговременная память в основном включает информацию в неглубоких узлах и микрокластерах (редко используемых) в листовых узлах. Кратковременная память включает в себя микрокластеры (часто используемые) в листовых узлах. Детали игнорируются добавочным усреднением. Долговременная память позволяет IHDR избежать таких проблем, как катастрофическое забывание (обычно присутствует в сетях прямой и обратной связи, основанных на BP).

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

• Оценено по многослойному распределению от грубого к мелкому.

• Быстрые локальные обновления, не требующие итерации. Некоторые существующие методы, такие как эволюционные вычисления и моделируемый отжиг, могут справиться с проблемой локальных минимумов, но требуют итеративных вычислений. И это не работает с живыми обновлениями.

метод

А. Объединение задач классификации и регрессии

В зависимости от типа вывода (классический или символьный вывод по сравнению с числовым выводом) задачи дискриминантного анализа можно разделить на две категории: классификация и регрессия.

Задачу классификации можно определить следующим образом: Учитывая набор обучающей выборки$L=\{(x_i, l_i)|i=1,2,..., n\}$, здесь$x_i\in X$входной (признаковый) вектор,$l_i$за$x_i$Соответствующая символьная метка, задача классификации для ввода любой неизвестной категории$x\in X$Определите, к какой категории он относится.

Задача регрессии аналогична задаче классификации, за исключением того, что метка класса$l_i$заменить$y_i$,$y_i\in Y, i=1,2,...,n$. Задача регрессии определяется следующим образом: Учитывая обучающий набор данных$L'=\{(x_i, y_i)|i=1,2,...,n\}$, задача регрессии для любого входного вектора$x\in X$Оцените его соответствующий выходной вектор$y(x)\in Y$.

Регрессионные задачи очень распространены. Проблема обучения — это задача регрессии, поскольку системе необходимо управлять исполнительными механизмами с изменяющимися значениями. Например: моторы, рубрики, тормоза и машины различного промышленного назначения. Кора головного мозга в биологии также выполняет задачи регрессии.

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

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

Здесь мы перечисляем три подхода к проецированию задачи классификации в задачу регрессии.

1. Каноническое отображение. будет$n$классные отметки сопоставляются с$n$объемное выходное пространство. во-первых$i$класс, соответствующий выходной вектор$y_i$за$n$размерный вектор, где$i$Каждый элемент равен 1, а все остальные элементы равны 0. Этот метод имеет большие ограничения в контексте поэтапного обучения, поскольку максимальное количество классов ограничено$n$.
2. Внедрение матрицы затрат. Если матрица затрат$[c_{i,j}]$доступно, то$n$Метки классов могут быть встроены в$(n-1)$размерное выходное пространство, используя вектор$y_i$Указывает категорию$i$, так что$||y_i-y_j||$и$c_{i,j}$около. Этот процесс не всегда возможен из-за предопределенной матрицы затрат.$[c_{i,j}]$Не часто легко получить. Количество категорий здесь также ограничено и не относится к поэтапному обучению.
3. Среднее значение входного пространства категорий. каждый относится к категории$l_i$образец$(x_{i,j},l_i)$, превращаются в$(x_{i,j},y_j)$, здесь$y_i$для всех принадлежащих к одной категории$l_i$из$x_{i,j}$среднее значение . В добавочном обучении это среднее может быть обновлено средним значением амнезии. Этот метод является предпочтительным решением из-за предположения, что аналогичные входные данные влекут за собой аналогичные выходные данные в большинстве задач обучения.

Б. Мотивация

В оставшейся части этой статьи мы рассматриваем общую проблему регрессии: постепенное приближение карты:$h:X\rightarrow Y$

Предположим, что обучающие выборки$\{(x_i, y_i)|x_i\in X, y_i \in Y, i=1,2,...,n\}$. Смысл пошаговой аппроксимации в том, что разработчик d использует только модель отображения предыдущего момента$h^{(i-1)}$и текущий входной образец$(x_i,y_i)$создать новую карту$h^{(i)}$:$h^{(i)}=d(h^{(i-1)}, x_i, y_i)$

В дереве IHDR есть три типа кластеров (также называемых нейронами): x-кластеры, y-кластеры и микрокластеры.

• x-кластеры и y-кластеры: чтобы охарактеризовать границу разделения подпространства отличительных признаков D каждого внутреннего узла. y-кластеры находятся в$Y$Представление в пространстве, используемое для предоставления виртуальных меток x-кластерам. x-кластеры определены в$X$пространство, чтобы разделить входное пространство вдоль дискриминативного подпространства D на внутренние узлы.
• микрокластер: состоит из$(x_i,y_i)$Указывает, что он существует только на листовых узлах. Конечно, если дерево IHDR допускает операции обрезки, то внутренние узлы нуждаются в микрокластере, потому что при удалении конечного узла его родительский узел может непосредственно выступать в роли конечного узла.

D. Бикластеризация

Каждый внутренний узел IHDR поддерживает y-кластеры и x-кластеры постепенно. Как показано на рисунке ниже, каждую категорию каждого узла можно разделить не более чем на q категорий (q — заданное максимальное значение).Математически описывается как входное пространство$X$Кластеризация находится в выходном пространстве$Y$как условие. Итак, для каждого x-кластера есть случайная величина$x\in X$О случайных величинах$y\in Y$Условное распределение вероятностей , обозначаемое как$p(x|Y\in c_i)$,в$c_i$первый$i$y-кластеры,$i-=1,2,...,q$.

$q$y-кластеры основаны на$y$Каждый поступающий образец идентифицируется$(x,y)$виртуальная этикетка. Виртуальные метки используются для определения текущего$(x,y)$, следует использовать его$x$Какой x-кластер обновить. Каждое x-скопление находится примерно на$X$Выборочная совокупность в пространстве, к которому она относится. Если требуется более точное приближение, он может создать дочерний узел.

Шаги для добавочного обновления следующие:

В каждом узле текущая выборка$(x,y)$середина$y$, используется для поиска ближайшего y-кластера (евклидово расстояние) и его использования для обновления центра этого y-кластера. Самый последний y-кластер указывает на$(x,y)$Связанный x-кластер. потом$(x,y)$Используется для обновления статистики x-кластера (средний вектор и матрица дисперсии). Статистика каждого x-кластера используется для оценки текущей выборки.$(x,y)$Вероятность принадлежности к каждому x-кластеру (здесь моделируется как многомерное распределение Гаусса).

Кроме того, центры x-кластеров предоставляют много важной информации, которую можно использовать для разделения подпространств. потому что эти x-кластеры сделаны в соответствии с$Y$Виртуально генерируются в космосе. Мы определяем пространство максимального дискриминантного признака (MDF)$D$как линейное пространство, разделяющее эти x-кластеры. q x-кластерам требуется q-1 дискриминантных признаков (поддерживающих q-1-мерное дискриминативное пространство D)

Почему оно называется максимальным дискриминантным пространством? Например, предположим, что у наших входных данных есть две функции, одна из которых содержит информацию, относящуюся к выходным данным, а другая не связана с выходными данными (как показано на рисунке ниже). Поскольку в центре двух x-кластеров есть функция, значение которой в основном одинаковое, эта функция игнорируется. Еще одна особенность с большими различиями важна для разделения двух классов. Таким образом, «шумовые» характеристики, не связанные с выходными данными, экранируются, и снижается влияние на эффективность обучения. Как показано на рисунке ниже, максимальный дискриминантный признак не обязательно ортогонален оси, на которой расположен признак, и его направление произвольно.

E. Адаптивная локальная квазиинвариантность

входная выборка$(x,y)$принимаются последовательно. непрерывный вектор$x(t)$и$x(t+1)$Возможно, связано с изображением отслеживаемого объекта (например, уход, движение в одном направлении, вращение, деформация, мимика, изменение освещения и т. д.) Эта квазиинвариантность носит адаптивный и локальный характер.

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

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

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

Как показано в (а) на приведенном выше рисунке, входные данные соответствуют четырем видам выходных данных, которые представлены разными символами. Но если не учитывать выходную информацию, то в этих состояниях бардак. Четкой закономерности не видно.

На рисунке (b), поскольку учитывается выходная информация, эти выборки могут быть разделены более разумно.

Дополнение читателя: все это основано на предположении, что аналогичные входные данные имеют аналогичные выходные данные. Помните! ! !

F. Биологические перспективы

На изображении ниже показано дерево IHDR. Каждый узел напоминает область коры. государственное пространство$X$представлен d-мерным вектором, который изначально грубо разделен на 4 части. Каждый раздел является дочерним элементом корневого узла. Каждый дочерний узел имеет свою небольшую область. Это деление от грубого к мелкому постепенно делит входное пространство на небольшие области. Если дочерний узел получает достаточно выборок, он будет разделен на q дочерних узлов. В листовых узлах микрокластеры начинаются с$(x_i, y_i)$форма существует.

если$x$дано, но$y$Если оно неизвестно, мы можем получить соответствующее выходное значение в качестве предсказания текущего состояния путем поиска в дереве IHDR до конечного узла.

Алгоритм IHDR

Алгоритм пошагового построения дерева IHDR описан ниже. Обучающие данные алгоритма вводятся в робот последовательно по времени, а$t$Образцы, полученные на данный момент, помечены как$(x_t, y_t),t=1,2,...$. Чем глубже построено дерево (чем больше слоев), тем меньше дисперсия x-кластеров. Когда количество выборок в узле слишком мало для получения статистической оценки x-кластеров, узел остается листовой точкой.

Процедура 1: Алгоритм IHDR.

• Инициализируйте корневой узел.
• Для t=0,1,2,... сделайте следующее: Получить текущий образец$(x_t,y_t)$. если$y_t$Если известно, вызовите update-tree(root,$x_t$, $y_t$), в противном случае вызовите calculate-response(root,$x_t$,$y$), и вывод$y$.

A. Update tree

Ниже приведен алгоритм постепенного обновления дерева. Корневой узел данного дерева и обучающие выборки$(x,y)$, используя только текущую выборку$(x,y)$Обновите дерево. Каждый раз, когда вызывается функция обновления дерева, дерево может увеличиваться. Программа для работы с адаптивной корковой пластичностью (три слоя). Системный параметр: q — максимальное количество подкластеров на внутренний узел.$b_s$- количество выборок, необходимых для каждого постоянного параметра (степени свободы) (взятых в этой статье$b_s=20$).

Procedure 2: Update-tree(root,$x$, $y$)

• 1) Инициализировать. Пусть A будет активированным узлом (ожидающим поиска), а A инициализирован как корневой узел.
• 2. поиск дерева. Когда A не является листовым узлом, выполнение выглядит следующим образом:
  а) Рассчитайте ответ. для ввода$x$Для каждого нейрона A вычислите их ответы. б) Конкуренция. Для всех q детей A побеждает ребенок с наибольшим ответом. c) Победивший дочерний узел в A считается следующим активным узлом.
• 3. Обновите податливые внутренние узлы. Обновите родительский узел A активного конечного узла (Примечание: чтобы избежать крупномасштабного разделения временного пространства для ограниченной пластичности, узлы-предки над родительским узлом листового узла не нужно обновлять.) вызвать update-note(A,$x$,$y$) для обновления узла A.
• 4) Инкрементная кластеризация. Вызовите update-cluster-pair(A,$x$,$y$).
• 5) Для листового узла A, если количество выборок$n$больше порогового значения (автоматически рассчитывается$NSPP=2(n-q)/q^2>b_s$), A используется как внутренний узел, и генерируются q конечных узлов (путем назначения микрокластеров A его новым дочерним узлам).

B. Update node

Учитывая узел N и обучающую выборку$(x,y)$, который использует$(x,y)$Обновите узел N. Эта процедура имеет дело с адаптивной пластичностью корковых блоков (внутри листовых точек).

Procedure 3: Update-node(N, x,$$y)

1. Обновите y-кластеры. Пусть c будет набором y-кластеров в N узлах. Вызывая update-clusters($y$,$c$), функция возвращает ближайший$y_i$индекс чего-либо.

2) Обновите x-кластер, связанный с индексом y-кластера на предыдущем шаге. использовать$x$Обновите среднее значение x-кластера, которое вводит механизм забывания для усиления эффекта новых данных. 3) Использовать наибольший дискриминантный признак для обновления подпространства узла N, так как i-й x-кластер уже обновлен. Следовательно, подпространство из N узлов необходимо повторно разделить.

C. Update clusters

данный образец$y$и набор кластеров$c=\{y_i|i=1,2,...,n\}$, обновление программы$c$кластеризация в . Параметры включают: q$c$Максимальное количество кластеров в ;$\delta_y>0$является разрешением выходного пространства.

Procedure 4: Update-clusters($y$, $c$)

1) Если$n<q$и$||y-y_j||>\delta_y$(Чтобы предотвратить создание нескольких кластеров очень маленьким или одним и тем же образцом), увеличьте$n=n+1$, настроить новый кластер$y_n=y$, и воля$y_n$добавить в$c$, возвращение. В противном случае сделайте следующее: 2) Найдите ближайшего соседа по следующей метрике$y_j$:$j=arg\min_{1\leq i \leq n}\{||y_i-y||\}$. 3) Обновить определенную часть самого последнего кластера$p$(Например,$p=0.2$Обновите только 20% кластеров), введите механизм забывания и верните$j$.

D. Update-cluster-pair

данный образец$(x,y)$и набор пар кластеров$c=\{(x_i,y_i)|i=1,2,...,n\}$. Программа обновлена$c$Лучший соответствующий кластер в . Программа представляет собой локальную операцию над каждым выходным нейроном (микрокластером). Параметры включают:$b_l>0$— максимально допустимое количество микрокластеров в листовых узлах;$\delta_x>0$является разрешением входного пространства.

Procedure 5: Update-cluster-pair($x$,$y$,$c$)

1) Если$n<b_l$и$||x-x_j||>\delta_X$,$n=n+1$, и установите новый кластер$(x_n,y_n)=(x,y)$, и воля$(x_n,y_n)$увеличить в$c$, и вернуться. В противном случае сделайте следующее: 2) Используйте следующие показатели, чтобы найти ближайший$x_j$:$j=arg\min_{1 \leq i \leq n}\{||x_i-x||\}$. 3) Воспользуйтесь преимуществами новых образцов$x$кластер обновления$x_j$, и ввести механизм забывания. 4) Воспользуйтесь преимуществами новых образцов$y$кластер обновления$y_j$, и ввести механизм забывания. 5) Вернуть обновленный$c$.

E. Compute response

Когда образец имеет только ввод$x$, не зная времени выхода. Мы вызываем программу вычисления-ответа IHDR, чтобы получить$x$Прогноз.

Procedure 6: Compute-response(root,$x$,$y$)

1. Сначала выполните ту же операцию в дереве обновлений, чтобы найти наиболее подходящий конечный узел A.

2) Рассчитать выход$y$. Пусть микрокластеры в листовом узле будут$c=\{(x_i,y_i)|i=1,2,...,n\}$. Используйте следующие показатели, чтобы найти$x$Наиболее подходящее совпадение:$j=arg\min_{1\leq i \leq n}\{||x-x_i||\}$Пусть прогнозируемый результат$y=y_j$,возвращение.

F. Механизмы забывания

Введение механизма забывания вдохновлено пластичностью нейронов головного мозга (требующей адаптивной адаптации к текущему опыту). Он также подлежит следующей статистической достоверности, описанной математическим языком: Чтобы оценить средний вектор распределения$\theta$(например, наблюдения$x_t,t=1,2,...,$Средний вектор нейронных синапсов используется в качестве вектора весов для нейронных синапсов), а среднее значение выборок является наиболее эффективной оценкой большого класса неизменных во времени распределений (например, экспоненциально распределенных кластеров, таких как распределения Гаусса). Определив наиболее эффективную оценку$\Gamma$- наименьшая ожидаемая ошибка среди всех возможных оценок,$E||\Gamma-\theta||^2$. Однако в практических ситуациях распределение наблюдений не является постоянным во времени, и необходимо использовать механизм забывания для медленного изменения распределения при сохранении квазиоптимальной достоверности оценки.

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

для каждых входных данных$x_1,x_2,...,x_t$Среднее значение задается как$\overline{x}^{(t)}=\frac{1}{t}\sum_{t=1}^t x_i=\sum_{i=1}^t \frac{1}{t}x_i$

Для приведенного выше утверждения каждый$x_i$путем умножения веса$\frac{1}{t}$, затем сложите и просуммируйте. Это называется усреднением равных весов. если$x_i$Инкрементальное прибытие, нам нужно постепенно обновлять среднее значение:$\overline{x}^{(t)}=\frac{(t-1)\overline{x}^{(t-1)}+x_t}{t}=\frac{t-1}{t}\overline{x}^{(t-1)}+\frac{1}{t}x_t$

В среднем внедрение механизма забывания выглядит следующим образом:$\overline{x}^{(t)}=\frac{t-1-\mu}{t}\overline{x}^{(t-1)}+\frac{1+\mu}{t}x_t$.

когда$\mu\geq0$, является параметром забывания.

Однако по мере того, как данные продолжают поступать, количество выборок продолжает увеличиваться, т. е.$t$растет. если$\mu$является фиксированным значением, то в$t$Когда он очень большой, его эффект почти равен нулю. Поэтому более целесообразно$\mu$должно медленно возрастать со временем, т. е. как функция времени$\mu(t)$. может быть выражена в виде кусочной функции, например, когда$t\leq t_1$При параметр забывания не вводится, т.е.$\mu(t)=0$;когда$t_1 < t \leq t_1$, мы делаем$\mu$медленно от 0 до$c$(Например,$c=1$);когда$t_2<t$, мы делаем$\mu(t)$медленное изменение скорости роста$1/m$Увеличивать. Вкратце это можно выразить следующим образом$\mu(t)=\left\{ \begin{matrix} 0 & t\leq t_1\\c(t-t_1)/(t_2-t_1) & t_1 < t \leq t_2\\ c+(t-t_1)/m & t_2< t\end{matrix}\right.$

так как$\lim_{t\rightarrow \infty}(1+\mu(t))/t=1/m$,когда$t$При увеличении до большого значения вес новых данных примерно такой же, как и без введения механизма забывания.$m$Вычисление равновзвешенного среднего по выборкам. такой рост$\mu(t)$Позволяет среднему отследить нестационарные случайные (означает медленно изменяющиеся во времени) входные данные.$x_t$.

Формула пошагового обновления выборочной ковариационной матрицы выглядит следующим образом:$\Gamma_x^{(t)}=\frac{t-1-\mu(t)}{t}\Gamma_x^{(t-1)}+\frac{1+\mu(t)}{t}(x_t-\overline{x}^{(t)})(x_t-\overline{x}^{(t)})^T$

Здесь следует отметить, что в приведенном выше выражении для расчета ковариации предполагается, что степень свободы выборки равна$t$, а не в пакетных вычислениях$t-1$. Потому что, даже если есть только одна выборка, связанная с ней ковариационная матрица не должна оцениваться как нулевой вектор, потому что$x_1$Это никогда не будет точным из-за теоремы неопределенности в физике. Например, исходная матрица отклонений$\Gamma_x^{(1)}$можно оценить как$\delta^2 I$,и$\delta^2$желаемый цифровой шум.

Дискриминантное подпространство и границы оптимальных классов

Каждый внутренний узел поддерживает подпространство максимального различительного признака (MDF), которое используется для улучшения способности модели к обобщению. Подпространство MDF каждого внутреннего узла обновляется образцами, назначенными этому узлу. В целях разделения каждый дочерний узел внутреннего узла представляет класс. Нам нужно использовать оптимальную границу класса, основанную на вероятности (на основе подпространства MDF), чтобы разделить входное пространство внутренних узлов. {выходное пространство--->MDF--->граница оптимального класса--->разделить входное пространство}

А. Дискриминантное подпространство

Когда размерность ввода очень высока (обычно не менее нескольких тысяч измерений), для эффективности вычислений мы не должны находиться в исходном входном пространстве.$X$представлять данные. Далее, чтобы лучше представить признаки, мы используем дискриминативное подпространство$D$Также игнорируются те, кто не имеет отношения к выходу.

Сначала мы рассмотрим X-кластеры, каждый X-кластер представлен своей статистической информацией (среднее значение и дисперсия). Когда размерность входного состояния очень велика, дисперсия представляет собой очень большую матрицу, поддерживать которую нереально. Мы вводим более эффективный способ: использование субстрипов для представления исходного пространства состояний.

Каждый внутренний узел содержит q x-кластеров. Центры этих q x-кластеров обозначаются как$C=\{c_1, c_2, ...,c_q|c_i\in X, i=1,2,...,q\}$

Центры этих кластеров содержат подпространства$D$информация о местоположении в пространстве состояний.$D$является дискриминантным пространством, потому что его форма кластеризации определяется выходным пространством$Y$решил.

дискриминантное подпространство$D$Шаги расчета следующие:

Предположим, что количество отсчетов в i-м кластере равно$n_i$, поэтому общее количество выборок этого внутреннего узла равно$n=\sum_{i=1}^q n_i$.

сделать$\overline{C}$является центром всех q кластеров$\overline{C}=\frac{1}{n}\sum_{i=1}^q n_i c_i$.

от$\overline{C}$Перейдите к вектору центра кластера, чтобы получить новый столбец векторов.$s_1, s_2, ...$,Как показано ниже. мы называем это по$S=\{s_i|i=1,2,...,q\}$Поддерживаемое подпространство — span(S).

И ортонормированный базис span(S)$a_1, a_2,...,a_{q-1}$в состоянии использовать$s_1, s_2, ...,s_q$построить (программа GSO ортогонализации Грама-Шмидта):

В приведенной выше программе следует отметить, что когда знаменатель первого шага равен 0, т. е.$s_1$Когда он равен нулю, он называется вырожденным. связанный с дегенерацией$s_i$следует удалить. Количество базисных векторов, полученных с помощью GSO, равно количеству линейно независимых элементов в S.

Предполагая, что эти ортонормированные базисы получены с помощью описанной выше процедуры, в этот момент приходит вектор состояния$x\in X$, сначала вычислим его точечную часть$s=x-\overline{C}$, а затем вычислить$x$Проекция на дискриминантное пространство$f=M^Ts$,в$M=[a_1, a_2, ..., a_{q-1}]$. мы называем$f$за$x$в линейном коллекторе$S$дискриминантные признаки. Среднее значение и дисперсия кластеров рассчитываются на основе дискриминантного подпространства.

B. Вероятностные меры

Одним из ограничений подпространства наибольшего дискриминантного признака является то, что его размерность может быть только q-1. В подпространстве нам нужно автоматически определить оптимальную границу класса для каждого дочернего узла на основе предполагаемого распределения вероятностей. Различные модели распределения вероятностей получают разные меры расстояния.

• отрицательное логарифмическое правдоподобие (NLL):

$G(x, c_i)=\frac{1}{2}(x-c_i)^T\Gamma_i^{-1}(x-c_i)+\frac{q-1}{2}ln(2\pi)+\frac{1}{2}ln(|\Gamma_i|)$

мы называем это состоянием$x$Гауссовский NLL для атрибутивного кластера i.$c_i$и$\Gamma_i$- среднее значение и матрица дисперсии сгруппированных выборок. Они обновляются с использованием среднего значения амнезии.

• Махаланобис NLL:

$M(x, c_i)=\frac{1}{2}(x-c_i)^T \Gamma^{-1}(x-c_i)+\frac{q-1}{2}ln(2\pi)+\frac{1}{2}ln(|F|)$

• Euclidean NLL:

$E(x, c_i)=\frac{1}{2}(x-c_i)^T\rho^2 I^{-1}(x-c_i)+\frac{q-1}{2}ln(2\pi)+\frac{1}{2}ln(|\rho^2 I|)$

здесь,$\Gamma$- матрица средней дисперсии q кластеров:$\Gamma=\frac{1}{q-1}\sum_{i=1}^{q-1}\Gamma_i$

Евклидова NLL одинаково обрабатывает все измерения и является хорошим выбором, когда количество выборок невелико.

Mahalanobis NLL использует внутриклассовую матрицу баллов$\Gamma$. Таким образом, NLL Махаланобиса равен евклидову NLL плюс LDA Фишера. Веса каждого измерения разные, а количество параметров$q(q-1)/2$, поэтому Mahalanobis NLL требует больше выборок.

C. Автоматический плавный переход между различными мерами

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

Мы будем использовать евклидову NLL, когда количество выборок невелико. Когда количество образцов увеличится, мы будем использовать Mahalanobis NLL. Мы используем полный гауссовский NLL, когда кластер имеет богатую выборку наблюдений.Границы NSPP ограничивают рост NSPP.

$\rho^2 I$Границы NSPP$b_e=min\{(n-1)(q-1), n_s\}$

$\Gamma$Границы NSPP$b_m=min\{max\{\frac{2(n-q)}{q}, 0\}, n_s\}$

$\Gamma_i$Границы NSPP$b_g=\frac{2(n-q)}{q^2}$

матрица рассеяния, зависящая от размера (SDSM):$W_i=w_e\rho^2 I+w_m \Gamma+w_g\Gamma_i$

некоторые места,$w_e = b_e/b, w_m=b_m/b, w_g=b_g/b$,$b$- нормировочный коэффициент.

Используйте матрицу рассеяния, зависящую от размера$W_i$, зависящее от размера отрицательное логарифмическое правдоподобие (SDNLL) получается как:

$L(x, c_i)=\frac{1}{2}(x-c_i)^TW_i^{-1}(x-c_i)+\frac{q-1}{2}ln(2\pi)+\frac{1}{2}ln(|W_i|)$

так как$b_e, b_m, b_g$автоматически изменится,$(L(x, c_i))$будет плавно переключаться на эти подходящие меры расстояния.

D. Учитывайте вычислительную эффективность

Из-за необходимости вычислений в реальном времени необходимо разработать эффективную схему неитеративных вычислений.

от$x$к каждому центру x-кластера$c_i$Матрица взвешенных квадратов расстояний выглядит следующим образом:

$d^2(x, c_i)=(x-c_i)^TW_i^{-1}(x-c_i)$

Расстояния между состояниями во всех узлах рассчитываются в$q-1$размерное дискриминантное пространство. Итак, СДСМ$(q-1)\times(q-1)$симметричная квадратная матрица. Нам просто нужно оценить$q(q-1)/2$параметры.

Чтобы более эффективно вычислить вышеуказанное расстояние, используйте алгоритм разложения Холецкого: симметричную квадратную матрицу можно разложить на$W=LL^T$

Разложение Холецкого см. в блоге.Разложение матрицы Разложение Холецкого

Предположим, мы получили разложение Холецкого,$W=LL^T$, и разреши$v=x-c_i$но$d^2(x, c_i)=v^TW_i^{-1}v=v^T(LL^T)^{-1}v=(L^{-1}v)^T(L^{-1}v)$

путем решения$Ly=v$,Потом$y=L^{-1}v$а также$d^2(x,c_i)=(L^{-1}v)^T(L^{-1}v)=||y||^2$, решать$Ly=v$Обратный метод можно использовать, когда , так как$L$для нижней треугольной матрицы.

遗留的问题

На шаге (3) алгоритма обновления узла B говорится, что минимальное дискриминантное подпространство узла нуждается в обновлении.Необходимо ли пересчитывать базисный вектор минимального дискриминантного подпространства? Алгоритму IHDR необходимо обновить минимальное дискриминативное подпространство родительского узла A активированного конечного узла. Затем в узле A есть два типа пространств: исходное пространство состояний (как правило, высокой размерности, нелегко напрямую вычислить матрицу дисперсии) X и минимальное дискриминантное подпространство D. Алгоритм говорит только об обновлении минимального дискриминантного подпространства узла A, а интуитивное понимание заключается в обновлении базисного вектора. Однако, как только базисный вектор изменяется, D изменяется. Среднее значение и дисперсия, рассчитанные ранее в этом пространстве, больше не доступны. Итак, как восстановить информацию о среднем значении и дисперсии в новом D? Среди них среднее может быть восстановлено путем синхронного поддержания среднего значения в пространстве X. Но как насчет дисперсии? Невозможно синхронно поддерживать информацию о дисперсии в пространстве X, верно? Потому что первоначальное намерение минимального дискриминантного подпространства состояло в том, чтобы избежать вычисления чрезмерно большой матрицы дисперсии в исходном пространстве X. Итак, как восстановить информацию о дисперсии? Если восстановление выполняется с использованием пары x-y листового узла, которому он принадлежит, является ли шаг обновления дисперсии с помощью механизма забывания избыточным? Потому что каждый раз, когда приходят новые данные, D будет обновляться, и дисперсию придется пересчитывать. Прежде чем он успеет итеративно обновиться, дисперсия снова изменится.

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