16
правок
Изменения
Нет описания правки
<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 [Общие понятия#Классификация задач машинного обучения|обучения с учителем]]: задачи описываются мета-признаками. Мета-признак описывает свойство задачи {{---}} например, разрежен ли датасет или нет, число категориальных или численных признаков объеков в датасете, число возможных меток, размер датасета и многое другое.
От хорошей модели ожидается высокая адаптируемость к новым задачам и окружениям, с которыми модель не сталкивалась во время на небольшом количестве примеров. Примеры задач мета-обучения.:
* Бот для игр, способный быстро обучиться новой игре
* Робот, выполняющий задачу на пригорке во время теста даже если он обучался на ровной поверхности
<h2>Обзор</h2>
Модель должна быть обучена на множестве задач и оптимизирована для лучшей производительности на нескольких задачах, включая такие,
с которыми модель не сталкивалась ранее. Каждой задаче соответствует множество наборов данных $\mathcal{D}$, каждый из которых содержит и векторы фичей признаков и разметку.
Оптимальные параметры модели:
Очень похоже на обычную задачу машинного обучения, только один датасет принимается за один сэмпл данных.
Ограничения {{---}} 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 году.
Пусть $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}
Общая идея такая: для каждого набора данных $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}$. После этого вычисляется эмпирический риск, на основе которого формируются метки классов. Затем мета-классификатор обучается на полученных результатах. В качестве описания набора данных выступает вектор мета-признаков, а в качестве метки — алгоритм, оказавшийся самым эффективным с точки зрения заранее выбранной меры качества.
Кажддый датасет $d \in \mathcal{D}$ содержит пары фичей признаков и меток, $\{(\mathbf{x}_i, y_i)\}$, каждая метка принадлежит известному множеству меток $\mathcal{LT}$.Датасет $d$ делится на две части: $d=\langle S, B\rangle$, обучающую $S$ и тестовую $B$ выборки. Часто принимается k-shot N-class задача {{- --}} обучающая выборка содержит $k$ размеченных примеров для каждого из $N$ классов.Скажем, наш классификатор $f_\theta$ с параметром $\theta$ показывает вероятность принадлежности точки из данных к классу $y$ при векторе фичей $x$признакопризнаков, $P_\theta(y|x)$.
Оптимальные параметры должны максимизировать вероятность получения верных меток среди нескольких обучающих выборок $B⊂\mathcal{D}$:
В пристрелочной (few-shot) классификации цель {{---}} уменьшить ошибку предсказания на неразмеченных данных. Чтобы его ускорить, сделаем следующее:
# возьмем подмножество меток, $LT\subset\mathcal{LT}$# возьмем обучающее множесто $S^L⊂DT⊂D$ и обучающую выборку $B^L⊂DT⊂D$. Оба содержат только данные с метками из подмножества с пункта 1: $L, y \in L, \forall (x, y) \in S^LT, B^LT$# Множество $S^LT$ подается на вход модели# Конечная оптимизация использует множество $B^LT$ , чтобы посчитать loss функцию потерь и обновить параметры модели через обратное распространение, так же, как это делается в обучении с учителем.
\begin{aligned}
\theta = \arg\max_\theta \color{red}{E_\mathbb{E}_{LT \subsetsim \mathcal{LT}}}[\mathbb{E} E__{\color{red}{S^L \subset\mathcal{D}sim T, }B^L \subsetcolor{red}{\mathcal{Dsim T}} [\sum_{(x, y)\in B^L} P_\theta(y \vert \mathbf{x, y} \color{red}{, S^L})] \color{red}{]}
\end{aligned}
Красным цветом выделена разница между обучением с учителем и подходом мета-обучения.
<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 мог быстро адаптироваться к новым задачам.
Пусть модель ученика будет $M_\theta$, параметризованной $\theta$, и meta-learner как $R_\theta$ с параметром $\theta$, и функция потерь $\mathcal{L}$.
# сдвигаем веса модели к новым параметрам.
$\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>
Initialize $\theta$
'''for''' $iteration = 1, 2,...$ '''do'''
Если мы хотим предоставить рекомендации для конкретной задачи $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$ и перейти к следующей итерации и выяснять какие еще задачи схожи друг с другом.
<h3>Суррогатные модели</h3>
{| class="wikitable"
|+ Metaмета-featureпризнаки
|-
! '''NameНазвание''' !! '''FormulaФормула''' !! '''RationaleОбъяснение''' !! '''VariantsВарианты'''
|-
| colspan="4" align="center" | '''simpleпростые'''
|-
| 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)
|-
| Nr # features || $p$ || Curse of dimensionality || $log(p)$, % categorical
|-
| Nr # classes || $c$ || Complexity, imbalance || ratio min/maj class
|-
| Nr # 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 # 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" | '''statisticalстатистические'''
|-
| Skewness || $\frac{E(X-\mu_{X})^{3}}{\sigma_{X}^{3}}$ || Feature normality || min,max,$\mu$,$\sigma$,$q_{1},q_{3}$
| 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}}$\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> ||
|-
| 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 \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> ||
| Class probability || $P(\texttt{C})$ || Class distribution || min,max,$\mu$,$\sigma$
|-
| colspan="4" align="center" | '''informationalинформационно-theoreticтеоретические'''
|-
| Class entropy || $H(\texttt{C})$ || Class imbalance ||
| Noise-signal ratio || $\frac{\overline{H(X)}-\overline{MI(C,X)}}{\overline{MI(C,X)}}$ || Noisiness of data ||
|-
| 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}$ ||
| 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> ||
|-
| colspan="4" align="center" | '''model-basedоснованные на модели'''
|-
| 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$
| Information gain || || Feature importance || min,max,$\mu$,$\sigma$, gini
|-
| 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> || See \citet{Pfahringer:2000p553}
|-
| Landmarker(Tree) || $P(\theta_{Tree},t_{j})$ || Data separability || Stump,RandomTree
|-
| Landmarker(Lin) || $P(\theta_{Lin},t_{j})$ || Linear separability || Lin.DisciminantDiscriminant
|-
| 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> ||
|-
| Subsample LM || $P(\theta_{i},t_{j},s_{t})$ || Probing performance <ref>Taciana AF Gomes, Ricardo BC Prud{\^e}ncioPrudencio, Carlos Soares, Andr{\'e} Andre LD Rossi and Andr{\'e} Andre 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>
== Примечания ==
