Публикации К. В. Воронцова

Список публикаций автоматически сгенерирован из библиографической базы MachLearn.bib с помощью программы BibTeX и конвертера Bbl2Html.
 

[1] Воронцов К. В., Кобзева Н. В.
Численные методы обработки данных для высокоэффективной жидкостной хроматографии // Информационные проблемы клинической токсикологии. — Москва, 1993.
www.ccas.ru/frc/papers/voron93remedi.pdf
Рассматривается алгоритм идентификации лекарственных препаратов в биосредах организма по данным жидкостной хроматографии. Алгоритм основан на матричном подходе к обработке числовых данных, поступающих со сканирующего ультрафиолетового детектора. Более полное использование первичных данных в совокупности с математическим моделированием формы хроматографических пиков позволяет существенно улучшить качество идентификации. Алгоритм позволяет корректно выделять спектры веществ, отсутствующих в базе данных системы, эффективно (в сотни раз) сжимать ранее полученные хроматограммы практически без потери точности представления данных, ускорить самообучение системы, повысить чувствительность прибора при предельно низких концентрациях. Все предлагаемые модификации относятся к программному обеспечению и не затрагивают аппаратной части хроматографической установки.
[2] Воронцов К. В.
Предварительная обработка данных для решения задач распознавания в жидкостной хроматографии. — Дипломная работа. Московский физико-технический институт. — 1994.
www.ccas.ru/frc/papers/voron94diplom.pdf
Рассматривается один из подходов к идентификации компонентов смеси химических веществ по данным высокоэффективной жидкостной хроматографии. Предлагаемые алгоритмы ориентированы на обработку исходных данных системы экстренной токсикологии REMEDI (Bio-Rad Laboratories, США), предназначенной для оперативного анализа образцов плазмы крови.
[3] Воронцов К. В.
Качество восстановления зависимостей по эмпирическим данным // Математические методы распознавания образов: 7-ая Всерос. конф. Тезисы докл. — Пущино, 1995. — С. 24–26.
Для оценивания качества обучения по прецедентам предлагается использовать комбинаторные функционалы типа скользящего контроля вместо принятых вероятностных функционалов. Для одного такого функционала доказывается оценка, аналогичная неравенствам Вапника-Червоненкиса, но при этом выборка не обязана быть случайной и независимой.
[4] Воронцов К. В.
Предварительная обработка данных для решения специального класса задач распознавания // ЖВМ и МФ. — 1995. — Т. 35, N° 10. — С. 1565–1575.
www.ccas.ru/frc/papers/voron95jvm.pdf
Рассматриваются алгоритмы предварительной обработки данных для прикладной задачи, описанной в [1].
[5] Vorontsov K. V.
Preliminary data processing for a special class of recognition problems // Comp. Maths Math. Phys. — 1995. — Vol. 35, no. 10. — Pp. 1259–1267.
www.ccas.ru/frc/papers/voron95jvm-eng.pdf
The English version of [4].
[6] Воронцов К. В.
О проблемно-ориентированной оптимизации базисов задач распознавания // ЖВМ и МФ. — 1998. — Т. 38, N° 5. — С. 870–880.
www.ccas.ru/frc/papers/voron98jvm.pdf
Предлагается оптимизационный метод построения алгоритмических композиций, основанный на алгебраическом подходе к проблеме распознавания. На каждом шаге метода в композицию добавляется один алгоритм, который настраивается по обучающей выборке совместно с корректирующей операцией. Подробно рассматривается случай монотонных корректирующих операций, для него доказывается сходимость метода. Вводится функционал качества алгоритма, равный числу дефектных пар обучающих объектов на заданной выборке. Описываются алгоритмы монотонизации выборки, необходимые для построения монотонной корректирующей операции.
[7] Vorontsov K. V.
The task-oriented optimization of bases in recognition problems // Comp. Maths Math. Phys. — 1998. — Vol. 38, no. 5. — Pp. 838–847.
www.ccas.ru/frc/papers/voron98jvm-eng.pdf
The English version of [6].
[8] Воронцов К. В.
Локальные базисы в алгебраическом подходе к проблеме распознавания. — Диссертация на соискание ученой степени к.ф.-м.н., М.: ВЦ РАН. — 1999.
www.ccas.ru/frc/thesis/VoronCanDisser.pdf
[9] Рудаков К. В., Воронцов К. В.
О методах оптимизации и монотонной коррекции в алгебраическом подходе к проблеме распознавания // Докл. РАН. — 1999. — Т. 367, N° 3. — С. 314–317.
www.ccas.ru/frc/papers/rudvoron99dan.pdf
Предлагается оптимизационный метод построения алгоритмических композиций, основанный на алгебраическом подходе к проблеме распознавания. Для построения композиции решается последовательность оптимизационных задач. На каждом шаге метода в композицию добавляется один алгоритм и перенастраивается корректирующая операция. Подробно рассматривается случай монотонных корректирующих операций. Описываются эффективные алгоритмы построения нелинейных монотонных корректирующих операций для задач распознавания и восстановления регрессии. Более подробное изложение и доказательства см. в [6, 10].
[10] Воронцов К. В.
Оптимизационные методы линейной и монотонной коррекции в алгебраическом подходе к проблеме распознавания // ЖВМ и МФ. — 2000. — Т. 40, N° 1. — С. 166–176.
www.ccas.ru/frc/papers/voron00jvm.pdf
Рассматривается оптимизационный метод построения алгоритмических композиций, основанный на алгебраическом подходе к проблеме распознавания. На каждом шаге метода в композицию добавляется один алгоритм, который настраивается по обучающей выборке совместно с корректирующей операцией. Предлагаются формулы пересчета весов и ответов на обучающих объектах, с помощью которых данная оптимизационная задача сводится к стандартной. Настройка алгоритма преследует две цели одновременно: аппроксимировать обучающую выборку и компенсировать совокупный дефект предыдущих алгоритмов. Вводится специальный параметр, позволяющий на каждом шаге перераспределять приоритет между этими двумя целями. Рассматриваются модификации метода, предназначенные для решения задач классификации и восстановления регрессии с использованием линейных и монотонных корректирующих операций.
[11] Воронцов К. В.
Язык и среда для описания и исследования алгоритмических суперпозиций // Искусственный Интеллект. — 2000. — N° 2. — С. 36–41.
Рассматриваются общие концепции нового инструментального средства, предназначенного для решения широкого класса задач обучения по прецедентам — среды и языка для разработки обучаемых алгоритмических композиций ASDIEL. Очерчен класс задач, для решения которых это средство предназначено, описана формальная модель данных, лежащая в его основе.
[12] Воронцов К. В.
Оценка качества монотонного решающего правила вне обучающей выборки // Интеллектуализация обработки информации: Тезисы докл. — Симферополь, 2002. — С. 24–26.
Приводится верхняя оценка функционала скользящего контроля для задачи классификации на два непересекающихся класса с монотонными решающими правилами. Данный класс имеет бесконечную емкость, тем не менее для него удается получить нетривиальную оценку качества, которая не превышает единицы даже в случае малых выборок. Полученная оценка не предполагает случайности и независимости выборки и не опирается на сложностные характеристики семейства алгоритмов.
[13] Воронцов К. В., Пшеничников С. Б.
Имитационное моделирование торгов: новая технология биржевых тренажеров // Индикатор. — 2002. — N° 2(42).
www.ccas.ru/frc/papers/voron02imitrade.pdf
В статье представляется биржевой тренажер Имитрейд, позволяющий освоить навыки биржевых операций в условиях, максимально приближенных к реальным торгам. В тренажере используется имитационная модель торгов, способная в точности воспроизводить реальную торговую сессию и адекватно реагировать на возмущающие воздействия обучаемых.
[14] Воронцов К. В.
Имитационное моделирование реальных биржевых торгов // ИММОД-2003: 1-ая Всеросс. конф.: Докл. — СПб., 2003. — С. 25–29.
www.ccas.ru/frc/papers/voron03imitrade.pdf
Рассматривается имитационная модель биржевых торгов, позволяющая детально воспроизводить реальные торговые сессии ММВБ. Для настройки модели используются методы распознавания образов. В докладе описываются основные свойства и строение модели, рассматривается биржевой тренажер Имитрейд и другие прикладные задачи, решаемые с помощью данной модели.
[15] Воронцов К. В.
Обзор современных исследований по проблеме качества обучения алгоритмов // Таврический вестник информатики и математики. — 2004.
www.ccas.ru/frc/papers/voron04twim.pdf
Обзор охватывает основные направления современных исследований феномена обобщающей способности, задача которых — уточнить сильно завышенные оценки статистической теории Вапника-Червоненкиса и предложить адекватные обоснования методов обучения по прецедентам. Выделяются следующие направления. 1. Оценивание эффективной сложности обучаемых алгоритмов, которая в ряде случаев оказывается существенно ниже теоретической. 2. Получение оценок, зависящих от отступов (margin) обучающих объектов в задачах классификации с пороговым решающим правилом. 3. Исследование обобщающей способности композиций алгоритмов, в том числе бустинга и баггинга. 4. Оценивание стабильности методов обучения (устойчивости относительно изменений обучающей выборки) и выявление взаимосвязей между стабильностью и обобщающей способностью. 5. Получение оценок качества для алгоритмов, выбираемых процедурой скользящего контроля. 6. Развитие комбинаторного подхода, обобщающего теорию Вапника-Червоненкиса. Библиография содержит 82 ссылки.
[16] Воронцов К. В.
Комбинаторные обоснования обучаемых алгоритмов // ЖВМиМФ. — 2004. — Т. 44, N° 11. — С. 2099–2112.
www.ccas.ru/frc/papers/voron04jvm.pdf
Рассматриваются комбинаторные функционалы качества обучения по прецедентам, основанные на принципе скользящего контроля. Выводятся их верхние оценки, более точные, чем оценки статистической теории Вапника-Червоненкиса, и при этом не предполагающие случайности и независимости исходных данных. Описывается эффект локализации семейства алгоритмов и вводится понятие локальной функции роста. С позиций комбинаторного подхода пересматриваются основные положения статистической теории. Анализируются основные причины завышенности сложностных оценок качества.
[17] Vorontsov K. V.
Combinatorial substantiation of learning algorithms // Comp. Maths Math. Phys. — 2004. — Vol. 44, no. 11. — Pp. 1997–2009.
www.ccas.ru/frc/papers/voron04jvm-eng.pdf
The English version of [16].
[18] Воронцов К. В.
Комбинаторные оценки качества обучения по прецедентам // Докл. РАН. — 2004. — Т. 394, N° 2. — С. 175–178.
www.ccas.ru/frc/papers/voron04qualdan.pdf
Рассматриваются функционалы скользящего контроля, характеризующие качество обучения алгоритмов по прецедентным эмпирическим данным. Приводятся верхние оценки этих функционалов, полученные без предположения случайности и независимости исходных данных. Описывается эффект локализации семейства алгоритмов и вводится понятие локальной функции роста. Рассматриваются основные причины завышенности известных вероятностных оценок качества. Развивается подход к оцениванию качества обучения, основанный на явном использовании априорной информации и не опирающийся на сложностные характеристики алгоритмов. Для задач классификации с универсальными ограничениями монотонности получены новые оценки качества, существенно более точные на малых выборках.
[19] Vorontsov K. V.
Combinatorial bounds for learning performance // Doklady Mathematics. — 2004. — Vol. 69, no. 1. — Pp. 145√–148.
www.ccas.ru/frc/papers/voron04qualdan-eng.pdf
The English version of [18].
[20] Воронцов К. В.
Комбинаторный подход к оценке качества обучаемых алгоритмов // Математические вопросы кибернетики / Под ред. О. Б. Лупанов. — М.: Физматлит, 2004. — Т. 13. — С. 5–36.
www.ccas.ru/frc/papers/voron04mpc.pdf
Излагаются основы комбинаторного подхода к проблеме оценивания качества восстановления зависимостей по эмпирическим данным. Для формализации понятия обобщающей способности вводятся комбинаторные функционалы скользящего контроля. Полученные комбинаторные оценки обобщают результаты статистической теории Вапника-Червоненкиса. При этом требования случайности исходных данных и равномерной сходимости частоты ошибок к их вероятности оказываются избыточными. Описывается эффект локализации семейства алгоритмов, благодаря которому семейства алгоритмов большой и даже бесконечной емкости могут обладать неплохой обучаемостью. С позиций комбинаторного подхода пересматриваются основные положения статистической теории. Выдвигается гипотеза о принципиальной завышенности сложностных оценок качества обучения. Исследуются два частных случая, в которых семейства алгоритмов имеют бесконечную емкость, тем не менее для них удается получить достаточно точные оценки качества обучения.
[21] Баринова О. В., Вальков А. С., Воронцов К. В., Громов С. А., Ефимов А. Н., Чехович Ю. В.
Система прогнозирования потребительского спроса Goods4Cast // Математические методы распознавания образов-12. — М.: МАКС Пресс, 2005. — С. 258–260.
www.ccas.ru/frc/papers/voron05goods4cast.pdf
Рассматривается задача прогнозирования потребительского спроса для розничной сети магазинов. Для прогнозирования используются быстрые алгоритмы, время настройки которых не более чем линейно по длине ряда. Для повышения качества прогнозов применяются адаптивные алгоритмические композиции, основанные на идеях алгебраического подхода. В качестве критерия настройки применяется неквадратичный несимметричный функционал потерь, оценивающий величину потерь в рублях от завышенного или заниженного прогноза. Предлагаемые алгоритмы реализованы в автоматизированной системе прогнозирования потребительского спроса Goods4Cast. Система строит прогнозы для 140 магазинов и 250000 товаров. Время расчета прогнозов для одного магазина около 5 минут на рабочей станции 2Xeon 3.2 ГГц.
[22] Кочедыков Д. А., Ивахненко А. А., Воронцов К. В.
Система кредитного скоринга на основе логических алгоритмов классификации // Математические методы распознавания образов-12. — М.: МАКС Пресс, 2005. — С. 349–353.
www.ccas.ru/frc/papers/voron05credit.pdf
Рассматривается задача кредитного скоринга, возникающая в кредитных организациях при принятии решений о выдаче кредитов. Перечисляются специфические особенности данной прикладной задачи, которые накладывают существенные ограничения на выбор модели алгоритма классификации и способы ее настройки. Для решения данной задачи предлагается использовать логические алгоритмы, основанные на поиске закономерностей в данных. Приводятся результаты экспериментального сравнения качества реализованных алгоритмов на реальных задачах выдачи кредитов. Кратко описывается архитекура программного комплекса ScoringAce.
[23] Романов М. Ю., Ументаев С. А., Кругов А. Е., Воронцов К. В.
Алгоритмы динамического обучения принятию решений в задаче формирования инвестиционного портфеля // Математические методы распознавания образов-12. — М.: МАКС Пресс, 2005. — С. 423–426.
www.ccas.ru/frc/papers/voron05portfolio.pdf
За последние 10–15 лет многие инвестиционные компании, хэдж-фонды, банки и частные инвесторы переходят на полностью автоматическое управление капиталом. Задача динамического формирования инвестиционного портфеля (on-line portfolio selection, PS) заключается в том, чтобы по мере поступления торговых данных автоматически подбирать набор активов (акций, фьючерсов, валют, и т. п.), оптимальный для вложения капитала. В настоящей работе задача PS рассматривается с позиций обучения по прецедентам. Строится высокоадаптивная система, обеспечивающая своевременное переключение с одного алгоритма на другой, а в более общем случае — построение композиции портфельных алгоритмов. Результаты тестирования на реальных данных американских фондовых бирж NYSE и NASDAQ показали, что система способна адаптироваться к рынку и обеспечивать достаточное качество на тех участках, где ни один из известных алгоритмов не дает стабильных результатов.
[24] Воронцов К. В., Каневский Д. Ю.
Коэволюционный метод обучения алгоритмических композиций // Таврический вестник информатики и математики. — 2005. — N° 2. — С. 51–66.
www.ccas.ru/frc/papers/voron05twim.pdf
Рассматривается новый метод построения алгоритмических композиций в задачах обучения по прецедентам. Данный метод является развитием идей алгебраического подхода к проблеме распознавания, а также методов бустинга, бэггинга и случайных подпространств. Для обучения базовых алгоритмов применяется специальный генетический алгоритм — кооперативная коэволюция. Метод является универсальным, то есть может применяться к любым семействам базовых алгоритмов, любым корректирующим операциям и любым методам их настройки. Эксперименты на реальных задачах классификации из репозитария UCI показывают, что данный метод позволяет строить композиции из малого числа алгоритмов, обладающие достаточно высокой обобщающей способностью.
[25] Воронцов К. В., Колосков А. О.
Профили компактности и выделение опорных объектов в метрических алгоритмах классификации // Искусственный Интеллект. — 2006. — С. 30–33.
www.ccas.ru/frc/papers/students/VoronKoloskov05mmro.pdf
Отбор опорных объектов (эталонов) в метрических алгоритмах классификации позволяет уменьшить объем хранимых данных, повысить скорость и качество классификации. В данной работе предлагается метод отбора, основанный на минимизации функционала полного скользящего контроля, вычисляемого по эффективной комбинаторной формуле. Метод основан на явной оптимизации профиля компактности выборки.
[26] Воронцов К. В., Рудаков К. В., Лексин В. А., Ефимов А. Н.
Выявление и визуализация метрических структур на множествах пользователей и ресурсов Интернет // Искусственный Интеллект. — 2006. — С. 285–288.
www.ccas.ru/frc/papers/voron05yandex.pdf
Для выявления предпочтений и информационных потребностей огромного числа пользователей по отношению к огромному числу ресурсов простейшая тактика «пользователи ресурса X посещают также множество ресурсов Y» представляется не вполне адекватной. Предлагается более тонкий анализ, основанный на принципе «схожи те пользователи, которые посещают схожие множества ресурсов, и схожи те ресурсы, на которые заходят схожие пользователи». На этом принципе построена технология анализа клиентских сред (АКС), разработанная в компании Форексис (www.forecsys.ru). В данной работе рассматривается применение АКС к обработке логов поисковой машины. Технология АКС позволяет решать задачи персонализации поиска, направленного предложения ресурсов пользователям, поиска схожих ресурсов и визуализации структуры Интернета в виде карт сходства.
[27] Воронцов К. В., Ивахненко А. А.
Эмпирические оценки локальной функции роста в задачах поиска логических закономерностей // Искусственный Интеллект. — 2006. — С. 281–284.
www.ccas.ru/frc/papers/students/VoronIvahnenko05mmro.pdf
Предлагается методика эмпирического оценивания эффективной локальной функции роста для семейств логических закономерностей. Результаты экспериментов позволяют выдвинуть гипотезу, что в реальных задачах классификации эффективная локальная функция роста имеет порядок единицы.
[28] Воронцов К. В., Егорова Е. В.
Динамически адаптируемые композиции алгоритмов прогнозирования // Искусственный Интеллект. — 2006. — С. 277–280.
www.ccas.ru/frc/papers/students/VoronEgorova05mmro.pdf
В статье рассматриваются три различных метода динамической перенастройки весов в линейных композициях алгоритмов прогнозирования. Экспериментально показано, что требование неотрицательности весов не только улучшает качество прогнозов, но и выступает в роли регуляризатора, повышая устойчивость композиции.
[29] Kanevskiy D. Y., Vorontsov K. V.
Cooperative coevolutionary ensemble learning // Multiple Classifier Systems: 7th International Workshop, Prague, Czech Republic, May 23-25, 2007. — Lecture Notes in Computer Science. Springer-Verlag, 2007. — Pp. 469–478.
www.ccas.ru/frc/papers/kanevskiy07ccel.pdf
[30] Воронцов К. В.
Слабая вероятностная аксиоматика и надежность эмпирических предсказаний // Математические методы распознавания образов-13. — М.: МАКС Пресс, 2007. — С. 21–25.
www.mmro.ru
Предлагается слабая вероятностная аксиоматика, существенно более простая, чем аксиоматика Колмогорова, в частности, не опирающаяся на теорию меры, но вполне достаточная для оценивания надежности эмпирических предсказаний. В рамках слабой аксиоматики доказаны аналоги таких фундаментальных фактов, как закон больших чисел, сходимость эмпирических функций распределения, многие ранговые критерии, оценки обобщающей способности алгоритмов классификации и регрессии.
[31] Ивахненко А. А., Воронцов К. В.
Верхние оценки переобученности и профили разнообразия логических закономерностей // Математические методы распознавания образов-13. — М.: МАКС Пресс, 2007. — С. 33–37.
www.mmro.ru
Логические алгоритмы классификации представляют собой композиции элементарных классификаторов, называемых также закономерностями. Существуют два противоположных подхода к повышению качества (обобщающей способности) таких алгоритмов: либо увеличение числа закономерностей в композиции, либо повышение качества закономерностей. Качество алгоритма в обоих случаях может оказаться сопоставимым, однако при втором подходе получаются более простые, легко интерпретируемые алгоритмы. В данной работе понятие обобщающей способности, которое обычно определяется для алгоритмов, распространяется на случай закономерностей. В рамках комбинаторного подхода [20] выводятся сложностные оценки качества закономерностей. Предлагается методика эмпирического измерения завышенности получаемых оценок, основанная на скользящем контроле.
[32] Кочедыков Д. А., Ивахненко А. А., Воронцов К. В.
Применение логических алгоритмов классификации в задачах кредитного скоринга и управления риском кредитного портфеля банка // Математические методы распознавания образов-13. — М.: МАКС Пресс, 2007. — С. 484–488.
www.mmro.ru
Рассматривается задача принятия решений о выдаче кредитов физическим лицам. Это стандартная задача классификации на два класса, имеющая следующие особенности: признаки разнотипны, в данных могут присутствовать пропуски и ошибки, объем обучающей выборки может быть крайне мал. Кроме того, наряду с классификацией клиента алгоритм должен выдавать оценку вероятности дефолта (probability of default, PD), т.,е. вероятности того, что клиент не вернет кредит или его часть. Оценки PD клиентов необходимы для анализа риска кредитного портфеля банка. В мировой практике кредитного скоринга широко применяется логистическая регрессия, в которой оценки PD получаются естественным образом. Однако, по сравнению с логическими алгоритмами, она хуже интерпретируема, требует заметно бóльших объемов обучающей выборки и основана на труднопроверяемых вероятностных предположениях. В данной работе предлагается метод оценивания PD клиента для логических алгоритмов, основанный на понятии переобученности.
[33] Венжега А. В., Ументаев С. А., Орлов А. А., Воронцов К. В.
Проблема переобучения при отборе признаков в линейной регрессии с фиксированными коэффициентами // Математические методы распознавания образов-13. — М.: МАКС Пресс, 2007. — С. 90–93.
www.mmro.ru
Проблема отбора информативных признаков часто возникает при решении задач классификации и прогнозирования. В условиях, когда обучающая выборка мала, а признаков много, увеличивается риск переобучения — найденная функция регрессии может допускать на новых данных существенно больше ошибок, чем на обучении. Это может быть связано как с неудачным отбором признаков, так и с переоптимизацией параметров модели. В данной работе рассматривается задача линейной регрессии, в которой коэффициенты регрессии фиксированы, т.,е. не настраиваются по обучающей выборке. Это позволяет исследовать переобучение, обусловленное исключительно отбором признаков. Данная регрессионная задача имеет ряд приложений в социологии и эконометрике.
[34] Лексин В. А., Воронцов К. В.
Анализ клиентских сред: выявление скрытых профилей и оценивание сходства клиентов и ресурсов // Математические методы распознавания образов-13. — М.: МАКС Пресс, 2007. — С. 488–491.
www.mmro.ru
Технология Анализа клиентских сред (АКС) основана на вычислении оценок сходства между ресурсами и между клиентами согласно принципу согласованности: «ресурсы схожи, если ими пользуются схожие клиенты; клиенты схожи, если они пользуются схожими ресурсами». В данной работе предлагается новый алгоритм АКС, основанный на выявлении интересов (скрытых профилей) клиентов и ресурсов. Алгоритм напоминает генеративные (generative model based) методы коллаборативной фильтрации (collaborative filtering), но отличается от них применением принципа согласованности.
[35] Ульянов Ф. М., Воронцов К. В.
Проблема переобучения функций близости при построении алгоритмов вычисления оценок // Математические методы распознавания образов-13. — М.: МАКС Пресс, 2007. — С. 105–108.
www.mmro.ru
Предлагается новый метод оптимизации параметров в модели АВО (алгоритмов вычисления оценок), использующий принцип выравнивания отступов, выделение нерелевантных объектов (выбросов) и оптимизацию системы опорных множеств методом случайного поиска с адаптацией. Предложенный алгоритм протестирован на 7 прикладных задачах классификации. Преимуществом метода является высокая обобщающая способность. В частности, в задаче распознавания участков генных последовательностей применение данного алгоритма позволило понизить частоту ошибок с 18% до 5.5%.
[36] Кузнецов М. Р., Туркин П. Ю., Воронцов К. В., Дьяконов А. Г., Ивахненко А. А., Сиваченко Е. А.
Прогнозирование результатов хирургического лечения атеросклероза на основе анализа клинических и иммунологических данных // Математические методы распознавания образов-13. — М.: МАКС Пресс, 2007. — С. 537–540.
www.mmro.ru
В данной работе решается задача прогнозирования результатов хирургического лечения атеросклероза артерий нижних конечностей. Это задача классификации на два класса (либо шунт приживется, либо нет), большой размерности (число признаков превышает число прецедентов), с разнотипными признаками, большим числом пропусков в данных и низкой точностью измерения признаков. Перечисленные особенности свойственны многим задачам медицинской диагностики. Отличительной особенностью данной задачи является то, что данные собираются из двух независимых источников: 18 признаков характеризуют гемодинамику вены, 17 признаков являются результатами иммунологического анализа. Совместный анализ этих данных позволяет впервые в практике изучения атеросклероза оценить влияние иммунных факторов и особенностей клеточных реакций на течение атеросклероза. В данной работе производится выбор наиболее точного метода классификации, способного «извлечь максимальную выгоду» из совмещения клинических и иммунологических данных.
[37] Воронцов К. В., Инякин А. С., Лисица А. В.
Система эмпирического измерения качества алгоритмов классификации // Математические методы распознавания образов-13. — М.: МАКС Пресс, 2007. — С. 577–580.
www.mmro.ru
Описывается комплексная методика измерения качества алгоритмов классификации, основанная на скользящем контроле. Она позволяет одновременно вычислять широкий спектр оценок, характеризующих различные аспекты обучаемости алгоритмов. В частности, оцениваются: средняя вариация, смещенность (степень неоптимальности) алгоритмической модели, профиль устойчивости, профиль разделимости выборки, профиль представительности объектов, профиль информативности признаков, и другие характеристики. Данную методику предполагается использовать в распределенной системе тестирования алгоритмов классификации. Система предоставляет доступ к задачам, методам и результатам тестирования через интуитивно понятный web-интерфейс. Система предназначена как для специалистов по анализу данных, так и для экспертов-прикладников. Она позволяет полностью автоматизировать типовое исследование, цель которого — выяснить, какой из известных методов лучше подходит для решения конкретной прикладной задачи классификации или класса задач.
[38] Vorontsov K. V.
Combinatorial probability and the tightness of generalization bounds // Pattern Recognition and Image Analysis. — 2008. — Vol. 18, no. 2. — Pp. 243–259.
www.springerlink.com/content/78537p01838123u7/
The English version of [48]. Accurate prediction of the generalization ability of a learning algorithm is an important problem in computational learning theory. The classical Vapnik-Chervonenkis (VC) generalization bounds are too general and therefore overestimate the expected error. Recently obtained data-dependent bounds are still overestimated. To find out why the bounds are loose, we reject the uniform convergence principle and apply a purely combinatorial approach that is free of any probabilistic assumptions, makes no approximations, and provides an empirical control of looseness. We introduce new data-dependent complexity measures: a local shatter coefficient and a nonscalar local shatter profile, which can give much tighter bounds than the classical VC shatter coefficient. An experiment on real datasets shows that the effective local measures may take very small values; thus, the effective local VC dimension takes values in [0,1] and therefore is not related to the dimension of the space.
[39] Vorontsov K. V.
On the influence of similarity of classifiers on the probability of overfitting // Pattern Recognition and Image Analysis: new information technologies (PRIA-9-2008). — Vol. 2. — Nizhni Novgorod, Russian Federation, 2008. — Pp. 303–306.
www.ccas.ru/frc/papers/voron08pria-conf-eng.pdf
The accurate bounding of the probability of overfitting stays a most challenging open problem in computational learning theory during last 40 years, starting with well known Vapnik-Chervonenkis (VC) theory. Recently obtained data-dependent bounds are still overestimated. This work being essentially experimental intends to find out a new direction of theoretical research. We show that the diversity of classifiers has a crucial influence on the probability of overfitting, so that tighter bounds can be obtained only by taking into account two effects simultaneously: the localization (also known as shell or splitting) of classifiers set and the similarity of classifiers.
[40] Leksin V. A., Vorontsov K. V.
The overfitting in probabilistic latent semantic models // Pattern Recognition and Image Analysis: new information technologies (PRIA-9-2008). — Vol. 1. — Nizhni Novgorod, Russian Federation, 2008. — Pp. 393–396.
www.ccas.ru/frc/papers/voron-leksin08pria-conf-eng.pdf
The symmetric EM algorithm is proposed for probabilistic latent semantic analysis in collaborative filtering. The algorithm allows to reveal the latent interest profiles of both users and items, then to easily construct high-quality similarity measures of all required types: user-user, item-item, and item-user. The advantage of the proposed approach is that different profiles are consistent to each other due to symmetry of the algorithm. To estimate the quality of profiles and similarity measures empirically we use a sample of labeled items and the kNN classifier. Experiment show that the excessive optimization is redundant and can lead to overfitting.
[41] Цюрмасто П. А., Воронцов К. В.
Анализ сходства алгоритмов классификации в оценках обобщающей способности // Интеллектуализация обработки информации (ИОИ-2008): Тезисы докл. — Симферополь: КНЦ НАН Украины, 2008. — С. 232–234.
www.ccas.ru/frc/papers/voron08tsurmasto.pdf
В рамках слабой вероятностной аксиоматики получена точная комбинаторная оценка вероятности переобучения для простого частного случая, когда семейство алгоритмов состоит только из двух элементов. Показано, что уже в этом случае имеет место эффект переобучения, причем вероятность переобучения можно уменьшать либо путем уменьшения различности векторов ошибок двух алгоритмов, либо путем увеличения разности их частот ошибок. Более сложный случай — цепочки алгоритмов — исследован экспериментально. Показано, что в этом случае свойства различности алгоритмов и расслоения семейства по частотам ошибок еще сильнее уменьшают вероятность переобучения.
[42] Воронцов К. В., Ивахненко А. А.
Мета-обучение критериев информативности логических закономерностей // Интеллектуализация обработки информации (ИОИ-2008): Тезисы докл. — Симферополь: КНЦ НАН Украины, 2008. — С. 52–54.
www.ccas.ru/frc/papers/voron08ivakhnenko.pdf
Логической закономерностью (или правилом) в данной работе называется предикат, заданный на множестве объектов, зависящий от небольшого числа признаков, выделяющий достаточно много объектов заданного класса и достаточно мало объектов всех остальных классов. Обычно для синтеза правил применяются эвристические алгоритмы дискретной оптимизации: поиск в глубину, поиск в ширину, адаптивный случайный поиск, эволюционный поиск, и др. В этих алгоритмах используются два критерия информативности правил: на стадии поиска оценивается перспективность дальнейшей модификации правила; на стадии финального отбора оценивается полезность правила в сочетании его с другими правилами. Известны десятки различных эвристических критериев перспективности и полезности правил. Оптимальными являются такие критерии, которые хорошо предсказывают обобщающую способность правила (частоту его ошибок на независимых контрольных данных). Теоретических оценок, способных давать достаточно точные предсказания, пока не существует. Несколько лет назад для оптимизации критериев перспективности и полезности стали применять эмпирическую методику, называемую мета-обучением. В последних работах Дж.,Фюрнкранца предлагается восстанавливать регрессионную зависимость обобщающей способности от частоты ошибок первого и второго рода, измеренной на обучающей выборке. При этом в роли объектов обучения выступают сотни тысяч всевозможных правил, найденных в ходе решения нескольких десятков реальных задач классификации. В данной работе предлагается усовершенствованная процедура мета-обучения, имеющая несколько существенных отличий от процедуры Фюрнкранца. Во-первых, в число регрессоров включаются оценки сложности правила: число правил, просмотренных в процессе перебора перед тем, как найдено данное правило; из них число правил с достаточно высокой точностью на обучающей выборке; число термов в правиле; коэффициент разнообразия (функция роста) множества правил с данным числом термов. Во-вторых, мета-обучение делается для каждой задачи и каждого класса в отдельности, чтобы учесть индивидуальные особенности задачи. В-третьих, вместо простейших жадных стратегий нисходящего поиска и покрытия выборки применяется «полужадный» поиск в ширину. В-четвертых, вид регрессионной модели выбирается исходя из известных сложностных оценок обобщающей способности (в работах Фюрнкранца для этого применялись нейронные сети или линейная регрессия). Эксперимент на 7 реальных задачах из репозитория UCI показал, что применение модифицированной процедуры мета-обучения повышает обобщающую способность как отдельных правил, так и их композиции. Использование информации о сложности правил, накопленной в процессе поиска, позволяет на несколько процентов точнее предсказывать обобщающую способность правил.
[43] Воронцов К. В., Инякин А. С., Стрижов В. В., Чехович Ю. В.
Machinelearning.ru — информационно-аналитический ресурс по проблемам машинного обучения и интеллектуального анализа данных // Интеллектуализация обработки информации (ИОИ-2008): Тезисы докл. — Симферополь: КНЦ НАН Украины, 2008. — С. 56–58.
www.ccas.ru/frc/papers/voron08machinelearning.pdf
Рассматривается созданный авторами вики-ресурс www.MachineLearning.ru и возможности его использования для организации удаленной совместной работы научных коллективов. Ресурс строится по принципам Википедии — свободной энциклопедии и обладает всеми ее основными возможностями и преимуществами. Содержимое ресурса создается научным сообществом и является общественным достоянием. В перспективе ресурс должен стать единым центром, в котором концентрируется научная информация, происходит обмен идеями, опытом и наработками, устанавливаются контакты и образуются научные сообщества, ведется работа с литературными источниками, документируются и обсуждаются текущие исследования, размещаются учебные материалы. Значительная часть рабочего времени ученого может проходить на страницах ресурса. Фактически, это инструмент, совмещающий в себе энциклопедию, научную конференцию, учебный семинар и блокнот для черновых записей. Современный инструмент, делающий научное знание общедоступным в момент его появления.
[44] Воронцов К. В., Инякин А. С., Лисица А. В., Романов М. Ю., Стрижов В. В., Хачай М. Ю., Чехович Ю. В.
Распределенная вычислительная система «полигон алгоритмов классификации» // Интеллектуализация обработки информации (ИОИ-2008): Тезисы докл. — Симферополь: КНЦ НАН Украины, 2008. — С. 54–56.
www.ccas.ru/frc/papers/voron08poligon.pdf
«Полигон» предназначен для массового тестирования алгоритмов классификации на реальных задачах и представления результатов тестирования через web-интерфейс. Задача классификации представляется в виде матрицы признаковых описаний объектов, в которой выделен целевой признак. Дополнительно могут задаваться типы признаков и матрица штрафов. База задач хранится централизованно на главном сервере «Полигона». Начальный набор задач формируется из репозитория UCI, кроме того, пользователи имеют возможность загружать свои задачи. Алгоритм классификации принимает на входе матрицу обучающей выборки, матрицу тестовой выборки, набор управляющих параметров. На выходе формируются матрицы классификаций обучающей и тестовой выборки. Алгоритмы реализуются в виде вычислительных модулей (plug-in) на удаленных вычислительных серверах, в соответствии с внутренними стандартами системы «Полигон». Методика тестирования основана на стандартной процедуре ntimes k-кратного скользящего контроля (ntimes k-fold cross-validation). Результаты классификации всех обучающих и контрольных подвыборок используются для вычисления набора показателей качества, существенно расширенного по сравнению с общепринятой методикой. Основной показатель качества — средняя частота ошибок на контроле, с доверительным интервалом. Кроме того, вычисляются: эмпирические распределения основного показателя и величины переобученности (разности частоты ошибок на обучении и контроле); ROC-кривые на обучении и контроле; разложение средней ошибки на вариацию и смещение (bias-variance); распределение вариации и смещения по объектам; эмпирическое распределение отступов (margin) на обучении и контроле для вещественнозначных классификаторов; профиль представительности объектов, позволяющий идентифицировать выбросы, профиль информативности объектов и признаков; показатели скорости обучения, и ряд других показателей и графиков. «Полигон» имеет ряд преимуществ в сравнении с WEKA, RapidMiner, R, Matlab и другими системами, применяемыми для тестирования алгоритмов машинного обучения. Во-первых, стандартные системы устанавливаются локально на компьютере пользователя, оставляя ему возможность модифицировать методику тестирования, задачи и алгоритмы. Поэтому эмпирические результаты, представляемые в разных статьях, оказываются различными и несопоставимыми, даже когда тестирование проводится на одних и тех задачах из репозитория UCI. Во-вторых, открытые системы WEKA и R не позволяют использовать коммерческие алгоритмы, хотя публикация результатов тестирования выгодна их владельцам. «Полигон» решает возникающие технические и юридические проблемы, так как алгоритмы остаются «на территории» их владельца. В-третьих, в «Полигоне» нет ограничений на язык программирования, на котором реализуются алгоритмы. WEKA и RapidMiner допускает только Java, что снижает скорость выполнения алгоритмов и затрудняет перенос в систему готовых алгоритмов, написанных на других языках. В-четвертых, к настоящему времени сложилась де факто стандартная методика тестирования, основанная на ntimes k-кратном скользящем контроле. «Полигон» существенно расширяет эту методику, вычисляя набор показателей, с разных сторон характеризующих качество алгоритмов.
[45] Ахуньянов И. Х., Воронцов К. В.
Метод опорных векторов с неотрицательными коэффициентами и его применения // Интеллектуализация обработки информации (ИОИ-2008): Тезисы докл. — Симферополь: КНЦ НАН Украины, 2008. — С. 18–19.
www.ccas.ru/frc/papers/voron08akhunianov.pdf
Разработан метод опорных векторов с неотрицательными коэффициентами (nnSVM) и рассмотрено несколько его применений для решения задач классификации. Первое применение — отбор информативных признаков в задачах классификации с априорной информацией о монотонном характере зависимости вероятности положительной классификации от всех или некоторых признаков. Второе применение — отбор минимального достаточного числа базовых алгоритмов и оптимизация весовых коэффициентов в линейных композициях алгоритмов классификации. В частности, метод может применяться для взвешенного голосования закономерностей (правил) в логических алгоритмах классификации. При этом автоматически отсеивается некоторое количество не достаточно информативных правил. Третье (наиболее интересное) применение — отбор минимального достаточного числа эталонных объектов в метрических алгоритмах классификации, таких как метод k ближайших соседей. В стандартном SVM все обучающие объекты делятся на три типа: опорные, нарушители (переходящие через границу разделяющей полосы) и неинформативные (не влияющие на вектор весов). В nnSVM оказывается уже 6 типов объектов, так как для каждого объекта появляются две новые возможности: либо объект является эталонным, либо объект не используется для классификации и его можно не хранить. Отметим, что понятия опорных и эталонных объектов существенно различаются. Эксперименты на модельных данных показали, что при определенных значениях двух управляющих параметров метода nnSVM отбирается небольшое число эталонных объектов. При этом качество классификации методом kNN по отобранным эталонам часто оказывается выше, чем у обычного kNN по полной выборке. Это можно объяснить тем, что nnSVM, как и стандартный SVM, основан на принципе максимизации зазора (maximum margin), что способствует повышению обобщающей способности.
[46] Каневский Д. Ю., Кудинов П. Ю., Воронцов К. В.
Прогнозирование с несимметричной функцией потерь при наличии стохастического тренда // Интеллектуализация обработки информации (ИОИ-2008): Тезисы докл. — Симферополь: КНЦ НАН Украины, 2008. — С. 113–115.
www.ccas.ru/frc/papers/voron08kanevskiy.pdf
При решении задач прогнозирования стандартной практикой является оценка математического ожидания прогнозируемой величины, что соответствует минимизации суммы квадратов ошибок прогноза. Существует целый ряд задач, в которых функция потерь отлична от квадратичной, и стандартный прогноз далек от оптимального. К ним относятся такие задачи, как макроэкономическое управление, где требуется тщательный учет рисков, и прогнозирование спроса, где ошибкам прогноза разного знака соответствуют разные экономические факторы. Задача оценивания плотности распределения прогноза ставилась многими исследователями, но это направление все еще занимает скромное место в обширной литературе по анализу временных рядов. Исследовались, главным образом, оценки качества построенной плотности распределения прогноза, но сама задача ее построения решена только для узкого класса временных рядов. В данной работе рассматривается новый подход к прогнозированию распределений, основанный на применении стандартных моделей, дающих точечные прогнозы. Предлагается строить временной ряд ошибок точечного алгоритма прогнозирования в режиме скользящего контроля. Анализ ошибок позволяет, во-первых, проверить корректность применения данного алгоритма прогнозирования к данному временному ряду с помощью стандартных статистических тестов. Во-вторых, в случае корректного выбора модели, эмпирическое распределение ошибок позволяет построить несмещенную оценку распределения прогноза. Для эффективной реализации данного подхода предлагается использовать широкий класс рекуррентных алгоритмов прогнозирования. Предложенный подход иллюстрируется построением класса моделей прогнозирования распределения для нестационарных временных рядов со стохастическим трендом. В качестве стандартных моделей, дающих точечные прогнозы, используются классические трендовые алгоритмы экспоненциального сглаживания — модели Хольта и Брауна. Работа предложенных алгоритмов прогнозирования плотности распределения демонстрируется на модельных временных рядах и реальных задачах прогнозирования потребительского спроса.
[47] Лебедева И. Е., Воронцов К. В.
Об одном методе статистически обоснованного сравнения временных рядов доходности паевых инвестиционных фондов // Интеллектуализация обработки информации (ИОИ-2008): Тезисы докл. — Симферополь: КНЦ НАН Украины, 2008. — С. 58–59.
www.ccas.ru/frc/papers/voron08lebedeva.pdf
В докладе рассматривается применение метода итерационной настройки (backfitting) для построения обобщенной линейной модели доходности паевого инвестиционного фонда. Предлагаемый метод статистически обоснован и не имеет эвристически задаваемых параметров, что делает его более удобным инструментом построения рейтингов фондов, по сравнению со стандартными методиками. Для проверки адекватности регрессионной модели применяется последовательность статистических тестов: сначала непараметрические тесты нулевого матожидания, стационарности, некоррелированности и нормальности регрессионных остатков. Если все эти тесты проходят (подтверждаются классические предположения многомерной линейной регрессии), то применяется серия более строгих параметрических тестов, основанных на гипотезе нормальности остатков. Если они также проходят, то линейная модель считается адекватной. На практике оказалось, что это происходит довольно редко (только для 10% фондов). В противном случае коэффициенты линейной модели заменяются медленно меняющимися функциями времени. Для их построения и применяется итерационная процедура backfitting, основанная на одномерном ядерном сглаживании. Ширину окна сглаживания предлагается выбирать максимальной, при которой модель успешно проходит всю совокупность статистических тестов.
[48] Воронцов К. В.
Комбинаторная вероятность и точность оценок обобщающей способности (оригинал статьи на русском языке) // Pattern Recognition and Image Analysis. — 2008.
www.ccas.ru/frc/papers/voron08pria.pdf
Вводится слабая вероятностная аксиоматика, не опирающаяся на теорию меры, в которой все вероятности непосредственно измеримы в эксперименте. Она полностью согласуется с сильной (колмогоровской) аксиоматикой, но область ее применимости ограничена задачами анализа данных. В рамках слабой аксиоматики рассматривается широкий класс задач эмпирического предсказания, включающий задачу предсказания частоты события (закон больших чисел) и задачу оценивания обобщающей способности (теория Вапника–Червоненкиса, ТВЧ). В слабой вероятностной аксиоматике оценки обобщающей способности выводятся для функционалов, построенных по принципу полного скользящего контроля. Это упрощает эмпирический анализ теоретических оценок, позволяет контролировать точность оценок, разделять и анализировать причины их завышенности. Предлагается эмпирическая методика для измерения степени завышенности, обусловленной каждой из причин. Теория обобщается для случая логических закономерностей, рассматривается алгоритм поиска закономерностей в виде информативных конъюнкций. Приводятся результаты эмпирического измерения завышенности оценок ТВЧ для набора реальных задач классификации из репозитория UCI. Оказывается, что в реальных задачах эффективная локальная емкость не превышает единицу.