Машинное обучение

Материал из MachineLearning.

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

Содержание

Машинное обучение (Machine Learning) — обширный подраздел искусственного интеллекта, изучающий методы построения алгоритмов, способных обучаться. Различают два типа обучения. Обучение по прецедентам, или индуктивное обучение, основано на выявлении общих закономерностей по частным эмпирическим данным. Дедуктивное обучение предполагает формализацию знаний экспертов и их перенос в компьютер в виде базы знаний. Дедуктивное обучение принято относить к области экспертных систем, поэтому термины машинное обучение и обучение по прецедентам можно считать синонимами.

Машинное обучение находится на стыке математической статистики, методов оптимизации и классических математических дисциплин, но имеет также и собственную специфику, связанную с проблемами вычислительной эффективности и переобучения. Многие методы индуктивного обучения разрабатывались как альтернатива классическим статистическим подходам. Многие методы тесно связаны с извлечением информации и интеллектуальным анализом данных (Data Mining).

Наиболее теоретические разделы машинного обучения объединены в отдельное направление, теорию вычислительного обучения (Computational Learning Theory, COLT).

Машинное обучение — не только математическая, но и практическая, инженерная дисциплина. Чистая теория, как правило, не приводит сразу к методам и алгоритмам, применимым на практике. Чтобы заставить их хорошо работать, приходится изобретать дополнительные эвристики, компенсирующие несоответствие сделанных в теории предположений условиям реальных задач. Практически ни одно исследование в машинном обучении не обходится без эксперимента на модельных или реальных данных, подтверждающего практическую работоспособность метода.

Общая постановка задачи обучения по прецедентам

Дано конечное множество прецедентов (объектов, ситуаций), по каждому из которых собраны (измерены) некоторые данные. Данные о прецеденте называют также его описанием. Совокупность всех имеющихся описаний прецедентов называется обучающей выборкой. Требуется по этим частным данным выявить общие зависимости, закономерности, взаимосвязи, присущие не только этой конкретной выборке, но вообще всем прецедентам, в том числе тем, которые ещё не наблюдались. Говорят также о восстановлении зависимостей по эмпирическим данным — этот термин был введён в работах Вапника и Червоненкиса.

Наиболее распространённым способом описания прецедентов является признаковое описание. Фиксируется совокупность n показателей, измеряемых у всех прецедентов. Если все n показателей числовые, то признаковые описания представляют собой числовые векторы размерности n. Возможны и более сложные случаи, когда прецеденты описываются временными рядами или сигналами, изображениями, видеорядами, текстами, попарными отношениями сходства или интенсивности взаимодействия, и т. д.

Для решения задачи обучения по прецедентам в первую очередь фиксируется модель восстанавливаемой зависимости. Затем вводится функционал качества, значение которого показывает, насколько хорошо модель описывает наблюдаемые данные. Алгоритм обучения (learning algorithm) ищет такой набор параметров модели, при котором функционал качества на заданной обучающей выборке принимает оптимальное значение. Процесс настройки (fitting) модели по выборке данных в большинстве случаев сводится к применению численных методов оптимизации.

Замечание о терминологии. В зарубежных публикациях термин algorithm употребляется только в указанном выше смысле, то есть это вычислительная процедура, которая по обучающей выборке производит настройку модели. Выходом алгоритма обучения является функция, аппроксимирующая неизвестную (восстанавливаемую) зависимость. В задачах классификации аппроксимирующую функцию принято называть классификатором (classifier), концептом (concept) или гипотезой (hypothesys); в задачах восстановления регрессии — функцией регрессии; иногда просто функцией. В русскоязычной литературе аппроксимирующую функцию также называют алгоритмом, подчёркивая, что и она должна допускать эффективную компьютерную реализацию.

Типология задач обучения по прецедентам

Основные стандартные типы задач

  • Обучение с учителем (supervised learning) — наиболее распространённый случай. Каждый прецедент представляет собой пару «объект, ответ». Требуется найти функциональную зависимость ответов от описаний объектов и построить алгоритм, принимающий на входе описание объекта и выдающий на выходе ответ. Функционал качества обычно определяется как средняя ошибка ответов, выданных алгоритмом, по всем объектам выборки.
    • Задача классификации (classification) отличается тем, что множество допустимых ответов конечно. Их называют метками классов (class label). Класс — это множество всех объектов с данным значением метки.
    • Задача регрессии (regression) отличается тем, что допустимым ответом является действительное число или числовой вектор.
    • Задача ранжирования (learning to rank) отличается тем, что ответы надо получить сразу на множестве объектов, после чего отсортировать их по значениям ответов. Может сводиться к задачам классификации или регрессии. Часто применяется в информационном поиске и анализе текстов.
    • Задача прогнозирования (forecasting) отличается тем, что объектами являются отрезки временных рядов, обрывающиеся в тот момент, когда требуется сделать прогноз на будущее. Для решения задач прогнозирования часто удаётся приспособить методы регрессии или классификации, причём во втором случае речь идёт скорее о задачах принятия решений.
  • Обучение без учителя (unsupervised learning). В этом случае ответы не задаются, и требуется искать зависимости между объектами.
    • Задача кластеризации (clustering) заключается в том, чтобы сгруппировать объекты в кластеры, используя данные о попарном сходстве объектов. Функционалы качества могут определяться по-разному, например, как отношение средних межкластерных и внутрикластерных расстояний.
    • Задача поиска ассоциативных правил (association rules learning). Исходные данные представляются в виде признаковых описаний. Требуется найти такие наборы признаков, и такие значения этих признаков, которые особенно часто (неслучайно часто) встречаются в признаковых описаниях объектов.
    • Задача фильтрации выбросов (outliers detection) — обнаружение в обучающей выборке небольшого числа нетипичных объектов. В некоторых приложениях их поиск является самоцелью (например, обнаружение мошенничества). В других приложениях эти объекты являются следствием ошибок в данных или неточности модели, то есть шумом, мешающим настраивать модель, и должны быть удалены из выборки, см. также робастные методы и одноклассовая классификация.
    • Задача построения доверительной области (quantile estimation) — области минимального объёма с достаточно гладкой границей, содержащей заданную долю выборки.
    • Задача сокращения размерности (dimensionality reduction) заключается в том, чтобы по исходным признакам с помощью некоторых функций преобразования перейти к наименьшему числу новых признаков, не потеряв при этом никакой существенной информации об объектах выборки. В классе линейных преобразований наиболее известным примером является метод главных компонент.
    • Задача заполнения пропущенных значений (missing values) — замена недостающих значений в матрице объекты–признаки их прогнозными значениями.
  • Частичное обучение (semi-supervised learning) занимает промежуточное положение между обучением с учителем и без учителя. Каждый прецедент представляет собой пару «объект, ответ», но ответы известны только на части прецедентов. Пример прикладной задачи — автоматическая рубрикация большого количества текстов при условии, что некоторые из них уже отнесены к каким-то рубрикам.
  • Трансдуктивное обучение (transductive learning). Дана конечная обучающая выборка прецедентов. Требуется по этим частным данным сделать предсказания отностительно других частных данных — тестовой выборки. В отличие от стандартной постановки, здесь не требуется выявлять общую закономерность, поскольку известно, что новых тестовых прецедентов не будет. С другой стороны, появляется возможность улучшить качество предсказаний за счёт анализа всей тестовой выборки целиком, например, путём её кластеризации. Во многих приложениях трансдуктивное обучение практически не отличается от частичного обучения.
  • Обучение с подкреплением (reinforcement learning). Роль объектов играют пары «ситуация, принятое решение», ответами являются значения функционала качества, характеризующего правильность принятых решений (реакцию среды). Как и в задачах прогнозирования, здесь существенную роль играет фактор времени. Примеры прикладных задач: формирование инвестиционных стратегий, автоматическое управление технологическими процессами, самообучение роботов, и т.д.
  • Динамическое обучение (online learning) может быть как обучением с учителем, так и без учителя. Специфика в том, что прецеденты поступают потоком. Требуется немедленно принимать решение по каждому прецеденту и одновременно доучивать модель зависимости с учётом новых прецедентов. Как и в задачах прогнозирования, здесь существенную роль играет фактор времени.
  • Метаобучение (meta-learning или learning-to-learn) отличается тем, что прецедентами являются ранее решённые задачи обучения. Требуется определить, какие из используемых в них эвристик работают более эффективно. Конечная цель — обеспечить постоянное автоматическое совершенствование алгоритма обучения с течением времени.
    • Многозадачное обучение (multi-task learning). Набор взаимосвязанных или схожих задач обучения решается одновременно, с помощью различных алгоритмов обучения, имеющих схожее внутренне представление. Информация о сходстве задач между собой позволяет более эффективно совершенствовать алгоритм обучения и повышать качество решения основной задачи.
    • Индуктивный перенос (inductive transfer). Опыт решения отдельных частных задач обучения по прецедентам переносится на решение последующих частных задач обучения. Для формализации и сохранения этого опыта применяются реляционные или иерархические структуры представления знаний.
    • Иногда к метаобучению ошибочно относят построение алгоритмических композиций, в частности, бустинг; однако в композициях несколько алгоритмов решают одну и ту же задачу, тогда как метаобучение предполагает, что решается много разных задач.

Специфические прикладные задачи

Некоторые задачи, возникающие в прикладных областях, имеют черты сразу нескольких стандартных типов задач обучения, поэтому их трудно однозначно отнести к какому-то одному типу.

  • Формирование инвестиционного портфеля (portfolio selection) — это динамическое обучение с подкреплением, в котором очень важен отбор информативных признаков. Роль признаков играют финансовые инструменты. Состав оптимального набора признаков (портфеля) может изменяться со временем. Функционалом качества является долгосрочная прибыль от инвестирования в данную стратегию управления портфелем.

Приложения

Целью машинного обучения является частичная или полная автоматизация решения сложных профессиональных задач в самых разных областях человеческой деятельности. Машинное обучение имеет широкий спектр приложений:

Сфера применений машинного обучения постоянно расширяется. Повсеместная информатизация приводит к накоплению огромных объёмов данных в науке, производстве, бизнесе, транспорте, здравоохранении. Возникающие при этом задачи прогнозирования, управления и принятия решений часто сводятся к обучению по прецедентам. Раньше, когда таких данных не было, эти задачи либо вообще не ставились, либо решались совершенно другими методами.

Подходы и методы

Подход к задачам обучения — это концепция, парадигма, точка зрения на процесс обучения, приводящая к набору базовых предположений, гипотез, эвристик, на основе которых строится модель, функционал качества и методы его оптимизации.

Разделение методов «по подходам» довольно условно. Разные подходы могут приводить к одной и той же модели, но разным методам её обучения. В некоторых случаях эти методы отличаются очень сильно, в других — совсем немного и «плавно трансформируются» друг в друга путём незначительных модификаций.

Статистическая классификация

В статистике решение задач классификации принято называть дискриминантным анализом.

Байесовская теория классификации основана на применении оптимального байесовского классификатора и оценивании плотностей распределения классов по обучающей выборке. Различные методы оценивания плотности порождают большое разнообразие байесовских классификаторов. Среди них можно выделить три группы методов:

Параметрическое оценивание плотности

Непараметрическое оценивание плотности

Оценивание плотности как смеси параметрических плотностей

Несколько особняком стоит наивный байесовский классификатор, который может быть как параметрическим, так и непараметрическим. Он основан на нереалистичном предположении о статистической независимости признаков. Благодаря этому метод чрезвычайно прост.

Другие теоретико-вероятностные и статистические подходы:

Классификация на основе сходства

Метрические алгоритмы классификации применяются в тех задачах, где удаётся естественным образом задавать объекты не их признаковыми описаниями, а матрицей попарных расстояний между объектами. Классификация объектов по их сходству основана на гипотезе компактности, которая гласит, что в «хорошей задаче» схожие объекты чаще лежат в одном классе, чем в разных.

Метрические алгоритмы относятся к методам рассуждения на основе прецедентов (Case Based Reasoning, CBR}. Здесь действительно можно говорить о «рассуждениях», так как на вопрос «почему объект u был отнесён к классу y?» алгоритм может дать понятный эксперту ответ: «потому, что имеются прецеденты — схожие с~ним объекты, принадлежащие классу y», и~предъявить список этих прецедентов.

Наиболее известные метрические алгоритмы классификации:

Классификация на основе разделимости

Большая группа методов классификации основана на явном построении разделяющей поверхности в пространстве объектов. Из них чаще всех применяются Линейные классификаторы:

Нейронные сети

Нейронные сети основаны на принципе коннективизма — в них соединяется большое количество относительно простых элементов, а обучение сводится к построению оптимальной структуры связей и настройке параметров связей.

Индукция правил (поиск закономерностей)

Категория:Логические алгоритмы классификации представляют собой композиции простых, легко интерпретируемых правил.

Кластеризация

Категория:Кластеризация

Регрессия

Алгоритмические композиции

Сокращение размерности

Выбор модели

Байесовский вывод

Категория:Байесовский вывод

Софт 

Система статистической обработки данных и работы с графикой R содержит обширный набор пакетов для машинного обучения.

Нейронные сети: нейронная сеть с одним скрытым слоем реализована в пакете nnet (поставляется в составе R). Пакет RSNNS предлагает интерфейс к Stuttgart Neural Network Simulator (SNNS). Интерфейс к библиотеке FCNN позволяет расширяемые пользователем искусственные нейронные сети в пакете FCNN4R.

Рекурсивное разделение: модели с древовидной структурой для регрессии, классификации и анализа дожития, следующие идеям в документации CART, реализованы в пакетах rpart и tree (поставляется с R). Пакет rpart рекомендуется для вычислений подобных CART-деревьям. Богатая панель инструментов алгоритмов разделения доступна в пакете Weka, RWeka обеспечивает интерфейс этой реализации, включая J4.8-вариант C4.5 и M5. Кубиxческий пакет подгоняет модели, основанными на правилах (подобными деревьям) с линейными регрессионными моделями в терминальных листах, основанных на коррекции наблюдений и бустинге. Пакет C50 может подогнать деревья классификации C5.0, модели, основанные на правилах и их версиях бустинга.

Two recursive partitioning algorithms with unbiased variable selection and statistical stopping criterion are implemented in package party. Function ctree() is based on non-parametrical conditional inference procedures for testing independence between response and each input variable whereas mob() can be used to partition parametric models. Extensible tools for visualizing binary trees and node distributions of the response are available in package party as well.

Tree-structured varying coefficient models are implemented in package vcrpart.

For problems with binary input variables the package LogicReg implements logic regression. Graphical tools for the visualization of trees are available in package maptree.

Trees for modelling longitudinal data by means of random effects is offered by package REEMtree. Partitioning of mixture models is performed by RPMM. Computational infrastructure for representing trees and unified methods for predition and visualization is implemented in partykit. This infrastructure is used by package evtree to implement evolutionary learning of globally optimal trees. Oblique trees are available in package oblique.tree.

Random Forests : The reference implementation of the random forest algorithm for regression and classification is available in package randomForest. Package ipred has bagging for regression, classification and survival analysis as well as bundling, a combination of multiple models via ensemble learning. In addition, a random forest variant for response variables measured at arbitrary scales based on conditional inference trees is implemented in package party. randomForestSRC implements a unified treatment of Breiman's random forests for survival, regression and classification problems. Quantile regression forests quantregForest allow to regress quantiles of a numeric response on exploratory variables via a random forest approach. For binary data, LogicForest is a forest of logic regression trees (package LogicReg. The varSelRF and Boruta packages focus on variable selection by means for random forest algorithms. In addition, packages ranger and Rborist offer R interfaces to fast C++ implementations of random forests.


Regularized and Shrinkage Methods : Regression models with some constraint on the parameter estimates can be fitted with the lasso2 and lars packages. Lasso with simultaneous updates for groups of parameters (groupwise lasso) is available in package grplasso; the grpreg package implements a number of other group penalization models, such as group MCP and group SCAD. The L1 regularization path for generalized linear models and Cox models can be obtained from functions available in package glmpath, the entire lasso or elastic-net regularization path (also in elasticnet) for linear regression, logistic and multinomial regression models can be obtained from package glmnet. The penalized package provides an alternative implementation of lasso (L1) and ridge (L2) penalized regression models (both GLM and Cox models). Package RXshrink can be used to identify and display TRACEs for a specified shrinkage path and to determine the appropriate extent of shrinkage. Semiparametric additive hazards models under lasso penalties are offered by package ahaz. A generalisation of the Lasso shrinkage technique for linear regression is called relaxed lasso and is available in package relaxo. Fisher's LDA projection with an optional LASSO penalty to produce sparse solutions is implemented in package penalizedLDA. The shrunken centroids classifier and utilities for gene expression analyses are implemented in package pamr. An implementation of multivariate adaptive regression splines is available in package earth. Variable selection through clone selection in SVMs in penalized models (SCAD or L1 penalties) is implemented in package penalizedSVM. Various forms of penalized discriminant analysis are implemented in packages hda, rda, and sda. Package LiblineaR offers an interface to the LIBLINEAR library. The ncvreg package fits linear and logistic regression models under the the SCAD and MCP regression penalties using a coordinate descent algorithm. High-throughput ridge regression (i.e., penalization with many predictor variables) and heteroskedastic effects models are the focus of the bigRR package. An implementation of bundle methods for regularized risk minimization is available form package bmrm. The Lasso under non-Gaussian and heteroscedastic errors is estimated by hdm, inference on low-dimensional components of Lasso regression and of estimated treatment effects in a high-dimensional setting are also contained. Package SIS implements sure independence screening in generalised linear and Cox models.

Boosting : Various forms of gradient boosting are implemented in package gbm (tree-based functional gradient descent boosting). The Hinge-loss is optimized by the boosting implementation in package bst. Package GAMBoost can be used to fit generalized additive models by a boosting algorithm. An extensible boosting framework for generalized linear, additive and nonparametric models is available in package mboost. Likelihood-based boosting for Cox models is implemented in CoxBoost and for mixed models in GMMBoost. GAMLSS models can be fitted using boosting by gamboostLSS.

Support Vector Machines and Kernel Methods : The function svm() from e1071 offers an interface to the LIBSVM library and package kernlab implements a flexible framework for kernel learning (including SVMs, RVMs and other kernel learning algorithms). An interface to the SVMlight implementation (only for one-against-all classification) is provided in package klaR. The relevant dimension in kernel feature spaces can be estimated using rdetools which also offers procedures for model selection and prediction.

Bayesian Methods : Bayesian Additive Regression Trees (BART), where the final model is defined in terms of the sum over many weak learners (not unlike ensemble methods), are implemented in package BayesTree. Bayesian nonstationary, semiparametric nonlinear regression and design by treed Gaussian processes including Bayesian CART and treed linear models are made available by package tgp.

Optimization using Genetic Algorithms : Packages rgp and rgenoud offer optimization routines based on genetic algorithms. The package Rmalschains implements memetic algorithms with local search chains, which are a special type of evolutionary algorithms, combining a steady state genetic algorithm with local search for real-valued parameter optimization.

Association Rules : Package arules provides both data structures for efficient handling of sparse binary data as well as interfaces to implementations of Apriori and Eclat for mining frequent itemsets, maximal frequent itemsets, closed frequent itemsets and association rules.

Fuzzy Rule-based Systems : Package frbs implements a host of standard methods for learning fuzzy rule-based systems from data for regression and classification. Package RoughSets provides comprehensive implementations of the rough set theory (RST) and the fuzzy rough set theory (FRST) in a single package.

Model selection and validation : Package e1071 has function tune() for hyper parameter tuning and function errorest() (ipred) can be used for error rate estimation. The cost parameter C for support vector machines can be chosen utilizing the functionality of package svmpath. Functions for ROC analysis and other visualisation techniques for comparing candidate classifiers are available from package ROCR. Packages hdi and stabs implement stability selection for a range of models, hdi also offers other inference procedures in high-dimensional models.

Other procedures : Evidential classifiers quantify the uncertainty about the class of a test pattern using a Dempster-Shafer mass function in package evclass. The OneR (One Rule) package offers a classification algorithm with enhancements for sophisticated handling of missing values and numeric data together with extensive diagnostic functions.

Meta packages : Package caret provides miscellaneous functions for building predictive models, including parameter tuning and variable importance measures. The package can be used with various parallel implementations (e.g. MPI, NWS etc). In a similar spirit, package mlr offers a high-level interface to various statistical and machine learning packages. Package SuperLearner implements a similar toolbox. The h2o package implements a general purpose machine learning platform that has scalable implementations of many popular algorithms such as random forest, GBM, GLM (with elastic net regularization), and deep learning (feedforward multilayer networks), among others.

Elements of Statistical Learning : Data sets, functions and examples from the book The Elements of Statistical Learning: Data Mining, Inference, and Prediction by Trevor Hastie, Robert Tibshirani and Jerome Friedman have been packaged and are available as ElemStatLearn.

GUI rattle is a graphical user interface for data mining in R.

CORElearn implements a rather broad class of machine learning

Конференции

Основные международные конференции — ICML, NIPS, ICPR, COLT.

Международные конференции в странах СНГ — ИОИ.

Основные всероссийские конференции — ММРО, РОАИ.

См. также Рейтинг международных научных конференций.

Ссылки

  • Google Machine Learning News — форумы и новости по машинному обучению на Гугле
  • hunch.net — блог Джона Лангфорда (John Langford) по проблемам машинного обучения
  • ML OSS (Machine learning open source software) — коллективный сайт разработчиков открытого софта для машинного обучения
  • KDnuggets — крупнейший портал по интеллектуальному анализу данных, поддерживаемый Григорием Пятецким-Шапиро, одним из идеологов Data Mining
  • ML challenges — cоревнования в решении задач машинного обучения
  • KDNet (Knowledge Discovery Network of Excellence) — международный проект, объединяющий представителей науки и бизнеса, решающих практические задачи интеллектуального анализа данных
  • MLpedia — вики-ресурс по машинному обучению, в последнее время почему-то недоступен
  • Wikipedia — категория Machine Learning в англоязычной Википедии
  • CiteSeer — основной источник знаний по Computer Science
  • CiteSeerX — альфа-версия нового CiteSeer, пока глючная, но зато пополняемая

См. также

Курсы лекций

Использованная литература

  1. Айвазян С. А., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: основы моделирования и первичная обработка данных. — М.: Финансы и статистика, 1983.
  2. Айвазян С. А., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: исследование зависимостей. — М.: Финансы и статистика, 1985.
  3. Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989.
  4. Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. — М.: Наука, 1974.
  5. Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.
  6. Журавлев Ю. И., Рязанов В. В., Сенько О. В. «Распознавание». Математические методы. Программная система. Практические применения. — М.: Фазис, 2006. ISBN 5-7036-0108-8.
  7. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999. ISBN 5-86134-060-9.
  8. Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознаванию. — Киев: Наукова думка, 2004. ISBN 966-00-0341-2.
  9. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. — Springer, 2001. ISBN 0-387-95284-5.
  10. MacKay D. On-line book: Information Theory, Inference, and Learning Algorithms. — 2005.
  11. Mitchell T. Machine Learning. — McGraw-Hill Science/Engineering/Math, 1997. ISBN 0-07-042807-7.
  12. Schölkopf B., Smola A.J. Learning with Kernels. Support Vector Machines, Regularization, Optimization, and Beyond. — MIT Press, Cambridge, MA, 2002 ISBN 13-978-0-262-19475-4 [2]
  13. Vapnik V.N. Statistical learning theory. — N.Y.: John Wiley & Sons, Inc., 1998. [3]
  14. Witten I.H., Frank E. Data Mining: Practical Machine Learning Tools and Techniques (Second Edition). — Morgan Kaufmann, 2005 ISBN 0-12-088407-0 [4]
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5»
Личные инструменты