| MachineLearning.RU | Главная | Публикации | Преподавание | Студентам | ChartLib | Софт | LaTeX | Ссылки | Рисунки | English |
Внимание! Эта страница обновляться больше не будет. Теперь обновления курса будут выкладываться на MachineLearning.ru
В курсе рассматриваются различные задачи машинного обучения (machine learning), в том числе задачи классификации, кластеризации, регрессии и прогнозирования. Изучаются различные методы решения этих задач.
Имеется множество объектов, каждому из которых поставлен в соответствие некоторый ответ. Это соответствие известно только на конечной выборке прецедентов — пар вида «объект–ответ». По этим данным необходимо восстановить зависимость, то есть построить алгоритм, который для любого объекта выдавал бы некоторый ответ, и при этом ошибался бы как можно реже.
В задачах медицинской диагностики объектами являются пациенты,
ответами — диагнозы или решения о целесообразности того или иного вида лечения.
В задачах кредитного скоринга (credit scoring) объектами являются заемщики
(точнее, анкеты, заполненные при подаче заявки на выдачу кредита),
ответами — решения выдать или не выдать кредит.
В задачах предсказания ухода клиентов (churn prediction) объектами являются
протоколы всех действий (платежей, транзакций, смен тарифного плана, и т.д.) клиента,
ответами — оценки вероятности того, что клиент откажется от услуг компании
в течение ближайшего времени (например, месяца).
В задачах прогнозирования продаж (sales forecast) объектами являются
временные ряды объемов продаж товаров в магазинах;
ответами — прогнозы объемов потребительского спроса.
Можно приводить еще десятки и сотни примеров приложений, в которых обучение по прецедентам
позволяет автоматизировать решение достаточно сложных профессиональных проблем.
Смотрите вводную лекцию.
Курс находится в стадии разработки. Пожалуйста, не стесняйтесь сообщать о найденных ошибках, высказывать замечания и предложения.
Местецкий Л. М.
Математические методы распознавания образов.
ВМиК МГУ,
кафедра ММП
— 2002.
www.ccas.ru/frc/papers/mestetskii04course.pdf.
Мерков А. Б.
Основные методы, применяемые для распознавания рукописного текста.
Лаборатория распознавания образов МЦНМО. — 2004.
http://www.recognition.mccme.ru/pub/RecognitionLab.html/methods.html.
Лифшиц Ю.
Современные задачи теоретической информатики.
ИТМО. — 2005.
http://teormin.ifmo.ru/education/modern.
Jaakkola T.
Machine Learning.
MIT. — 2004.
http://www.ai.mit.edu/people/tommi/courses.html.
Внимание! Более свежая версия этого текста находится здесь: MachineLearning.ru
Проблема обобщающей способности является ключевой и в то же время наиболее сложной в машинном обучении. Если алгоритм обучен по конечной выборке прецедентов, то как предсказать качество его работы на новых объектах? Почему это вообще возможно? Как надо обучать алгоритм, чтобы он редко ошибался на новых данных?
Активное исследование этих вопросов началось в конце 60-х, когда В.Н.Вапник и А.Я.Червоненкис предложили статистическую теорию восстановления зависимостей по эмпирическим данным. Они получили верхние оценки вероятности ошибок обученного алгоритма, позволившие обосновать давно замеченный эмпирический факт: по мере увеличения сложности используемого семейства алгоритмов качество обучения сначала улучшается, затем начинает ухудшаться. Ухудшение связано с эффектом переобучения: чрезмерно сложные алгоритмы имеют избыточное число свободных параметров; при обучении этих параметров по выборке алгоритм настраивается не только на восстановление зависимости, но и на воспроизведение разного рода погрешностей. Погрешности в реальных задачах всегда присутствуют: во-первых, это ошибки измерения (шум), во-вторых, что гораздо существеннее, это невязка между используемой моделью и неизвестной истинной зависимостью. В теории Вапника-Червоненкиса разработан метод структурной минимизации риска (СМР), позволяющий автоматически находить модель оптимальной сложности.
К сожалению, статистические оценки чрезвычайно сильно завышены. В методе СМР это часто влечет переупрощение модели. Несмотря на 40-летние усилия многих ученых, точные оценки качества обучения до сих пор не получены.
Основные направления исследований:
— комбинаторная теория обобщающей способности;
— уточнение оценок обобщающей способности для различных частных случаев;
— разработка новых алгоритмов обучения на их основе.
Ключевые слова:
generalization ability, computational learning theory, Vapnik-Chervonenkis theory.
Комбинаторная статистика. Это направление логично вытекает из предыдущего и является его обобщением. Оказывается, многие фундаментальные факты теории вероятностей и математической статистики можно переформулировать и доказать, не опираясь на колмогоровскую аксиоматику, то есть не используя теорию меры, и даже не употребляя само понятие вероятности. В задачах анализа данных мы всегда имеем дело с выборками конечной длины. Поэтому естественно ставить вопрос не «какова вероятность события?», а «какой может быть частота этого события на скрытых (пока еще не известных) данных?». Ответы на эти два вопроса, вообще говоря, различны, причем на выборках малой длины различие существенно. Вероятность события — абстрактная идеализированная величина. Частота события — это как раз то, что реально измеряется в эксперименте. Именно ее и имеет смысл предсказывать.
В частотной постановке удается переформулировать закон больших чисел, закон сходимости эмпирических распределений (критерий Смирнова), многие статические критерии, в первую очередь, ранговые критерии, теорию обобщающей способности, теорию информации. Во многих случаях получаемые оценки являются точными, т.е. не асимптотическими и не завышенными. Однако для их вычисления может потребоваться разработка специальных эффективных алгоритмов.
Основные направления исследований:
— выяснение границ применимости слабой вероятностной аксиоматики;
— точные (комбинаторные) статистические критерии;
— эффективные алгоритмы вычисления комбинаторных оценок.
Методы обучения алгоритмических композиций применяются в сложных задачах, когда имеющиеся (базовые) алгоритмы не дают желаемого качества обучения. В таких случаях строят композиции алгоритмов, стараясь, чтобы ошибки различных алгоритмов скомпенсировали друг друга.
Самый простой пример композиции — усреднение ответов, выдаваемых базовыми алгоритмами. Можно усреднять с весами. Можно выделять области компетентности различных алгоритмов, и в каждой области использовать свое распределение весов. Можно строить композиции алгоритмов с помощью нелинейных операций. Какой из этих методов лучше? В каких задачах? Как обучать базовые алгоритмы, учитывая, что они будут работать не по-отдельности, а в составе композиции? Можно ли приспособить для этого стандартные методы обучения? Как оценивать и целенаправленно улучшать обобщающую способность композиции? Как при этом сделать число алгоритмов в композиции поменьше?
Идея алгоритмических композиций была выдвинута в середине 70-х годов в работах академика РАН Ю.И.Журавлева. В зарубежных исследованиях это тема стала чрезвычайно популярной в 90-е годы, после изобретения алгоритмов бустинга, смесей экспертов и других композитных конструкций.
Основные направления исследований:
— разработка эффективных алгоритмов построения композиций;
— повышение обобщающей способности композиций;
— сравнительный анализ различных методов построения композиций.
Ключевые слова:
multiple classifier systems, ensemble learning, classifier fusion, mixture of experts.
Анализ клиентских сред (АКС) является относительно новой и быстро развивающейся областью интеллектуального анализа данных (data mining). В современном бизнесе чрезвычайно востребовано решение следующей задачи, точнее даже группы задач.
Имеется некоторый набор ресурсов (товаров, услуг, предметов) которыми пользуется огромное количество клиентов. Все действия пользователей протоколируются в электронном виде. Эти данные содержат ценнейшую информацию, необходимую для повышения качества оказываемых услуг, однако извлечь ее не так просто ввиду огромного объема данных. Какие ресурсы наиболее популярны, и среди каких групп клиентов? Возможно ли угадать интересы клиента и сформировать для него персональное предложение, от которого он с высокой вероятностью не откажется? Как выявить клиентов, собирающихся в ближайшее время отказаться от обслуживания? Эти и другие задачи решаются в системах управления взаимоотношениями с клиентами (client relationship management, CRM). Создание математического обеспечения для них является актуальной, наукоемкой задачей.
Один из типичных примеров клиентской среды — интернет-портал, предоставляющий доступ к большому количеству ресурсов, скажем, интернет-магазин или поисковый сервер. Технология АКС позволяет решать задачи персонализации контента — когда результаты поиска, информационные каталоги, предложения товаров и услуг, и т.д. выстраиваются в таком порядке, чтобы пользователь без труда находил информацию, необходимую именно ему, именно в данный момент.
Основные направления исследований:
— коллаборативная фильтрация;
— разработка эффективных алгоритмов АКС;
— решение задач персонализации контента;
— и других прикладных задач.
Ключевые слова:
collaborative filtering, web usage mining, personalization, client relationship management.
|
|