16
правок
Изменения
Нет описания правки
<b>Мета-обучение</b> {{---}} подход, позволяющий определять оптимальный наиболее подходящий алгоритм (иногда , вместе с параметрами к нему) для конкретной задачииз портфолио алгоритмов. Основная идея мета-обучения {{---}} свести задачу выбора алгоритма к задаче [[Общие понятия#Классификация задач машинного обучения|обучения с учителем]]: задачи описываются мета-признаками. Мета-признак описывает свойство задачи, {{---}} например, разрежен ли датасет или нет, число категориальных или численных признаков объектов объеков в датасете, число возможных меток, размер датасета и многое другое.
От хорошей модели ожидается хорошая высокая адаптируемость или генерализуемость новых задач к новым задачам и окруженийокружениям, с которыми модель не сталкивалась во время на небольшом количестве примеров. Примеры задач мета-обучения.:
<h2>Обзор</h2>
Оптимальные параметры модели:
\begin{aligned}
\theta^* = \arg\min_\theta \mathbb{E}_{\mathcal{D}\sim p(\mathcal{D})} [\mathcal{L}_\theta(\mathcal{D})].
\end{aligned}
Очень похоже на обычную задачу машинного обучения, только один датасет принимается за один сэмпл данных.
\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, y)\in B}P_\theta(y \vert \mathbf{x}a_2)], & \scriptstyle{\text{; trained with mini-batches.}}
\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 функцию потерь и обновить параметры модели через обратное распространение, так же , как это делается в обучении с учителем. Можно представить каждую пару сэмплированного датасета $(S^L,B^L)$ как одну точку. Модель обучается таким образом, чтобы она могла обобщиться до других датасетов.Красным выделен дифф между обучением с учителем и мета-обучением.
\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]] (большие текстовые корпуса), когда доступен только ограниченный набор образцов данных для конкретной задачи. Мета-обучение идет еще на один шаг впередМодель обучается таким образом, вместо того чтобы подстраивать ее под одну задачу, она оптимизирует модель, чтобы она была хороша для многих задачмогла обобщиться до других датасетов.
<h2>Основанные на оптимизации</h2>
Модели [[глубокое обучение | глубокого обучения ]] (англ. <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'a используя небольшой train set небольшую обучающую выборку так, чтобы learner мог быстро адаптироваться к новым задачам.
Пусть модель ученика будет $M_θM_\theta$, параметризованной $θ\theta$, и meta-learner как $R_ΘR_\theta$ с параметром $θ\theta$ , и функция потерь $\mathcal{L}$.
Обновление параметров learner'a во время $t$ c learning rate cо скоростью обучения $\alpha_t$ (шаг градиентного спуска):
\begin{aligned}
\theta_t = \theta_{t-1} - \alpha_t \nabla_{\theta_{t-1}}\mathcal{L}_t,
\end{aligned}
\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), & \scriptstyle{\text{как сильно мы забываем старые значения параметров}}\\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}}\\\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}
<h3>REPTILE</h3>
Reptile {{---}} относительно простой алгоритм мета-обучения, похожий на MAML, например, тем, что оба используют мета-оптимизацию через градиентный спуск и оба не чувствительны к модели.
# сэмплируем задачу;# тренируемся на ней несколькими шагами градиентного спуска;
# сдвигаем веса модели к новым параметрам.
$\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'''
<h2>Определение множества конфигураций</h2>
Предшествующие вычисления могут быть также использованы для изучения пространства более успешных конфигураций $\theta\star$. Более подходящие под задачу конфигурации могут серьезно ускорить поиск оптимальных моделей, это важно при ограниченных вычислительных ресурсах. Альтернативный подход сперва узнать оптимальные гиперпараметры, а потом через приращение производительности определить важность каждого из гиперпараметров. Это и было сделано в лабе OpenML, провели около 500 000 экспериментов на 6 алгоритмах и 38 датасетах. Стандартные значения изучались вместе для всех гиперпараметров алгоритма посредством обучения суррогатных моделей на большом числе задач. После того, как уже проверены многие варианты конфигураций, выбирается такая, которая минимизирует ??? для всех задач, становится стандартной. Далее определяется важность каждого из гиперпараметров. Чем больше меняется приращение производительности, тем более важный гиперпараметр мы изменяемрессурсах.
<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}$.
<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}$.
$L: \Theta \times M \rightarrow \textbf{P},$
В таблице представлен обзор наиболее используемых мета-фичейпризнаков.
{| 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>
== Примечания ==
<references/>
== Источники информации ==
* https://lilianweng.github.io/lil-log/2018/11/30/meta-learning.html#define-the-meta-learning-problem
* https://arxiv.org/pdf/1810.03548.pdf