77
правок
Изменения
Нет описания правки
<b>Мета-обучение</b> {{---}} подход, повзоляющий позволяющий определять оптимальный алгоритм (иногда, вместе с параметрами к нему) для конкретной задачи. Основная идея мета-обучения {{---}} свети свести задачу выбора алгоритма к задаче обучения с учителем: задачи описываются мета-фичамипризнаками. Мета-фича признак описывает свойство задачи {{---}} напмример, например, разрежен ли датасет или нет, число категориальных или численных признаков объектов в датасете, число возможных меток, размер датасета и многое другое.
От хорошей модели ожидается хорошая адаптируемость или генерализуемость новых задач и окружений, с которыми модель не сталкивалась во время обучения.
Такими задачами являются:
* Классификатор, тренированный на изображениях собак и велосипедов, после некоторых показанных ему кошек, смог определить, есть ли на новой картинке кошка;* Игровой бот, способный быстро обучиться новой игре;* Робот, выполняющий задачу на пригорке во время теста даже если он тренировался на ровной поверхности.
Ограничения{{- --}} 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>
<h2>Simple viewОбзор</h2>
Хорошая модель мета-обучения должна быть обучена на множестве задач и оптимизирована для лучшей производительности на нескольких задачах,
\begin{aligned}
\theta^* = \arg\min_\theta \mathbb{E}_{\mathcal{D}\sim p(\mathcal{D})} [\mathcal{L}_\theta(\mathcal{D})].
\end{aligned}
Очень похоже на обычную задачу машинного обучения, только один датасет принимается за один сэмпл данных.
Few-shot классификатор {{---}} конкретизация мета-обучения в области обучения с учителем. Датасет $\mathcal{D}$ делится на две части: $\mathcal{D}=\langle S, B\rangle$,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)$
Оптимальные параметры должны максимизировать вероятность верных меток среди нескольких training sets $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})] , & \scriptstyle{\text{; trained with mini-batches.}}
\end{aligned}
# возьмем train set $S^L⊂D$ и train batch $B^L⊂D$. Оба содержат только данные с метками из подмножества с пункта 1:
\begin{aligned}
L, y \in L, \forall (x, y) \in S^L, B^L,
\end{aligned}
# Множество $S^L$ подается на вход модели.;# Конечная оптимизация использует множество $B^L$ чтобы посчитать loss и обновить параметры модели через обратное распространение, так же, как это делается в обучении с учителем.
Можно представить каждую пару сэмплированного датасета $(S^L,B^L)$ как одну точку. Модель обучается таким образом, чтобыона чтобы она могла обобщиться до других датасетов.
Красным выделен дифф между обучением с учителем и мета-обучением.
\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}{]},
\end{aligned}
Идея в некоторой степени аналогична использованию предварительно обученной модели в классификации изображений (ImageNet) или в языковом моделировании (большие текстовые корпуса), когда доступен только ограниченный набор образцов данных для конкретной задачи. Мета-обучение идет еще на один шаг вперед, вместо того, чтобы подстраивать ее под одну задачу, она оптимизирует модель, чтобы она была хороша для многих задач.
<h2>Основанные на оптимизации</h2>
Модели глубокого обучения (deep learning) обучаются через обратное распространение градиентов. Тем не менее, оптимизация, основанная на градиентах не разрабатывалась для работы с небольшим количеством обучающих семплов, и не сходится за малое число оптимизационных шагов. Подход в мета-обучении, основанный на оптимизации как раз про это.
<h3>LSTM-meta-learner</h3>
Оптимизационный алгоитм алгоритм может быть явно смоделирован. Ravi & Larochelle (2017) это и сделали и назвали его "meta-learner". Цель meta-learner'а {{--- }} эффективно обновлять параметры learner'a используя небольшой train set так, чтобы learner мог быстро адаптироваться к новым задачам.
Пусть модель ученика будет $M_θ$, параметризованной $θ$, и meta-learner как $R_Θ$ с параметром $θ$, и функция потерь $\mathcal{L}$.
Обновление параметров learner'a во время $t$ c learning rate $\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, например, тем, что оба используют мета-оптимизацию через градиентый градиентный спуск и оба не чувствительны к модели.
# сэмплируем задачу;# тренируемся на ней несколькими шагами градиентного спуска;
# сдвигаем веса модели к новым параметрам.
<h2>Определение множества конфигураций</h2>
Предшествующие выисления вычисления могут быть также использованы для изучения пространства более успешных конфигураций $\theta\star$. Более подходящие под задачу конфигурации могут серьезно ускорить поиск оптимальных моделей, это важно при ограниченных вычислительных рессурсахресурсах.
Альтернативный подход сперва узнать оптимальные гипермараметрыгиперпараметры, а потом через приращение производительности определить важность каждого из гиперпараметров. Это и было сделано в лабе OpenML, провели около 500 000 экспериментов на 6 алгоритмах и 38 датасетах. Стандартные значения изучались вместе для всех гиперпараметров алгоритма посредством обучения суррогатных моделей для этого алгоритма на большом числе задач. После того, как уже проверены многие варинаты варианты конфигураций, выбирается такая, которая минимизирует ??? для всех задач, становится стандартной.Далее определяется важность каждого из гиперпараметров. Чем больше меняется приращение производительности, тем более важный гиперпараметр мы изменяем.
Если мы хотим предоставить рекомендации для конкретной задачи $t_{new}$, нам нужна дополнительная информация о том, насколько $t_{new}$ похожа на предыдущие задачи $t_j$. Первый способ {{---}} посчитать число рекомендованных конфигураций для $t_newt_{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_newP_{new}$ и , перейти к следующей итерации и выяснять какие еще задачи схожи друг с другом.
<h3>Relative landmarks</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}$.
Так же можно обучать суррогатные модели на Гауссовских процессах (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}$. Суррогатные модели обучаются только на $P_{i, new}$, а следующий $\theta_{i}$ поулчается получается путем нахождения средневзвешенного expected improvement $P_{i, new}$ и предсказанных улучшений на всех предшествующих $P_{i, j}$.
Веса предшествующих задач могут быть переопределены через точность суррогатной модели или через relative landmarks.
Вес ожидаемого улучшения (expected improvement) постепенно возрастает с каждой итерацией (с увеличением собранного эвиденса $P_{i, new}$).
<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},$
В таблице представлен обзор наиболее используемых мета-фичей.
| colspan="4" align="center" | '''simple'''
|-
| Nr instances || $n$ || Speed, Scalability \citep{Michie1994} <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 \citep{Michie1994} || $log(p)$, % categorical
|-
| Nr classes || $c$ || Complexity, imbalance \citep{Michie1994} || ratio min/maj class
|-
| Nr missing values || $m$ || Imputation effects \citep{kalousis02} <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 \citep{Rousseeuw2011} <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 \citep{Michie1994} || min,max,$\mu$,$\sigma$,$q_{1},q_{3}$
|-
| Kurtosis || $\frac{E(X-\mu_{X})^{4}}{\sigma_{X}^{4}}$ || Feature normality \citep{Michie1994} || min,max,$\mu$,$\sigma$,$q_{1},q_{3}$
|-
| Correlation || $\rho_{X_{1}X_{2}}$ || Feature interdependence \citep{Michie1994} || min,max,$\mu$,$\sigma$,$\rho_{XY}$
|-
| Covariance || $cov_{X_{1}X_{2}}$ || Feature interdependence \citep{Michie1994} || min,max,$\mu$,$\sigma$,$cov_{XY}$
|-
| Concentration || $\tau_{X_{1}X_{2}}$ || Feature interdependence \citep{Kalousis2001a} <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}$
|-
| Sparsity || sparsity(X) || Degree of discreteness \citep{Salama2013} <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$
|-
| Gravity || gravity(X) || Inter-class dispersion \citep{Ali2006} <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 \citep{kalousis02} || $p_{val_{XY}}$\citep{soares+04}
|-
| Coeff. of variation || $\frac{\sigma_{Y}}{\mu_{Y}}$ || Variation in target \citep{soares+04} <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 \citep{Michie1994} || $\frac{\lambda_{1}}{\sum_{i} \lambda_{i}}$\citep{Michie1994<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 \citep{bardenet2013collaborative} <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 \citep{Michie1994} || min,max,$\mu$,$\sigma$
|-
| colspan="4" align="center" | '''informational-theoretic'''
|-
| Class entropy || $H(\texttt{C})$ || Class imbalance \citep{Michie1994} ||
|-
| Norm. entropy || $\frac{H(\texttt{X})}{log_{2}n}$ || Feature informativeness \citep<ref>Ciro Castiello, Giovanna Castellano, and Anna~Maria Fanelli. Meta-data: {Castiello2005C} haracterization of input features for meta-learning, pages 457 -- 468, 2005.</ref> || min,max,$\mu$,$\sigma$
|-
| Mutual inform. || $MI(\texttt{C},\texttt{X})$ || Feature importance \citep{Michie1994} || min,max,$\mu$,$\sigma$
|-
| Uncertainty coeff. || $\frac{MI(\texttt{C},\texttt{X})}{H(\texttt{C})}$ || <ref>Feature importance \citep{A. Agresti:2002p7509} . Categorical Data Analysis. Wiley Interscience, 2002.</ref> || min,max,$\mu$,$\sigma$
|-
| Equiv. nr. feats || $\frac{H(C)}{\overline{MI(C,X)}}$ || Intrinsic dimensionality \citep{Michie1994} ||
|-
| Noise-signal ratio || $\frac{\overline{H(X)}-\overline{MI(C,X)}}{\overline{MI(C,X)}}$ || Noisiness of data \citep{Michie1994} ||
|-
| 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}$ \citep{Ho:2002} || See \citet{}{Ho:2002}
|-
| Volume of overlap || || Class distribution overlap \citep{<ref>Tin Kam Ho:and Mitra Basu. Complexity measures of supervised classification problems. Pattern Analysis and Machine Intellig, 2002} .</ref> || See \citet{Ho:2002}
|-
| Concept variation || || Task complexity \citep{<ref>R. Vilalta:2002p5805} . Understanding accuracy performance through concept characterization and algorithm analysis. ICML Workshop on Recent Advances in Meta-Learning and Future Work, 1999.</ref> || See \citet{Vilalta:1999p5745}
|-
| Data consistency || || Data quality <ref>C K{\citep{Kopf:2002p5864"o} pf and I Iglezakis. Combination of task description strategies and case base properties for meta-learning, 2002.</ref> || See \citet{Kopf:2002p5864}
|-
| 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
|-
| Nr nodes, leaves || <tex>|\eta|,Branch length |\psi|</tex> || Concept complexity \citep{Peng:2002p705} || Tree depthmin,max,$\mu$,$\sigma$
|-
| Branch length Nodes per feature || <tex>|| Concept complexity \citepeta_{Peng:2002p705X} |</tex> || Feature importance || min,max,$\mu$,$\sigma$
|-
| Nodes Leaves per feature class || <tex>\frac{|\eta_psi_{Xc}|}{|\psi|}</tex> || Feature importance Class complexity <ref>Andray Filchenkov and Arseniy Pendryak. Dataset metafeature description for recommending feature selection. In \citepemph{Peng:2002p705ISMW FRUCT} , pages 11--18, 2015.</ref> || min,max,$\mu$,$\sigma$
|-
| Leaves per class agreement || <tex>\frac{|n_{\psi_{ci}}|}{|\psi|n}</tex> || Class complexity separability <ref>Bernhard Pfahringer, Hilan Bensusan, and Christophe G. Giraud-Carrier. Meta-learning by landmarking various learning algorithms.In \citepemph{Filchenkov2015} 17th International Conference on Machine Learning (ICML), 2000.</ref> || min,max,$\mu$,$\sigma$
|-
|-
| 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 \citepemph{Pfahringer:2000p55317th International Conference on Machine Learning (ICML)} , pages 743 -- 750, 2000.</ref> || See \citet{Pfahringer:2000p553}
|-
| Landmarker(Tree) || $P(\theta_{Tree},t_{j})$ || Data separability \citep{Pfahringer:2000p553} || Stump,RandomTree
|-
| Landmarker(Lin) || $P(\theta_{Lin},t_{j})$ || Linear separability \citep{Pfahringer:2000p553} || Lin.Disciminant
|-
| Landmarker(NB) || $P(\theta_{NB},t_{j})$ || Feature independence \citep{Pfahringer:2000p553} || See <ref>Daren Ler, Irena Koprinska, and Sanjay Chawla. Utilizing regression-based landmarkers within a meta-learning framework for algorithm selection. \citetemph{Ler:2005p1680Technical Report 569. University of Sydney}, pages 44--51, 2005.</ref>
|-
| Relative LM || $P_{a,j} - P_{b,j}$ || Probing performance <ref>J F{\"u}rnkranz and J Petrak. An evaluation of landmarking variants. \citepemph{Furnkranz:2001p1278ECML/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}ncio, Carlos Soares, Andr{\citep'e} LD Rossi and Andr{Soares:2001p708\'e} 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+})$.
Многие мета-фичи вычисляются по одиночным фичам или комбинации фичей, и должны быть агрегированы через min,max,$\mu$,$\sigma$,quartiles или гистограммами . Во время вычисления похожести задач важно нормализовать все мета-фичи [kalousisbardnet], использовать feature selection <ref>L Todorovski and S Dzeroski. Experiments in meta-level learning with ILP. Lecture Notes in Computer Science, 1704:98–106, 1999.</ref> или использовать dimensionality reduction (PCA, например).
