Редактирование: Мета-обучение

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
<b>Мета-обучение</b> {{---}} подход, позволяющий определять наиболее подходящий алгоритм (иногда, вместе с параметрами к нему) для конкретной задачи из портфолио алгоритмов. Основная идея мета-обучения {{---}} свести задачу выбора алгоритма к задаче [[Общие понятия#Классификация задач машинного обучения|обучения с учителем]]: задачи описываются мета-признаками. Мета-признак описывает свойство задачи {{---}} например, разрежен ли датасет или нет, число категориальных или численных признаков объеков в датасете, число возможных меток, размер датасета и многое другое.
+
<b>Мета-обучение</b> {{---}} подход, позволяющий определять наиболее подходящий алгоритм (иногда, вместе с параметрами к нему) для конкретной задачи из портфолио алгоритмов. Основная идея мета-обучения {{---}} свести задачу выбора алгоритма к задаче [https://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D1%81_%D1%83%D1%87%D0%B8%D1%82%D0%B5%D0%BB%D0%B5%D0%BC обучения с учителем]: задачи описываются мета-признаками. Мета-признак описывает свойство задачи {{---}} например, разрежен ли датасет или нет, число категориальных или численных признаков объеков в датасете, число возможных меток, размер датасета и многое другое.
  
От хорошей модели ожидается высокая адаптируемость к новым задачам и окружениям, на небольшом количестве примеров. Примеры задач мета-обучения:
+
От хорошей модели ожидается высокая адаптируемость к новым задачам и окружениям, с которыми модель не сталкивалась во время обучения.
  
* Классификатор обучали на изображениях собак и велосипедов, давайте дообучим его определять еще и кошек
+
Такими задачами являются:
 +
* Классификатор обучали на изображениях собак и велосипедов, давайте покажем ему кошек и проверим, сможет ли классификатор определить, есть ли на новой картинке кошка
 
* Бот для игр, способный быстро обучиться новой игре
 
* Бот для игр, способный быстро обучиться новой игре
 
* Робот, выполняющий задачу на пригорке во время теста даже если он обучался на ровной поверхности
 
* Робот, выполняющий задачу на пригорке во время теста даже если он обучался на ровной поверхности
 +
 +
Ограничения {{---}} 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> (NFL), доказанная в 1996 году.
 +
Пусть $P(d_{m}^{y}| f, m, a)$ {{---}} условная вероятность получения частного решения $d_m$ после $m$ итераций работы алгоритма $a$ при целевой функции $f$. Для любой пары алгоритмов $a_1$ и $a_2$ иммет место равенство
 +
\begin{aligned}
 +
\sum_{f}P(d_{m}^{y}| f, m, a_1) = \sum_{f}P(d_{m}^{y}| f, m, a_2)
 +
\end{aligned}
 +
 +
Иначе говоря, не существует алгоритма классификации, который лучше всех других на всех возможных входных данных.
  
 
<h2>Обзор</h2>
 
<h2>Обзор</h2>
  
 
Модель должна быть обучена на множестве задач и оптимизирована для лучшей производительности на нескольких задачах, включая такие,
 
Модель должна быть обучена на множестве задач и оптимизирована для лучшей производительности на нескольких задачах, включая такие,
с которыми модель не сталкивалась ранее. Каждой задаче соответствует множество наборов данных $\mathcal{D}$, каждый из которых содержит и векторы признаков и разметку.
+
с которыми модель не сталкивалась ранее. Каждой задаче соответствует датасет $\mathcal{D}$, содержащий и векторы фичей и правильную разметку.
 
Оптимальные параметры модели:
 
Оптимальные параметры модели:
  
Строка 19: Строка 28:
 
Очень похоже на обычную задачу машинного обучения, только один датасет принимается за один сэмпл данных.
 
Очень похоже на обычную задачу машинного обучения, только один датасет принимается за один сэмпл данных.
  
Ограничения {{---}} no free lunch (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 году.
+
Few-shot классификатор конкретизация мета-обучения в области обучения с учителем. Датасет $\mathcal{D}$ делится на две части: $\mathcal{D}=\langle S, B\rangle$,
Пусть $P(d_{m}^{y}| f, m, a)$ {{---}} условная вероятность получения частного решения $d_m$ после $m$ итераций работы алгоритма $a$ при целевой функции $f$. Для любой пары алгоритмов $a_1$ и $a_2$ иммет место равенство
+
обучающую $S$ и тестовую $B$ выборки. Часто принимается k-shot N-class задача - обучающая выборка содержит $k$ размеченных примеров для каждого из $N$ классов.
 +
Датасет $\mathcal{D}$ содержит пары фичей и меток, $\mathcal{D} = \{(\mathbf{x}_i, y_i)\}$ и каждая метка принадлежит известному множеству меток $\mathcal{L}$. Скажем, наш классификатор $f_\theta$ с параметром $\theta$ показывает вероятность принадлежности точки из данных к классу $y$ при векторе фичей $x$, $P_\theta(y|x)$
 +
Оптимальные параметры должны максимизировать вероятность верных меток среди нескольких обучающих выборок $B⊂\mathcal{D}$:
  
 
\begin{aligned}
 
\begin{aligned}
\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}_{(\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})] & \scriptstyle{\text{ <font color=green> // использовали мини-батчи для обучения</font>}}
 
\end{aligned}
 
\end{aligned}
  
Общая идея такая: для каждого набора данных $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>. Каждый алгоритм запускается на всех наборах данных из $\mathcal{D}$. После этого вычисляется эмпирический риск, на основе которого формируются метки классов. Затем мета-классификатор обучается на полученных результатах. В качестве описания набора данных выступает вектор мета-признаков, а в качестве метки — алгоритм, оказавшийся самым эффективным с точки зрения заранее выбранной меры качества.
+
В few-shot классификации цель {{---}} уменьшить ошибку предсказания на неразмеченных данных. Чтобы его ускорить, сделаем следующее:
 
+
# возьмем подмножество меток, $L\subset\mathcal{L}$
Кажддый датасет $d \in \mathcal{D}$ содержит пары признаков и меток, $\{(\mathbf{x}_i, y_i)\}$, каждая метка принадлежит известному множеству меток $\mathcal{T}$.
+
# возьмем обучающее множесто $S^L⊂D$ и обучающую выборку $B^L⊂D$. Оба содержат только данные с метками из подмножества с пункта 1:
Датасет $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}
\theta^* &= {\arg\max}_{\theta} \mathbb{E}_{(\mathbf{x}, y)\in \mathcal{D}}[P_\theta(y \vert \mathbf{x})] & \\
+
L, y \in L, \forall (x, y) \in S^L, B^L
\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}
  
В пристрелочной (few-shot) классификации цель {{---}} уменьшить ошибку предсказания на неразмеченных данных. Чтобы его ускорить, сделаем следующее:
+
# Множество $S^L$ подается на вход модели
# возьмем подмножество меток, $T\subset\mathcal{T}$
+
# Конечная оптимизация использует множество $B^L$ чтобы посчитать loss и обновить параметры модели через обратное распространение, так же, как это делается в обучении с учителем, разница между ними выделена красным цветом в формуле.
# возьмем обучающее множесто $S^T⊂D$ и обучающую выборку $B^T⊂D$. Оба содержат только данные с метками из подмножества с пункта 1: $L, y \in L, \forall (x, y) \in S^T, B^T$
 
# Множество $S^T$ подается на вход модели
 
# Конечная оптимизация использует множество $B^T$, чтобы посчитать функцию потерь и обновить параметры модели через обратное распространение, так же, как это делается в обучении с учителем.
 
  
 
\begin{aligned}
 
\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})]]
+
\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}{]}
 
\end{aligned}
 
\end{aligned}
Красным цветом выделена разница между обучением с учителем и подходом мета-обучения.
 
  
Идея в некоторой степени аналогична использованию предварительно обученной модели в классификации изображений (ImageNet) или в [[обработка естественного языка | NLP]] (большие текстовые корпуса),
+
Идея в некоторой степени аналогична использованию предварительно обученной модели в классификации изображений (ImageNet) или в NLP[LINK] (большие текстовые корпуса), когда доступен только ограниченный набор образцов данных для конкретной задачи. Модель обучается таким образом, чтобы она могла обобщиться до других датасетов.
когда доступен только ограниченный набор образцов данных для конкретной задачи. Модель обучается таким образом, чтобы она могла обобщиться до других датасетов.
 
  
 
<h2>Основанные на оптимизации</h2>
 
<h2>Основанные на оптимизации</h2>
  
Модели [[глубокое обучение | глубокого обучения]] (англ. <i>deep learning</i>) обучаются через обратное распространение градиентов.
+
Модели глубокого обучения (англ. \emphdeep learning) обучаются через обратное распространение градиентов. [дичь] Тем не менее, оптимизация, основанная на градиентах не разрабатывалась для работы с небольшим количеством обучающих семплов, и не сходится за малое число оптимизационных шагов. Подход в мета-обучении, основанный на оптимизации как раз про это.[/дичь]
  
 
<h3>LSTM-meta-learner</h3>
 
<h3>LSTM-meta-learner</h3>
Оптимизационный алгоритм может быть явно смоделирован. Рави и Ларошель <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 мог быстро адаптироваться к новым задачам.
+
Оптимизационный алгоритм может быть явно смоделирован. Ravi & Larochelle (2017) это и сделали и назвали его "meta-learner". Цель meta-learner'а - эффективно обновлять свои параметры используя небольшую обучающую выборку так, чтобы learner мог быстро адаптироваться к новым задачам.
  
 
Пусть модель ученика будет $M_\theta$, параметризованной $\theta$, и meta-learner как $R_\theta$ с параметром $\theta$, и функция потерь $\mathcal{L}$.
 
Пусть модель ученика будет $M_\theta$, параметризованной $\theta$, и meta-learner как $R_\theta$ с параметром $\theta$, и функция потерь $\mathcal{L}$.
Строка 78: Строка 81:
  
 
\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) & \\
+
  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{ <font color=green> // как сильно мы забываем старые значения параметров</font>}}\\
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) & \\
+
  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{ <font color=green> // рейт обучения на шаге t</font>}}\\
\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>
Строка 93: Строка 95:
 
# сдвигаем веса модели к новым параметрам.
 
# сдвигаем веса модели к новым параметрам.
  
$\text{SGD}(\mathcal{L}_{\tau_i}, \theta, k)$ выполняет стохастический градиентный спуск на $k$ шагов c функцией потерь $\mathcal{L}_{\tau_i}$, начиная с параметра $\theta$ и возвращает конечный вектор параметров. Градиент reptile определяется как $(\theta - W)/\alpha$, где $\alpha$ {{---}} размер шага, используемый функцией $SGD$.
+
$\text{SGD}(\mathcal{L}_{\tau_i}, \theta, k)$ выполняет стохастический градиентный спуск на $k$ шагов на лоссе $\mathcal{L}_{\tau_i}$, начиная с параметра $\theta$ и возвращает конечный вектор параметров. Градиент reptile определяется как $(\theta - W)/\alpha$, где $\alpha$ {{---}} размер шага, используемый функцией $SGD$.
  
   <font color=green>// Алгоритм REPTILE</font>
+
   <font color=green>// Algorithm REPTILE, batched version</font>
 
   Initialize $\theta$
 
   Initialize $\theta$
 
   '''for''' $iteration = 1, 2,...$ '''do'''
 
   '''for''' $iteration = 1, 2,...$ '''do'''
Строка 112: Строка 114:
 
Если мы хотим предоставить рекомендации для конкретной задачи $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$, yielding новый эвиденс $\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$ определенной как взвшенная
+
Так же можно обучать суррогатные модели на Гауссовских процессах (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}$.
сумма $\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>, используется для определения похожести между векторами relative landmarks для $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}$.
Строка 133: Строка 135:
  
 
{| class="wikitable"
 
{| class="wikitable"
|+ мета-признаки
+
|+ Meta-feature
 
|-
 
|-
! '''Название''' !! '''Формула''' !! '''Объяснение''' !! '''Варианты'''
+
! '''Name''' !! '''Formula''' !! '''Rationale''' !! '''Variants'''
 
|-
 
|-
| colspan="4" align="center" | '''простые'''
+
| colspan="4" align="center" | '''simple'''
 
|-
 
|-
| # 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 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)
 
|-
 
|-
| # features || $p$ || Curse of dimensionality || $log(p)$, % categorical
+
| Nr features || $p$ || Curse of dimensionality || $log(p)$, % categorical
 
|-
 
|-
| # classes || $c$ || Complexity, imbalance || ratio min/maj class
+
| Nr classes || $c$ || Complexity, imbalance || ratio min/maj class
 
|-
 
|-
| # 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
+
| Nr 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
 
|-
 
|-
| # 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$
+
| Nr 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$
 
|-
 
|-
| colspan="4" align="center" | '''статистические'''
+
| colspan="4" align="center" | '''statistical'''
 
|-
 
|-
 
| Skewness || $\frac{E(X-\mu_{X})^{3}}{\sigma_{X}^{3}}$ || Feature normality || 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}$
Строка 165: Строка 167:
 
| 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> ||
 
| 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> ||
 
|-
 
|-
| ANOVA p-value || $p_{val_{\texttt{X}_{1}X_{2}}}$ || Feature redundancy || $p_{val_{XY}}$
+
| ANOVA p-value || $p_{val_{\texttt{X}_{1}X_{2}}}$ || Feature redundancy || $p_{val_{XY}}$\citep{soares+04}
 
|-
 
|-
 
| 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> ||
 
| 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 $\rho_{\lambda_{1}}$ || $\sqrt{\frac{\lambda_{1}}{1+\lambda_{1}}}$ || Variance in first PC || $\frac{\lambda_{1}}{\sum_{i} \lambda_{i}}$
+
| PCA $\rho_{\lambda_{1}}$ || $\sqrt{\frac{\lambda_{1}}{1+\lambda_{1}}}$ || Variance in first PC || $\frac{\lambda_{1}}{\sum_{i} \lambda_{i}}$\citep{<re[https://www1.maths.leeds.ac.uk~charlesstatlogwhole.pdf]</ref>f>}
 
|-
 
|-
| PCA skewness || || Skewness of first PC || PCA kurtosis
+
| PCA skewness || || Skewness of first PC \citep{feurer2014using} || PCA kurtosis
 
|-
 
|-
 
| 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> ||
 
| 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> ||
Строка 177: Строка 179:
 
| Class probability || $P(\texttt{C})$ || Class distribution || min,max,$\mu$,$\sigma$
 
| Class probability || $P(\texttt{C})$ || Class distribution || min,max,$\mu$,$\sigma$
 
|-
 
|-
| colspan="4" align="center" | '''информационно-теоретические'''
+
| colspan="4" align="center" | '''informational-theoretic'''
 
|-
 
|-
 
| Class entropy  || $H(\texttt{C})$ || Class imbalance ||
 
| Class entropy  || $H(\texttt{C})$ || Class imbalance ||
Строка 191: Строка 193:
 
| Noise-signal ratio || $\frac{\overline{H(X)}-\overline{MI(C,X)}}{\overline{MI(C,X)}}$ || Noisiness of data ||
 
| Noise-signal ratio || $\frac{\overline{H(X)}-\overline{MI(C,X)}}{\overline{MI(C,X)}}$ || Noisiness of data ||
 
|-
 
|-
| colspan="4" align="center" | '''сложностные'''
+
| colspan="4" align="center" | '''complexity'''
 
|-
 
|-
 
| Fisher's discrimin. || $\frac{(\mu_{c1}-\mu_{c2})^{2}}{\sigma_{c1}^{2}-\sigma_{c2}^{2}}$ || Separability classes $c_{1},c_{2}$ ||  
 
| Fisher's discrimin. || $\frac{(\mu_{c1}-\mu_{c2})^{2}}{\sigma_{c1}^{2}-\sigma_{c2}^{2}}$ || Separability classes $c_{1},c_{2}$ ||  
Строка 199: Строка 201:
 
| 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> ||
 
| 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> ||
 
|-
 
|-
| 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> ||
+
| Data consistency || || Data quality <ref>C K{\"o}pf and I Iglezakis. Combination of task description strategies and case base properties for meta-learning, 2002.</ref> ||
 
|-
 
|-
| colspan="4" align="center" | '''основанные на модели'''
+
| colspan="4" align="center" | '''model-based'''
 
|-  
 
|-  
| # 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
+
| Nr 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 || min,max,$\mu$,$\sigma$
 
| Branch length || || Concept complexity || min,max,$\mu$,$\sigma$
Строка 215: Строка 217:
 
| Information gain || || Feature importance || 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 <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(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> || See \citet{Pfahringer:2000p553}
 
|-
 
|-
 
| Landmarker(Tree) || $P(\theta_{Tree},t_{j})$ || Data separability || Stump,RandomTree
 
| Landmarker(Tree) || $P(\theta_{Tree},t_{j})$ || Data separability || Stump,RandomTree
 
|-
 
|-
| Landmarker(Lin) || $P(\theta_{Lin},t_{j})$ || Linear separability || Lin.Discriminant
+
| Landmarker(Lin) || $P(\theta_{Lin},t_{j})$ || Linear separability || Lin.Disciminant
 
|-
 
|-
| 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>
+
| Landmarker(NB) || $P(\theta_{NB},t_{j})$ || Feature independence || See <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 <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> ||
+
| Relative LM || $P_{a,j} - P_{b,j}$ || Probing performance <ref>J F{\"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 <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> ||
+
| Subsample LM || $P(\theta_{i},t_{j},s_{t})$ || Probing performance <ref>Taciana AF Gomes, Ricardo BC Prud{\^e}ncio, Carlos Soares, Andr{\'e} LD Rossi and Andr{\'e} Carvalho. Combining meta-learning and search techniques to select parameters for support vector machines, 2012.</ref> ||
 
|-
 
|-
 
|}
 
|}
 
 
Непрерывные признаки $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> Лэндмарки </h2>
 
Лэндмарки {{---}} один из подходов для описания задач мета-обучения. В отличие от предшетсвенников, использовавших только статистические метрики, лэндмарки стараются
 
определить расположение конкретной задачи мета-обучения в пространстве всех задач обучения, измеряя производительность некоторых простых и эффективных алгоритмов.
 
Таким образом, можно сказать, что алгоритм обучения сам характеризуют задачу.
 
 
<h3> Относительные лэндмарки </h3>
 
Первая мера для вычисления "похожести" задач вычисляла попарно разницу в производительности, так же называемую "relative landmarks" $RL_{a,b,j} = P_{a,j} - P_{b,j}$ между двумя конфигурациями $\theta_{a}$ и $\theta_{b}$ на конкретной задаче $t_{j}$.
 
 
<h3> Линейный дискриминант </h3>
 
 
Линейный дискриминант (англ. 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> {{---}} вероятностный классификатор, основанный на [[Формула Байеса | теореме Байеса]]. Называется наивным потому что  предполагается, что все атрибуты независимы друг от друга.
+
Непрерывные фичи $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+})$.
  
<h3> 1NN </h3>
+
Многие мета-фичи вычисляются по одиночным фичам или комбинации фичей, и должны быть агрегированы через min,max,$\mu$,$\sigma$,quartiles или гистограммами.
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], использовать отбор признаков <ref>L Todorovski and S Dzeroski. Experiments in meta-level learning with ILP. Lecture Notes in Computer Science, 1704:98–106, 1999.</ref> или использовать уменьшение размерности (PCA, например).
  
 
== Примечания ==
 
== Примечания ==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: