Мета-обучение — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Замена текстовых ссылок на сноски)
м (rollbackEdits.php mass rollback)
 
(не показаны 22 промежуточные версии 5 участников)
Строка 1: Строка 1:
<b>Мета-обучение</b> {{---}} подход, позволяющий определять оптимальный алгоритм (иногда, вместе с параметрами к нему) для конкретной задачи. Основная идея мета-обучения {{---}} свести задачу выбора алгоритма к задаче обучения с учителем: задачи описываются мета-фичами. Мета-фича описывает свойство задачи {{---}} например, разрежен ли датасет или нет.
+
<b>Мета-обучение</b>(англ. Meta-learning) {{---}} подход, позволяющий определять наиболее подходящий алгоритм (иногда, вместе с параметрами к нему) для конкретной задачи из портфолио алгоритмов. Основная идея мета-обучения {{---}} свести задачу выбора алгоритма к задаче [[Общие понятия#Классификация задач машинного обучения|обучения с учителем]]: задачи описываются мета-признаками. Мета-признак описывает свойство задачи {{---}} например, разрежен ли датасет или нет, число категориальных или численных признаков объектов в датасете, число возможных меток, размер датасета и многое другое.
  
От хорошей модели ожидается хорошая адаптируемость или генерализуемость новых задач и окружений, с которыми модель не сталкивалась во время обучения.
+
От хорошей модели ожидается высокая адаптируемость к новым задачам и окружениям, на небольшом количестве примеров.
  
Такими задачами являются:
+
<h2>Обзор</h2>
* Классификатор, тренированный на изображениях собак и велосипедов, после некоторых показанных ему кошек, смог определить, есть ли на новой картинке кошка
 
* Игровой бот, способный быстро обучиться новой игре
 
* Робот, выполняющий задачу на пригорке во время теста даже если он тренировался на ровной поверхности
 
  
Ограничения
+
Модель должна быть обучена на множестве задач и оптимизирована для лучшей производительности на нескольких задачах, включая такие,
- No free lunch teorem<ref>[https://www.researchgate.net/publication/221997149_No_Free_Lunch_Theorems_for_Search Wolpert and Macready, 1996]</ref><ref>[https://www.researchgate.net/publication/228671734_Toward_a_justification_of_meta-learning_Is_the_no_free_lunch_theorem_a_show-stopper Giraud-Carrier and Provost, 2005]</ref>
+
с которыми модель не сталкивалась ранее. Каждой задаче соответствует множество наборов данных $\mathcal{D}$, каждый из которых содержит и векторы признаков и разметку.
 
 
<h2>Simple view</h2>
 
 
 
Хорошая модель мета-обучения должна быть обучена на множестве задач и оптимизирована для лучшей производительности на нескольких задачах,
 
включая такие, с которыми модель не сталкивалась ранее. Каждой задаче соответствует датасет $\mathcal{D}$, содержащий и векторы фичей и правильную разметку.
 
 
Оптимальные параметры модели:
 
Оптимальные параметры модели:
  
Строка 21: Строка 13:
 
\end{aligned}
 
\end{aligned}
  
Очень похоже на обычную задачу машинного обучения, только один датасет принимается за один сэмпл данных.
+
Очень похоже на обычную задачу машинного обучения, только один датасет принимается за один образец данных.
  
Few-shot классификатор конкретизация мета-обучения в области обучения с учителем. Датасет $\mathcal{D}$ делится на две части: $\mathcal{D}=\langle S, B\rangle$,
+
Ограничения {{---}} Теорема о том, что бесплатного завтрака не бывает(англ. No Free Lunch Theorem, сокр. NFL) theorem<ref>[https://www.researchgate.net/publication/221997149_No_Free_Lunch_Theorems_for_Search Wolpert and Macready, 1996]</ref><ref>[https://www.researchgate.net/publication/228671734_Toward_a_justification_of_meta-learning_Is_the_no_free_lunch_theorem_a_show-stopper Giraud-Carrier and Provost, 2005]</ref> , доказанная в 1996 году.
train set $S$ и test set $B$. Часто принимается k-shot N-class задача - train set содержит $k$ размеченных примеров для каждого из $N$ классов.
+
{{Теорема
Датасет $\mathcal{D}$ содержит пары фичей и меток, $\mathcal{D} = \{(\mathbf{x}_i, y_i)\}$ и каждая метка принадлежит известному множеству меток $\mathcal{L}$. Скажем, наш классификатор $f_θ$ с параметром $θ$ показывает вероятность принадлежности точки из данных к классу $y$ при векторе фичей $x$, $Pθ(y|x)$
+
|about = No free Lunch Theorem
Оптимальные параметры должны максимизировать вероятность верных меток среди нескольких training sets $B⊂\mathcal{D}$:
+
|statement = Пусть <tex>P(d_{m}^{y}| f, m, a)</tex> {{---}} условная вероятность получения частного решения $d_m$ после $m$ итераций работы алгоритма $a$ при целевой функции $f$. Для любой пары алгоритмов $a_1$ и $a_2$ имеет место равенство:
  
 +
<tex>
 +
\\
 
\begin{aligned}
 
\begin{aligned}
\theta^* &= {\arg\max}_{\theta} \mathbb{E}_{(\mathbf{x}, y)\in \mathcal{D}}[P_\theta(y \vert \mathbf{x})] &\\
+
\sum_{f}P(d_{m}^{y}| f, m, a_1) = \sum_{f}P(d_{m}^{y}| f, m, a_2)
\theta^* &= {\arg\max}_{\theta} \mathbb{E}_{B\subset \mathcal{D}}[\sum_{(\mathbf{x}, y)\in B}P_\theta(y \vert \mathbf{x})] & \scriptstyle{\text{; trained with mini-batches.}}
 
 
\end{aligned}
 
\end{aligned}
 +
</tex>
 +
}}
 +
Иными словами, если встречается задача, которая не похожа на то, что решалось ранее, то мы не сможем сразу придумать для него эффективное решение.
  
В few-shot классификации цель {{---}} уменьшить ошибку предсказания на неразмеченных данных с данным train set для "быстрого обучения". Чтобы ускорить процесс обучения, сделаем следующее:
+
Общая идея мета-обучения: для каждого набора данных $d \in \mathcal{D}$ вычисляется вектор мета-признаков, которые описывают свойства этого набора данных. Ими могут быть: число категориальных или численных признаков объектов в $d$, число возможных меток, размер $d$ и многие другие<ref>[https://www.fruct.org/publications/ainl-fruct/files/Fil.pdf Datasets meta-feature description for recommending feature selection algorithm]</ref>. Подробнее о конкретных метапризнаках смотреть [[Мета-обучение#Определение множества конфигураций|ниже]]
# возьмем подмножество меток, $L\subset\mathcal{L}$
+
 
# возьмем train set $S^L⊂D$ и train batch $B^L⊂D$. Оба содержат только данные с метками из подмножества с пункта 1:
+
Каждый алгоритм запускается на всех наборах данных из $\mathcal{D}$. После этого вычисляется эмпирический риск, на основе которого формируются метки классов. Затем мета-классификатор обучается на полученных результатах. В качестве описания набора данных выступает вектор мета-признаков, а в качестве метки — алгоритм, оказавшийся самым эффективным с точки зрения заранее выбранной меры качества.  
 +
 
 +
Каждый датасет $d \in \mathcal{D}$ содержит пары признаков и меток, $\{(x_i, y_i)\}$, каждая метка принадлежит известному множеству меток $\mathcal{T}$.
 +
Датасет $d$ делится на две части: $d=\langle S, B\rangle$, обучающую $S$ и тестовую $B$ выборки. Часто принимается k-shot N-class задача {{---}} обучающая выборка содержит $k$ размеченных примеров для каждого из $N$ классов.
 +
Скажем, наш классификатор $f_\theta$ с параметром $\theta$ показывает вероятность принадлежности точки из данных к классу $y$ при векторе признаков, $P_\theta(y|x)$.
 +
Оптимальные параметры должны максимизировать вероятность получения верных меток среди нескольких обучающих выборок $B⊂\mathcal{D}$:
  
 
\begin{aligned}
 
\begin{aligned}
L, y \in L, \forall (x, y) \in S^L, B^L
+
\theta^* &= {\arg\max}_{\theta} \mathbb{E}_{(\mathbf{x}, y)\in \mathcal{D}}[P_\theta(y \vert \mathbf{x})] & \\
 +
\theta^* &= {\arg\max}_{\theta} \mathbb{E}_{B\subset \mathcal{D}}[\sum_{(\mathbf{x}, y)\in B}P_\theta(y \vert \mathbf{x})] & \\
 
\end{aligned}
 
\end{aligned}
  
# Множество $S^L$ подается на вход модели.
+
В пристрелочной (few-shot) классификации цель {{---}} уменьшить ошибку предсказания на неразмеченных данных. Чтобы его ускорить, сделаем следующее:
# Конечная оптимизация использует множество $B^L$ чтобы посчитать loss и обновить параметры модели через обратное распространение, так же, как это делается в обучении с учителем.
+
# Возьмем подмножество меток, $T\subset\mathcal{T}$
 
+
# Возьмем обучающее множество $S^T⊂D$ и обучающую выборку $B^T⊂D$. Оба содержат только данные с метками из подмножества с пункта 1: $L, y \in L, \forall (x, y) \in S^T, B^T$
Можно представить каждую пару сэмплированного датасета $(S^L,B^L)$ как одну точку. Модель обучается таким образом, чтобы она могла обобщиться до других датасетов.
+
# Множество $S^T$ подается на вход модели
Красным выделен дифф между обучением с учителем и мета-обучением.
+
# Конечная оптимизация использует множество $B^T$, чтобы посчитать функцию потерь и обновить параметры модели через обратное распространение, так же, как это делается в обучении с учителем.
  
 
\begin{aligned}
 
\begin{aligned}
\theta = \arg\max_\theta \color{red}{E_{L\subset\mathcal{L}}[} E_{\color{red}{S^L \subset\mathcal{D}, }B^L \subset\mathcal{D}} [\sum_{(x, y)\in B^L} P_\theta(x, y\color{red}{, S^L})] \color{red}{]}
+
\theta = \arg\max_\theta \color{red}{\mathbb{E}_{T \sim \mathcal{T}}}[ \mathbb{E}_{\color{red}{S \sim T,} B \color{red}{\sim T}} [\sum_{(x, y) \in B} P_\theta(y \vert \mathbf{x} \color{red}{, S})]]
 
\end{aligned}
 
\end{aligned}
 +
Красным цветом выделена разница между обучением с учителем и подходом мета-обучения.
  
Идея в некоторой степени аналогична использованию предварительно обученной модели в классификации изображений (ImageNet) или в языковом моделировании (большие текстовые корпуса), когда доступен только ограниченный набор образцов данных для конкретной задачи. Мета-обучение идет еще  на один шаг вперед, вместо того, чтобы подстраивать ее под одну задачу, она оптимизирует модель, чтобы она была хороша для многих задач.
+
Идея в некоторой степени аналогична использованию предварительно обученной модели в классификации изображений (ImageNet) или в [[обработка естественного языка | NLP]] (большие текстовые корпуса),
 
+
когда доступен только ограниченный набор образцов данных для конкретной задачи. Модель обучается таким образом, чтобы она могла обобщиться до других датасетов.
<h2>Основанные на оптимизации</h2>
 
  
Модели глубокого обучения (deep learning) обучаются через обратное распространение градиентов. Тем не менее, оптимизация, основанная на градиентах не разрабатывалась для работы с небольшим количеством обучающих семплов, и не сходится за малое число оптимизационных шагов. Подход в мета-обучении, основанный на оптимизации как раз про это.
+
<h2>Оптимизации методов Мета-обучения</h2>
  
 
<h3>LSTM-meta-learner</h3>
 
<h3>LSTM-meta-learner</h3>
Оптимизационный алгоритм может быть явно смоделирован. Ravi & Larochelle (2017) это и сделали и назвали его "meta-learner". Цель meta-learner'а - эффективно обновлять параметры learner'a используя небольшой train set так, чтобы learner мог быстро адаптироваться к новым задачам.
+
{{main|Долгая краткосрочная память}}
 +
Оптимизационный алгоритм может быть явно смоделирован. Рави и Ларошель <ref>[https://openreview.net/pdf?id=rJY0-Kcll Ravie & Larochelle, Optimization as a model for a few-shot learning, 2017]</ref> это и сделали и назвали его "meta-learner". Цель meta-learner'а {{---}} эффективно обновлять свои параметры используя небольшую обучающую выборку так, чтобы learner мог быстро адаптироваться к новым задачам.
  
Пусть модель ученика будет $M_θ$, параметризованной $θ$, и meta-learner как $R_Θ$ с параметром $θ$, и функция потерь $\mathcal{L}$.
+
Пусть модель ученика будет $M_\theta$, параметризованной $\theta$, и meta-learner как $R_\theta$ с параметром $\theta$, и функция потерь $\mathcal{L}$.
  
Обновление параметров learner'a во время $t$ c learning rate $\alpha_t$ (шаг градиентного спуска):
+
Обновление параметров learner'a во время $t$ со скоростью обучения $\alpha_t$ (шаг градиентного спуска):
  
 
\begin{aligned}
 
\begin{aligned}
Строка 79: Строка 82:
  
 
\begin{aligned}
 
\begin{aligned}
f_t &= \sigma(\mathbf{W}_f \cdot [\nabla_{\theta_{t-1}}\mathcal{L}_t, \mathcal{L}_t, \theta_{t-1}, f_{t-1}] + \mathbf{b}_f) & \scriptstyle{\text{; как сильно мы забываем старые значения параметров.}}\\
+
f_t &= \sigma(\mathbf{W}_f \cdot [\nabla_{\theta_{t-1}}\mathcal{L}_t, \mathcal{L}_t, \theta_{t-1}, f_{t-1}] + \mathbf{b}_f) & \\
i_t &= \sigma(\mathbf{W}_i \cdot [\nabla_{\theta_{t-1}}\mathcal{L}_t, \mathcal{L}_t, \theta_{t-1}, i_{t-1}] + \mathbf{b}_i) & \scriptstyle{\text{; соответствует рейту обучения на шаге t.}}\\
+
i_t &= \sigma(\mathbf{W}_i \cdot [\nabla_{\theta_{t-1}}\mathcal{L}_t, \mathcal{L}_t, \theta_{t-1}, i_{t-1}] + \mathbf{b}_i) & \\
\tilde{\theta}_t &= -\nabla_{\theta_{t-1}}\mathcal{L}_t &\\
+
\tilde{\theta}_t &= -\nabla_{\theta_{t-1}}\mathcal{L}_t & \\
\theta_t &= f_t \odot \theta_{t-1} + i_t \odot \tilde{\theta}_t &\\
+
\theta_t &= f_t \odot \theta_{t-1} + i_t \odot \tilde{\theta}_t & \\
 
\end{aligned}
 
\end{aligned}
 
+
$f_t$ {{---}} как сильно мы забываем старые значения параметров на шаге $t$, $i_t$ {{---}} рейт обучения на шаге $t$.
я ничего не понял..
 
  
 
<h3>REPTILE</h3>
 
<h3>REPTILE</h3>
Строка 91: Строка 93:
 
Reptile {{---}} относительно простой алгоритм мета-обучения, похожий на MAML, например, тем, что оба используют мета-оптимизацию через градиентный спуск и оба не чувствительны к модели.
 
Reptile {{---}} относительно простой алгоритм мета-обучения, похожий на MAML, например, тем, что оба используют мета-оптимизацию через градиентный спуск и оба не чувствительны к модели.
  
# сэмплируем задачу
+
# Случайным образом разбиваем задачук на подмножества
 
# тренируемся на ней несколькими шагами градиентного спуска
 
# тренируемся на ней несколькими шагами градиентного спуска
 
# сдвигаем веса модели к новым параметрам.
 
# сдвигаем веса модели к новым параметрам.
  
$\text{SGD}(\mathcal{L}_{\tau_i}, \theta, k)$ выполняет стохастический градиентный спуск на $k$ шагов на лоссе $\mathcal{L}_{\tau_i}$, начиная с параметра $\theta$ и возвращает конечный вектор параметров. Градиент reptile определяется как $(\theta - W)/\alpha$, где $\alpha$ {{---}} размер шага, используемый функцией $SGD$.
+
$\text{SGD}(\mathcal{L}_{\tau_i}, \theta, k)$ выполняет стохастический градиентный спуск на $k$ шагов c функцией потерь $\mathcal{L}_{\tau_i}$, начиная с параметра $\theta$ и возвращает конечный вектор параметров. Градиент reptile определяется как $(\theta - W)/\alpha$, где $\alpha$ {{---}} размер шага, используемый функцией $SGD$.
  
   <font color=green>// Algorithm REPTILE, batched version</font>
+
   <font color=green>// Алгоритм REPTILE</font>
 
   Initialize $\theta$
 
   Initialize $\theta$
 
   '''for''' $iteration = 1, 2,...$ '''do'''
 
   '''for''' $iteration = 1, 2,...$ '''do'''
Строка 108: Строка 110:
  
 
<h2>Определение множества конфигураций</h2>
 
<h2>Определение множества конфигураций</h2>
Предшествующие вычисления могут быть также использованы для изучения пространства более успешных конфигураций \theta\star. Более подходящие под задачу конфигурации могут серьезно ускорить поиск оптимальных моделей, это важно при ограниченных вычислительных рессурсах.
+
Предшествующие вычисления могут быть также использованы для изучения пространства более успешных конфигураций $\theta^{\star}$. Более подходящие под задачу конфигурации могут серьезно ускорить поиск оптимальных моделей, это важно при ограниченных вычислительных ресурсах.
  
Альтернативный подход сперва узнать оптимальные гиперпараметры, а потом через приращение производительности определить важность каждого из гиперпараметров. Это и было сделано в лабе OpenML, провели около 500 000 экспериментов на 6 алгоритмах и 38 датасетах. Стандартные значения изучались вместе для всех гиперпараметров алгоритма посредством обучения суррогатных моделей для этого алгоритма на большом числе задач. После того, как уже проверены многие варианты конфигураций, выбирается такая, которая минимизирует ??? для всех задач, становится стандартной.Далее определяется важность каждого из гиперпараметров. Чем больше меняется приращение производительности, тем более важный гиперпараметр мы изменяем.
+
Альтернативный подход сперва узнать оптимальные гиперпараметры, а потом через приращение производительности определить важность каждого из гиперпараметров. Это и было сделано в лаборатории OpenML, где провели около 500 000 экспериментов на 6 алгоритмах, использовав при этом 38 датасетах. Стандартные значения изучались вместе для всех гиперпараметров алгоритма посредством обучения суррогатных моделей на большом числе задач. После того, как уже проверены многие варианты конфигураций, выбирается такая, которая минимизирует средний риск для всех задач, и становится стандартной. Далее определяется важность каждого из гиперпараметров. Чем больше меняется приращение производительности, тем более важный гиперпараметр мы изменяем.
  
Если мы хотим предоставить рекомендации для конкретной задачи $t_{new}$, нам нужна дополнительная информация о том, насколько $t_{new}$ похожа на предыдущие задачи $t_j$. Первый способ {{---}} посчитать число рекомендованных конфигураций для $t_new$, yielding новый эвиденс $\mathbf{P}_{new}$. Если позже мы будем наблюдать, что вычисления $P_{i,new}$ соответствуют $P_{i, j}$, то $t_{j}$ и $t_{new}$ могут быть очень похожими. Мы можем применить это знания для обучения meta-learner'a который предсказывает множество рекомендуемых конфигураций $\Theta^{*}_{new}$ for $t_{new}$.
+
Если мы хотим предоставить рекомендации для конкретной задачи $t_{new}$, нам нужна дополнительная информация о том, насколько $t_{new}$ похожа на предыдущие задачи $t_j$. Первый способ {{---}} посчитать число рекомендованных конфигураций для $t_{new}$,получая новое докозательство $\mathbf{P}_{new}$. Если позже мы будем наблюдать, что вычисления $P_{i,new}$ соответствуют $P_{i, j}$, то $t_{j}$ и $t_{new}$ могут быть очень похожими. Мы можем применить это знания для обучения meta-learner'a который предсказывает множество рекомендуемых конфигураций $\Theta^{*}_{new}$ for $t_{new}$.
Более того, можно пойти дальше и добавить $\Theta^{*}_{new}$ в $P_new$ и перейти к следующей итерации и выяснять какие еще задачи схожи друг с другом.
+
Более того, можно пойти дальше и добавить $\Theta^{*}_{new}$ в $P_{new$ и перейти к следующей итерации и выяснять какие еще задачи схожи друг с другом.
 
 
<h3>Relative landmarks</h3>
 
Первая мера для вычисления "похожести" задач вычисляла попарно разницу в производительности, так же называемую "relative landmarks" $RL_{a,b,j} = P_{a,j} - P_{b,j}$ между двумя конфигурациями $\theta_{a}$ и $\theta_{b}$ на конкретной задаче $t_{j}$.
 
  
 
<h3>Суррогатные модели</h3>
 
<h3>Суррогатные модели</h3>
 
Более гибкий способ передать информацию {{---}} построить суррогатную модель $s_{j}(\theta_{i}) = P_{i,j}$ для всех предшествующих задач $t_{j}$, обученную с использованием всех доступных $\mathbf{P}$. Можно определить "похожесть" задач в терминах ошибок между $s_{j}(\theta_{i})$ и $P_{i,new}$: если суррогатная модель для $t_{j}$ может генерировать точные предсказания для $t_{new}$, тогда такие задачи весьма похожи. Обычно это делается в комбинации с Байесовской оптимизацией для определения следующей $\theta_{i}$.
 
Более гибкий способ передать информацию {{---}} построить суррогатную модель $s_{j}(\theta_{i}) = P_{i,j}$ для всех предшествующих задач $t_{j}$, обученную с использованием всех доступных $\mathbf{P}$. Можно определить "похожесть" задач в терминах ошибок между $s_{j}(\theta_{i})$ и $P_{i,new}$: если суррогатная модель для $t_{j}$ может генерировать точные предсказания для $t_{new}$, тогда такие задачи весьма похожи. Обычно это делается в комбинации с Байесовской оптимизацией для определения следующей $\theta_{i}$.
  
Так же можно обучать суррогатные модели на Гауссовских процессах (GP) для каждой предыдущей задачи и еще одну для $t_{new}$ и объединить их во взвешенную и нормализованную сумму, с медианой $\mu$ определенной как взвшенная сумма $\mu_{j}$ полученных из задач $t_{j}$. Веса $\mu_{j}$ считаются через Nadaraya-Watson kernel-weighted average, где каждая задача представлена вектором relative landmarks и Epanechnikov quadratic kernel используется для определения похожести между векторами relative landmarks для $t_{j}$ и $t_{new}$. Чем больше $t_{j}$ похожа на  $t_{new}$, тем больше получится вес $s_{j}$, увеличивающий влияние суррогатной модели для $t_{j}$.
+
Так же можно обучать суррогатные модели на Гауссовских процессах (GP) для каждой предыдущей задачи и еще одну для $t_{new}$ и объединить их во взвешенную и нормализованную сумму, с медианой $\mu$ определенной как взвешанная
 +
сумма $\mu_{j}$ полученных из задач $t_{j}$. Веса $\mu_{j}$ считаются методом Надарая-Ватсона<ref>[http://www.maths.manchester.ac.uk/~peterf/MATH38011/NPR%20N-W%20Estimator.pdf Nadaraya-Watson estimator]</ref>, где каждая задача представлена вектором относительных ориентиров (англ. relative landmarks) или
 +
ядром Епанечникова<ref>[https://epubs.siam.org/doi/10.1137/1114019 V. A. Epanechnikov, Non-Parametric Estimation of a Multivariate Probability Density]</ref>, используется для определения похожести между векторами относительных ориентиров для $t_{j}$ и $t_{new}$.
 +
Чем больше $t_{j}$ похожа на  $t_{new}$, тем больше получится вес $s_{j}$, увеличивающий влияние суррогатной модели для $t_{j}$.
  
 
Суррогатные модели обучаются только на $P_{i, new}$, а следующий $\theta_{i}$ получается путем нахождения средневзвешенного expected improvement $P_{i, new}$ и предсказанных улучшений на всех предшествующих $P_{i, j}$.
 
Суррогатные модели обучаются только на $P_{i, new}$, а следующий $\theta_{i}$ получается путем нахождения средневзвешенного expected improvement $P_{i, new}$ и предсказанных улучшений на всех предшествующих $P_{i, j}$.
Веса предшествующих задач могут быть переопределены через точность суррогатной модели или через relative landmarks.
+
Веса предшествующих задач могут быть переопределены через точность суррогатной модели или через относительных ориентиров.
 
Вес ожидаемого улучшения (expected improvement) постепенно возрастает с каждой итерацией (с увеличением собранного эвиденса $P_{i, new}$).
 
Вес ожидаемого улучшения (expected improvement) постепенно возрастает с каждой итерацией (с увеличением собранного эвиденса $P_{i, new}$).
  
 
<h3>Обучение на свойствах задачи (learning on task properties)</h3>
 
<h3>Обучение на свойствах задачи (learning on task properties)</h3>
Каждая задача $t_{j} \in T$ может быть описана вектором $m(t_j) = (m_{j,1}, ...,m_{j,K})$ из $K$ мета-фичей $m_{j, k} \in M$ $M$ {{---}} множество мета-фичей. Можно определить меру "похожести" задач, основанную, например, на Евклидовом расстоянии между $m(t_i)$ и $m(t_j)$, тогда можно будет использовать информацию из наиболее похожей задачи на новую задачу $t_{new}$. Более того, используя предшествующие вычисления $\textbf{P}$ можно обучить meta-learner'a $L$ предсказывать производительность $P_{i, new}$ конфигураций $\theta_{i}$ на новых задачах $t_{new}$.
+
Каждая задача $t_{j} \in T$ может быть описана вектором $m(t_j) = (m_{j,1}, ...,m_{j,K})$ из $K$ мета-признаков $m_{j, k} \in M$,где $M$ {{---}} множество мета-признаков. Можно определить меру "похожести" задач, основанную, например, на Евклидовом расстоянии между $m(t_i)$ и $m(t_j)$, тогда можно будет использовать информацию из наиболее похожей задачи на новую задачу $t_{new}$. Более того, используя предшествующие вычисления $\textbf{P}$ можно обучить meta-learner'a $L$ предсказывать производительность $P_{i, new}$ конфигураций $\theta_{i}$ на новых задачах $t_{new}$.
  
 
$L: \Theta \times M \rightarrow \textbf{P}$
 
$L: \Theta \times M \rightarrow \textbf{P}$
  
В таблице представлен обзор наиболее используемых мета-фичей.
+
В таблице ниже представлен обзор наиболее используемых мета-признаков.
  
 
{| class="wikitable"
 
{| class="wikitable"
|+ Meta-feature
+
|+ мета-признаки
|-
 
! '''Name''' !! '''Formula''' !! '''Rationale''' !! '''Variants'''
 
 
|-
 
|-
| colspan="4" align="center" | '''simple'''
+
! '''Название''' !! '''Формула''' !! '''Объяснение''' !! '''Варианты'''
 
|-
 
|-
| Nr instances || $n$ || Speed, Scalability \citep{Michie1994} || $p/n$, $log(n)$, log(n/p)
+
| colspan="4" align="center" | '''простые'''
 
|-
 
|-
| Nr features || $p$ || Curse of dimensionality \citep{Michie1994} || $log(p)$, % categorical
+
| instances || $n$ || Speed, Scalability<ref>[https://www1.maths.leeds.ac.uk~charlesstatlogwhole.pdf Donald Michie, David J. Spiegelhalter, Charles C. Taylor, and John Campbell. Machine Learning, Neural and Statistical Classification, 1994]</ref> || $p/n$, $log(n)$, log(n/p)
 
|-
 
|-
| Nr classes || $c$ || Complexity, imbalance \citep{Michie1994} || ratio min/maj class
+
| features || $p$ || Curse of dimensionality || $log(p)$, % categorical
 
|-
 
|-
| Nr missing values || $m$ || Imputation effects \citep{kalousis02} || % missing
+
| classes || $c$ || Complexity, imbalance || ratio min/maj class
 
|-
 
|-
| Nr outliers || $o$ || Data noisiness \citep{Rousseeuw2011} || $o/n$
+
| Percent of missing values || $m$ || Imputation effects <ref>A. Kalousis. Algorithm Selection via Meta-Learning. PhD thesis, University of Geneva, Department of Computer Science, 2002</ref> || % missing
 
|-
 
|-
| colspan="4" align="center" | '''statistical'''
+
| outliers || $o$ || Data noisiness <ref>Peter J. Rousseeuw and Mia Hubert. Robust statistics for outlier detection. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2011.</ref> || $o/n$
 
|-
 
|-
| Skewness || $\frac{E(X-\mu_{X})^{3}}{\sigma_{X}^{3}}$ || Feature normality \citep{Michie1994} || min,max,$\mu$,$\sigma$,$q_{1},q_{3}$
+
| colspan="4" align="center" | '''статистические'''
 
|-
 
|-
| Kurtosis || $\frac{E(X-\mu_{X})^{4}}{\sigma_{X}^{4}}$ || Feature normality \citep{Michie1994} || min,max,$\mu$,$\sigma$,$q_{1},q_{3}$
+
| Skewness || $\frac{E(X-\mu_{X})^{3}}{\sigma_{X}^{3}}$ || Feature normality || min,max,$\mu$,$\sigma$,$q_{1},q_{3}$
 
|-
 
|-
| Correlation || $\rho_{X_{1}X_{2}}$ || Feature interdependence \citep{Michie1994} || min,max,$\mu$,$\sigma$,$\rho_{XY}$
+
| Kurtosis || $\frac{E(X-\mu_{X})^{4}}{\sigma_{X}^{4}}$ || Feature normality || min,max,$\mu$,$\sigma$,$q_{1},q_{3}$
 
|-
 
|-
| Covariance || $cov_{X_{1}X_{2}}$ || Feature interdependence \citep{Michie1994} || min,max,$\mu$,$\sigma$,$cov_{XY}$
+
| Correlation || $\rho_{X_{1}X_{2}}$ || Feature interdependence || min,max,$\mu$,$\sigma$,$\rho_{XY}$
 
|-
 
|-
| Concentration || $\tau_{X_{1}X_{2}}$ || Feature interdependence \citep{Kalousis2001a} || min,max,$\mu$,$\sigma$,$\tau_{XY}$
+
| Covariance || $cov_{X_{1}X_{2}}$ || Feature interdependence || min,max,$\mu$,$\sigma$,$cov_{XY}$
 
|-
 
|-
| Sparsity || sparsity(X) || Degree of discreteness \citep{Salama2013} || min,max,$\mu$,$\sigma$
+
| Concentration || $\tau_{X_{1}X_{2}}$ || Feature interdependence <ref>Alexandros Kalousis and Melanie Hilario. Model selection via meta-learning: a comparative study.Intl Journ. on Artificial Intelligence Tools, 2001.</ref> || min,max,$\mu$,$\sigma$,$\tau_{XY}$
 
|-
 
|-
| Gravity || gravity(X) || Inter-class dispersion \citep{Ali2006} ||
+
| Sparsity || sparsity(X) || Degree of discreteness <ref>Mostafa A. Salama, Aboul~Ella Hassanien, and Kenneth Revett. Employment of neural network and rough set in meta-learning, 2013.</ref> || min,max,$\mu$,$\sigma$
 
|-
 
|-
| ANOVA p-value || $p_{val_{\texttt{X}_{1}X_{2}}}$ || Feature redundancy \citep{kalousis02} || $p_{val_{XY}}$\citep{soares+04}
+
| Gravity || gravity(X) || Inter-class dispersion <ref>Shawkat Ali and Kate~A. Smith-Miles. On learning algorithm selection for classification. Applied Soft Computing, 2006.</ref> ||
 
|-
 
|-
| Coeff. of variation || $\frac{\sigma_{Y}}{\mu_{Y}}$ || Variation in target \citep{soares+04} ||
+
| ANOVA p-value || $p_{val_{\texttt{X}_{1}X_{2}}}$ || Feature redundancy || $p_{val_{XY}}$
 
|-
 
|-
| PCA $\rho_{\lambda_{1}}$ || $\sqrt{\frac{\lambda_{1}}{1+\lambda_{1}}}$ || Variance in first PC \citep{Michie1994} || $\frac{\lambda_{1}}{\sum_{i} \lambda_{i}}$\citep{Michie1994}
+
| Coeff. of variation || $\frac{\sigma_{Y}}{\mu_{Y}}$ || Variation in target <ref>C. Soares, P. Brazdil, and P. Kuba. A meta-learning method to select the kernel width in support vector  regression, 2004.</ref> ||
 
|-
 
|-
| PCA skewness || || Skewness of first PC \citep{feurer2014using} || PCA kurtosis
+
| PCA $\rho_{\lambda_{1}}$ || $\sqrt{\frac{\lambda_{1}}{1+\lambda_{1}}}$ || Variance in first PC || $\frac{\lambda_{1}}{\sum_{i} \lambda_{i}}$
 
|-
 
|-
| PCA 95\% || $\frac{dim_{95\% var}}{p}$ || Intrinsic dimensionality \citep{bardenet2013collaborative} ||
+
| PCA skewness || || Skewness of first PC || PCA kurtosis
 
|-
 
|-
| Class probability || $P(\texttt{C})$ || Class distribution \citep{Michie1994} || min,max,$\mu$,$\sigma$
+
| PCA 95\% || $\frac{dim_{95\% var}}{p}$ || Intrinsic dimensionality <ref>R ́emi Bardenet, M ́aty ́as Brendel, Bal ́azs K ́egl, and Michele Sebag. Collaborative hyperparameter tuning. In Proceedings of ICML 2013, pages 199–207, 2013</ref> ||
 
|-
 
|-
| colspan="4" align="center" | '''informational-theoretic'''
+
| Class probability || $P(\texttt{C})$ || Class distribution || min,max,$\mu$,$\sigma$
 
|-
 
|-
| Class entropy  || $H(\texttt{C})$ || Class imbalance \citep{Michie1994} ||
+
| colspan="4" align="center" | '''информационно-теоретические'''
 
|-
 
|-
| Norm. entropy || $\frac{H(\texttt{X})}{log_{2}n}$ || Feature informativeness \citep{Castiello2005} || min,max,$\mu$,$\sigma$
+
| Class entropy || $H(\texttt{C})$ || Class imbalance ||
 
|-
 
|-
| Mutual inform. || $MI(\texttt{C},\texttt{X})$ || Feature importance \citep{Michie1994} || min,max,$\mu$,$\sigma$
+
| Norm. entropy || $\frac{H(\texttt{X})}{log_{2}n}$ || Feature informativeness <ref>Ciro Castiello, Giovanna Castellano, and Anna~Maria Fanelli. Meta-data: {C}haracterization of input features for meta-learning, pages 457 -- 468, 2005.</ref> || min,max,$\mu$,$\sigma$
 
|-
 
|-
| Uncertainty coeff. || $\frac{MI(\texttt{C},\texttt{X})}{H(\texttt{C})}$ || Feature importance \citep{Agresti:2002p7509} || min,max,$\mu$,$\sigma$
+
| Mutual inform. || $MI(\texttt{C},\texttt{X})$ || Feature importance || min,max,$\mu$,$\sigma$
 
|-
 
|-
| Equiv. nr. feats || $\frac{H(C)}{\overline{MI(C,X)}}$ || Intrinsic dimensionality \citep{Michie1994} ||
+
| Uncertainty coeff. || $\frac{MI(\texttt{C},\texttt{X})}{H(\texttt{C})}$ || <ref>Feature importance A. Agresti. Categorical Data Analysis. Wiley Interscience, 2002.</ref> || min,max,$\mu$,$\sigma$
 
|-
 
|-
| Noise-signal ratio || $\frac{\overline{H(X)}-\overline{MI(C,X)}}{\overline{MI(C,X)}}$ || Noisiness of data \citep{Michie1994} ||
+
| Equiv. nr. feats || $\frac{H(C)}{\overline{MI(C,X)}}$ || Intrinsic dimensionality ||
 
|-
 
|-
| colspan="4" align="center" | '''complexity'''
+
| Noise-signal ratio || $\frac{\overline{H(X)}-\overline{MI(C,X)}}{\overline{MI(C,X)}}$ || Noisiness of data ||
 
|-
 
|-
| Fisher's discrimin. || $\frac{(\mu_{c1}-\mu_{c2})^{2}}{\sigma_{c1}^{2}-\sigma_{c2}^{2}}$ || Separability classes $c_{1},c_{2}$ \citep{Ho:2002} || See \citet{}{Ho:2002}
+
| colspan="4" align="center" | '''сложностные'''
 
|-
 
|-
| Volume of overlap || || Class distribution overlap \citep{Ho:2002} || See \citet{Ho:2002}
+
| Fisher's discrimin. || $\frac{(\mu_{c1}-\mu_{c2})^{2}}{\sigma_{c1}^{2}-\sigma_{c2}^{2}}$ || Separability classes $c_{1},c_{2}$ ||
 
|-
 
|-
| Concept variation || || Task complexity \citep{Vilalta:2002p5805} || See \citet{Vilalta:1999p5745}
+
| Volume of overlap || || Class distribution overlap <ref>Tin Kam Ho and Mitra Basu. Complexity measures of supervised classification problems. Pattern Analysis and Machine Intellig, 2002.</ref> ||  
 
|-
 
|-
| Data consistency || || Data quality \citep{Kopf:2002p5864} || See \citet{Kopf:2002p5864}
+
| Concept variation || || Task complexity <ref>R. Vilalta. Understanding accuracy performance through concept characterization and algorithm analysis. ICML Workshop on Recent Advances in Meta-Learning and Future Work, 1999.</ref> ||
 
|-
 
|-
| colspan="4" align="center" | '''model-based'''
+
| Data consistency || || Data quality <ref>C K\ddot{o}pf and I Iglezakis. Combination of task description strategies and case base properties for meta-learning, 2002.</ref> ||
 
|-
 
|-
| Nr nodes, leaves || <tex>|\eta|,|\psi|</tex> || Concept complexity \citep{Peng:2002p705} || Tree depth
+
| colspan="4" align="center" | '''основанные на модели'''
 +
|-
 +
| # nodes, leaves || <tex>|\eta|,|\psi|</tex> || Concept complexity <ref>Y Peng, P Flach, C Soares, and P Brazdil. Improved dataset characterisation for meta-learning, 2002.</ref> || Tree depth
 
|-
 
|-
| Branch length || || Concept complexity \citep{Peng:2002p705} || min,max,$\mu$,$\sigma$
+
| Branch length || || Concept complexity || min,max,$\mu$,$\sigma$
 
|-
 
|-
| Nodes per feature || <tex>|\eta_{X}|</tex> || Feature importance \citep{Peng:2002p705} || min,max,$\mu$,$\sigma$
+
| Nodes per feature || <tex>|\eta_{X}|</tex> || Feature importance || min,max,$\mu$,$\sigma$
 
|-
 
|-
| Leaves per class || <tex>\frac{|\psi_{c}|}{|\psi|}</tex> ||  Class complexity \citep{Filchenkov2015} || min,max,$\mu$,$\sigma$
+
| Leaves per class || <tex>\frac{|\psi_{c}|}{|\psi|}</tex> ||  Class complexity <ref>Andray Filchenkov and Arseniy Pendryak. Dataset metafeature description for recommending feature selection. In \emph{ISMW FRUCT}, pages 11--18, 2015.</ref> || min,max,$\mu$,$\sigma$
 
|-
 
|-
| Leaves agreement || <tex>\frac{n_{\psi_{i}}}{n}</tex> ||  Class separability \citep{Bensusan2000} || min,max,$\mu$,$\sigma$
+
| Leaves agreement || <tex>\frac{n_{\psi_{i}}}{n}</tex> ||  Class separability <ref>Bernhard Pfahringer, Hilan Bensusan, and Christophe G. Giraud-Carrier. Meta-learning by landmarking various learning algorithms.In \emph{17th International Conference on Machine Learning (ICML), 2000.</ref> || min,max,$\mu$,$\sigma$
 
|-
 
|-
| Information gain || || Feature importance \citep{Bensusan2000} || min,max,$\mu$,$\sigma$, gini
+
| Information gain || || Feature importance || min,max,$\mu$,$\sigma$, gini
 
|-
 
|-
| colspan="4" align="center" | '''landmarks'''
+
| colspan="4" align="center" | '''ориентиры (landmarks)'''
 
|-
 
|-
| Landmarker(1NN) || $P(\theta_{1NN},t_{j})$ || Data sparsity \citep{Pfahringer:2000p553} || See \citet{Pfahringer:2000p553}
+
| Landmarker(1NN) || $P(\theta_{1NN},t_{j})$ || Data sparsity <ref>Bernhard Pfahringer, Hilan Bensusan, and Christophe G. Giraud-Carrier. Meta-learning by landmarking various learning algorithms.In \emph{17th International Conference on Machine Learning (ICML)}, pages 743 -- 750, 2000.</ref> ||  
 
|-
 
|-
| Landmarker(Tree) || $P(\theta_{Tree},t_{j})$ || Data separability \citep{Pfahringer:2000p553} || Stump,RandomTree
+
| Landmarker(Tree) || $P(\theta_{Tree},t_{j})$ || Data separability || Stump,RandomTree
 
|-
 
|-
| Landmarker(Lin) || $P(\theta_{Lin},t_{j})$ || Linear separability \citep{Pfahringer:2000p553} || Lin.Disciminant
+
| Landmarker(Lin) || $P(\theta_{Lin},t_{j})$ || Linear separability || Lin.Discriminant
 
|-
 
|-
| Landmarker(NB) || $P(\theta_{NB},t_{j})$ || Feature independence \citep{Pfahringer:2000p553} || See \citet{Ler:2005p1680}
+
| Landmarker(NB) || $P(\theta_{NB},t_{j})$ || Feature independence || <ref>Daren Ler, Irena Koprinska, and Sanjay Chawla. Utilizing regression-based landmarkers within a meta-learning framework for algorithm selection. \emph{Technical Report 569. University of Sydney}, pages 44--51, 2005.</ref>
 
|-
 
|-
| Relative LM || $P_{a,j} - P_{b,j}$ || Probing performance \citep{Furnkranz:2001p1278} ||
+
| Relative LM || $P_{a,j} - P_{b,j}$ || Probing performance <ref>J F\ddot{u}rnkranz and J Petrak. An evaluation of landmarking variants. \emph{ECML/PKDD 2001 Workshop on Integrating Aspects of Data Mining, Decision Support and Meta-Learning}, pages 57--68, 2001.</ref> ||
 
|-
 
|-
| Subsample LM || $P(\theta_{i},t_{j},s_{t})$ || Probing performance \citep{Soares:2001p708} ||
+
| Subsample LM || $P(\theta_{i},t_{j},s_{t})$ || Probing performance <ref>Taciana AF Gomes, Ricardo BC Prudencio, Carlos Soares, Andre LD Rossi and Andre Carvalho. Combining meta-learning and search techniques to select parameters for support vector machines, 2012.</ref> ||
 
|-
 
|-
 
|}
 
|}
  
Непрерывные фичи $X$ и таргет $Y$ имеют медиану $\mu_{X}$, stdev $\sigma_{X}$, variance $\sigma^{2}_{X}$. Категориальные фичи $\texttt{X}$ и класс $\texttt{C}$ имеют категориальные значения $\pi_{i}$, условные вероятности $\pi_{i|j}$, совместные вероятности $\pi_{i,j}$, предельные вероятности $\pi_{i+}=\sum_{j}\pi_{ij}$, энтропию $H(\texttt{X})=-\sum_{i}\pi_{i+}log_{2}(\pi_{i+})$.
+
 
 +
Непрерывные признаки $X$ и таргет $Y$ имеют медиану $\mu_{X}$, стандартное отклонение $\sigma_{X}$ и дисперсию $\sigma^{2}_{X}$. Категориальные признаки $\texttt{X}$ и класс $\texttt{C}$ имеют категориальные значения $\pi_{i}$, условные вероятности $\pi_{i|j}$, совместные вероятности $\pi_{i,j}$, предельные вероятности $\pi_{i+}=\sum_{j}\pi_{ij}$ и энтропию $H(\texttt{X})=-\sum_{i}\pi_{i+}log_{2}(\pi_{i+})$.
 +
 
 +
Многие мета-признаки вычисляются по одиночным признакам или их комбинации, и должны быть агрегированы через min, max, $\mu$, $\sigma$, квартили или гистограммы.
 +
 
 +
Во время вычисления похожести задач важно нормализовать все мета-признаки, использовать отбор признаков <ref>L Todorovski and S Dzeroski. Experiments in meta-level learning with ILP. Lecture Notes in Computer Science, 1704:98–106, 1999.</ref> или использовать [[уменьшение размерности | уменьшение размерности]] (например, principal component analisys {{---}} [[Метод главных компонент (PCA)| PCA]]).
 +
 
 +
<h2> Ориентиры (англ. landmarks) </h2>
 +
Ориентиры {{---}} один из подходов для описания задач мета-обучения. В отличие от предшественников, использовавших только статистические метрики, ориентиры стараются
 +
определить расположение конкретной задачи мета-обучения в пространстве всех задач обучения, измеряя производительность некоторых простых и эффективных алгоритмов.
 +
Таким образом, можно сказать, что алгоритм обучения сам характеризуют задачу.
 +
 
 +
<h3> Относительные ориентиры </h3>
 +
Первая мера для вычисления "похожести" задач вычисляла попарно разницу в производительности, так же называемую "relative landmarks" $RL_{a,b,j} = P_{a,j} - P_{b,j}$ между двумя конфигурациями $\theta_{a}$ и $\theta_{b}$ на конкретной задаче $t_{j}$.
 +
 
 +
<h3> Линейный дискриминант </h3>
  
Многие мета-фичи вычисляются по одиночным фичам или комбинации фичей, и должны быть агрегированы через min,max,$\mu$,$\sigma$,quartiles или гистограммами [kalousis]
+
Линейный дискриминант (англ. linear discriminant) $P(\theta_{Lin},t_{j})$ можно понимать как группировка и разделение категорий соответствующих конкретным признакам. Линейный дискриминант
 +
обычно ищет линейную комбинацию признаков, которая лучше всего разделит классы. Результат {{---}} линия, плоскость или гиперплоскость, зависит от числа комбинированных признаков.
 +
 
 +
<h3> Наивный Байесовский лэндмарк </h3>
 +
 
 +
Наивный Байесовский лэндмарк $P(\theta_{NB},t_{j})$ <ref>Daren Ler, Irena Koprinska, and Sanjay Chawla. Utilizing regression-based landmarkers within a meta-learning framework for algorithm selection. \emph{Technical Report 569. University of Sydney}, pages 44--51, 2005.</ref> {{---}} вероятностный классификатор, основанный на [[Формула Байеса | теореме Байеса]]. Называется наивным потому что  предполагается, что все атрибуты независимы друг от друга.
 +
 
 +
<h3> 1NN </h3>
 +
Elite 1-nearest neighbor $P(\theta_{1NN},t_{j})$ <ref>Bernhard Pfahringer, Hilan Bensusan, and Christophe G. Giraud-Carrier. Meta-learning by landmarking various learning algorithms.In \emph{17th International Conference on Machine Learning (ICML)}, pages 743 -- 750, 2000.</ref> [[Метрический классификатор и метод ближайших соседей|kNN]] c $k = 1$.
 +
Elite {{---}} вариация основного метода, но в этом случае на вход kNN подается предварительно отобранное множество самых информативных примеров (у них минимлаьная
 +
разница приращения информации (information gain).Помогает установить, является ли задача релевантной, если похожи их атрибуты.
  
Во время вычисления похожести задач важно нормализовать все мета-фичи [bardnet], использовать feature selection [todorovski] или использовать dimensionality reduction (PCA, например).
 
  
 
== Примечания ==
 
== Примечания ==
 
<references/>
 
<references/>
  
 +
== См. Также ==
 +
#[[Модель алгоритма и ее выбор|Модель алгоритма и ее выбор]]
 +
== Источники информации ==
 
* https://lilianweng.github.io/lil-log/2018/11/30/meta-learning.html#define-the-meta-learning-problem
 
* https://lilianweng.github.io/lil-log/2018/11/30/meta-learning.html#define-the-meta-learning-problem
 
* https://arxiv.org/pdf/1810.03548.pdf
 
* https://arxiv.org/pdf/1810.03548.pdf
 
* https://www.ml4aad.org/wp-content/uploads/2018/09/chapter2-metalearning.pdf
 
* https://www.ml4aad.org/wp-content/uploads/2018/09/chapter2-metalearning.pdf
 
* https://openreview.net/pdf?id=rJY0-Kcll
 
* https://openreview.net/pdf?id=rJY0-Kcll
 +
* https://www1.maths.leeds.ac.uk/~charles/statlog/whole.pdf
 
* https://www.fruct.org/publications/ainl-fruct/files/Fil.pdf
 
* https://www.fruct.org/publications/ainl-fruct/files/Fil.pdf
* Alexandros Kalousis and Melanie Hilario. Model selection via meta-learning: a comparative study. Intl Journ. on Artificial Intelligence Tools, 10(4):525–554, 2001.
+
 
* R ́emi Bardenet, M ́aty ́as Brendel, Bal ́azs K ́egl, and Michele Sebag. Collaborative hyperparameter tuning. In Proceedings of ICML 2013, pages 199–207, 2013
+
[[Категория: Машинное обучение]]
* L Todorovski and S Dzeroski. Experiments in meta-level learning with ILP. Lecture Notes in Computer Science, 1704:98–106, 1999.
 

Текущая версия на 19:34, 4 сентября 2022

Мета-обучение(англ. Meta-learning) — подход, позволяющий определять наиболее подходящий алгоритм (иногда, вместе с параметрами к нему) для конкретной задачи из портфолио алгоритмов. Основная идея мета-обучения — свести задачу выбора алгоритма к задаче обучения с учителем: задачи описываются мета-признаками. Мета-признак описывает свойство задачи — например, разрежен ли датасет или нет, число категориальных или численных признаков объектов в датасете, число возможных меток, размер датасета и многое другое.

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

Обзор

Модель должна быть обучена на множестве задач и оптимизирована для лучшей производительности на нескольких задачах, включая такие, с которыми модель не сталкивалась ранее. Каждой задаче соответствует множество наборов данных $\mathcal{D}$, каждый из которых содержит и векторы признаков и разметку. Оптимальные параметры модели:

\begin{aligned} \theta^* = \arg\min_\theta \mathbb{E}_{\mathcal{D}\sim p(\mathcal{D})} [\mathcal{L}_\theta(\mathcal{D})] \end{aligned}

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

Ограничения — Теорема о том, что бесплатного завтрака не бывает(англ. No Free Lunch Theorem, сокр. NFL) theorem[1][2] , доказанная в 1996 году.

Теорема (No free Lunch Theorem):
Пусть [math]P(d_{m}^{y}| f, m, a)[/math] — условная вероятность получения частного решения $d_m$ после $m$ итераций работы алгоритма $a$ при целевой функции $f$. Для любой пары алгоритмов $a_1$ и $a_2$ имеет место равенство: [math] \\ \begin{aligned} \sum_{f}P(d_{m}^{y}| f, m, a_1) = \sum_{f}P(d_{m}^{y}| f, m, a_2) \end{aligned} [/math]

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

Общая идея мета-обучения: для каждого набора данных $d \in \mathcal{D}$ вычисляется вектор мета-признаков, которые описывают свойства этого набора данных. Ими могут быть: число категориальных или численных признаков объектов в $d$, число возможных меток, размер $d$ и многие другие[3]. Подробнее о конкретных метапризнаках смотреть ниже

Каждый алгоритм запускается на всех наборах данных из $\mathcal{D}$. После этого вычисляется эмпирический риск, на основе которого формируются метки классов. Затем мета-классификатор обучается на полученных результатах. В качестве описания набора данных выступает вектор мета-признаков, а в качестве метки — алгоритм, оказавшийся самым эффективным с точки зрения заранее выбранной меры качества.

Каждый датасет $d \in \mathcal{D}$ содержит пары признаков и меток, $\{(x_i, y_i)\}$, каждая метка принадлежит известному множеству меток $\mathcal{T}$. Датасет $d$ делится на две части: $d=\langle S, B\rangle$, обучающую $S$ и тестовую $B$ выборки. Часто принимается k-shot N-class задача — обучающая выборка содержит $k$ размеченных примеров для каждого из $N$ классов. Скажем, наш классификатор $f_\theta$ с параметром $\theta$ показывает вероятность принадлежности точки из данных к классу $y$ при векторе признаков, $P_\theta(y|x)$. Оптимальные параметры должны максимизировать вероятность получения верных меток среди нескольких обучающих выборок $B⊂\mathcal{D}$:

\begin{aligned} \theta^* &= {\arg\max}_{\theta} \mathbb{E}_{(\mathbf{x}, y)\in \mathcal{D}}[P_\theta(y \vert \mathbf{x})] & \\ \theta^* &= {\arg\max}_{\theta} \mathbb{E}_{B\subset \mathcal{D}}[\sum_{(\mathbf{x}, y)\in B}P_\theta(y \vert \mathbf{x})] & \\ \end{aligned}

В пристрелочной (few-shot) классификации цель — уменьшить ошибку предсказания на неразмеченных данных. Чтобы его ускорить, сделаем следующее:

  1. Возьмем подмножество меток, $T\subset\mathcal{T}$
  2. Возьмем обучающее множество $S^T⊂D$ и обучающую выборку $B^T⊂D$. Оба содержат только данные с метками из подмножества с пункта 1: $L, y \in L, \forall (x, y) \in S^T, B^T$
  3. Множество $S^T$ подается на вход модели
  4. Конечная оптимизация использует множество $B^T$, чтобы посчитать функцию потерь и обновить параметры модели через обратное распространение, так же, как это делается в обучении с учителем.

\begin{aligned} \theta = \arg\max_\theta \color{red}{\mathbb{E}_{T \sim \mathcal{T}}}[ \mathbb{E}_{\color{red}{S \sim T,} B \color{red}{\sim T}} [\sum_{(x, y) \in B} P_\theta(y \vert \mathbf{x} \color{red}{, S})]] \end{aligned} Красным цветом выделена разница между обучением с учителем и подходом мета-обучения.

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

Оптимизации методов Мета-обучения

LSTM-meta-learner

Оптимизационный алгоритм может быть явно смоделирован. Рави и Ларошель [4] это и сделали и назвали его "meta-learner". Цель meta-learner'а — эффективно обновлять свои параметры используя небольшую обучающую выборку так, чтобы learner мог быстро адаптироваться к новым задачам.

Пусть модель ученика будет $M_\theta$, параметризованной $\theta$, и meta-learner как $R_\theta$ с параметром $\theta$, и функция потерь $\mathcal{L}$.

Обновление параметров learner'a во время $t$ со скоростью обучения $\alpha_t$ (шаг градиентного спуска):

\begin{aligned} \theta_t = \theta_{t-1} - \alpha_t \nabla_{\theta_{t-1}}\mathcal{L}_t \end{aligned}

Обновление памяти ячейки LSTM выглядит так:

\begin{aligned} c_t = f_t \odot c_{t-1} + i_t \odot \tilde{c}_t = \theta_{t-1} - \alpha_t\nabla_{\theta_{t-1}}\mathcal{L}_t \end{aligned}

$c_t$ — параметры сети $\theta_t$, $\tilde{c}_t = -\nabla_{\theta_{t-1}}\mathcal{L}_t$ при $f_t$ = 1.

$f_t$ = 1, $\tilde{c}_t = -\nabla_{\theta_{t-1}}\mathcal{L}_t$ - не оптимальные значения, их изменение может оказаться полезным, если вы попали в неудачный локальный минимум.

\begin{aligned} f_t &= \sigma(\mathbf{W}_f \cdot [\nabla_{\theta_{t-1}}\mathcal{L}_t, \mathcal{L}_t, \theta_{t-1}, f_{t-1}] + \mathbf{b}_f) & \\ i_t &= \sigma(\mathbf{W}_i \cdot [\nabla_{\theta_{t-1}}\mathcal{L}_t, \mathcal{L}_t, \theta_{t-1}, i_{t-1}] + \mathbf{b}_i) & \\ \tilde{\theta}_t &= -\nabla_{\theta_{t-1}}\mathcal{L}_t & \\ \theta_t &= f_t \odot \theta_{t-1} + i_t \odot \tilde{\theta}_t & \\ \end{aligned} $f_t$ — как сильно мы забываем старые значения параметров на шаге $t$, $i_t$ — рейт обучения на шаге $t$.

REPTILE

Reptile — относительно простой алгоритм мета-обучения, похожий на MAML, например, тем, что оба используют мета-оптимизацию через градиентный спуск и оба не чувствительны к модели.

  1. Случайным образом разбиваем задачук на подмножества
  2. тренируемся на ней несколькими шагами градиентного спуска
  3. сдвигаем веса модели к новым параметрам.

$\text{SGD}(\mathcal{L}_{\tau_i}, \theta, k)$ выполняет стохастический градиентный спуск на $k$ шагов c функцией потерь $\mathcal{L}_{\tau_i}$, начиная с параметра $\theta$ и возвращает конечный вектор параметров. Градиент reptile определяется как $(\theta - W)/\alpha$, где $\alpha$ — размер шага, используемый функцией $SGD$.

 // Алгоритм REPTILE
 Initialize $\theta$
 for $iteration = 1, 2,...$ do
   Sample tasks $\tau_1, \tau_2, ..., \tau_n$
   for $i = 1, 2, ..., n$ do
     Compute $W_i = \text{SGD}(\mathcal{L}_{\tau_i}, \theta, k)$
   end for
   Update $\theta \leftarrow \theta + \beta 1/n \sum (W_i - \theta)$
 end for

Определение множества конфигураций

Предшествующие вычисления могут быть также использованы для изучения пространства более успешных конфигураций $\theta^{\star}$. Более подходящие под задачу конфигурации могут серьезно ускорить поиск оптимальных моделей, это важно при ограниченных вычислительных ресурсах.

Альтернативный подход сперва узнать оптимальные гиперпараметры, а потом через приращение производительности определить важность каждого из гиперпараметров. Это и было сделано в лаборатории OpenML, где провели около 500 000 экспериментов на 6 алгоритмах, использовав при этом 38 датасетах. Стандартные значения изучались вместе для всех гиперпараметров алгоритма посредством обучения суррогатных моделей на большом числе задач. После того, как уже проверены многие варианты конфигураций, выбирается такая, которая минимизирует средний риск для всех задач, и становится стандартной. Далее определяется важность каждого из гиперпараметров. Чем больше меняется приращение производительности, тем более важный гиперпараметр мы изменяем.

Если мы хотим предоставить рекомендации для конкретной задачи $t_{new}$, нам нужна дополнительная информация о том, насколько $t_{new}$ похожа на предыдущие задачи $t_j$. Первый способ — посчитать число рекомендованных конфигураций для $t_{new}$,получая новое докозательство $\mathbf{P}_{new}$. Если позже мы будем наблюдать, что вычисления $P_{i,new}$ соответствуют $P_{i, j}$, то $t_{j}$ и $t_{new}$ могут быть очень похожими. Мы можем применить это знания для обучения meta-learner'a который предсказывает множество рекомендуемых конфигураций $\Theta^{*}_{new}$ for $t_{new}$. Более того, можно пойти дальше и добавить $\Theta^{*}_{new}$ в $P_{new$ и перейти к следующей итерации и выяснять какие еще задачи схожи друг с другом.

Суррогатные модели

Более гибкий способ передать информацию — построить суррогатную модель $s_{j}(\theta_{i}) = P_{i,j}$ для всех предшествующих задач $t_{j}$, обученную с использованием всех доступных $\mathbf{P}$. Можно определить "похожесть" задач в терминах ошибок между $s_{j}(\theta_{i})$ и $P_{i,new}$: если суррогатная модель для $t_{j}$ может генерировать точные предсказания для $t_{new}$, тогда такие задачи весьма похожи. Обычно это делается в комбинации с Байесовской оптимизацией для определения следующей $\theta_{i}$.

Так же можно обучать суррогатные модели на Гауссовских процессах (GP) для каждой предыдущей задачи и еще одну для $t_{new}$ и объединить их во взвешенную и нормализованную сумму, с медианой $\mu$ определенной как взвешанная сумма $\mu_{j}$ полученных из задач $t_{j}$. Веса $\mu_{j}$ считаются методом Надарая-Ватсона[5], где каждая задача представлена вектором относительных ориентиров (англ. relative landmarks) или ядром Епанечникова[6], используется для определения похожести между векторами относительных ориентиров для $t_{j}$ и $t_{new}$. Чем больше $t_{j}$ похожа на $t_{new}$, тем больше получится вес $s_{j}$, увеличивающий влияние суррогатной модели для $t_{j}$.

Суррогатные модели обучаются только на $P_{i, new}$, а следующий $\theta_{i}$ получается путем нахождения средневзвешенного expected improvement $P_{i, new}$ и предсказанных улучшений на всех предшествующих $P_{i, j}$. Веса предшествующих задач могут быть переопределены через точность суррогатной модели или через относительных ориентиров. Вес ожидаемого улучшения (expected improvement) постепенно возрастает с каждой итерацией (с увеличением собранного эвиденса $P_{i, new}$).

Обучение на свойствах задачи (learning on task properties)

Каждая задача $t_{j} \in T$ может быть описана вектором $m(t_j) = (m_{j,1}, ...,m_{j,K})$ из $K$ мета-признаков $m_{j, k} \in M$,где $M$ — множество мета-признаков. Можно определить меру "похожести" задач, основанную, например, на Евклидовом расстоянии между $m(t_i)$ и $m(t_j)$, тогда можно будет использовать информацию из наиболее похожей задачи на новую задачу $t_{new}$. Более того, используя предшествующие вычисления $\textbf{P}$ можно обучить meta-learner'a $L$ предсказывать производительность $P_{i, new}$ конфигураций $\theta_{i}$ на новых задачах $t_{new}$.

$L: \Theta \times M \rightarrow \textbf{P}$

В таблице ниже представлен обзор наиболее используемых мета-признаков.

мета-признаки
Название Формула Объяснение Варианты
простые
instances $n$ Speed, Scalability[7] $p/n$, $log(n)$, log(n/p)
features $p$ Curse of dimensionality $log(p)$, % categorical
classes $c$ Complexity, imbalance ratio min/maj class
Percent of missing values $m$ Imputation effects [8]  % missing
outliers $o$ Data noisiness [9] $o/n$
статистические
Skewness $\frac{E(X-\mu_{X})^{3}}{\sigma_{X}^{3}}$ Feature normality min,max,$\mu$,$\sigma$,$q_{1},q_{3}$
Kurtosis $\frac{E(X-\mu_{X})^{4}}{\sigma_{X}^{4}}$ Feature normality min,max,$\mu$,$\sigma$,$q_{1},q_{3}$
Correlation $\rho_{X_{1}X_{2}}$ Feature interdependence min,max,$\mu$,$\sigma$,$\rho_{XY}$
Covariance $cov_{X_{1}X_{2}}$ Feature interdependence min,max,$\mu$,$\sigma$,$cov_{XY}$
Concentration $\tau_{X_{1}X_{2}}$ Feature interdependence [10] min,max,$\mu$,$\sigma$,$\tau_{XY}$
Sparsity sparsity(X) Degree of discreteness [11] min,max,$\mu$,$\sigma$
Gravity gravity(X) Inter-class dispersion [12]
ANOVA p-value $p_{val_{\texttt{X}_{1}X_{2}}}$ Feature redundancy $p_{val_{XY}}$
Coeff. of variation $\frac{\sigma_{Y}}{\mu_{Y}}$ Variation in target [13]
PCA $\rho_{\lambda_{1}}$ $\sqrt{\frac{\lambda_{1}}{1+\lambda_{1}}}$ Variance in first PC $\frac{\lambda_{1}}{\sum_{i} \lambda_{i}}$
PCA skewness Skewness of first PC PCA kurtosis
PCA 95\% $\frac{dim_{95\% var}}{p}$ Intrinsic dimensionality [14]
Class probability $P(\texttt{C})$ Class distribution min,max,$\mu$,$\sigma$
информационно-теоретические
Class entropy $H(\texttt{C})$ Class imbalance
Norm. entropy $\frac{H(\texttt{X})}{log_{2}n}$ Feature informativeness [15] min,max,$\mu$,$\sigma$
Mutual inform. $MI(\texttt{C},\texttt{X})$ Feature importance min,max,$\mu$,$\sigma$
Uncertainty coeff. $\frac{MI(\texttt{C},\texttt{X})}{H(\texttt{C})}$ [16] min,max,$\mu$,$\sigma$
Equiv. nr. feats $\frac{H(C)}{\overline{MI(C,X)}}$ Intrinsic dimensionality
Noise-signal ratio $\frac{\overline{H(X)}-\overline{MI(C,X)}}{\overline{MI(C,X)}}$ Noisiness of data
сложностные
Fisher's discrimin. $\frac{(\mu_{c1}-\mu_{c2})^{2}}{\sigma_{c1}^{2}-\sigma_{c2}^{2}}$ Separability classes $c_{1},c_{2}$
Volume of overlap Class distribution overlap [17]
Concept variation Task complexity [18]
Data consistency Data quality [19]
основанные на модели
# nodes, leaves [math]|\eta|,|\psi|[/math] Concept complexity [20] Tree depth
Branch length Concept complexity min,max,$\mu$,$\sigma$
Nodes per feature [math]|\eta_{X}|[/math] Feature importance min,max,$\mu$,$\sigma$
Leaves per class [math]\frac{|\psi_{c}|}{|\psi|}[/math] Class complexity [21] min,max,$\mu$,$\sigma$
Leaves agreement [math]\frac{n_{\psi_{i}}}{n}[/math] Class separability [22] min,max,$\mu$,$\sigma$
Information gain Feature importance min,max,$\mu$,$\sigma$, gini
ориентиры (landmarks)
Landmarker(1NN) $P(\theta_{1NN},t_{j})$ Data sparsity [23]
Landmarker(Tree) $P(\theta_{Tree},t_{j})$ Data separability Stump,RandomTree
Landmarker(Lin) $P(\theta_{Lin},t_{j})$ Linear separability Lin.Discriminant
Landmarker(NB) $P(\theta_{NB},t_{j})$ Feature independence [24]
Relative LM $P_{a,j} - P_{b,j}$ Probing performance [25]
Subsample LM $P(\theta_{i},t_{j},s_{t})$ Probing performance [26]


Непрерывные признаки $X$ и таргет $Y$ имеют медиану $\mu_{X}$, стандартное отклонение $\sigma_{X}$ и дисперсию $\sigma^{2}_{X}$. Категориальные признаки $\texttt{X}$ и класс $\texttt{C}$ имеют категориальные значения $\pi_{i}$, условные вероятности $\pi_{i|j}$, совместные вероятности $\pi_{i,j}$, предельные вероятности $\pi_{i+}=\sum_{j}\pi_{ij}$ и энтропию $H(\texttt{X})=-\sum_{i}\pi_{i+}log_{2}(\pi_{i+})$.

Многие мета-признаки вычисляются по одиночным признакам или их комбинации, и должны быть агрегированы через min, max, $\mu$, $\sigma$, квартили или гистограммы.

Во время вычисления похожести задач важно нормализовать все мета-признаки, использовать отбор признаков [27] или использовать уменьшение размерности (например, principal component analisys — PCA).

Ориентиры (англ. landmarks)

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

Относительные ориентиры

Первая мера для вычисления "похожести" задач вычисляла попарно разницу в производительности, так же называемую "relative landmarks" $RL_{a,b,j} = P_{a,j} - P_{b,j}$ между двумя конфигурациями $\theta_{a}$ и $\theta_{b}$ на конкретной задаче $t_{j}$.

Линейный дискриминант

Линейный дискриминант (англ. linear discriminant) $P(\theta_{Lin},t_{j})$ можно понимать как группировка и разделение категорий соответствующих конкретным признакам. Линейный дискриминант обычно ищет линейную комбинацию признаков, которая лучше всего разделит классы. Результат — линия, плоскость или гиперплоскость, зависит от числа комбинированных признаков.

Наивный Байесовский лэндмарк

Наивный Байесовский лэндмарк $P(\theta_{NB},t_{j})$ [28] — вероятностный классификатор, основанный на теореме Байеса. Называется наивным потому что предполагается, что все атрибуты независимы друг от друга.

1NN

Elite 1-nearest neighbor $P(\theta_{1NN},t_{j})$ [29] kNN c $k = 1$. Elite — вариация основного метода, но в этом случае на вход kNN подается предварительно отобранное множество самых информативных примеров (у них минимлаьная разница приращения информации (information gain).Помогает установить, является ли задача релевантной, если похожи их атрибуты.


Примечания

  1. Wolpert and Macready, 1996
  2. Giraud-Carrier and Provost, 2005
  3. Datasets meta-feature description for recommending feature selection algorithm
  4. Ravie & Larochelle, Optimization as a model for a few-shot learning, 2017
  5. Nadaraya-Watson estimator
  6. V. A. Epanechnikov, Non-Parametric Estimation of a Multivariate Probability Density
  7. Donald Michie, David J. Spiegelhalter, Charles C. Taylor, and John Campbell. Machine Learning, Neural and Statistical Classification, 1994
  8. A. Kalousis. Algorithm Selection via Meta-Learning. PhD thesis, University of Geneva, Department of Computer Science, 2002
  9. Peter J. Rousseeuw and Mia Hubert. Robust statistics for outlier detection. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2011.
  10. Alexandros Kalousis and Melanie Hilario. Model selection via meta-learning: a comparative study.Intl Journ. on Artificial Intelligence Tools, 2001.
  11. Mostafa A. Salama, Aboul~Ella Hassanien, and Kenneth Revett. Employment of neural network and rough set in meta-learning, 2013.
  12. Shawkat Ali and Kate~A. Smith-Miles. On learning algorithm selection for classification. Applied Soft Computing, 2006.
  13. C. Soares, P. Brazdil, and P. Kuba. A meta-learning method to select the kernel width in support vector regression, 2004.
  14. R ́emi Bardenet, M ́aty ́as Brendel, Bal ́azs K ́egl, and Michele Sebag. Collaborative hyperparameter tuning. In Proceedings of ICML 2013, pages 199–207, 2013
  15. Ciro Castiello, Giovanna Castellano, and Anna~Maria Fanelli. Meta-data: {C}haracterization of input features for meta-learning, pages 457 -- 468, 2005.
  16. Feature importance A. Agresti. Categorical Data Analysis. Wiley Interscience, 2002.
  17. Tin Kam Ho and Mitra Basu. Complexity measures of supervised classification problems. Pattern Analysis and Machine Intellig, 2002.
  18. R. Vilalta. Understanding accuracy performance through concept characterization and algorithm analysis. ICML Workshop on Recent Advances in Meta-Learning and Future Work, 1999.
  19. C K\ddot{o}pf and I Iglezakis. Combination of task description strategies and case base properties for meta-learning, 2002.
  20. Y Peng, P Flach, C Soares, and P Brazdil. Improved dataset characterisation for meta-learning, 2002.
  21. Andray Filchenkov and Arseniy Pendryak. Dataset metafeature description for recommending feature selection. In \emph{ISMW FRUCT}, pages 11--18, 2015.
  22. Bernhard Pfahringer, Hilan Bensusan, and Christophe G. Giraud-Carrier. Meta-learning by landmarking various learning algorithms.In \emph{17th International Conference on Machine Learning (ICML), 2000.
  23. Bernhard Pfahringer, Hilan Bensusan, and Christophe G. Giraud-Carrier. Meta-learning by landmarking various learning algorithms.In \emph{17th International Conference on Machine Learning (ICML)}, pages 743 -- 750, 2000.
  24. Daren Ler, Irena Koprinska, and Sanjay Chawla. Utilizing regression-based landmarkers within a meta-learning framework for algorithm selection. \emph{Technical Report 569. University of Sydney}, pages 44--51, 2005.
  25. J F\ddot{u}rnkranz and J Petrak. An evaluation of landmarking variants. \emph{ECML/PKDD 2001 Workshop on Integrating Aspects of Data Mining, Decision Support and Meta-Learning}, pages 57--68, 2001.
  26. Taciana AF Gomes, Ricardo BC Prudencio, Carlos Soares, Andre LD Rossi and Andre Carvalho. Combining meta-learning and search techniques to select parameters for support vector machines, 2012.
  27. L Todorovski and S Dzeroski. Experiments in meta-level learning with ILP. Lecture Notes in Computer Science, 1704:98–106, 1999.
  28. Daren Ler, Irena Koprinska, and Sanjay Chawla. Utilizing regression-based landmarkers within a meta-learning framework for algorithm selection. \emph{Technical Report 569. University of Sydney}, pages 44--51, 2005.
  29. Bernhard Pfahringer, Hilan Bensusan, and Christophe G. Giraud-Carrier. Meta-learning by landmarking various learning algorithms.In \emph{17th International Conference on Machine Learning (ICML)}, pages 743 -- 750, 2000.

См. Также

  1. Модель алгоритма и ее выбор

Источники информации