Аннотация:
Введена модель популяционной генетики типа Лотки–Вольтерры с мутациями на статистическом многообразии. Мутации в модели описываются диффузией на статистическом многообразии с генератором в виде оператора Лапласа–Бельтрами с метрикой Фишера–Рао, т. е. модель объединяет популяционную генетику и информационную геометрию. Такая модель описывает обобщение модели теории машинного обучения, модели порождающих соревновательных сетей, на случай популяций порождающих соревновательных сетей. Введенная модель описывает контроль переобучения для порождающих соревновательных сетей.
Ключевые слова:
теория обучения, популяционная генетика, теория эволюции.
В настоящей работе обсуждаются параллели между популяционной генетикой и теорией машинного обучения. Модель порождающих соревновательных сетей (ПСС, или GAN, generative adversarial networks) [1], [2] описывает некоторый гибрид модели теории обучения (метода максимального правдоподобия) и теории игр (проблемы минимакса) для двух игроков, называемых дискриминатором и генератором. Обнаружилось, что ПСС в высокой степени устойчивы к переобучению, что можно рассматривать как регуляризацию метода максимального правдоподобия моделью из теории игр. В настоящей работе построена модель популяционной генетики типа модели Лотки–Вольтерры с мутациями на статистическом многообразии, обобщающая модель соревновательных сетей теории обучения (а также некоторый аналог модели Эйгена на статистическом многообразии). В предыдущих работах автора исследовались приложения модели Эйгена популяционной генетики в теории обучения [3], [4]. Аналогии между теорией обучения и теорией эволюции обсуждались еще Тьюрингом [5] и привлекают интерес в настоящее время [6].
Можно предположить, что эффективность соревновательных сетей имеет ту же природу, что и известный в теории эволюции эффект ускорения эволюции при наличии хищников. В рамках предлагаемой модели для соревновательных сетей хищником является генератор, жертвой – дискриминатор, их взаимодействие описывается некоторым вариантом модели Лотки–Вольтерры. Мутации описываются диффузией на статистических многообразиях (соответственно дискриминатора и генератора); распределения дискриминаторов (генераторов) на соответствующих статистических многообразиях рассматриваются как популяции жертв (хищников) с различными геномами; приспособление есть сосредоточение популяций дискриминатора и генератора в окрестности решения задачи обучения для соревновательной сети. Таким образом, модель сочетает методы теории машинного обучения, популяционной генетики и информационной геометрии.
Контроль переобучения в рассматриваемой модели выглядит следующим образом: взаимодействие между дискриминатором и генератором устроено так, что алгоритм обучения подавляет узкие пики популяции на узких максимумах функции правдоподобия и заставляет популяцию занимать более широкие области в пространстве гипотез. В соответствии с принципом алгоритмической устойчивости (см. раздел 4) узкие пики отвечают режиму переобучения. С точки зрения популяционной генетики это означает, что более специализированный хищник эффективнее охотится.
Статья имеет следующую структуру. В разделе 2 излагается модель соревновательных сетей. В разделе 3 вводится ее популяционное обобщение в виде модели Лотки–Вольтерры с мутациями, а также вариант модели Эйгена популяционной генетики в рамках информационной геометрии. В разделе 4 обсуждается контроль переобучения для рассмотренных моделей популяционной генетики. В приложении приводятся определения, использующиеся в методе максимального правдоподобия, теории игр, модели Лотки–Вольтерры, модели Лотки–Вольтерры с мутациями и информационной геометрии.
2. Порождающие соревновательные сети
Обсудим модель ПСС [1], [2] (см. также [7]). Пусть $X$ есть пространство исследуемых объектов, $p_\mathrm{data}$ – обучающая выборка (распределение) на $X$. В модели соревновательных сетей используются два параметрических распределения вероятностей: дискриминатор $D(x, \theta_\mathrm{d})$ с параметром $\theta_\mathrm{d}$ и генератор $p_\mathrm{gen}(x,\theta_\mathrm{g})$ с параметром $\theta_\mathrm{g}$.
Модель ПСС включает следующие задачи оптимизации: дискриминатор максимизирует близость к данным $p_\mathrm{data}$ и удаленность от генератора $p_\mathrm{gen}$,
Фактически в работах [1], [2] использовалась немного другая (эквивалентная) конструкция: вместо параметрического семейства $p_\mathrm{gen}$ распределений генератора на $X$ использовались распределение на некотором вспомогательном пространстве и параметрическое семейство отображений этого пространства в $X$.
При этом распределение данных есть (обучающая) выборка $\{x_i\}$, $i=1,\dots,n$, тогда функционал (1) принимает вид эмпирической суммы
Аргумент логарифма должен быть положителен, что задает ограничение на параметрическое семейство дискриминаторов – величина $D(x,\theta_\mathrm{d})$ должна быть меньше единицы.
Объединение этих двух задач дает следующую задачу из теории игр (проблема минимакса, равновесие Нэша): найти $\theta_\mathrm{d}$ и $\theta_\mathrm{g}$ такие, что достигается минимакс
При этом распределение генератора $p_\mathrm{gen}(x,\theta_\mathrm{g})$ (где $\theta_\mathrm{g}$ есть решение задачи минимакса) есть решение задачи обучения для модели порождающих соревновательных сетей.
Второй член в (2) (добавка к эмпирической сумме) и проблема минимакса служат борьбе с переобучением в задаче нахождения распределения максимального правдоподобия, т. е. максимизации первого члена в (2).
Эволюционная теория игр. Рассмотренная выше модель теории игр имеет следующую биологическую интерпретацию. Обучающая выборка $p_\mathrm{data}$ есть распределение травы, дискриминатор $D$ – распределение травоядных, генератор $p_\mathrm{gen}$ – распределение хищных. Задачи оптимизации интерпретируются как задачи эволюции: травоядный $D$ ищет траву и убегает от хищников, хищник $p_\mathrm{gen}$ ищет травоядных. Параметры $\theta_\mathrm{d}$ и $\theta_\mathrm{g}$ (параметры для дискриминатора и генератора) суть генотипы травоядных и хищных, вариация этих параметров означает наличие мутаций генотипов. Задача оптимизации означает дарвиновскую эволюцию, приспособление есть приближение дискриминатора и генератора к решению задачи минимакса для соревновательной сети.
Известно, что появление хищников вызывает ускорение эволюции. Мы обсуждаем этот эффект с точки зрения теории обучения. Для теории обучения это выглядит как добавление в эмпирический риск вклада от игры с нулевой суммой, а стимуляция эволюции хищниками есть регуляризация задачи обучения для борьбы с переобучением.
3. Популяционное обобщение модели соревновательных сетей
Переход от рассмотрения индивидуальных систем к рассмотрению ансамблей систем в физике отвечает переходу от механики к статистической механике, а в теории биологической эволюции – переходу от дарвинизма к популяционной генетике. Представляется, что подобный подход плодотворен также в теории машинного обучения. В стандартном подходе алгоритм обучения выполняет оптимизацию некоторого функционала на пространстве гипотез. В популяционном подходе такой алгоритм выполняет преобразование популяции обучающихся систем на пространстве гипотез к популяции, сосредоточенной в окрестности оптимума задачи обучения. Утверждается, что в популяционном подходе к обучению становятся более понятными некоторые аспекты теории обучения, в частности переобучение (см. раздел 4).
Построим модель типа Лотки–Вольтерры с мутациями, описывающую обобщение модели ПСС на случай популяций (распределений сетей по параметрам). А именно, мы рассмотрим модель типа Лотки–Вольтерры, где дискриминатор есть жертва, а генератор есть хищник. Популяции дискриминаторов и генераторов проживают на своих статистических многообразиях; в данной модели статистическое многообразие есть пространство геномов, диффузия на этом пространстве описывает мутации. Обучение для такой модели сводится к сходимости популяций дискриминатора и генератора (для модели ПСС это в основном популяции генератора) к популяциям, сосредоточенным на окрестности решения задачи обучения, т. е. гипотеза для генератора, дающая пик популяции генератора, может рассматриваться как решение задачи обучения.
Введем следующие обозначения: пусть $X$ с параметром $x$ есть пространство данных, $Y$ с параметром $y$ есть пространство (геномов) дискриминатора, $Z$ с параметром $z$ есть пространство (геномов) генератора. Таким образом, вдобавок к распределению данных на $X$ мы рассматриваем популяции дискриминаторов $f(y,t)$ на $Y$ и генераторов $g(z,t)$ на $Z$ (не обязательно нормированные).
Пусть динамика популяции дискриминатора описывается уравнением диффузии на статистическом многообразии $Y$, генератор диффузии есть оператор Лапласа–Бельтрами для метрики Фишера (см. приложение)
Члены с функциями $A$ и $B$ берутся из задачи минимакса для (1), (2). Рост функции $f(y,t)$ происходит за счет близости дискриминатора с параметром $y$ к данным, описываемым функцией $A(y)$ (5) (функцией правдоподобия)
$\alpha>0$. Член с $C>0$ для генератора описывает вымирание хищника при отсутствии жертв, константы $M_\mathrm{d},M_\mathrm{g}>0$ регулируют скорость мутаций для дискриминатора и генератора соответственно, $N_\mathrm{d},N_\mathrm{g}>0$ регулируют взаимодействие дискриминатора и генератора.
Здесь для члена с функцией $A$ по сравнению с (1), (2) применена экспонента, чтобы получить положительную функцию (логарифм может быть неположителен). Функция $A(y)$ также зависит от данных (от обучающей выборки), эта функция сосредоточена на значениях параметра (гипотезы) $y$ дискриминатора, для которых дискриминатор достаточно близок к распределению данных. Обучающая выборка для $A(y)$ в моделях популяционной генетики может зависеть от меняющихся от времени внешних условий, т. е. содержать зависящий от времени шум (тогда $A(y)$ зависит от времени).
Значения функции $B(y,z)$ вида (6) снижаются при удалении распределения генератора от распределения дискриминатора, т. е. узкие пики дискриминатора сильнее подавляются, или более специализированный хищник эффективнее охотится. Это влечет для системы (3), (4) эффект подавления узких пиков популяций для дискриминатора и генератора – соответствующие популяции будут стремиться занять более широкие области на своих статистических многообразиях; этому способствует также наличие генераторов диффузии в уравнениях (3), (4), но дополнительный эффект будет даваться также нелинейными членами.
Фактически для описанного эффекта не важен конкретный вид (6) функции $B(y,z)$ (как в работе [1]), важно, чтобы эта функция снижалась при удалении дискриминатора от генератора. Поэтому можно выбрать эту функцию в “кулоновском” виде
где $D(p|q)$ – расстояние Кульбака–Лейблера. Для модели ПСС генератор притягивается к дискриминатору, а дискриминатор от него отталкивается (“кулоновское” взаимодействие несимметрично).
Следует отметить, что равновесие Нэша (решение задачи минимакса) не обязано существовать в классе чистых стратегий. С точки зрения модели типа Лотки–Вольтерра это связано с возможностью существования популяционных циклов, для модели с мутациями подобные циклы могут включать не только осцилляции населенности, но также изменения геномов.
На основе уравнения (3) можно предложить аналог модели Эйгена [8] в рамках информационной геометрии, а именно уравнение
(см. также работы автора [3], [4], где обсуждается применение модели Эйгена популяционной генетики к теории обучения). В такой модели будет сохраняться общая населенность (интеграл $\int_Y f(y)\,dy$), если она равна $N$, потому что множитель в последнем члене не зависит от $y$. Для уравнения типа Лотки–Вольтерры это уже не так.
В настоящей модели информационная геометрия используется для введения метрики Фишера и оператора Лапласа–Бельтрами на статистическом многообразии (обзор информационной геометрии в классическом и квантовом случаях см. в [9]–[13], категорные аспекты информационной геометрии обсуждаются в [14]).
4. Контроль переобучения
Обсудим разные режимы решения задачи обучения (на примере оценки максимального правдоподобия).
Недообучение есть ситуация, когда мы не способны получить оценку максимального правдоподобия (не можем решить задачу оптимизации).
Желаемый результат обучения есть воспроизводимость обучения на контрольной выборке (способность к обобщению), т. е. оценка максимального правдоподобия должна слабо зависеть от выборки для большинства (по вероятности) выборок (т. е. для выборки общего положения).
Переобучение есть ситуация в теории обучения, когда имеют место высокое правдоподобие (малый риск) на обучающей выборке и при этом малое правдоподобие на контрольной выборке, т. е. существует сильная зависимость правдоподобия от выборки. Эффект связан с подгонкой гипотезы модели обучения под обучающую выборку (включая ее случайные особенности), в результате максимальное правдоподобие достигается на гипотезах, сильно удаленных от правильной, что проявляется в низком правдоподобии на контрольной выборке (низкой способности обобщения).
Для контроля переобучения предлагались следующие подходы. Модель обучения должна иметь конечную и малую VC-размерность (модель обучения должна быть простой) [15]. Минимумы функционала риска должны быть плоскими [16] (что в данной работе обсуждалось в связи с принципом минимальной длины описания для модели обучения). Обсуждались различные формы алгоритмической устойчивости [17]–[19] решения задачи обучения (некоторые разновидности устойчивости решения алгоритма обучения к возмущениям обучающей выборки).
С точки зрения алгоритмической устойчивости решения задачи обучения, если такое решение обладает способностью обобщения, оно отвечает максимуму для относительно широкого пика правдоподобия в пространстве гипотез. Узкие пики правдоподобия должны отвечать переобучению. Кроме того, такие пики должны быть достаточно далеко от настоящих (устойчивых) решений задачи обучения (потому что такое решение отвечает широкому пику). Таким образом, обучение есть нахождение максимума достаточно широкого пика правдоподобия в пространстве гипотез для обучающей выборки общего положения.
Контроль переобучения с точки зрения модели типа Эйгена (8) выглядит следующим образом: для узких пиков популяции на переобученных гипотезах мутации на близлежащие гипотезы (где приспособленность низка) ведут к снижению пиков и уменьшению переобучения. Возможная зависимость функции $A(y)$ вида (5) от времени (через зависимость данных от времени) усиливает этот эффект – пик приспособленности может сдвинуться относительно пика популяции, что для узких пиков снижает приспособленность (это в точности эффект отсутствия устойчивости обучения при модификации выборки). Подобный механизм обсуждался Фишером [20], т. е. Фишер фактически обсуждал для популяционной генетики некоторый вариант алгоритмической устойчивости. С другой стороны, слишком высокая скорость мутаций ведет к размыванию всех пиков, даже отвечающих правильной гипотезе (пик приспособленности для которой должен быть достаточно широким). Слишком высокая скорость мутаций в рамках модели Эйгена обсуждается как катастрофа ошибок и выражается в падении эффективности очищающего отбора в популяционной генетике.
Контроль переобучения с точки зрения модели типа Лотки–Вольтерры с мутациями (3), (4) имеет следующий вид: попадание хищника (генератора) на узкий пик популяции жертвы (дискриминатора) ведет к быстрому размножению хищника и подавлению острого пика. Это заставляет дискриминатора занимать более широкие области в пространстве гипотез, так как значения функции $B(y,z)$ вида (6) или (7) снижаются при удалении распределения генератора от распределения дискриминатора, т. е. узкие пики дискриминатора сильнее подавляются, более специализированый хищник эффективнее охотится. Это ведет к аналогичному поведению для генератора, при этом эти более широкие пики должны быть сосредоточены в области наличия данных (обучающей выборки). Это должно вести к снижению переобучения за счет подавления узких пиков популяций дискриминатора и генератора. Два других механизма контроля переобучения такие же, как для описанной выше модели типа Эйгена, – мутации и возможная зависимость функции $A(y)$ от времени. Скорость размножения хищника выше, чем скорость мутаций, поэтому модель типа Лотки–Вольтерры с мутациями обеспечивает более эффективный контроль переобучения, чем модель типа Эйгена; это также объясняет ускорение биологической эволюции при наличии хищников.
Таким образом, модели популяционной генетики [20] и эволюционной теории игр [21] имеют прямое отношение к современным моделям машинного обучения. Введенная модель Лотки–Вольтерры с мутациями (3), (4) может рассматриваться как популяционное обобщение модели ПСС. Такая модель порождает устойчивые к переобучению в смысле [17], [19] решения задачи обучения (отвечающие плоским максимумам правдоподобия [16]). Дарвиновское приспособление для такой модели популяционной генетики есть сходимость популяций дискриминатора и генератора к некоторым распределениям, сосредоточенным в окрестности решения задачи минимакса для ПСС. Также было введено обобщение модели Эйгена (8) на случай информационной геометрии.
Приложение
Метод максимального правдоподобия. Рассмотрим параметрическое семейство распределений вероятности $p(x,\theta)$, $x\in X$, с параметром $\theta$. Пусть $\{x_i\}$ – выборка независимых испытаний в $X$ (т. е. мы предполагаем существование распределения вероятности $q$ на $X$, которое порождает такую выборку). Функция правдоподобия имеет вид произведения плотностей вероятности для событий из выборки
принимает вид эмпирической суммы. Мы считаем, что распределение $p(x,\theta_0)$, отвечающее оценке максимального правдоподобия, приближает неизвестное распределение $q(x)$.
Переобучение является известной проблемой теории обучения: подгонка $p(x,\theta)$ к обучающей выборке $\{x_i\}$ может иметь высокое правдоподобие, но при этом низкое правдоподобие на контрольной выборке $\{x'_i\}$ (некоторой другой выборке, порожденной распределением $q$). Борьба с переобучением в теории обучения обычно сводится к регуляризации (добавкам к эмпирической сумме, изменяющим вид функции правдоподобия, или другой разновидности функционала эмпирического риска).
Теория игр. Игра есть функция нескольких переменных, называемых игроками. Игра принимает значения, равные набору вещественных чисел, по одному для каждого игрока
$i$-е число в наборе $v_i$ называется выигрышем для $i$-го игрока. Переменная $s_i$ для каждого игрока принимает значения, называемые (чистыми) стратегиями; для каждого игрока имеется свое множество стратегий.
Пример: два игрока, игра с нулевой суммой (сумма выигрышей игроков равна нулю).
Смешанная стратегия для $i$-го игрока: распределение вероятностей $p_i(s_j^i)$ для стратегий этого игрока, индекс $j$ нумерует различные стратегии для $i$-го игрока. Выигрыш $i$-го игрока для набора смешанных стратегий
есть усреднение выигрыша $i$-го игрока по смешанным стратегиям для всех игроков. Здесь индекс $j_k$ пробегает значения возможных стратегий $s_k$ для $k$-го игрока: $s_k\in\{s_{1}^k,\dots,s_{m_k}^k\}$.
Равновесие Нэша: набор стратегий, в которых ни один участник не может увеличить выигрыш, изменив свою стратегию, если другие участники своих стратегий не меняют. Существует в классе смешанных стратегий (в классе чистых стратегий может не существовать).
Максимин: наибольший выигрыш, который данный игрок может получить, не зная действий других игроков,
где $x$ – численность жертвы, $y$ – численность хищника, все константы положительны, нелинейный член описывает взаимодействие хищника и жертвы. Для экологической ниши конечного объема первое уравнение принимает вид ($N>0$)
Модель Лотки–Вольтерры с мутациями обобщает приведенную выше модель следующим образом: имеются жертвы $x_i$, хищники $y_m$, уравнения популяционной динамики имеют вид
Матрица $A$ имеет следующий смысл: диагональная часть описывает размножение жертв, внедиагональная часть описывает мутации (матричные элементы положительны). Матрица $C$ имеет следующий смысл: диагональная часть (с отрицательными матричными элементами) описывает вымирание хищников, внедиагональная часть описывает мутации (эти матричные элементы положительны). Матрица $B$ описывает взаимодействие хищника и жертвы (матричные элементы положительны).
Для ограниченной экологической ниши первое уравнение принимает вид
При отсутствии хищников ($y_n=0$) это уравнение принимает вид уравнения модели Эйгена [8], описывающей конкуренцию генотипов в ограниченной экологической нише при наличии мутаций.
Информационная геометрия [9]–[14]. Статистическое многообразие есть многообразие параметров параметрического распределения вероятности, или многообразие, точки которого являются распределениями вероятности на пространстве $X$ (предполагается гладкая зависимость распределения от параметров).
Расстояние Кульбака–Лейблера (несимметричное) между двумя распределениями вероятностей на $X$ определяется как
Автор заявляет, что у него нет конфликта интересов.
Список литературы
1.
I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, Y. Bengio, “Generative adversarial nets”, 28th Annual Conference on Neural Information Processing Systems 2014 (Montreal, Canada, 8–13 December, 2014), Advances in Neural Information Processing Systems, 27, eds. Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, K. Q. Weinberger, NIPS Foundation, La Jolla, CA, 2014, 2672–2680, arXiv: 1406.2661
2.
I. Goodfellow, NIPS 2016 tutorial: Generative adversarial networks, arXiv: 1701.00160
3.
S. V. Kozyrev, “Learning theory and population genetics”, Lobachevskii J. Math., 43:7 (2022), 1655–1662
4.
S. V. Kozyrev, “Learning by population genetics and matrix Riccati equation”, Entropy, 25:2 (2023), 348, 9 pp.
5.
A. M. Turing, “Computing machinery and intelligence”, Mind, LIX:236 (1950), 433–460
6.
V. Vanchurin, Yu. I. Wolf, M. I. Katsnelson, E. V. Koonin, “Towards a theory of evolution as multilevel learning”, Proc. Natl. Acad. Sci. USA, 119:6 (2022), e2120037119, 12 pp.
7.
С. Николенко, А. Кадурин, Е. Архангельская, Глубокое обучение. Погружение в мир нейронных сетей, Питер, СПб., 2018
8.
M. Eigen, J. McCaskill, P. Schuster, “Molecular quasi-species”, J. Phys. Chem., 92:24 (1988), 6881–6891
9.
Е. А. Морозова, Н. Н. Ченцов, “Естественная геометрия семейств вероятностных законов”, Теория вероятностей – 8, Итоги науки и техн. Сер. Соврем. пробл. матем. Фундам. направления, 83, ВИНИТИ, М., 1991, 133–265
10.
Н. Н. Ченцов, Статистические решающие правила и оптимальные выводы, Наука, М., 1972
11.
S. Amari, Differential-Geometrical Methods in Statistics, Lecture Notes in Statistics, 28, Springer, Berlin, 1985
12.
S. Amari, H. Nagaoka, Methods of Information Geometry, Translations of Mathematical Monographs, 191, AMS, Providence, RI, 2000
13.
P. Gibilisco, E. Riccomagno, M. P. Rogantin, H. P. Wynn (eds.), Algebraic and Geometric Methods in Statistics, Cambridge Univ. Press, Cambridge, 2010
14.
N. Combe, Yu. I. Manin, M. Marcolli, “Geometry of information: Classical and quantum aspects”, Theor. Comput. Sci., 908 (2022), 2–27, arXiv: 2107.08006
15.
V. N. Vapnik, The Nature of Statistical Learning Theory, Springer, New York, 2000
16.
S. Hochreiter, J. Schmidhuber, “Flat minima”, Neural Computation, 9:1 (1997), 1–42
17.
O. Bousquet, A. Elisseeff, “Stability and generalization”, J. Mach. Learn. Res., 2:3 (2002), 499–526
18.
S. Kutin, P. Niyogi, “Almost-everywhere algorithmic stability and generalization error”, Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence (UAI2002) (Alberta, Canada, August 1–4, 2002), eds. A. Darwiche, N. Friedman, Morgan Kaufmann Publ., San Francisco, CA, 2002, 275–282, arXiv: 1301.0579
19.
T. Poggio, R. Rifkin, S. Mukherjee, P. Niyogi, “General conditions for predictivity in learning theory”, Nature, 428 (2004), 419–422
20.
Р. Фишер, Генетическая теория естественного отбора, НИЦ “Регулярная и хаотическая динамика”, М.–Ижевск, 2011
21.
J. Maynard Smith, Evolution and the Theory of Games, Cambridge Univ. Press, Cambridge, 1982
Образец цитирования:
С. В. Козырев, “Модель типа Лотки–Вольтерры с мутациями и порождающие соревновательные сети”, ТМФ, 218:2 (2024), 320–329; Theoret. and Math. Phys., 218:2 (2024), 276–284