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}$, содержащий каждый из которых содержит и векторы фичей признаков и правильную разметку.
Оптимальные параметры модели:
Очень похоже на обычную задачу машинного обучения, только один датасет принимается за один сэмпл данных.
\begin{aligned}
\theta^* &= sum_{\arg\maxf}_P(d_{\thetam} \mathbb^{E}_{(\mathbf{xy}| f, m, ya_1)= \in \mathcalsum_{Df}}[P_\thetaP(y \vert \mathbfd_{xm})] &\\\theta^* &= {\arg\max}_{\theta} \mathbb{E}_{B\subset \mathcal{D}}[\sum_{(\mathbf{xy}| f, m, ya_2)\in B}P_\theta(y \vert \mathbf{x})] & \scriptstyle{\text{ <font color=green> // использовали мини-батчи для обучения</font>}}
\end{aligned}
\begin{aligned}
\end{aligned}
В пристрелочной (few-shot) классификации цель {{---}} уменьшить ошибку предсказания на неразмеченных данных. Чтобы его ускорить, сделаем следующее:# возьмем подмножество меток, $T\subset\mathcal{T}$# возьмем обучающее множесто $S^T⊂D$ и обучающую выборку $B^T⊂D$. Оба содержат только данные с метками из подмножества с пункта 1: $L, y \in L, \forall (x, y) \in S^T, B^T$# Множество $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}
Красным цветом выделена разница между обучением с учителем и подходом мета-обучения.
Идея в некоторой степени аналогична использованию предварительно обученной модели в классификации изображений (ImageNet) или в [[обработка естественного языка | NLP[LINK]] (большие текстовые корпуса), когда доступен только ограниченный набор образцов данных для конкретной задачи. Модель обучается таким образом, чтобы она могла обобщиться до других датасетов.
<h2>Основанные на оптимизации</h2>
Модели [[глубокое обучение | глубокого обучения ]] (англ. \emphdeep <i>deep learning</i>) обучаются через обратное распространение градиентов. [дичь] Тем не менее, оптимизация, основанная на градиентах не разрабатывалась для работы с небольшим количеством обучающих семплов, и не сходится за малое число оптимизационных шагов. Подход в мета-обучении, основанный на оптимизации как раз про это.[/дичь]
<h3>LSTM-meta-learner</h3>
Оптимизационный алгоритм может быть явно смоделирован. Ravi Рави и Ларошель <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}$.
\begin{aligned}
\end{aligned}
$f_t$ {{---}} как сильно мы забываем старые значения параметров на шаге $t$, $i_t$ {{---}} рейт обучения на шаге $t$.
<h3>REPTILE</h3>
# сдвигаем веса модели к новым параметрам.
$\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>
Более гибкий способ передать информацию {{---}} построить суррогатную модель $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}$ считаются через методом Надарая-Уотсон<ref>[http://www.maths.manchester.ac.uk/~peterf/MATH38011/NPR%20N-W%20Estimator.pdf Nadaraya-Watson kernel-weighted averageestimator]</ref>, где каждая задача представлена вектором relative landmarks и илиядром Епанечникова<ref>[https://epubs.siam.org/doi/10.1137/1114019 V. A. Epanechnikov quadratic kernel , 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}$.
{| 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>
== Примечания ==