Изменения

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

Мета-обучение

2315 байт добавлено, 18:42, 28 января 2019
обновил референсы, улучшил связность
<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>
Хорошая модель мета-обучения должна быть обучена на множестве задач и оптимизирована для лучшей производительности на нескольких задачах,
Предшествующие вычисления могут быть также использованы для изучения пространства более успешных конфигураций \theta\star. Более подходящие под задачу конфигурации могут серьезно ускорить поиск оптимальных моделей, это важно при ограниченных вычислительных рессурсах.
Альтернативный подход сперва узнать оптимальные гиперпараметры, а потом через приращение производительности определить важность каждого из гиперпараметров. Это и было сделано в лабе OpenML, провели около 500 000 экспериментов на 6 алгоритмах и 38 датасетах. Стандартные значения изучались вместе для всех гиперпараметров алгоритма посредством обучения суррогатных моделей для этого алгоритма на большом числе задач. После того, как уже проверены многие варианты конфигураций, выбирается такая, которая минимизирует ??? для всех задач, становится стандартной.Далее определяется важность каждого из гиперпараметров. Чем больше меняется приращение производительности, тем более важный гиперпараметр мы изменяем.
Если мы хотим предоставить рекомендации для конкретной задачи $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}$.
| 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$
|-
| Leaves agreement || <tex>\frac{n_{\psi_{i}}}{n}</tex> || Class separability \citep{Bensusan2000} || min,max,$\mu$,$\sigma$|-| Information gain || || Feature importance \citep{Bensusan2000} || 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 \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 или гистограммами [kalousis].
Во время вычисления похожести задач важно нормализовать все мета-фичи [bardnet], использовать feature selection [todorovski] <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, например).
== Примечания ==
* https://www.ml4aad.org/wp-content/uploads/2018/09/chapter2-metalearning.pdf
* https://openreview.net/pdf?id=rJY0-Kcll
* https://www1.maths.leeds.ac.uk/~charles/statlog/whole.pdf
* https://www.fruct.org/publications/ainl-fruct/files/Fil.pdf
* Alexandros Kalousis and Melanie Hilario. Model selection via meta-learning: a comparative study. Intl Journ. on Artificial Intelligence Tools, 10(4):525–554, 2001.
* 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
* L Todorovski and S Dzeroski. Experiments in meta-level learning with ILP. Lecture Notes in Computer Science, 1704:98–106, 1999.
[[Категория: Машинное обучение]]
16
правок

Навигация