Алгебраический подход к проблеме распознавания (Algebraic Approach to Machine Learning)

[1] Журавлев Ю. И.
Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. — 1978. — Т. 33. — С. 5–68.
www.ccas.ru/frc/papers/zhuravlev78prob33.pdf
Основополагающая работа по алгебраическому подходу к проблеме распознавания. Проводится анализ существующих моделей алгоритмов. Предлагается универсальная схема построения алгоритмов распознавания в виде суперпозиций алгоритмических операторов, корректирующих операций и решающих правил. Построение корректных алгоритмов указанного вида предлагается вести алгебраическими методами — путем синтеза базиса в алгебраическом замыкании модели алгоритмов и поиска алгоритма в виде разложения по базису. Такой подход позволяет отказаться от использования трудоемких оптимизационных процедур и обеспечить корректность алгоритма «по построению». Вводятся понятия разрешимости и регулярности задач распознавания и полноты моделей алгоритмов. Доказывается полнота некоторых алгебраических замыканий.
[2] Zhuravlev J. I.
An algebraic approach to recognition or classifications problems // Pattern Recognition and Image Analysis. — 1998. — Vol. 8, no. 1. — Pp. 59–100.
www.ccas.ru/frc/papers/zhuravlev78prob33-eng.pdf
The English version of [1].
[3] Журавлев Ю. И.
Корректные алгебры над множествами некорректных (эвристических) алгоритмов. Часть I // Кибернетика. — 1977. — N° 4. — С. 5–17.
[4] Журавлев Ю. И.
Корректные алгебры над множествами некорректных (эвристических) алгоритмов. Часть II // Кибернетика. — 1977. — N° 6. — С. 21–27.
[5] Журавлев Ю. И.
Корректные алгебры над множествами некорректных (эвристических) алгоритмов. Часть III // Кибернетика. — 1978. — N° 2. — С. 35–43.
[6] Журавлев Ю. И.
Об алгебраических методах в задачах распознавания и классификации // Распознавание, классификация, прогноз. — 1988. — Т. 1. — С. 9–16.
www.ccas.ru/frc/papers/zhuravlev88rkp.pdf
[7] Журавлев Ю. И., Гуревич И. Б.
Распознавание образов и распознавание изображений // Распознавание, классификация, прогноз. — 1989. — Т. 2. — С. 5–73.
www.ccas.ru/frc/papers/zhuravlev89gurevich.pdf
[8] Рязанов В. В., Сенько О. В.
О некоторых моделях голосования и методах их оптимизации // Распознавание, классификация, прогноз. — 1990. — Т. 3. — С. 106–145.
[9] Zhuravlev J. I., Gurevich I. B.
Pattern recognition and image recognition // Pattern Recognition and Image Analysis. — 1991. — Vol. 1, no. 2.
www.ccas.ru/frc/papers/zhuravlev91gurevich-eng.pdf
[10] Zhuravlev J. I.
Algebraic methods in recognition and classification problems // Pattern Recognition and Image Analysis. — 1991. — Vol. 1, no. 1.
www.ccas.ru/frc/papers/zhuravlev90pria-eng.pdf
[11] Zhuravlev J. I.
Algebraic methods for designing algorithms for pattern recognition and forecasting // Pattern Recognition and Image Analysis. — 1999. — Vol. 9, no. 4. — Pp. 790–791.
www.ccas.ru/frc/papers/zhuravlev99pria-eng.pdf
[12] Рудаков К. В.
О числе гиперплоскостей, разделяющих конечные множества в евклидовом пространстве // ДАН СССР. — 1976. — Т. 231, N° 6. — С. 1296–1299.
[13] Рудаков К. В.
О корректности алгоритмов распознавания типа потенциальных функций // ЖВМиМФ. — 1980. — Т. 20, N° 3. — С. 738–744.
www.ccas.ru/frc/papers/rudakov80correct.pdf
[14] Рудаков К. В.
О некоторых универсальных ограничениях для алгоритмов классификации // ЖВМиМФ. — 1986. — Т. 26, N° 11. — С. 1719–1730.
www.ccas.ru/frc/papers/rudakov86universal.pdf
[15] Рудаков К. В.
О симметрических и функциональных ограничениях для алгоритмов классификации // ДАН СССР. — 1987. — Т. 297, N° 1. — С. 43–46.
www.ccas.ru/frc/papers/rudakov87dan.pdf
[16] Rudakov K. V.
On symmetric and functional restrictions for classification algorithms // Soviet Math. Dokl. — 1988. — Vol. 36, no. 3. — Pp. 428–431.
www.ccas.ru/frc/papers/rudakov87dan-eng.pdf
The English version of [15].
[17] Рудаков К. В.
Универсальные и локальные ограничения в проблеме коррекции эвристических алгоритмов // Кибернетика. — 1987. — N° 2. — С. 30–35.
www.ccas.ru/frc/papers/rudakov87universal.pdf
[18] Рудаков К. В.
Полнота и универсальные ограничения в проблеме коррекции эвристических алгоритмов классификации // Кибернетика. — 1987. — N° 3. — С. 106–109.
[19] Рудаков К. В.
Симметрические и функциональные ограничения в проблеме коррекции эвристических алгоритмов классификации // Кибернетика. — 1987. — N° 4. — С. 73–77.
www.ccas.ru/frc/papers/rudakov87symmetr.pdf
[20] Рудаков К. В.
О применении универсальных ограничений при исследовании алгоритмов классификации // Кибернетика. — 1988. — N° 1. — С. 1–5.
www.ccas.ru/frc/papers/rudakov88universal.pdf
[21] Журавлев Ю. И., Рудаков К. В.
Об алгебраической коррекции процедур обработки (преобразования) информации // Проблемы прикладной математики и информатики. — 1987. — С. 187–198.
www.ccas.ru/frc/papers/zhurrud87correct.pdf
[22] Рудаков К. В., Трофимов С. В.
Алгоритм синтеза корректных процедур распознавания для задач с непересекающимися классами // ЖВМиМФ. — 1988. — Т. 28, N° 9. — С. 1431–1434.
www.ccas.ru/frc/papers/rudakov88trofim.pdf
[23] Рудаков К. В.
Об алгебраической теории универсальных и локальных ограничений для задач классификации // Распознавание, Классификация, Прогноз. — 1988. — Т. 1. — С. 176–200.
www.ccas.ru/frc/papers/rudakov88rkp.pdf
[24] Рудаков К. В., Воронцов К. В.
О методах оптимизации и монотонной коррекции в алгебраическом подходе к проблеме распознавания // Докл. РАН. — 1999. — Т. 367, N° 3. — С. 314–317.
www.ccas.ru/frc/papers/rudvoron99dan.pdf
Предлагается оптимизационный метод построения алгоритмических композиций, основанный на алгебраическом подходе к проблеме распознавания. Для построения композиции решается последовательность оптимизационных задач. На каждом шаге метода в композицию добавляется один алгоритм и перенастраивается корректирующая операция. Подробно рассматривается случай монотонных корректирующих операций. Описываются эффективные алгоритмы построения нелинейных монотонных корректирующих операций для задач распознавания и восстановления регрессии. Более подробное изложение и доказательства см. в [26, 28].
[25] Rudakov K. V., Vorontsov K. V.
Methods of optimization and monotone correction in the algebraic approach to the recognition problem // Doklady Mathematics. — 1999. — Vol. 60, no. 1. — P. 139.
The English version of [24].
[26] Воронцов К. В.
О проблемно-ориентированной оптимизации базисов задач распознавания // ЖВМ и МФ. — 1998. — Т. 38, N° 5. — С. 870–880.
www.ccas.ru/frc/papers/voron98jvm.pdf
Предлагается оптимизационный метод построения алгоритмических композиций, основанный на алгебраическом подходе к проблеме распознавания. На каждом шаге метода в композицию добавляется один алгоритм, который настраивается по обучающей выборке совместно с корректирующей операцией. Подробно рассматривается случай монотонных корректирующих операций, для него доказывается сходимость метода. Вводится функционал качества алгоритма, равный числу дефектных пар обучающих объектов на заданной выборке. Описываются алгоритмы монотонизации выборки, необходимые для построения монотонной корректирующей операции.
[27] 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 [26].
[28] Воронцов К. В.
Оптимизационные методы линейной и монотонной коррекции в алгебраическом подходе к проблеме распознавания // ЖВМ и МФ. — 2000. — Т. 40, N° 1. — С. 166–176.
www.ccas.ru/frc/papers/voron00jvm.pdf
Рассматривается оптимизационный метод построения алгоритмических композиций, основанный на алгебраическом подходе к проблеме распознавания. На каждом шаге метода в композицию добавляется один алгоритм, который настраивается по обучающей выборке совместно с корректирующей операцией. Предлагаются формулы пересчета весов и ответов на обучающих объектах, с помощью которых данная оптимизационная задача сводится к стандартной. Настройка алгоритма преследует две цели одновременно: аппроксимировать обучающую выборку и компенсировать совокупный дефект предыдущих алгоритмов. Вводится специальный параметр, позволяющий на каждом шаге перераспределять приоритет между этими двумя целями. Рассматриваются модификации метода, предназначенные для решения задач классификации и восстановления регрессии с использованием линейных и монотонных корректирующих операций.
[29] Рудаков К. В., Чехович Ю. В.
Алгебраический подход к проблеме синтеза обучаемых алгоритмов выделения трендов // Доклады РАН. — 2003. — Т. 388, N° 1. — С. 33–36.
www.ccas.ru/frc/papers/rudakov03chehovich.pdf
[30] Rudakov K. V., Chehovich J. V.
Algebraic approach to the problem of synthesis of trainable algorithms for trend revealing // Doklady Mathematics. — 2003. — Vol. 67, no. 1. — Pp. 127–130.
www.ccas.ru/frc/papers/rudakov03chehovich-eng.pdf
The English version of [29].
[31] Рудаков К. В., Чехович Ю. В.
Критерии полноты моделей алгоритмов и семейств решающих правил для задач классификации с теоретико-множественными ограничениями // Доклады РАН. — 2004. — Т. 394, N° 4. — С. ?
www.ccas.ru/frc/papers/rudakov04chehovich-dan1.pdf
В контексте алгебраического подхода к синтезу корректных алгоритмов распознавания образов, классификации и прогнозирования рассматривается класс задач, характеризующийся наличием явным образом заданных теоретико-множественных ограничений на множество допустимых ответов алгоритма.
[32] Rudakov K. V., Chehovich J. V.
Completeness criteria for models of algorithms and decision rule classes in classification problem with set-theoretic constraints // Doklady Mathematics. — 2004. — Vol. 69, no. 1. — Pp. 149–151.
www.ccas.ru/frc/papers/rudakov04chehovich-dan1-eng.pdf
The English version of [31].
[33] Рудаков К. В.
Алгебраическая теория универсальных и локальных ограничений для алгоритмов распознавания. — Диссертация на соискание ученой степени д.ф.-м.н., М.: ВЦ РАН. — 1992.
www.ccas.ru/frc/thesis/RudakovDocDisser.pdf
[34] Рудаков К. В.
Алгебраическая теория универсальных и локальных ограничений для алгоритмов распознавания. — Автореферат диссертации на соискание ученой степени д.ф.-м.н., М.: ВЦ РАН. — 1992.
www.ccas.ru/frc/thesis/RudakovDocAutoref.pdf
[35] Воронцов К. В.
Локальные базисы в алгебраическом подходе к проблеме распознавания. — Диссертация на соискание ученой степени к.ф.-м.н., М.: ВЦ РАН. — 1999.
www.ccas.ru/frc/thesis/VoronCanDisser.pdf
[36] Воронцов К. В.
Локальные базисы в алгебраическом подходе к проблеме распознавания. — Автореферат диссертации на соискание ученой степени к.ф.-м.н., М.: ВЦ РАН. — 1999.
www.ccas.ru/frc/thesis/VoronCanAutoref.pdf
[37] Чехович Ю. В.
Элементы алгебраической теории синтеза обучаемых алгоритмов выделения трендов. — Диссертация на соискание ученой степени к.ф.-м.н., М.: ВЦ РАН. — 2003.
www.ccas.ru/frc/thesis/ChehovichCanDisser.pdf
[38] Воронцов К. В.
Проблемно-ориентированные методы алгебраического подхода. — 2002.
www.ccas.ru/frc/papers/voron02po4.pdf
Конспект 4 лекций, прочитанных в 2001–2003 г.г. на кафедре Математических методов прогнозирования ВМиК МГУ в дополнение к курсу К. В. Рудакова «Математические методы классификации и прогнозирования».
[39] Shibzukhov Z. M.
Correct sigma-pi extensions of one admissible class of algorithms // Doklady Mathematics. — 2004. — Vol. 69, no. 1. — Pp. 152–154.
www.ccas.ru/frc/papers/shibzukhov04dan-eng.pdf

Логические алгоритмы классификации (Rule Induction)

[40] Вайнцвайг М. Н.
Алгоритм обучения распознаванию образов «кора» // Алгоритмы обучения распознаванию образов / Под ред. В. Н. Вапник. — М.: Советское радио, 1973. — С. 110–116.
[41] Полякова М. П., Вайнцвайг М. Н.
Об использовании метода «голосования» признаков в алгоритмах распознавания // Моделирование обучения и поведения. — М., 1975. — С. 25≈28.
[42] Dubner P. N.
Statistical tests for feature selection in KORA recognition algorithms // Pattern Recognition and Image Analysis. — 1994. — Vol. 4, no. 4. — P. 396.
[43] Ryazanov V. V.
Recognition algorithms based on local optimality criteria // Pattern Recognition and Image Analysis. — 1994. — Vol. 4, no. 2. — Pp. 98–109.
[44] Djukova E. V., Zhuravlev J. I., Rudakov K. V.
Algebraic-logic synthesis of correct recognition procedures based on elementary algorithms // Computational Mathematics and Mathematical Physics. — 1996. — Vol. 36, no. 8. — Pp. 1161–1167.
www.ccas.ru/frc/papers/djukova96jvm-eng.pdf
[45] Djukova E. V., Zhuravlev J. I.
Discrete methods of information analysis in recognition and algorithms synthesis // Pattern Recognition and Image Analysis. — 1997. — Vol. 7, no. 2. — Pp. 192–207.
www.ccas.ru/frc/papers/djukova97discrete.pdf
[46] Дюкова Е. В., Инякин А. С.
Задача таксономии и тупиковые покрытия целочисленной матрицы. — М.: ВЦ РАН, 2003. — 25 с.
www.ccas.ru/frc/papers/djukova01taxon.pdf
[47] Kirnos E. A., Pyt'ev Y. P., Djukova E. V.
Training kora-type algorithms // Pattern Recognition and Image Analysis. — 2002. — Vol. 12, no. 1. — Pp. 19–25.
www.ccas.ru/frc/papers/djukova01training.pdf
[48] Djukova E. V., Peskov N. V.
Selection of typical objects in classes for recognition problems // Pattern Recognition and Image Analysis. — 2002. — Vol. 12, no. 3. — P. 243√249.
www.ccas.ru/frc/papers/djukova02selection.pdf
[49] Дюкова Е. В., Песков Н. В.
Поиск информативных фрагментов описаний объектов в дискретных процедурах распознавания // ЖВМиМФ. — 2002. — Т. 42, N° 5. — С. 741–753.
www.ccas.ru/frc/papers/djukova02poisk.pdf
[50] Djukova E. V.
Discrete recognition procedures: The complexity of realization // Pattern Recognition and Image Analysis. — 2003. — Vol. 13, no. 1. — Pp. 8–10.
www.ccas.ru/frc/papers/djukova03discrete.pdf
[51] Djukova E. V., Inyakin A. S., Peskov N. V.
Recent trends in discrete analysis of information in recognition problems // Pattern Recognition and Image Analysis. — 2003. — Vol. 13, no. 1. — Pp. 11–13.
www.ccas.ru/frc/papers/djukova03recent.pdf
[52] Djukova E. V.
Discrete (logic) recognition procedures: Principles of construction, complexity of realization, and basic models // Pattern Recognition and Image Analysis. — 2003. — Vol. 13, no. 1. — Pp. 417–425.
www.ccas.ru/frc/papers/djukova03discretelogic.pdf
[53] Djukova E. V., Inyakin A. S., Peskov N. V.
Methods of combinatorial analysis in synthesis of efficient recognition algorithms // Pattern Recognition and Image Analysis. — 2003. — Vol. 13, no. 3. — Pp. 426–432.
www.ccas.ru/frc/papers/djukova03methods.pdf
[54] Дюкова Е. В.
Дискретные (логические) процедуры распознавания: принципы конструирования, сложность реализации и основные модели. — М.: Прометей, 2003. — 29 с. — Учебное пособие для студентов математических факультетов педвузов.
www.ccas.ru/frc/papers/djukova03mp.pdf
В учебном пособии изложены общие принципы, лежащие в основе дискретного подхода к задачам распознавания, центральной проблемой которого является поиск информативных фрагментов признаковых описаний объектов. При поиске информативных фрагментов используется аппарат логических функций, в частности методы преобразования нормальных форм булевых функций, а также теория покрытий булевых и целочисленных матриц. Рассматриваются основные модели дискретных (логических) процедур распознавания и изучаются вопросы, связанные со сложностью их реализации.
[55] Дюкова Е. В.
Дискретные (логические) процедуры распознавания: принципы конструирования, сложность реализации и основные модели. — 2003. — Приложение к учебному пособию.
www.ccas.ru/frc/papers/djukova03appendix.pdf
[56] Дюкова Е. В., Инякин А. С.
О процедурах классификации, основанных на построении покрытий классов // ЖВМиМФ. — 2003. — Т. 43, N° 12. — С. 1910–1921.
www.ccas.ru/frc/papers/djukova03covering.pdf
[57] Djukova E. V., Inyakin A. S.
Classification procedures based on the construction of class coverings // Computational Mathematics and Mathematical Physics. — 2003. — Vol. 43, no. 12. — P. 1812√1822.
www.ccas.ru/frc/papers/djukova03covering-eng.pdf
The English version of [56].
[58] Дюкова Е. В.
О числе тупиковых покрытий целочисленной матрицы // ЖВМиМФ. — 2005. — Vol. 45, no. 5. — Pp. 935–940.
www.ccas.ru/frc/papers/djukova05number.pdf
[59] Djukova E. V.
On the number of irreducible coverings of an integer matrix // Computational Mathematics and Mathematical Physics. — 2005. — Vol. 45, no. 5. — Pp. 903–908.
www.ccas.ru/frc/papers/djukova05number-eng.pdf
The English version of [58].
[60] Песков Н. В.
Поиск информативных фрагментов описаний объектов в задачах распознавания. — Диссертация на соискание ученой степени к.ф.-м.н., М.: ВЦ РАН. — 2004.
www.ccas.ru/frc/thesis/PeskovCanDisser.pdf
[61] Песков Н. В.
Поиск информативных фрагментов описаний объектов в задачах распознавания. — Автореферат диссертации на соискание ученой степени к.ф.-м.н., М.: ВЦ РАН. — 2004.
www.ccas.ru/frc/thesis/PeskovCanAutoref.pdf
[62] Дюкова Е. В., Песков Н. В.
Построение распознающих процедур на базе элементарных классификаторов // Математические вопросы кибернетики / Под ред. О. Б. Лупанов. — М.: Физматлит, 2005. — Т. 14.
www.ccas.ru/frc/papers/djukova05construction.pdf
[63] Djukova E. V., Inyakin A. S., Peskov N. V., Sakharov A. A.
Combinatorial (logical) data analysis in pattern recognition problems // Pattern Recognition and Image Analysis. — 2005. — Vol. 15, no. 1. — Pp. 46–48.
www.ccas.ru/frc/papers/djukova05combinatorial.pdf
[64] Dem▓yanov E. A., Djukova E. V., Inyakin A. S., Peskov N. V.
An analysis of the results of polls with the aim of classifying the regions of the russian federation // Pattern Recognition and Image Analysis. — 2005. — Vol. 15, no. 2. — Pp. 536–538.
www.ccas.ru/frc/papers/djukova05polls.pdf
[65] Djukova E. V., Inyakin A. S., Peskov N. V., Sakharov A. A.
Increasing the efficiency of combinatorial logical data analysis in recognition and classification problems // Pattern Recognition and Image Analysis. — 2005. — Vol. 16, no. 4. — Pp. 707–711.
www.ccas.ru/frc/papers/djukova06increasing.pdf
[66] Журавлев Ю. И.
Об алгоритмах распознавания с представительными наборами (о логических алгоритмах) // ЖВМиМФ. — 2002. — Т. 42, N° 9. — С. 1425–1435.
www.ccas.ru/frc/papers/zhuravlev02jvm.pdf
[67] Zhuravlev J. I.
Recognition algorithms with representative sets // Computational Mathematics and Mathematical Physics. — 2002. — Vol. 42, no. 9. — Pp. 1372–1382.
www.ccas.ru/frc/papers/zhuravlev02jvm-eng.pdf
The English version of [66].
[68] Ryazanov V. V., Sen'ko O. V., Zhuravlev J. I.
Methods for recognition and prediction based on the voting procedures // Pattern Recognition and Image Analysis. — 1999. — Vol. 9, no. 4. — Pp. 713–718.
www.ccas.ru/frc/papers/ryazanov99pria-eng.pdf
[69] Сенько О. В.
Перестановочный тест в методе оптимальных разбиений // ЖВМиМФ. — 2003. — Т. 43, N° 9. — С. 1438–1447.
www.ccas.ru/frc/papers/senko03jvm.pdf
[70] Frank E., Witten I. H.
Generating accurate rule sets without global optimization // Proc. 15th International Conf. on Machine Learning. — Morgan Kaufmann, San Francisco, CA, 1998. — Pp. 144–151.
citeseer.ist.psu.edu/frank98generating.html
[71] Cohen W. W.
Fast effective rule induction // Proc. of the 12th International Conference on Machine Learning, Tahoe City, CA. — Morgan Kaufmann, 1995. — Pp. 115–123.
citeseer.ist.psu.edu/cohen95fast.html
RIPPERk (Repeated Iterative Pruning to Produce Error Reduction) — простой и эффективный алгоритм построения покрывающего набора (решающего списка) конъюнкций. Алгоритм имеет столь же высокую обобщающую способность, как C4.5rules и столь же высокую эффективность, как IREP. Объем вычислений практически линеен по длине обучающей выборки, что позволяет обрабатывать сотни тысяч объектов за приемлемое время. Алгоритм RIPPERk отличается от IREP тремя модификациями. 1. Изменен эвристический критерий, оптимизируемый при редукции правил. 2. Введен новый критерий останова, основанный на принципе минимума длины описания (MDL). 3. Построенные правила поочередно перестраиваются k раз. Эмпирическое сравнение всех упомянутых алгоритмов проведено на 22 реальных задачах из репозитория UCI.
[72] Cohen W. W., Singer Y.
A simple, fast and effective rule learner // Proc. of the 16 National Conference on Artificial Intelligence. — 1999. — Pp. 335–342.
citeseer.ist.psu.edu/198445.html
SLIPPER (Simple Learner with Iterative Pruning to Produce Error Reduction) — простой и эффективный алгоритм классификации, основанный на взвешенном голосовании конъюнкций. Для построения набора конъюнкций используется бустинг. В роли слабого классификатора может выступать произвольный жадный алгоритм синтеза конъюнкций. Конъюнкции наращиваются по случайной подвыборке, составляющей порядка 2/3 данных, затем редуцируются по оставшейся части данных. Описаны эксперименты по проверке алгоритма на наборе из 32 реальных задач, причем только половина задач использовалась на этапе разработки алгоритма, на остальных производилось финальное тестирование. Точность SLIPPER оказалась несколько выше, чем у алгоритмов RIPPER, C4.5, C5.0, а скорость — на порядок ниже, но в пределах mln m, где m — длина выборки. Среднее (по задачам) количество конъюнкций — втрое больше, чем у RIPPER.
[73] Ruckert U., Kramer S.
Towards tight bounds for rule learning // Proc. 21th International Conference on Machine Learning, Banff, Canada. — 2004. — P. ??
www.machinelearning.org/icml2004_proc.html
Предлагается алгоритм взвешенного голосования над логическими правилами, имеющими вид конъюнкций простых логических условий. Для построения конъюнкций используется «жадный» алгоритм стохастического локального поиска (SLS). Веса правил рассматриваются как апостериорное распределение вероятностей, индуцированное методом обучения. Для вычисления весов правил используется подход, аналогичный [196] — вес экспоненциально убывает с ростом числа ошибок, допущенных правилом. Для предложенного алгоритма удается вывести достаточно точные численные оценки обобщающей способности. За основу взята теорема МакАллестера [74], доказанная в рамках байесовской PAC-теории. Показано, что оценки могут быть улучшены, если разрешить алгоритмам отказываться от классификации. Эксперименты на реальных данных (35 задач из репозитория UCI) подтверждают, что алгоритм сравним по качеству с лучшими логическими алгоритмами классификации SVM, PART, JRIP, а также баггингом над PART и JRIP. Сопоставление оценок вероятности ошибки с 10-кратным скользящим контролем показывает, что оценки завышены всего лишь в 2–5 раз. Это лучше, чем для машин покрывающих множеств (SCM) Маршанда [354]. Таким образом, полученные оценки обобщающей способности являются одними из наиболее точных на момент выхода статьи.
[74] McAllester D.
PAC-bayesian model averaging // COLT: Proceedings of the Workshop on Computational Learning Theory. — Morgan Kaufmann Publishers, 1999.
citeseer.ist.psu.edu/mcallester99pacbayesian.html
[75] Au W.-H., Chan K. C. C., Yao X.
A novel evolutionary data mining algorithm with applications to churn prediction // IEEE Trans. Evolutionary Computation. — 2003. — Vol. 7, no. 6. — Pp. 532–545.
dblp.uni-trier.de
[76] Fürnkranz J.
Modeling rule precision // LWA / Ed. by A. Abecker, S. Bickel, U. Brefeld, I. Drost, N. Henze, O. Herden, M. Minor et al. — Humbold-Universitat Berlin, 2004. — Pp. 147–154.
http://dblp.uni-trier.de/db/conf/lwa/lwa2004.html#Furnkranz04
Рассматриваются алгоритмы обучения логических правил (rule learning), основанные на «жадных» стратегиях нисходящего поиска и покрытия выборки. Точность правила (rule precision) определяется как отношение числа покрытых объектов своего класса к числу всех покрытых правилом объектов. Строится эмпирическая зависимость точности правил на контрольной выборке от их точности на обучающей выборке. Для этого формируется мета-выборка, объектами которой являются все правила, найденные алгоритмом поиска в 27 задачах классификации из репозитория UCI, всего около 114 тысяч правил. Одномерная регрессионная задача мета-обучения (meta-learning) решается с помощью нейронной сети с 5 нейронами в скрытом слое. Найденная зависимость используется при поиске правил на обучающей выборке вместо обычного критерия качества правил. Экспериментаы показывают, что это приводит к улучшению обобщающей способности правил, то есть увеличению их точности на тестовых данных. Тестирование проводится на 10 задачах из репозитория UCI, не использовавшихся для мета-обучения.
[77] Fürnkranz J., Flach P. A.
Roc `n' rule learning-towards a better understanding of covering algorithms // Machine Learning. — 2005. — Vol. 58, no. 1. — Pp. 39–77.
http://dblp.uni-trier.de/db/journals/ml/ml58.html#FurnkranzF05
Рассматриваются алгоритмы обучения логических правил (rule learning), основанные на «жадных» стратегиях нисходящего поиска и покрытия выборки. Статья носит в занчительной степени обзорный характер — в ней собрано и рассмотрено около 20 различных эвристических критериев, используемых для поиска и отбора правил. Для визуализации процесса постепенного улучшения правила предлагается использовать график в осях (n,p), названный coverage space или NP-space, где n и p — число отрицательных и положительных примеров, покрытых правилом. Эти графики можно также рассматривать как ROC-кривые. Анализ показывает, что все критерии делятся на две большие группы: одни максимизируют площать под ROC-кривой, тем самым избегая априорных предположений о различиях в цене ошибки классов; другие в явном виде учитывают эти различия. Рассматривается m-оценка, обобщающая обе эти стратегии. Показано, что критерий CN2 (значимость отличия правила от случайного классификатора), не позволяет избежать переобучения. Показаны недостатки критерия Foil, основанного на принципе минимума длины описания (MDL). Основной вывод работы: стратерии предварительного усечения правил (pre-pruning) еще не достаточно хорошо изучены.
[78] Janssen F., Fürnkranz J.
On trading off consistency and coverage in inductive rule learning // LWA / Ed. by K.-D. Althoff, M. Schaaf. — Vol. 1. — University of Hildesheim, Institute of Computer Science, 2006. — Pp. 306–313.
http://dblp.uni-trier.de/db/conf/lwa/lwa2006.html#JanssenF06
Рассматриваются алгоритмы обучения логических правил (rule learning), основанные на «жадной» стратегии «разделяй и властвуй» (нисходящего поиска и покрытия выборки). Ставится задача построения оптимального эвристического критерия качества правил, позволяющего по обучающим данным находить правила, обладающие высокой точностью на контрольных данных (обобщающей способностью). Рассматриваются критерии вида h(n,p), где n и p — число отрицательных и положительных примеров, покрытых правилом. Рассматривается 8 различных критериев. Три из них имеют управляющий параметр, изменяющий стратегию поиска правил либо в сторону увеличения числа покрываемых объектов, либо в сторону уменьшения числа ошибок. Для определения оптимального значения этого параметра производится мета-обучение (meta-learning) по мета-выборке, составленной из всех правил, найденных в 27 реальных задачах классификации из репозитория UCI. Интересно, что все три параметрических критерия при оптимальном значении параметра оказываются схожими. Использование параметрических критериев с оптимальным значением параметра позволяет повысить качество классификации до уровня алгоритма RIPPER, причем без применения трудоемких процедур усечения (pruning).
[79] Janssen F., Fürnkranz J.
Meta-learning rule learning heuristics // LWA / Ed. by A. Hinneburg. — Martin-Luther-University Halle-Wittenberg, 2007. — Pp. 167–174.
http://dblp.uni-trier.de/db/conf/lwa/lwa2007.html#JanssenF07
Рассматриваются алгоритмы обучения логических правил (rule learning), основанные на «жадных» стратегиях нисходящего поиска и покрытия выборки. Ставится задача мета-обучения критерия качества правил по выборке всех правил, найденных в 27 задачах классификации из репозитория UCI. Оптимальный критерий должен на входе получать характеристики n и p (число отрицательных и положительных примеров, покрытых правилом) на обучающей выборке; а на выходе давать оценку обобщающей способности правила, то есть оценку n и p на неизвестной контрольной выборке. Эта зависимость восстанавливается с помощью линейной регрессии или сигмоидной нейронной сети с 1, 5 или 10 нейронами в скрытом слое. Данная работа отличается от предыдущих % [76, 78] тем, что теперь при мета-обучении зависимой переменной является не точность правила на контроле, а точность лучшего из всех правил, полученных из данного путем жадного наращивания. Эксперимент на 30 задачах из UCI, не использованных для мета-обучения, показал, что обученный критерий строит классификаторы более высокого качества.

Алгоритмы вычисления оценок (Estimates Calculation Algorithms)

[80] Журавлев Ю. И.
Об отделимости подмножеств вершин n-мерного единичного куба // Труды математического института им. В. А. Стеклова. — 1958. — Т. LI. — С. 143–157.
www.ccas.ru/frc/papers/zhuravlev58separability.pdf
[81] Журавлев Ю. И.
Теоретико-множественные методы в алгебре логики // Проблемы кибернетики. — 1962. — Т. 8. — С. 5–44.
www.ccas.ru/frc/papers/zhuravlev62settheory.pdf
[82] Журавлев Ю. И.
Экстремальные задачи, возникающие при обосновании эвристических процедур // Приблемы прикладной математики и механики. — М.: Наука, 1971. — С. 67–74.
www.ccas.ru/frc/papers/zhuravlev71extremal.pdf
[83] Журавлев Ю. И., Никифоров В. В.
Алгоритмы распознавания, основанные на вычислении оценок // Кибернетика. — 1971. — N° 3.
[84] Журавлев Ю. И.
Экстремальные алгоритмы в математических моделях для задач распознавания и классификации // Доклады АН СССР. Математика. — 1976. — Т. 231, N° 3.
[85] Журавлев Ю. И.
Непараметрические задачи распознавания образов // Кибернетика. — 1976. — N° 6.
[86] Березина В. В., Рудаков К. В.
О моделях алгоритмов распознавания для решения одной задачи медицинского прогнозирования // Кибернетика. — 1983. — N° 4. — С. 116–119.
www.ccas.ru/frc/papers/rudakov83medic.pdf
[87] Ашуров А. Р., Рудаков К. В.
Алгоритмы вычисления оценок для задачи распознавания объектов с континуальной начальной информацией // ЖВМиМФ. — 1984. — Т. 24, N° 12. — С. 1871–1880.
www.ccas.ru/frc/papers/rudakov84avo.pdf
[88] Матросов В. Л.
Корректные алгебры ограниченной емкости над множествами некорректных алгоритмов // ДАН СССР. — 1980. — Т. 253, N° 1. — С. 25–30.
www.ccas.ru/frc/papers/matrosov80dan.pdf
[89] Матросов В. Л.
О критериях полноты модели алгоритмов вычисления оценок и ее алгебраических замыканий // ДАН СССР. — 1981. — Т. 258, N° 4. — С. 791–796.
[90] Матросов В. Л.
Оптимальные алгоритмы в алгебраических замыканиях операторов вычисления оценок // ДАН СССР. — 1982. — Т. 262, N° 4. — С. 818–822.
[91] Матросов В. Л.
емкость алгебраических расширений модели алгоритмов вычисления оценок // ЖВМиМФ. — 1984. — Т. 24, N° 11. — С. 1719–1730.
[92] Матросов В. Л.
Нижние границы емкости многомерных алгебр алгоритмов вычисления оценок // ЖВМиМФ. — 1984. — Т. 24, N° 12. — С. 1881–1892.
[93] Матросов В. Л.
емкость алгоритмических многочленов над множеством алгоритмов вычисления оценок // ЖВМиМФ. — 1985. — Т. 25, N° 1. — С. 122–133.
[94] Бушманов О. Н., Дюкова Е. В., Журавлев Ю. И., Кочетков Д. В., Рязанов В. В.
Система анализа и распознавания образов // Распознавание, классификация, прогноз. — 1989. — Т. 2. — С. 250–273.
www.ccas.ru/frc/papers/bushmanov89obraz.pdf

Теория Вапника-Червоненкиса (VC Theory and VC-dimension)

[95] Вапник В. Н., Червоненкис А. Я.
О равномерной сходимости частот появления событий к их вероятностям // ДАН СССР. — 1968. — Т. 181, N° 4. — С. 781–784.
Работа закладывает основы статистической теории восстановления зависимостей по эмпирическим данным. Рассматриваются необходимые и достаточные условия равномерной сходимости частот появления событий к их вероятностям. Вводится понятие функции роста системы событий. Более подробное изложение и доказательства см. в [96].
[96] Вапник В. Н., Червоненкис А. Я.
О равномерной сходимости частот появления событий к их вероятностям // Теория вероятностей и ее применения. — 1971. — Т. 16, N° 2. — С. 264–280.
Вводятся понятия функции роста, энтропии и емкости системы событий. Доказывается, что частота сходится к вероятности равномерно по системе событий тогда и только тогда, когда доля энтропии, приходящейся на один элемент выборки, стремится к нулю с ростом длины выборки. Выводятся оценки скорости сходимости, позволяющие обосновать применимость метода минимизации эмпирического риска для решения задач распознавания. Эти оценки нетривиальны только в том случае, когда емкость семейства алгоритмов много меньше длины обучающей выборки.
[97] Вапник В. Н., Червоненкис А. Я.
Теория распознавания образов. — М.: Наука, 1974.
Первая классическая монография по статистической теории восстановления зависимостей. Приводится обзор алгоритмов распознавания. Вводятся понятия функции роста, энтропии и емкости системы событий, характеризующие сложность семейства алгоритмов. Выводятся оценки скорости равномерной сходимости частоты ошибок к их вероятности, позволяющие обосновать применимость метода минимизации эмпирического риска для решения задач распознавания. В доказательствах используется комбинаторная техника, основанная на оценивании разности частот в двух подвыборках одинаковой длины. Предлагается метод упорядоченной минимизации риска для целенаправленного выбора модели алгоритмов оптимальной сложности. Доказывается, что емкость семейства линейных решающих правил равна числу свободных параметров.
[98] Вапник В. Н.
Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.
Вторая классическая монография по статистической теории обучения. Основные идеи [97] распространяются на задачи восстановления регрессии и интерпретации результатов косвенных экспериментов. Предлагается метод упорядоченной минимизации суммарного риска, предназначенный для выбора модели алгоритмов оптимальной сложности. Новый метод, в отличие от ранее предложенного, оценивает качество восстановления зависимости в конечном множестве точек, а не на всем пространстве, поэтому обладает более высокой точностью. Описывается ряд алгоритмов распознавания образов, восстановления регрессии, селекции выборки.
[99] Vapnik V.
Estimation of Dependencies Based on Empirical Data. — Springer-Verlag, New York, 1982.
[100] Rissanen J.
Modeling by shortest data description // Automatica. — 1978. — Vol. 14. — Pp. 465–471.
[101] Valiant L. G.
A theory of the learnable // Communications of the ACM. — 1984. — Vol. 27. — Pp. 1134–1142.
[102] Вапник В., Глазкова Т., Кощеев В., Михальский А., Червоненкис А.
Алгоритмы и программы восстановления зависимостей. — М.: Наука, 1984. — 815 с.
[103] Матросов В. Л., Кукулиев Б. М.
Оценка прогнозирующей способности распознающих алгоритмов // Распознавание, классификация, прогноз. — 1990. — Т. 3. — С. 89–105.
[104] Семочкин А. Н.
Линейные достроения частичного порядка на конечных множествах // Деп. в ВИНИТИ. — 1998. — N° 2964–В98. — С. 19.
[105] Семочкин А. Н.
Оценки функционала качества для класса алгоритмов с универсальными ограничениями монотонности // Деп. в ВИНИТИ. — 1998. — N° 2965–В98. — С. 20.
[106] Bartlett P.
Lower bounds on the Vapnik-Chervonenkis dimension of multi-layer threshold networks // Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory. — ACM Press, New York, NY, 1993. — Pp. 144–150.
citeseer.ist.psu.edu/bartlett93lower.html
[107] Anthony M., Shawe-Taylor J.
A result of Vapnik with applications // Discrete Applied Mathematics. — 1993. — Vol. 47, no. 2. — Pp. 207–217.
citeseer.ist.psu.edu/anthony91result.html
[108] Karpinski M., Macintyre A.
Polynomial bounds for VC dimension of sigmoidal neural networks // 27th ACM Symposium on Theory of Computing, Las Vegas, Nevada, US. — 1995. — Pp. 200–208.
citeseer.ist.psu.edu/karpinski95polynomial.html
[109] Mertens S., Engel A.
Vapnik-Chervonenkis dimension of neural networks with binary weights // Phys. Rev. E. — 1997. — Vol. 55, no. 4. — Pp. 4478–4488.
[110] Kearns M. J., Schapire R. E.
Efficient distribution-free learning of probabilistic concepts // Computational Learning Theory and Natural Learning Systems, Volume I: Constraints and Prospect, edited by Stephen Jose Hanson, George A. Drastal, and Ronald L. Rivest, Bradford/MIT Press. — 1994. — Vol. 1.
citeseer.ist.psu.edu/article/kearns93efficient.html
[111] Vapnik V., Levin E., Cun Y. L.
Measuring the VC-dimension of a learning machine // Neural Computation. — 1994. — Vol. 6, no. 5. — Pp. 851–876.
citeseer.ist.psu.edu/vapnik94measuring.html
Вводится понятие эффективной емкости семейства алгоритмов. Эта величина не превышает емкости Вапника-Червоненкиса (VC-dimension) и может быть подставлена вместо нее в оценки скорости равномерной сходимости [96, 98, 99]. Предлагается эмпирический метод измерения эффективной емкости для задач классификации с двумя классами. Вводится понятие равномерного отклонения ошибок — это максимальная разность частот ошибок на двух подвыборках одинаковой длины, где максимум берется по семейству алгоритмов. Для матожидания равномерного отклонения ошибок выводится теоретическая верхняя оценка, зависящая от эффективной емкости семейства и длины выборки. С другой стороны, равномерное отклонение ошибок допускает эмпирическое измерение, поскольку максимизация разности частот ошибок эквивалентна обучению на всей выборке, в которой на половине объектов инвертированы ответы. Приравнивание двух оценок, теоретической и эмпирической, при различных длинах выборки позволяет измерить эффективную емкость семейства. Эксперименты по измерению эффективной емкости линейных решающих правил и нейронных сетей показали следующее. (1) Эффективная емкость может быть существенно меньше классической емкости. (2) Эмпирические данные хорошо ложатся на теоретическую зависимость равномерного отклонения ошибок от длины выборки, что позволяет говорить о правомерности предложенного метода измерения эффективной емкости. (3) Эффективная емкость линейных решающих правил совпадает с размерностью подпространства объектов, в котором располагается исходная выборка. (4) Измеренные значения эффективной емкости практически не зависят от сложности задачи (величины шума). Недостатком метода являются: неконструктивность определения эффективной емкости и сложный вид теоретической оценки равномерного отклонения ошибок. Формула оценки содержит два дополнительных параметра, которые не вполне обоснованно полагаются «универсальными постоянными» и определяются путем «калибровки» по модельной задаче.
[112] Bottou L., Cortes C., Vapnik V.
On the effective VC dimension. — 1994.
citeseer.ist.psu.edu/bottou94effective.html
Вводится понятие эффективной емкости, отличное от [111]. Предлагается метод измерения эффективной емкости, также основанный на эмпирической оценке равномерного отклонения ошибок (максимальной разности частот ошибок на двух подвыборках одинаковой длины), но существенно более простой для реализации. Основное отличие заключаются в использовании процедуры скользящего контроля для измерения равномерного отклонения ошибок, что позволяет избежать сложных параметрических аппроксимаций. Получаемые оценки емкости зависят не только от выборки данных, но и от используемого метода обучения.
[113] Shao X., Cherkassky V., Li W.
Measuring the VC-dimension using optimized experimental design // Neural Computation. — 2000. — Vol. 12, no. 8. — Pp. 1969–1986.
citeseer.ist.psu.edu/311578.html
[114] Vapnik V.
The nature of statistical learning theory. — Springer-Verlag, New York, 1995.
[115] Vapnik V.
The nature of statistical learning theory. — 2 edition. — Springer-Verlag, New York, 2000.
[116] Vapnik V.
Statistical Learning Theory. — Wiley, New York, 1998.
[117] Cortes C.
Prediction of generalization ability in learning machines: Ph.D. thesis. — University of Rochester, 1994.
[118] Vayatis N., Azencott R.
Distribution-dependent Vapnik-Chervonenkis bounds // Lecture Notes in Computer Science. — 1999. — Vol. 1572. — Pp. 230–240.
citeseer.ist.psu.edu/vayatis99distributiondependent.html
Статья содержит обзор результатов, полученных разными авторами в период 1982–1995, уточняющих оценки Вапника-Червоненкиса для скорости равномерной сходимости эмпирических частот к вероятностям. Отмечается, что наиболее точной является оценка Талагранда [142]. Выводится новая, несколько более точная, оценка, справедливая при ограничении класса вероятностных распределений на множестве исходных объектов. Обсуждается возможность использования полученной оценки при измерении эффективной емкости семейств алгоритмов [111].
[119] Shawe-Taylor J., Bartlett P. L.
Structural risk minimization over data-dependent hierarchies // IEEE Trans. on Information Theory. — 1998. — Vol. 44, no. 5. — Pp. 1926–1940.
citeseer.ist.psu.edu/article/shawe-taylor98structural.html
[120] Williamson R., Shawe-Taylor J., Scholkopf B., Smola A.
Sample based generalization bounds: Tech. Rep. NeuroCOLT Technical Report NC-TR-99-055: 1999.
citeseer.ist.psu.edu/williamson99sample.html
[121] Воронцов К. В.
Качество восстановления зависимостей по эмпирическим данным // Математические методы распознавания образов: 7-ая Всерос. конф. Тезисы докл. — Пущино, 1995. — С. 24–26.
Для оценивания качества обучения по прецедентам предлагается использовать комбинаторные функционалы типа скользящего контроля вместо принятых вероятностных функционалов. Для одного такого функционала доказывается оценка, аналогичная неравенствам Вапника-Червоненкиса, но при этом выборка не обязана быть случайной и независимой.
[122] Воронцов К. В.
Оценка качества монотонного решающего правила вне обучающей выборки // Интеллектуализация обработки информации: Тезисы докл. — Симферополь, 2002. — С. 24–26.
Приводится верхняя оценка функционала скользящего контроля для задачи классификации на два непересекающихся класса с монотонными решающими правилами. Данный класс имеет бесконечную емкость, тем не менее для него удается получить нетривиальную оценку качества, которая не превышает единицы даже в случае малых выборок. Полученная оценка не предполагает случайности и независимости выборки и не опирается на сложностные характеристики семейства алгоритмов.
[123] Herbrich R., Williamson R.
Algorithmic luckiness // Journal of Machine Learning Research. — 2002. — no. 3. — Pp. 175–212.
citeseer.ist.psu.edu/article/herbrich02algorithmic.html
[124] Воронцов К. В.
О комбинаторном подходе к оценке качества обучения алгоритмов // Математические методы распознавания образов: 11-ая Всерос. конф. Тезисы докл. — Пущино, 2003. — С. 47–49.
[125] Воронцов К. В.
Комбинаторные оценки качества обучения по прецедентам // Докл. РАН. — 2004. — Т. 394, N° 2. — С. 175–178.
www.ccas.ru/frc/papers/voron04qualdan.pdf
Рассматриваются функционалы скользящего контроля, характеризующие качество обучения алгоритмов по прецедентным эмпирическим данным. Приводятся верхние оценки этих функционалов, полученные без предположения случайности и независимости исходных данных. Описывается эффект локализации семейства алгоритмов и вводится понятие локальной функции роста. Рассматриваются основные причины завышенности известных вероятностных оценок качества. Развивается подход к оцениванию качества обучения, основанный на явном использовании априорной информации и не опирающийся на сложностные характеристики алгоритмов. Для задач классификации с универсальными ограничениями монотонности получены новые оценки качества, существенно более точные на малых выборках.
[126] 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 [125].
[127] Воронцов К. В.
Обзор современных исследований по проблеме качества обучения алгоритмов // Таврический вестник информатики и математики. — 2004.
www.ccas.ru/frc/papers/voron04twim.pdf
Обзор охватывает основные направления современных исследований феномена обобщающей способности, задача которых — уточнить сильно завышенные оценки статистической теории Вапника-Червоненкиса и предложить адекватные обоснования методов обучения по прецедентам. Выделяются следующие направления. 1. Оценивание эффективной сложности обучаемых алгоритмов, которая в ряде случаев оказывается существенно ниже теоретической. 2. Получение оценок, зависящих от отступов (margin) обучающих объектов в задачах классификации с пороговым решающим правилом. 3. Исследование обобщающей способности композиций алгоритмов, в том числе бустинга и баггинга. 4. Оценивание стабильности методов обучения (устойчивости относительно изменений обучающей выборки) и выявление взаимосвязей между стабильностью и обобщающей способностью. 5. Получение оценок качества для алгоритмов, выбираемых процедурой скользящего контроля. 6. Развитие комбинаторного подхода, обобщающего теорию Вапника-Червоненкиса. Библиография содержит 82 ссылки.
[128] Воронцов К. В.
Комбинаторные обоснования обучаемых алгоритмов // ЖВМиМФ. — 2004. — Т. 44, N° 11. — С. 2099–2112.
www.ccas.ru/frc/papers/voron04jvm.pdf
Рассматриваются комбинаторные функционалы качества обучения по прецедентам, основанные на принципе скользящего контроля. Выводятся их верхние оценки, более точные, чем оценки статистической теории Вапника-Червоненкиса, и при этом не предполагающие случайности и независимости исходных данных. Описывается эффект локализации семейства алгоритмов и вводится понятие локальной функции роста. С позиций комбинаторного подхода пересматриваются основные положения статистической теории. Анализируются основные причины завышенности сложностных оценок качества.
[129] 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 [128].
[130] Воронцов К. В.
Комбинаторный подход к оценке качества обучаемых алгоритмов // Математические вопросы кибернетики / Под ред. О. Б. Лупанов. — М.: Физматлит, 2004. — Т. 13. — С. 5–36.
www.ccas.ru/frc/papers/voron04mpc.pdf
Излагаются основы комбинаторного подхода к проблеме оценивания качества восстановления зависимостей по эмпирическим данным. Для формализации понятия обобщающей способности вводятся комбинаторные функционалы скользящего контроля. Полученные комбинаторные оценки обобщают результаты статистической теории Вапника-Червоненкиса. При этом требования случайности исходных данных и равномерной сходимости частоты ошибок к их вероятности оказываются избыточными. Описывается эффект локализации семейства алгоритмов, благодаря которому семейства алгоритмов большой и даже бесконечной емкости могут обладать неплохой обучаемостью. С позиций комбинаторного подхода пересматриваются основные положения статистической теории. Выдвигается гипотеза о принципиальной завышенности сложностных оценок качества обучения. Исследуются два частных случая, в которых семейства алгоритмов имеют бесконечную емкость, тем не менее для них удается получить достаточно точные оценки качества обучения.
[131] Воронцов К. В.
Слабая вероятностная аксиоматика и надежность эмпирических предсказаний // Математические методы распознавания образов-13. — М.: МАКС Пресс, 2007. — С. 21–25.
www.mmro.ru
Предлагается слабая вероятностная аксиоматика, существенно более простая, чем аксиоматика Колмогорова, в частности, не опирающаяся на теорию меры, но вполне достаточная для оценивания надежности эмпирических предсказаний. В рамках слабой аксиоматики доказаны аналоги таких фундаментальных фактов, как закон больших чисел, сходимость эмпирических функций распределения, многие ранговые критерии, оценки обобщающей способности алгоритмов классификации и регрессии.
[132] Воронцов К. В., Инякин А. С., Лисица А. В.
Система эмпирического измерения качества алгоритмов классификации // Математические методы распознавания образов-13. — М.: МАКС Пресс, 2007. — С. 577–580.
www.mmro.ru
Описывается комплексная методика измерения качества алгоритмов классификации, основанная на скользящем контроле. Она позволяет одновременно вычислять широкий спектр оценок, характеризующих различные аспекты обучаемости алгоритмов. В частности, оцениваются: средняя вариация, смещенность (степень неоптимальности) алгоритмической модели, профиль устойчивости, профиль разделимости выборки, профиль представительности объектов, профиль информативности признаков, и другие характеристики. Данную методику предполагается использовать в распределенной системе тестирования алгоритмов классификации. Система предоставляет доступ к задачам, методам и результатам тестирования через интуитивно понятный web-интерфейс. Система предназначена как для специалистов по анализу данных, так и для экспертов.
[133] Воронцов К. В., Колосков А. О.
Профили компактности и выделение опорных объектов в метрических алгоритмах классификации // Искусственный Интеллект. — 2006. — С. 30–33.
www.ccas.ru/frc/papers/students/VoronKoloskov05mmro.pdf
Отбор опорных объектов (эталонов) в метрических алгоритмах классификации позволяет уменьшить объем хранимых данных, повысить скорость и качество классификации. В данной работе предлагается метод отбора, основанный на минимизации функционала полного скользящего контроля, вычисляемого по эффективной комбинаторной формуле. Метод основан на явной оптимизации профиля компактности выборки.
[134] Кочедыков Д. А., Ивахненко А. А., Воронцов К. В.
Система кредитного скоринга на основе логических алгоритмов классификации // Математические методы распознавания образов-12. — М.: МАКС Пресс, 2005. — С. 349–353.
www.ccas.ru/frc/papers/voron05credit.pdf
Рассматривается задача кредитного скоринга, возникающая в кредитных организациях при принятии решений о выдаче кредитов. Перечисляются специфические особенности данной прикладной задачи, которые накладывают существенные ограничения на выбор модели алгоритма классификации и способы ее настройки. Для решения данной задачи предлагается использовать логические алгоритмы, основанные на поиске закономерностей в данных. Приводятся результаты экспериментального сравнения качества реализованных алгоритмов на реальных задачах выдачи кредитов. Кратко описывается архитекура программного комплекса ScoringAce.
[135] Воронцов К. В., Ивахненко А. А.
Эмпирические оценки локальной функции роста в задачах поиска логических закономерностей // Искусственный Интеллект. — 2006. — С. 281–284.
www.ccas.ru/frc/papers/students/VoronIvahnenko05mmro.pdf
Предлагается методика эмпирического оценивания эффективной локальной функции роста для семейств логических закономерностей. Результаты экспериментов позволяют выдвинуть гипотезу, что в реальных задачах классификации эффективная локальная функция роста имеет порядок единицы.
[136] Ивахненко А. А., Воронцов К. В.
Верхние оценки переобученности и профили разнообразия логических закономерностей // Математические методы распознавания образов-13. — М.: МАКС Пресс, 2007. — С. 33–37.
www.mmro.ru
Логические алгоритмы классификации представляют собой композиции элементарных классификаторов, называемых также закономерностями. Существуют два противоположных подхода к повышению качества (обобщающей способности) таких алгоритмов: либо увеличение числа закономерностей в композиции, либо повышение качества закономерностей. Качество алгоритма в обоих случаях может оказаться сопоставимым, однако при втором подходе получаются более простые, легко интерпретируемые алгоритмы. В данной работе понятие обобщающей способности, которое обычно определяется для алгоритмов, распространяется на случай закономерностей. В рамках комбинаторного подхода [130] выводятся сложностные оценки качества закономерностей. Предлагается методика эмпирического измерения завышенности получаемых оценок, основанная на скользящем контроле.
[137] Ульянов Ф. М., Воронцов К. В.
Проблема переобучения функций близости при построении алгоритмов вычисления оценок // Математические методы распознавания образов-13. — М.: МАКС Пресс, 2007. — С. 105–108.
www.mmro.ru
Предлагается новый метод оптимизации параметров в модели АВО (алгоритмов вычисления оценок), использующий принцип выравнивания отступов, выделение нерелевантных объектов (выбросов) и оптимизацию системы опорных множеств методом случайного поиска с адаптацией. Предложенный алгоритм протестирован на 7 прикладных задачах классификации. Преимуществом метода является высокая обобщающая способность. В частности, в задаче распознавания участков генных последовательностей применение данного алгоритма позволило понизить частоту ошибок с 18% до 5.5%.
[138] Донской В. И.
Колмогоровская сложность классов общерекурсивных функций с ограниченной емкостью // Таврический вестник информатики и математики. — 2005. — N° 1. — С. 25–34.
www.ccas.ru/frc/papers/donskoy05kolmogorov.pdf

Концентрация вероятности (Concentration of Probability)

[139] Chernoff H.
A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations // Annals of Math. Stat. — 1952. — Vol. 23. — Pp. 493–509.
[140] McDiarmid C.
On the method of bounded differences // In Surveys in Combinatorics, London Math. Soc. Lecture Notes Series. — 1989. — Vol. 141. — Pp. 148–188.
[141] Lugosi G., Pawlak M.
On the posterior-probability estimate of the error of nonparametric classification rules // IEEE Transactions on Information Theory. — 1994. — Vol. 40, no. 2. — Pp. 475–481.
[142] Talagrand. M.
Sharper bounds for gaussian and empirical processes // Annals of Probability. — 1994. — no. 22. — Pp. 28–76.
[143] Talagrand M.
Concentration of measure and isoperimetric inequalities in product space // Publ. Math. I.H.E.S. — 1995. — no. 81. — Pp. 73–205.
citeseer.ist.psu.edu/talagrand95concentration.html
[144] Boucheron S., Lugosi G., Massart P.
A sharp concentration inequality with applications // Random Structures and Algorithms. — 2000. — Vol. 16, no. 3. — Pp. 277–292.
citeseer.ist.psu.edu/article/boucheron99sharp.html
[145] Bartlett P. L., Mendelson S.
Rademacher and Gaussian complexities: Risk bounds and structural results // COLT: 14th Annual Conference on Computational Learning Theory. — Vol. 2111. — Springer, Berlin, 2001. — Pp. 224–240.
citeseer.ist.psu.edu/bartlett02rademacher.html
[146] Koltchinskii V., Panchenko D.
Rademacher processes and bounding the risk of function learning // High Dimensional Probability, II / Ed. by D. E. Gine, J.Wellner. — Birkhauser, 1999. — Pp. 443–457.
citeseer.ist.psu.edu/article/koltchinskii99rademacher.html
[147] Bartlett P., Bousquet O., Mendelson S.
Localized rademacher complexities // COLT: 15th Annual Conference on Computational Learning Theory. — Springer, Berlin, 2002. — Pp. 44–58.
citeseer.ist.psu.edu/bartlett02localized.html
[148] Boucheron S., Lugosi G., Massart P.
Concentration inequalities using the entropy method // The Annals of Probability. — 2003. — Vol. 31, no. 3.
citeseer.ist.psu.edu/boucheron02concentration.html
[149] Anthony M.
Uniform glivenko-cantelli theorems and concentration of measure in the mathematical modelling of learning: Tech. Rep. LSE-CDAM-2002-07: 2002.
www.maths.lse.ac.uk/Personal/martin/mresearch.html
[150] Lugosi G.
On concentration-of-measure inequalities. — Machine Learning Summer School, Australian National University, Canberra. — 2003.
citeseer.ist.psu.edu/lugosi98concentrationmeasure.html
[151] Boucheron S., Bousquet O., Lugosi G.
Theory of classification: A survey of some recent advances // ESAIM: Probability and Statistics. — 2005. — no. 9. — Pp. 323–375.
www.econ.upf.edu/simlugosi/esaimsurvey.pdf
[152] Desyatnikov I., Meir R.
Data-dependent bounds for multi-category classification based on convex losses // COLT: 16th Annual Conference on Learning Theory / Ed. by B. Scholkopf, M. Warmuth. — Springer Verlag, Heidelberg, 2003. — Pp. 159–172.
citeseer.ist.psu.edu/desyatnikov03datadependent.html
[153] Bartlett P. L., Mendelson S., Philips P.
Local complexities for empirical risk minimization // COLT: 17th Annual Conference on Learning Theory / Ed. by J. Shawe-Taylor, Y. Singer. — Springer-Verlag, 2004. — Pp. 270–284.
[154] Langford J., Blum A.
Microchoice bounds and self bounding learning algorithms // Computational Learing Theory. — 1999. — Pp. 209–214.
citeseer.ist.psu.edu/article/langford00microchoice.html
[155] Langford J.
Quantitatively tight sample complexity bounds. — 2002. — Carnegie Mellon Thesis.
citeseer.ist.psu.edu/langford02quantitatively.html
[156] Langford J.
Combining train set and test set bounds // ICML'02. — 2002.
citeseer.ist.psu.edu/612035.html

Метод опорных векторов (Support Vector Machines, SVM)

[157] Mercer J.
Functions of positive and negative type and their connection with the theory of integral equations // Philos. Trans. Roy. Soc. London. — 1909. — Vol. A, no. 209. — Pp. 415–446.
[158] Cortes C., Vapnik V.
Support-vector networks // Machine Learning. — 1995. — Vol. 20, no. 3. — Pp. 273–297.
citeseer.ist.psu.edu/cortes95supportvector.html
[159] Osuna E., Freund R., Girosi F.
Support vector machines: Training and applications: Tech. Rep. AIM-1602: 1997.
citeseer.ist.psu.edu/osuna97support.html
[160] Osuna E., Freund R., Girosi F.
An improved training algorithm for support vector machines // Neural Networks for Signal Processing VII. IEEE Workshop. — 1997. — Pp. 276–285.
citeseer.ist.psu.edu/osuna97improved.html
[161] Platt J. C.
Fast training support vector machines using sequential minimal optimization // Advances in Kernel Methods / Ed. by B. Scholkopf, C. C. Burges, A. J. Smola. — MIT Press, 1999. — Pp. 185–208.
[162] Fine S., Scheinberg K.
INCAS: An incremental active set method for SVM: Tech. rep.: 2002.
citeseer.ist.psu.edu/fine02incas.html
[163] Scheinberg K.
An efficient implementation of an active set method for svms // J. Mach. Learn. Res. — 2006. — Vol. 7. — Pp. 2237–2257.
[164] Burges C. J. C.
A tutorial on support vector machines for pattern recognition // Data Mining and Knowledge Discovery. — 1998. — Vol. 2, no. 2. — Pp. 121–167.
citeseer.ist.psu.edu/burges98tutorial.html
[165] Burges C. J. C.
Geometry and invariance in kernel based methods // Advances in Kernel Methods / Ed. by B. Scholkopf, C. C. Burges, A. J. Smola. — MIT Press, 1999. — Pp. 89 – 116.
[166] Smola A., Schoelkopf B.
A tutorial on support vector regression: Tech. Rep. NeuroCOLT2 NC2-TR-1998-030: 1998.
citeseer.ist.psu.edu/smola98tutorial.html
[167] Tipping M.
The relevance vector machine // Advances in Neural Information Processing Systems, San Mateo, CA. — Morgan Kaufmann, 2000.
citeseer.ist.psu.edu/tipping00relevance.html
[168] Bartlett P., Shawe-Taylor J.
Generalization performance of support vector machines and other pattern classifiers // Advances in Kernel Methods. — MIT Press, Cambridge, USA, 1998.
citeseer.ist.psu.edu/bartlett98generalization.html
[169] Shawe-Taylor J., Cristianini N.
Robust bounds on generalization from the margin distribution: Tech. Rep. NC2–TR–1998–029: Royal Holloway, University of London, 1998.
citeseer.ist.psu.edu/shawe-taylor98robust.html
[170] Vapnik V., Chapelle O.
Bounds on error expectation for support vector machines // Neural Computation. — 2000. — Vol. 12, no. 9. — Pp. 2013–2036.
citeseer.ist.psu.edu/vapnik99bounds.html
[171] Joachims T.
Estimating the generalization performance of a SVM efficiently // Proceedings of ICML-00, 17th International Conference on Machine Learning / Ed. by P. Langley. — Stanford, US: Morgan Kaufmann Publishers, San Francisco, US, 2000. — Pp. 431–438.
citeseer.ist.psu.edu/joachims00estimating.html

Дискриминантный анализ (Discriminant Analysis)

[172] Fisher R. A.
The use of multiple measurements in taxonomic problem // Ann. Eugen. — 1936. — no. 7. — Pp. 179–188.

Нейронные сети (Artificial Neural Nets)

[173] McCulloch W. S., Pitts W.
A logical calculus of ideas immanent in nervous activity // Bulletin of Mathematical Biophysics. — 1943. — no. 5. — Pp. 115–133.
[174] Hebb D.
The organization of behavior. — New York: Wiley, 1949.
[175] Stone M. N.
The generalized Weierstrass approximation theorem // Math. Mag. — 1948. — Vol. 21. — Pp. 167–183, 237–254.
[176] Колмогоров А. Н.
О представлении непрерывных функций нескольких переменных в виде суперпозиции непрерывных функций одного переменного // Докл. АН СССР. — 1958. — Т. 114, N° 5. — С. 953–956.
[177] Rosenblatt R.
Principles of neuro dynamics. — New York: Spartan books, 1959.
[178] Widrow B., Hoff M. E.
Adaptive switching circuits // IRE WESCON Convention Record. — DUNNO, 1960. — Pp. 96–104.
[179] Novikoff A. B. J.
On convergence proofs on perceptrons // Proceedings of the Symposium on the Mathematical Theory of Automata. — Vol. 12. — Polytechnic Institute of Brooklyn, 1962. — Pp. 615–622.
[180] Minsky M., Papert S.
Perceptrons: an Introduction to Computational Geometry. — MIT Press, 1968.
[181] Минский М., Пайперт С.
Персепроны. — М.: Мир, 1971.
[182] Rummelhart D. E., Hinton G. E., Williams R. J.
Learning internal representations by error propagation // Vol. 1 of Computational models of cognition and perception, chap. 8. — Cambridge, MA: MIT Press, 1986. — Pp. 319–362.
[183] Durbin R., Rummelhart D. E.
Product units: A computationally powerful and biologically plausible extension to backpropagation networks // Neural Computation. — 1989. — Vol. 1, no. 4. — Pp. 133–142.
[184] Bishop C. M.
Neural Networks for Pattern Recognition. — Oxford University Press, 1995.
[185] LeCun Y., Bottou L., Orr G. B., Muller K.-R.
Efficient BackProp // Neural Networks: tricks of the trade. — Springer, 1998.
[186] LeCun Y., Denker J., Solla S., Howard R. E., Jackel L. D.
Optimal brain damage // Advances in Neural Information Processing Systems II / Ed. by D. S. Touretzky. — San Mateo, CA: Morgan Kauffman, 1990.
citeseer.ist.psu.edu/lecun90optimal.html
[187] Hassibi B., Stork D. G.
Second order derivatives for network pruning: Optimal brain surgeon // Advances in Neural Information Processing Systems / Ed. by S. J. Hanson, J. D. Cowan, C. L. Giles. — Vol. 5. — Morgan Kaufmann, San Mateo, CA, 1993. — Pp. 164–171.
citeseer.ist.psu.edu/hassibi93second.html
[188] Blum A., Rivest R. L.
Training a 3-node neural network is NP-complete // Machine Learning: From Theory to Applications. — 1993. — Pp. 9–28.
citeseer.ist.psu.edu/blum92training.html
[189] Anthony M., Bartlett P. L.
Neural Network Learning: Theoretical Foundations. — Cambridge University Press, Cambridge, 1999.
[190] LeCun Y., Boser B., Denker J. S., Henderson D., Howard R. E., Hubbard W., Jackel L. D.
Backpropagation applied to handwritten zip code recognition // Neural Computation. — 1989. — Vol. 1, no. 4. — Pp. 541–551.
[191] Нейроинформатика / А. Н. Горбань, В. Л. Дунин-Барковский, А. Н. Кирдин, Е. М. Миркес, А. Ю. Новоходько, Д. А. Россиев, С. А. Терехов и др. — Новосибирск: Наука, 1998. — С. 296.
[192] Головко В. А.
Нейронные сети: обучение, организация и применение. — М.: ИПРЖР, 2001.
[193] Круглов В. В., Борисов В. В.
Искусственные нейронные сети: теория и практика. — М.: Горячая линия–Телеком, 2001.
[194] Хайкин С.
Нейронные сети: полный курс, 2-е издание. — М.: Издательский дом «Вильямс», 2006.

Бустинг и баггинг (Boosting and Bagging)

[195] Kearns M., Valiant L. G.
Cryptographic limitations on learning Boolean formulae and finite automata // Proc. of the 21st Annual ACM Symposium on Theory of Computing. — 1989. — Pp. 433–444.
citeseer.ist.psu.edu/kearns89cryptographic.html
[196] Littlestone N., Warmuth M. K.
The weighted majority algorithm // IEEE Symposium on Foundations of Computer Science. — 1989. — Pp. 256–261.
citeseer.ist.psu.edu/littlestone92weighted.html
[197] Schapire R. E.
The strength of weak learnability // Machine Learning. — 1990. — Vol. 5. — Pp. 197–227.
citeseer.ist.psu.edu/schapire90strength.html
[198] Freund Y.
Boosting a weak learning algorithm by majority // COLT: Proceedings of the Workshop on Computational Learning Theory. — Morgan Kaufmann Publishers, 1990.
citeseer.ist.psu.edu/freund95boosting.html
[199] Freund Y., Schapire R. E.
A decision-theoretic generalization of on-line learning and an application to boosting // European Conference on Computational Learning Theory. — 1995. — Pp. 23–37.
citeseer.ist.psu.edu/article/freund95decisiontheoretic.html
[200] Freund Y., Schapire R. E.
Experiments with a new boosting algorithm // International Conference on Machine Learning. — 1996. — Pp. 148–156.
citeseer.ist.psu.edu/freund96experiments.html
[201] Schapire R. E., Freund Y., Lee W. S., Bartlett P.
Boosting the margin: a new explanation for the effectiveness of voting methods // Annals of Statistics. — 1998. — Vol. 26, no. 5. — Pp. 1651–1686.
citeseer.ist.psu.edu/article/schapire98boosting.html
Дается теоретическое обоснование неожиданной эффективности взвешенного голосования методом бустинга. Эксперименты показывают, что ошибка на независимой тестовой выборке не увеличивается с ростом сложности алгоритма (числа базовых классификаторов), и более того, продолжает уменьшаться даже после достижения безошибочной классификации обучающей выборки. На самом деле голосование не увеличивает сложность алгоритма, а лишь сглаживает прогнозы базовых классификаторов. Более тонкий анализ показывает, что по мере добавления новых классификаторов бустинг увеличивает отступы обучающих объектов («раздвигает» классы) гораздо эффективней, чем другие методы голосования (баггинг и ECOC). Полученные оценки обобщающей способности существенно точнее сложностных и дают качественное обоснование феноменам бустинга. Тем не менее они также сильно завышены и требуют, чтобы длина обучающей выборки имела порядок 104–106.
[202] Koltchinskii V., Panchenko D., Lozano F.
Further explanation of the effectiveness of voting methods: The game between margins and weights // 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Amsterdam, The Netherlands, July 2001, Proceedings. — Vol. 2111. — Springer, Berlin, 2001. — Pp. 241–255.
citeseer.ist.psu.edu/476199.html
[203] Breiman L.
Bagging predictors // Machine Learning. — 1996. — Vol. 24, no. 2. — Pp. 123–140.
citeseer.ist.psu.edu/breiman96bagging.html
[204] Breiman L.
Bias, variance, and arcing classifiers: Tech. Rep. 460: Statistics Department, University of California, 1996.
citeseer.ist.psu.edu/breiman96bias.html
[205] Quinlan J. R.
Bagging, boosting, and C4.5 // AAAI/IAAI, Vol. 1. — 1996. — Pp. 725–730.
citeseer.ist.psu.edu/quinlan96bagging.html
[206] Poggio T., Rifkin R., Mukherjee S., Rakhlin A.
Bagging regularizes. — 2002.
citeseer.ist.psu.edu/poggio02bagging.html
[207] Breiman L.
Arcing classifiers // The Annals of Statistics. — 1998. — Vol. 26, no. 3. — Pp. 801–849.
citeseer.ist.psu.edu/breiman98arcing.html
[208] Freund Y., Schapire R. E.
Discussion of the paper “Arcing classifiers” by Leo Breiman // The Annals of Statistics. — 1998. — Vol. 26, no. 3. — Pp. 824–832.
citeseer.ist.psu.edu/freund97discussion.html
Обсуждаются результаты экспериментального сравнения алгоритмов бустинга и баггинга. Оба метода предназначены для взвешенного голосования «слабых» классификаторов. Конструктивное различие состоит в том, что для настройки каждого слабого классификатора баггинг случайным образом выбирает обучающие подвыборки, а бустинг детерминированным образом устанавливает веса обучающих объектов. При этом баггинг направлен исключительно на уменьшение вариации (variance). Эксперименты показывают, что бустинг способствует уменьшению как вариации, так и смещения (bias). Эффективность бустинга объясняется тем, что он пытается максимизировать отступы обучающих объектов даже после достижения безошибочной классификации обучающей выборки [201]. В заключение приводится перечень открытых проблем для исследования.
[209] Hastie T., Tibshirani R.
Generalized additive models // Statistical Science. — 1986. — Vol. 1. — Pp. 297–318.
citeseer.ist.psu.edu/hastie95generalized.html
[210] Friedman J., Hastie T., Tibshirani R.
Additive logistic regression: a statistical view of boosting: Tech. rep.: Dept. of Statistics, Stanford University Technical Report, 1998.
citeseer.ist.psu.edu/friedman98additive.html
[211] Schapire R. E., Singer Y.
Improved boosting using confidence-rated predictions // Machine Learning. — 1999. — Vol. 37, no. 3. — Pp. 297–336.
citeseer.ist.psu.edu/article/singer99improved.html
[212] Schapire R. E.
Theoretical views of boosting and applications // Algorithmic Learning Theory, 10th International Conference, ALT '99, Tokyo, Japan, December 1999, Proceedings. — Vol. 1720. — Springer, 1999. — Pp. 13–25.
citeseer.ist.psu.edu/article/schapire99theoretical.html
[213] Freund Y., Schapire R. E.
A short introduction to boosting // J. Japan. Soc. for Artif. Intel. — 1999. — Vol. 14, no. 5. — Pp. 771–780.
citeseer.ist.psu.edu/freund99short.html
[214] Schapire R. E.
A brief introduction to boosting // International Joint Conference on Artificial Intelligence. — 1999. — Pp. 1401–1406.
citeseer.ist.psu.edu/schapire99brief.html
Краткое описание алгоритма AdaBoost.
[215] Bauer E., Kohavi R.
An empirical comparison of voting classification algorithms: Bagging, boosting, and variants // Machine Learning. — 1999. — Vol. 36, no. 1-2. — Pp. 105–139.
citeseer.ist.psu.edu/bauer99empirical.html
[216] Freund Y.
An adaptive version of the boost by majority algorithm // COLT: Proceedings of the Workshop on Computational Learning Theory. — Morgan Kaufmann Publishers, 1999.
citeseer.ist.psu.edu/article/freund00adaptive.html
[217] Schapire R.
The boosting approach to machine learning: An overview // MSRI Workshop on Nonlinear Estimation and Classification, Berkeley, CA. — 2001.
citeseer.ist.psu.edu/schapire02boosting.html
[218] Moerland P., Mayoraz E.
Dynaboost: Combining boosted hypotheses in a dynamic way: Tech. rep.: IDIAP Research Report 99-09, 1999.
citeseer.ist.psu.edu/moerland99dynaboost.html
[219] Grove A. J., Schuurmans D.
Boosting in the limit: Maximizing the margin of learned ensembles // AAAI/IAAI. — 1998. — Pp. 692–699.
citeseer.ist.psu.edu/grove98boosting.html
[220] Ratsch G., Onoda T., Muller K.-R.
Soft margins for AdaBoost // Machine Learning. — 2001. — Vol. 42, no. 3. — Pp. 287–320.
citeseer.ist.psu.edu/ratsch00soft.html
[221] Ratsch G., Onoda T., Muller K. R.
An improvement of adaboost to avoid overfitting // Advances in Neutral Information Processing Systems, Kitakyushu, Japan. — 1998. — Pp. 506–509.
citeseer.ist.psu.edu/6344.html
[222] Webb G. I.
MultiBoosting: A technique for combining Boosting and Wagging // Machine Learning. — 2000. — Vol. 40, no. 2. — Pp. 159–196.
citeseer.ist.psu.edu/webb98multiboosting.html
[223] Kuncheva L. I., Jain L. C.
Designing classifier fusion systems by genetic algorithms // IEEE-EC. — November 2000. — Vol. 4, no. 4. — P. 327.
citeseer.ist.psu.edu/kuncheva00designing.html
[224] Skurichina M., Kuncheva L., Duin R.
Bagging and boosting for the nearest mean classifier: Effects of sample size on diversity and accuracy // Multiple Classifier Systems (Proc. Third International Workshop MCS, Cagliari, Italy) / Ed. by F. Roli, J. Kittler. — Vol. 2364. — Springer, Berlin, 2002. — Pp. 62–71.
citeseer.ist.psu.edu/539135.html
При комбинировании классификаторов обычно предполагается, что чем сильнее различаются элементы ансамбля, тем выше его обобщающая способность (generalization performance). Для проверки этой гипотезы исследуется точность (accuracy) и разнообразие (diversity) ансамблей, получаемых методами бустинга [217] и баггинга [203] над классификаторами ближайших средних (Nearest Mean Classifier [505]). Эксперименты на 4 реальных задачах из репозитория UCI [554] показали, что и точность, и разнообразие зависят от длины обучающей выборки. Бустинг работает лучше на больших обучающих выборках, баггинг — на малых. При увеличении длины выборки баггинг уменьшает разнообразие классификаторов, а бустинг увеличивает. Бустинг лучше воспроизводит границы классов сложной формы.
[225] Kuncheva L., Whitaker C.
Measures of diversity in classifier ensembles and their relationship with the ensemble accuracy // Machine Learning. — 2003. — Vol. 51, no. 2. — Pp. 181–207.
citeseer.ist.psu.edu/kuncheva00measures.html
[226] Skurichina M., Duin R. P. W.
Limited bagging, boosting and the random subspace method for linear classifiers // Pattern Analysis & Applications. — 2002. — no. 5. — Pp. 121–135.
citeseer.ist.psu.edu/skurichina02limited.html
[227] Kuncheva L., Skurichina M., Duin R.
An experimental study on diversity for bagging and boosting with linear classifiers // Information Fusion. — 2002. — Vol. 3, no. 4. — Pp. 245–258.
citeseer.ist.psu.edu/kuncheva02experimental.html
[228] Kuncheva L.
Combining pattern classifiers. — John Wiley & Sons, Inc., 2004.
[229] Jin R., Liu Y., Si L., Carbonell J., Hauptmann A.
A new boosting algorithm using input-dependent regularizer // The 20-th International Conference on Machine Learning. — 2003.
citeseer.ist.psu.edu/jin03new.html
Предлагается новый вариант алгоритма бустинга WeightBoost, более устойчивый к шумовым искажениям данных, и потому менее склонный к переобучению, чем исходный алгоритм AdaBoost. В новом алгоритме веса базовых классификаторов не постоянны и зависят от объекта. Для каждого классификатора выделяется своя «область компетентности», на которой он настраивается наиболее точно. Конкретней, вес базового классификатора на объекте тем меньше, чем большее (по модулю) значение принимает на данном объекте линейная комбинация всех предыдущих классификаторов. Именно такими выбросами проявляют себя зашумленные объекты. Таким образом, WeightBoost перестает настраиваться на объектах, оказавшихся «трудными» для большинства базовых классификаторов, считая эти объекты зашумленными. Предложенный алгоритм сравнивается с другими вариантами бустинга AdaBoost, ε-Boost, WeightDecay на 8 реальных задачах из репозитория UCI. В 6 случаях из 8 результат WeightBoost оказывается не хуже.
[230] Maclin R., Opitz D.
An empirical evaluation of bagging and boosting // AAAI/IAAI. — 1997. — Pp. 546–551.
citeseer.ist.psu.edu/maclin97empirical.html
[231] Tsymbal A., Puuronen S.
Ensemble feature selection with the simple bayesian classification in medical diagnostics // 15 IEEE Symp. on Computer-Based Medical Systems CBMS. — 2002. — P. 225.
citeseer.ist.psu.edu/623033.html
[232] Dietterich T. G.
An experimental comparison of three methods for constructing ensembles of decision trees: Bagging, boosting, and randomization // Machine Learning. — 2000. — Vol. 40, no. 2. — Pp. 139–157.
citeseer.ist.psu.edu/article/dietterich98experimental.html
[233] Ho T. K.
The random subspace method for constructing decision forests // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 1998. — Vol. 20, no. 8. — Pp. 832–844.
citeseer.ist.psu.edu/ho98random.html
[234] Ting K. M., Zheng Z.
Improving the performance of boosting for naive bayesian classification // Pacific-Asia Conference on Knowledge Discovery and Data Mining. — 1999. — Pp. 296–305.
citeseer.ist.psu.edu/article/ting99improving.html
[235] Zheng Z., Webb G.
Multiple boosting: A combination of boosting and bagging // Proceedings of the 4th International Conference on Parallel and Distributed Processing Techniques and Applications. CSREA Press. — 1998. — Pp. 1133–1140.
citeseer.ist.psu.edu/zheng98multiple.html
[236] Zheng Z., Webb G., Ting K.
Integrating boosting and stochastic attribute selection committees for further improving the performance of decision tree learning // Proceedings of the 10th IEEE International Conference on Tools with Artificial Intelligence. — IEEE Computer Society Press, 1998. — Pp. 216–223.
citeseer.ist.psu.edu/article/zheng98integrating.html
[237] Zheng Z., Webb G. I.
Stochastic attribute selection committees with multiple boosting: Learning more accurate and more stable classifer committees // Pacific-Asia Conference on Knowledge Discovery and Data Mining. — 1999. — Pp. 123–132.
citeseer.ist.psu.edu/article/zheng98stochastic.html
[238] Zheng Z., Webb G. I.
Multi strategy ensemble learning: Reducing error by combining ensemble learning techniques // IEEE transactions on knowledge and data engineering. — 2004. — Vol. 16, no. 8. — Pp. 980–991.
www.csse.monash.edu.au/simwebb/Files/WebbZheng03.pdf
[239] Ridgeway G., Madigan D., Richardson T., O'Kane J.
Interpretable boosted naive bayes classification // Knowledge Discovery and Data Mining. — 1998. — Pp. 101–104.
citeseer.ist.psu.edu/ridgeway98interpretable.html
[240] Zheng Z.
Naive bayesian classifier committees // European Conference on Machine Learning. — 1998. — Pp. 196–207.
citeseer.ist.psu.edu/zheng98naive.html
[241] Domingos P.
Why does bagging work? a bayesian account and its implications // Knowledge Discovery and Data Mining. — 1997. — Pp. 155–158.
citeseer.ist.psu.edu/21089.html
[242] Evgeniou T., Perez-Breva L., Pontil M., Poggio T.
Bounds on the generalization performance of kernel machine ensembles // Proc. 17th International Conf. on Machine Learning. — Morgan Kaufmann, San Francisco, CA, 2000. — Pp. 271–278.
citeseer.ist.psu.edu/evgeniou99bounds.html

Смеси экспертов (Mixtures of Experts) и EM-алгоритм

[243] Шлезингер М. И.
О самопроизвольном различении образов // Читающие автоматы. — Киев, Наукова думка, 1965. — Pp. 38–45.
[244] Dempster A. P., Laird N. M., Rubin D. B.
Maximum likelihood from incomplete data via the EM algorithm // J. of the Royal Statistical Society, Series B. — 1977. — no. 34. — Pp. 1–38.
[245] Wu C. F. G.
On the convergence properties of the EM algorithm // The Annals of Statistics. — 1983. — no. 11. — Pp. 95–103.
citeseer.ist.psu.edu/78906.html
[246] Xu L., Jordan M. I., Hinton G. E.
An alternative model for mixtures of experts // Advances in Neural Information Processing Systems / Ed. by G. Tesauro, D. Touretzky, T. Leen. — Vol. 7. — The MIT Press, 1995. — Pp. 633–640.
citeseer.ist.psu.edu/xu95alternative.html
[247] Xu L., Jordan M. I.
On convergence properties of the EM algorithm for gaussian mixtures // Neural Computation. — 1996. — Vol. 8, no. 1. — Pp. 129–151.
citeseer.ist.psu.edu/xu95convergence.html
[248] Xu L., Jordan M. I.
Theoretical and experimental studies of the EM algorithm for unsupervised learning based on finite gaussian mixtures: Tech. Rep. 9302: MIT Computational Cognitive Science, Cambridge, MA, 1993.
[249] Jordan M. I., Xu L.
Convergence results for the EM algorithm to mixtures of experts architectures: Tech. Rep. A.I. Memo No. 1458: MIT, Cambridge, MA, 1993.
[250] Jacobs R. A., Jordan M. I., Nowlan S. J., Hinton G. E.
Adaptive mixtures of local experts // Neural Computation. — 1991. — no. 3. — Pp. 79–87.
[251] Jordan M. I., Jacobs R. A.
Hierarchical mixtures of experts and the EM algorithm // Neural Computation. — 1994. — no. 6. — Pp. 181–214.
citeseer.ist.psu.edu/article/jordan94hierarchical.html
[252] Jamshidian M., Jennrich R. I.
Conjugate gradient acceleration of the em algorithm // Journal of the American Statistical Association. — 1993. — Vol. 88, no. 421. — Pp. 221–228.
[253] Liu C., Sun D.
Acceleration of em algorithm for mixtures models using ecme // ASA Proceedings of The Stat. Comp. Session. — 1997. — Pp. 109–114.
citeseer.ist.psu.edu/liu97acceleration.html
[254] Fritsch J., Finke M., Waibel A.
Adaptively growing hierarchical mixtures of experts // Advances in Neural Information Processing Systems / Ed. by M. C. Mozer, M. I. Jordan, T. Petsche. — Vol. 9. — The MIT Press, 1997. — P. 459.
citeseer.ist.psu.edu/73627.html
[255] Waterhouse S. R., Robinson A. J.
Classification using hierarchical mixtures of experts // Proceedings of the 1994 IEEE Workshop on Neural Networks for Signal Processing IV. — Long Beach, CA: IEEE Press, 1994. — Pp. 177–186.
citeseer.ist.psu.edu/waterhouse94classification.html
[256] Воронцов К. В.
О композициях дипольных классификаторов // Интеллектуализация обработки информации (ИОИ-2006). — Симферополь: КНЦ НАН Украины, 2006. — С. 38–40.
В докладе предлагается модель алгоритмов классификации, которую можно рассматривать как обобщение алгоритмов вычисления оценок (АВО), метода потенциальных функций, двуслойного персептрона и машин покрывающих множеств.

Метод комитетов (Committee Machines)

[257] Мазуров В. Д.
Комитеты системы неравенств и задача распознавания // Кибернетика. — 1971. — N° 3.
[258] Osborne M. L.
The seniority logic: A logic for a committee machine // IEEE Trans. on Comp. — 1977. — Vol. C-26, no. 12. — Pp. 1302–1306.
[259] Белецкий Н. Г.
Применение комитетов для многоклассовой классификации // Численный анализ решения задач линейного и выпуклого программирования. — Свердловск, 1983. — С. 156–162.
[260] Мазуров В. Д.
Метод комитетов в задачах оптимизации и классификации. — М.: Наука, 1990.
[261] Хачай М. Ю.
Об оценке числа членов минимального комитета системы линейных неравенств // Журнал вычислительной математики и математической физики. — 1997. — Т. 37. — С. 1399–1404.
tom.imm.uran.ru/khachay/publications/mine/index.htm
[262] Hachai M. Y., Rybin A. I.
A new estimate of the number of members in a minimum committee of a linear inequalities system // Pattern Recognition and Image Analysis. — 1998. — Vol. 8, no. 4. — Pp. 491–496.
tom.imm.uran.ru/khachay/publications/mine/index.htm
[263] Mazurov V., Khachai M., Rybin A.
Committee constructions for solving problems of selection, diagnostics and prediction // Proceedings of the Steklov Institute of mathematics. — 2002. — Vol. 1. — Pp. 67–101.
tom.imm.uran.ru/khachay/publications/mine/psis67.pdf
[264] Хачай М. Ю.
О вычислительной сложности задачи о минимальном комитете и смежных задач // Доклады РАН. — 2006. — Т. 406, N° 6. — С. 742√745.
tom.imm.uran.ru/khachay/publications/mine/index.htm

Комбинации классификаторов (Combined Classifiers)

[265] Айзерман М. А., Браверман Э. М., Розоноэр Л. И.
Метод потенциальных функций в теории обучения машин. — М.: Наука, 1970. — P. 320.
[266] Растригин Л. А., Эренштейн Р. Х.
Коллективные правила распознавания. — М.: Энергия, 1981. — P. 244.
[267] Wolpert D. H.
Stacked generalization // Neural Networks. — 1992. — no. 5. — Pp. 241–259.
citeseer.ist.psu.edu/wolpert92stacked.html
[268] Tresp V., Taniguchi M.
Combining estimators using non-constant weighting functions // Advances in Neural Information Processing Systems / Ed. by G. Tesauro, D. Touretzky, T. Leen. — Vol. 7. — The MIT Press, 1995. — Pp. 419–426.
citeseer.ist.psu.edu/tresp95combining.html
[269] Tresp V.
Committee machines // Handbook for Neural Network Signal Processing / Ed. by Y. H. Hu, J.-N. Hwang. — CRC Press, 2001.
citeseer.ist.psu.edu/tresp01committee.html
[270] Boser B. E., Guyon I., Vapnik V.
A training algorithm for optimal margin classifiers // Computational Learning Theory. — 1992. — Pp. 144–152.
citeseer.ist.psu.edu/boser92training.html
[271] Bartlett P. L.
For valid generalization the size of the weights is more important than the size of the network // Advances in Neural Information Processing Systems / Ed. by M. C. Mozer, M. I. Jordan, T. Petsche. — Vol. 9. — The MIT Press, 1997. — P. 134.
citeseer.ist.psu.edu/bartlett97for.html
Дается качественно новое, по сравнению с теорией Вапника-Червоненкиса [97], обоснование применимости выпуклых комбинаций обучаемых алгоритмов, в частности, нейронных сетей. Оказывается, сложность выпуклой комбинации классификаторов равна не суммарной, и даже не максимальной (как ранее предполагалось), а средней взвешенной сложности отдельных классификаторов с теми же весами, с которыми они входят в комбинацию. Вытекающие отсюда оценки обобщающей способности (generalization performance) существенно лучше сложностных оценок, хотя и они все еще сильно завышены. Полученный результат дает теоретическое обоснование эвристикам, направленным на уменьшение весов в процессе обучения, таким как weight decay и early stopping.
[272] Bartlett P. L., Long P. M., Williamson R. C.
Fat-shattering and the learnability of real-valued functions // Journal of Computer and System Sciences. — 1996. — Vol. 52, no. 3. — Pp. 434–452.
citeseer.ist.psu.edu/bartlett95fatshattering.html
[273] Bartlett P.
The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network // IEEE Transactions on Information Theory. — 1998. — Vol. 44, no. 2. — Pp. 525–536.
discus.anu.edu.au/simbartlett
Теория обучаемых систем говорит, что нейронная сеть имеет хорошую обобщающую способность, если число обучающих объектов зависит по меньшей мере линейно от количества настраиваемых параметров сети. В статье показывается, что если алгоритм обучения находит сеть с малыми весами и малой квадратичной ошибкой на обучении, то обобщающая способность зависит от величины весов в бóльшей степени, чем от их количества. Техника доказательств, основанная на понятиях отступа (margin) и fat-размерности (fat-shattering dimension), может быть применена и к другим алгоритмам распознавания. В частности, этот же подход распространяется на случай метрического пространства объектов, когда алгоритм обучения строит разделяющую поверхность, проходящую в достаточном удалении от обучающих объектов.
[274] Lee W. S., Bartlett P., Williamson R. C.
The importance of convexity in learning with squared loss // IEEE Transactions on Information Theory. — 1998. — Vol. 44, no. 5. — Pp. 1974–1980.
citeseer.ist.psu.edu/206820.html
[275] Mason L., Bartlett P., Baxter J.
Direct optimization of margins improves generalization in combined classifiers // Proceedings of the 1998 conference on Advances in Neural Information Processing Systems II. — MIT Press, 1999. — Pp. 288–294.
citeseer.ist.psu.edu/mason98direct.html
[276] Mason L., Bartlett P., Golea M.
Generalization error of combined classifiers: Tech. rep.: Department of Systems Engineering, Australian National University, 1997.
citeseer.ist.psu.edu/mason97generalization.html
Выводится верхняя оценка вероятности ошибки для решающих правил, представимых в виде пороговой выпуклой комбинации пороговых выпуклых комбинаций базовых классификаторов. К данному типу правил относятся нейросети с одним скрытым уровнем, а также алгоритмы взвешенного голосования (в частности, бустинг [217]) над решающими деревьями. Полученные оценки зависят от доли обучающих объектов с малым отступом (margin) и средневзвешенной сложности базовых классификаторов, взятых с теми же весами, с которыми они входят в выпуклую комбинацию. Используется представление бинарных решающих деревьев в виде пороговых выпуклых комбинаций. Вводится новая мера сложности решающего дерева — эффективное число листьев, которое зависит от распределения обучающих объектов по листьям дерева. Оно может оказаться существенно меньше общего числа листьев, если значительная доля листьев редко используется при классификации, занимаясь обработкой «исключительных ситуаций».
[277] Mason L.
Margins and Combined Classifiers: Ph.D. thesis / Australian National University. — 1999.
[278] Rosset S., Zhu J., Hastie T.
Margin maximizing loss functions // Advances in Neural Information Processing Systems 16 / Ed. by S. Thrun, L. Saul, B. Schölkopf. — Cambridge, MA: MIT Press, 2004.
citeseer.ist.psu.edu/rosset03margin.html
[279] Allwein E. L., Schapire R. E., Singer Y.
Reducing multiclass to binary: A unifying approach for margin classifiers // Proc. 17th International Conf. on Machine Learning. — Morgan Kaufmann, San Francisco, CA, 2000. — Pp. 9–16.
citeseer.ist.psu.edu/article/allwein00reducing.html
[280] Golea M., Bartlett P., Lee W. S., Mason L.
Generalization in decision trees and DNF: Does size matter? // Advances in Neural Information Processing Systems / Ed. by M. I. Jordan, M. J. Kearns, S. A. Solla. — Vol. 10. — The MIT Press, 1998.
citeseer.ist.psu.edu/golea97generalization.html
Последние исследования [273] продемонстрировали, что вероятность ошибки пороговых выпуклых комбинаций (таких, как машины опорных векторов, сигмоидальные нейросети и бустинг) не зависит от сложности классификатора и может быть существенно ниже границ, предсказываемых теорией Вапника-Червоненкиса [97]. В данной статье этот результат обобщается на класс булевых функций, представимых в виде выпуклой комбинации булевых функций (термов) с пороговым решающим правилом. В таком виде представимы бинарные решающие деревья и дизъюнктивные нормальные формы. С помощью техники [273] показывается, что сложность комбинации равна средней взвешенной сложности термов, взятых с теми же весами, с которыми они входят в комбинацию. Вводится новая мера сложности — эффективное число термов, которое может оказаться существенно меньше, когда значительная доля термов редко используется при классификации, занимаясь обработкой «исключительных ситуаций».
[281] Bax E. T.
Validation of voting committees // Neural Computation. — 1998. — Vol. 10, no. 4. — Pp. 975–986.
citeseer.ist.psu.edu/bax97validation.html
[282] Smola A., Bartlett P., Scholkopf B., Schuurmans D.
Advances in large margin classifiers. — MIT Press, Cambridge, MA. — 2000.
citeseer.ist.psu.edu/article/smola00advances.html
[283] Valentini G., Dietterich T.
Bias-variance analysis and ensembles of SVM // MCS Third International Workshop, Cagliari, Italy. — Lecture Notes in Computer Science. Springer-Verlag, 2002.
citeseer.ist.psu.edu/valentini02biasvariance.html
[284] Valentini G., Masulli F.
Ensembles of learning machines // Neural Nets WIRN Vietri-02 / Ed. by M. Marinaro, R. Tagliaferri. — Springer-Verlag, Heidelberg (Germany), 2002.
citeseer.ist.psu.edu/valentini02ensembles.html
[285] Garg A., Har-Peled S., Roth D.
Generalization bounds for linear learning algorithms: Tech. Rep. UIUCDCS-R-: University of Illinois, Department of Computer Science, 2001.
citeseer.ist.psu.edu/455960.html
[286] Garg A., Har-Peled S., Roth D.
On generalization bounds, projection profile, and margin distribution // ICML'02. — 2002.
citeseer.ist.psu.edu/garg02generalization.html
[287] Garg A., Roth D.
Margin distribution and learning algorithms // ICML'03. — 2003. — Pp. 210–217.
citeseer.ist.psu.edu/600544.html
[288] Koltchinskii V., Panchenko D.
Empirical margin distributions and bounding the generalization error of combined classifiers. — 2000.
citeseer.ist.psu.edu/koltchinskii00empirical.html
[289] Evgeniou T., Pontil M., Elisseeff A.
Leave one out error, stability, and generalization of voting combinations of classifiers: Tech. Rep. 2001-21-TM: INSEAD, 2001.
citeseer.ist.psu.edu/445768.html
Исследуется обобщающая способность алгоритмов взвешенного голосования вещественнозначных классификаторов. Рассматривается частный случай, когда голосование производится методом баггинга [203] при фиксированных весах, а в качестве классификаторов используются ядерные алгоритмы (kernel machines). В частности, это могут быть машины опорных векторов (SVM, support vector machines [158]), построенные с разными ядрами, по разным обучающим подвыборкам, и/или по различным подописаниям объектов. В отличие от принятого подхода, обобщающая способность характеризуется не вероятностью ошибочной классификации, а ошибкой скользящего контроля с одним отделяемым объектом (Loo, leave-one-out cross-validation). Выводится верхняя оценка Loo для машин опорных векторов. При фиксированных весах Loo выпуклой комбинации нескольких SVM оценивается сверху суммой их Loo, взятых с теми же весами. Выводятся новые оценки стабильности выпуклой комбинации классификаторов. Ошибка скользящего контроля стабильных алгоритмов сходится к вероятности ошибочной классификации со скоростью порядка корня квадратного от длины выборки. Это означает, что при определенных условиях баггинг может увеличивать стабильность базовых классификаторов. Теоретические оценки подтверждаются экспериментами на 4 реальных задачах из репозитория UCI, а также на выборке рукописных символов, предоставленной почтовой службой США [190]. Приводятся результаты экспериментального сравнения обобщающей способности взвешенного голосования при фиксированных и настраиваемых весах, а также отдельных классификаторов без голосования. Комбинации с настраиваемыми весами существенно менее чувствительны к изменениям ядер в базовых классификаторах. Отмечается, что взвешенное голосование SVM практически не улучшает обобщающую способность по сравнению с отдельной SVM. Тем не менее, взвешенное голосование обладает существенно большей эффективностью при распараллеливании, поскольку базовые алгоритмы можно настраивать на подвыборках существенно меньшей длины.
[290] Antos A., Kegl B., Linder T., Lugosi G.
Data-dependent margin-based generalization bounds for classification // Journal of Machine Learning Research. — 2002. — Pp. 73–98.
citeseer.ist.psu.edu/article/antos02datadependent.html
[291] Воронцов К. В., Каневский Д. Ю.
Коэволюционный метод обучения алгоритмических композиций // Таврический вестник информатики и математики. — 2005. — N° 2. — С. 51–66.
www.ccas.ru/frc/papers/voron05twim.pdf
Рассматривается новый метод построения алгоритмических композиций в задачах обучения по прецедентам. Данный метод является развитием идей алгебраического подхода к проблеме распознавания, а также методов бустинга, бэггинга и случайных подпространств. Для обучения базовых алгоритмов применяется специальный генетический алгоритм — кооперативная коэволюция. Метод является универсальным, то есть может применяться к любым семействам базовых алгоритмов, любым корректирующим операциям и любым методам их настройки. Эксперименты на реальных задачах классификации из репозитария UCI показывают, что данный метод позволяет строить композиции из малого числа алгоритмов, обладающие достаточно высокой обобщающей способностью.
[292] 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

Выбор модели алгоритмов (Model Selection)

[293] Ивахненко А. Г., Юрачковский Ю. П.
Моделирование сложных систем по экспериментальным данным. — М.: Радио и связь, 1987.
[294] Kearns M. J., Mansour Y., Ng A. Y., Ron D.
An experimental and theoretical comparison of model selection methods // 8th Conf. on Computational Learning Theory, Santa Cruz, California, US. — 1995. — Pp. 21–30.
citeseer.ist.psu.edu/kearns95experimental.html
Сравнивается обобщающая способность трех методов выбора модели оптимальной сложности в задачах классификации: GRM — гарантированная минимизация риска по Вапнику, MDL — принцип минимальной длины описания по Риссанену, CV — скользящий контроль. Первые два основаны на явном введении штрафа за сложность. На модельной задаче ни один из них не оказался универсально лучшим. GRM склонен переупрощать, а MDL — переусложнять модель. При наличии шума эти эффекты усиливаются и не устраняются умножением штрафной функции на константу. Обобщающая способность CV ограничена сверху оценкой, немного худшей, чем вероятность ошибки произвольного штрафного метода на выборках несколько меньшего объема. Для любого штрафного метода существует задача, на которой он вообще не способен определить оптимум сложности модели. CV более устойчив к шуму и быстрее сходится с ростом длины выборки. Вывод: при отсутствии обоснованного предпочтения штрафных методов лучше применять CV.
[295] Andersson A., Davidsson P., Lind'en J.
Measuring generalization quality: Tech. Rep. LU–CS–TR: 98–202: Department of Computer Science, Lund University, Lund, Sweden, 1998.
citeseer.ist.psu.edu/andersson98measuring.html

Отбор признаков (Features Selection)

[296] Zhang P.
Inference after variable selection in linear regression models // Biometrika. — 1992. — no. 79. — P. 741√746.
[297] Miller A.
Subset selection in regression. — Chapman & Hall/CRC, 2002.
[298] Tibshirani R. J.
Regression shrinkage and selection via the lasso // Journal of the Royal Statistical Society. Series B (Methodological). — 1996. — Vol. 58, no. 1. — Pp. 267–288.
citeseer.ist.psu.edu/tibshirani94regression.html
[299] Osborne M. R., Presnell B., Turlach B. A.
A new approach to variable selection in least squares problems // IMA Journal of Numerical Analysis. — 2000. — Vol. 20, no. 3. — Pp. 389–403.
citeseer.ist.psu.edu/osborne99new.html
[300] Efron B., Hastie T., Johnstone I., Tibshirani R.
Least angle regression: Tech. rep.: Department of Statistics, Stanford University, 2002.
citeseer.ist.psu.edu/efron02least.html
[301] Zhao P., Yu B.
On model selection consistency of lasso: Tech. Rep. 24: Statistics Department, UC Berkeley, 2006.
citeseer.ist.psu.edu/zhao06model.html
[302] Park M. Y., Hastie T.
l regularization path algorithm for generalized linear models. — 2006.
citeseer.ist.psu.edu/park06regularization.html
[303] Hastie T., Taylor J., Tibshirani R., Walther G.
Forward stagewise regression and the monotone lasso // Electronic Journal of Statistics. — 2007. — no. 1. — Pp. 1–29.
citeseer.ist.psu.edu/hastie06forward.html

Анализ вариации и смещения (Bias plus Variance)

[304] Kohavi R., Wolpert D. H.
Bias plus variance decomposition for zero-one loss functions // Machine Learning: Proceedings of the Thirteenth International Conference / Ed. by L. Saitta. — Morgan Kaufmann, 1996. — Pp. 275–283.
citeseer.ist.psu.edu/kohavi96bias.html
[305] Domingos P.
A unified bias-variance decomposition for zero-one and squared loss // AAAI/IAAI. — 2000. — Pp. 564–569.
citeseer.ist.psu.edu/article/domingos00unified.html
[306] Domingos P.
A unified bias-variance decomposition and its applications // Proc. 17th International Conf. on Machine Learning. — Morgan Kaufmann, San Francisco, CA, 2000. — Pp. 231–238.
citeseer.ist.psu.edu/domingos00unified.html
Предлагаются определения вариации и смещения, обобщенные на случай произвольной функции потерь. При квадратичной функции потерь определение совпадает с классическим — среднеквадратичная ошибка раскладывается в сумму вариации, смещения и неустранимого шума. При бинарной функции потерь разложение также аддитивно, но коэффициенты при компонентах вариации и шума не обязательно единицы. В частности, коэффициент при вариации принимает отрицательное значение на смещенных объектах (т.,е. тех, для которых большинство алгоритмов, обученных по заданной системе обучающих выборок, дают неверный ответ). Предлагается методика измерения вариации и смещения, основанная на однократном разбиении выборки на обучающую и тестовую часть (в пропорции 2:1), с последующей генерацией 100 обучающих подвыборок методом бутстрепа. Вариация и смещение оцениваются отдельно для каждого тестового объекта. Эксперименты проводятся на 30 реальных задачах из репозитория UCI, для 3 алгоритмов: решающие деревья С4.5, бустинг над C4.5, метод k ближайших соседей. Эмпирический анализ вариации и смещения позволяет лучше понимать многие особенности алгоритмов классификации, в частности, почему простые алгоритмы превосходят сложные, и почему композиции алгоритмов превосходят отдельно взятые алгоритмы.
[307] Webb G. I., Conilione P.
Estimating bias and variance from data. — 2003.
citeseer.ist.psu.edu/rey04estimating.html

Стабильность алгоритмов обучения (Stability of Learning Algorithms)

[308] Rogers W., Wagner T.
A finite sample distribution-free performance bound for local discrimination rules // Annals of Statistics. — 1978. — Vol. 6, no. 3. — Pp. 506–514.
[309] Devroye L. P., Wagner T. J.
Distribution-free inequalities for the deleted and holdout error estimates // IEEE Transactions on Information Theory. — 1979. — Vol. 25, no. 2. — Pp. 202–207.
[310] Devroye L. P., Wagner T. J.
Distribution-free performance bounds for potential function rules // IEEE Transactions on Information Theory. — 1979. — Vol. 25, no. 5. — Pp. 601–604.
[311] Devroye L., Gyorfi L., Krzyzak A., Lugosi G.
On the strong universal consistency of nearest neighbor regression function estimates // Annals of Statistics. — 1994. — no. 22. — Pp. 1371–1385.
citeseer.ist.psu.edu/devroye92strong.html
[312] Bax E. T.
Similar classifiers and VC error bounds: Tech. Rep. CalTech-CS-TR97-14: 6 1997.
citeseer.ist.psu.edu/bax97similar.html
[313] Bousquet O., Elisseeff A.
Algorithmic stability and generalization performance // Advances in Neural Information Processing Systems 13. — 2001. — Pp. 196–202.
citeseer.ist.psu.edu/article/bousquet00algorithmic.html
Получены новые оценки обобщающей способности, которые не зависят от сложности семейства алгоритмов и используют только свойство стабильности метода обучения. Метод обучения называется стабильным, если удаление одного обучающего объекта приводит к незначительному изменению результирующего алгоритма. Для сопоставления полученных оценок с классическими вместо функционала равномерной сходимости вводится новый функционал качества, явным образом зависящий от метода обучения (отображения, которое обучающей выборке ставит в соответствие алгоритм). Для данного функционала остаются верны все классические оценки, использующие различные меры сложности семейства алгоритмов: мощность покрытия, функцию роста или фат-размерность. Перечисленные общие результаты справедливы как для задач классификации, так и для восстановления регрессии. Показано, что алгоритмы построения линейной регрессии и некоторые алгоритмы, использующие принцип регуляризации, являются стабильными. При этом увеличение регуляризирующего коэффициента приводит к увеличению стабильности. Отмечается, что в общем случае стабильность не дает лучших оценок обобщающей способности, чем классический сложностный подход. Тем не менее, усиление оценок возможно при наличии подходящей априорной информации. Такой информацией может быть распределение на множестве исходных объектов в случае линейной регрессии, либо модель предметной области в случае методов регуляризации.
[314] Bousquet O., Elisseeff A.
Stability and generalization // Journal of Machine Learning Research. — 2002. — no. 2. — Pp. 499–526.
citeseer.ist.psu.edu/article/bousquet00stability.html
Работа является развитием [313]. Выводятся новые верхние оценки обобщающей способности стабильных алгоритмов классификации и восстановления регрессии. Оценивается отклонение средней ошибки на обучении от матожидания ошибки, а также отклонение скользящего контроля с одним отделяемым объектом (leave-one-out cross-validation) от матожидания ошибки. В обоих случаях оценки не зависят от сложности семейства алгоритмов, а только от стабильности метода обучения, причем во втором случае оценки несколько точнее. Вводятся несколько понятий стабильности. Условие равномерной стабильности (uniform stability) сильнее стабильности результирующих алгоритмов (hypothesis stability), которое, в свою очередь, сильнее стабильности ошибок (error stability). Стабильность классификации (classification stability) является вариантом равномерной стабильности, адаптированным для случая вещественнозначных классификаторов. Для равномерно стабильных методов получены полиномиальные оценки, обобщающие результаты Девроя и Вагнера [309]. Для случая стабильности алгоритмов получены новые экспоненциальные оценки. Ранее свойство стабильности было доказано только для локальных методов типа ближайших соседей. В данной работе доказывается стабильность широкого класса методов, основанных на минимизации регуляризованных функционалов. Этот результат применяется к методу опорных векторов (SVM) и регуляризации с использованием дивергенции Кульбака-Лейблера (относительной энтропии).
[315] Kutin S., Niyogi P.
The interaction of stability and weakness in AdaBoost. — 2001.
citeseer.ist.psu.edu/kutin01interaction.html
[316] Kutin S., Niyogi P.
Almost-everywhere algorithmic stability and generalization error: Tech. Rep. TR-2002-03: University of Chicago, 2002.
citeseer.ist.psu.edu/kutin02almosteverywhere.html
[317] Elisseeff A., Evgeniou T., Pontil M.
Stability of randomized learning algorithms // Journal of Machine Learning Research. — 2005. — no. 6. — Pp. 55–79.
jmlr.csail.mit.edu

Скользящий контроль (Cross Validation)

[318] Efron B.
The Jackknife, the Bootstrap, and Other Resampling Plans. — SIAM, Philadelphia, 1982.
[319] Эфрон Б.
Нетрадиционные методы многомерного статистического анализа. — М: Финансы и статистика, 1988.
[320] Kohavi R.
A study of cross-validation and bootstrap for accuracy estimation and model selection // 14th International Joint Conference on Artificial Intelligence, Palais de Congres Montreal, Quebec, Canada. — 1995. — Pp. 1137–1145.
citeseer.ist.psu.edu/kohavi95study.html
[321] Kearns M.
A bound on the error of cross validation using the approximation and estimation rates, with consequences for the training-test split // Advances in Neural Information Processing Systems / Ed. by D. S. Touretzky, M. C. Mozer, M. E. Hasselmo. — Vol. 8. — The MIT Press, 1996. — Pp. 183–189.
citeseer.ist.psu.edu/kearns96bound.html
Рассматривается метод структурной минимизации риска, в котором семейство оптимальной сложности выбирается по результату теста на независимой контрольной выборке. Выводится оценка вероятности ошибки для алгоритма, получаемого данным методом. Оценка зависит от емкости (VC-dimension) рассматриваемых семейств. На модельной задаче «выделения одномерных интервалов» исследуется вопрос об оптимальном соотношении между числом обучающих и тестовых объектов. При невысокой сложности восстанавливаемой зависимости оценка слабо зависит от этого соотношения. По мере увеличения сложности оптимум становится более выраженным, оптимальное значение доли тестовых объектов уменьшается. Рекомендуемое соотношение, подходящее для большинства случаев — около 10% тестовых объектов.
[322] Kearns M. J., Ron D.
Algorithmic stability and sanity-check bounds for leave-one-out cross-validation // Computational Learning Theory. — 1997. — Pp. 152–162.
citeseer.ist.psu.edu/kearns97algorithmic.html
Принято считать, что скользящий контроль характеризует обобщающую способность алгоритма лучше, чем частота ошибок на обучающей выборке. В данной статье авторам удается показать лишь то, что он не может характеризовать ее существенно хуже. Рассматривается задача классификации на два класса и функционал скользящего контроля с одним отделяемым объектом (leave-one-out cross-validation). Выводится верхняя оценка отклонения скользящего контроля от вероятности ошибки алгоритма, полученного по той же выборке. Данная оценка аналогична оценкам отклонения частоты ошибок на обучении от вероятности ошибки, полученным в статистической теории Вапника-Червоненкиса. Она также зависит от емкости семейства алгоритмов, и также справедлива при произвольном распределении вероятностей на множестве объектов, то есть является оценкой «худшего случая». Отличие заключается в том, что для оценивания скользящего контроля потребовалось ввести два дополнительных предположения. Во-первых, метод обучения должен обладать свойством стабильности, когда малое изменение обучающей выборки приводит к малому изменению обученного алгоритма. Вводится два различных понятия стабильности: стабильность результирующих алгоритмов (hypothesis stability), и стабильность ошибок (error stability). Предположение о стабильности ошибок является менее обременительным и лучше подходит для случая, когда восстанавливаемая зависимость не обязательно содержится в семействе алгоритмов (unrealizable case). Доказывается, что для семейств конечной емкости метод минимизации эмпирического риска является стабильным. Во-вторых, скользящий контроль должен «переоценивать» (overestimate) частоту ошибок на обучении, то есть значение скользящего контроля с высокой вероятностью должно быть не сильно меньше частоты ошибок на обучении. Несмотря на указанные дополнительные предположения, полученная оценка дает всего лишь «разумные» верхние границы (sanity-check bounds) для отклонения скользящего контроля от вероятности ошибок. Выводятся также нижние оценки, показывающие необходимость требований стабильности, переоценивания и конечной емкости. Таким образом, подтвердить исходное предположение об «особой эффективности» скользящего контроля пока не удается.
[323] Ng A. Y.
Preventing overfitting of cross-validation data // Proc. 14th International Conference on Machine Learning. — Morgan Kaufmann, 1997. — Pp. 245–253.
citeseer.ist.psu.edu/ng97preventing.html
Исследуется эффект переобучения, возникающий при выборе модели из заданного конечного набора моделей методом скользящего контроля (CV). Если число моделей велико, а контрольная выборка имеет небольшую длину и достаточно сильно «зашумлена», то оценка скользящего контроля может случайно оказаться наилучшей для модели, весьма далекой от оптимальной. Предлагается метод обнаружения и устранения эффекта переобучения, основанный на следующих соображениях. Если частота ошибок на контроле оказывается меньше присущего выборке уровня шума, то это свидетельствует о переобучении. Вероятность выбора наилучшей модели максимальна, когда частота ошибок на контроле совпадает с уровнем шума. Поэтому в качестве оптимальной предлагается выбирать модель с числом ошибок на контроле, немного большим наименьшего. Точнее говоря, предлагается отбрасывать k% моделей с наименьшим числом ошибок на контроле. Этот алгоритм назван k-процентным скользящим контролем (k-percentile-CV). Предлагается также алгоритм оптимального выбора числа k с помощью обычного скользящего контроля с одним отделяемым объектом (leave-one-out cross-validation или LOOCV). Полученный в результате объединения этих двух процедур алгоритм назван LOOCVCV (leave-one-out cross-validated cross-validation). Эффективность данного алгоритма иллюстрируется на модельных задачах с искусственно генерируемым шумом. При уровне шума более 5–10% алгоритм LOOCVCV выбирает лучшие модели, чем обычный CV. При меньшем уровне шума, когда нет оснований подозревать CV в переобучении, рекомендуется применять обычный CV.
[324] Holden S. B.
Cross-validation and the pac learning model: Tech. Rep. RN/96/64: Dept. of CS, Univ. College, London, 1996.
[325] Anthony M., Holden S. B.
Cross-validation for binary classification by real-valued functions: Theoretical analysis // Computational Learing Theory. — 1998. — Pp. 218–229.
citeseer.ist.psu.edu/anthony98crossvalidation.html
[326] Zhu H., Rohwer R.
No free lunch for cross-validation // Neural Computation. — 1996. — Vol. 8, no. 7. — Pp. 1421–1426.
citeseer.ist.psu.edu/zhu96no.html
[327] Goutte C.
Note on free lunches and cross-validation // Neural Computation. — 1997. — Vol. 9, no. 6. — Pp. 1245–1249.
citeseer.ist.psu.edu/goutte97note.html
[328] Bontempi G., Birattari M.
A bound on the cross-validation estimate for algorithm assessment // Eleventh Belgium/Netherlands Conference on Artificial Intelligence (BNAIC). — 1999. — Pp. 115–122.
citeseer.ist.psu.edu/225930.html
Вводятся два различных понятия обобщающей способности: первое характеризует отдельный алгоритм, полученный в результате обучения, второе характеризует метод обучения в целом. В предшествовавших работах [321, 322, 324] оценивалось отклонение скользящего контроля от обобщающей способности отдельного алгоритма. Скорость сходимости этой величины к нулю очень мала, зависит от емкости семейства и стабильности метода обучения. Отсюда делался слишком слабый вывод о том, что скользящий контроль характеризует качество алгоритма всего лишь не хуже, чем частота ошибок на обучении (sanity-check bounds). В данной работе получена оценка отклонения скользящего контроля от обобщающей способности it метода обучения, которая не зависит от емкости семейства, а только от длины обучения и контроля. Таким образом, данная работа проясняет природу скользящего контроля. Завышенность предыдущих оценок объясняется неудачным выбором функционала качества.
[329] Blum A., Kalai A., Langford J.
Beating the hold-out: Bounds for k-fold and progressive cross-validation // Computational Learing Theory. — 1999. — Pp. 203–208.
citeseer.ist.psu.edu/blum99beating.html
[330] Mullin M., Sukthankar R.
Complete cross-validation for nearest neighbor classifiers // Proceedings of International Conference on Machine Learning. — 2000.
citeseer.ist.psu.edu/309025.html
Для алгоритма ближайших соседей и некоторых его вариаций получены эффективные формулы вычисления функционала полного скользящего контроля. Данный функционал определяется через множество всех разбиений выборки на обучающую и контрольную подвыборки заданной длины. Сложность вычисления квадратична по длине выборки, в то время как непосредственный перебор разбиений экспоненциален.
[331] Scheffer T.
Predicting the generalization performance of cross validatory model selection criteria // Proc. 17th International Conf. on Machine Learning. — Morgan Kaufmann, San Francisco, CA, 2000. — Pp. 831–838.
citeseer.ist.psu.edu/scheffer00predicting.html

Априорные ограничения (A Priory Knowledge)

[332] Abu-Mostafa Y. S.
Hints // Neural Computation. — 1995. — Vol. 7, no. 4. — Pp. 639–671.
citeseer.ist.psu.edu/abu-mostafa95hints.html
[333] Sill J., Abu-Mostafa Y. S.
Monotonicity hints // Advances in Neural Information Processing Systems / Ed. by M. C. Mozer, M. I. Jordan, T. Petsche. — Vol. 9. — The MIT Press, 1997. — P. 634.
citeseer.ist.psu.edu/sill97monotonicity.html
[334] Sill J.
Monotonic networks // Advances in Neural Information Processing Systems / Ed. by M. I. Jordan, M. J. Kearns, S. A. Solla. — Vol. 10. — The MIT Press, 1998.
citeseer.ist.psu.edu/156430.html
[335] Sill J.
Generalization bounds for connected function classes.
citeseer.ist.psu.edu/127284.html
[336] Sill J.
The capacity of monotonic functions // Discrete Applied Mathematics (special issue on VC dimension). — 1998. — Vol. 86. — Pp. 95–107.
citeseer.ist.psu.edu/49191.html
Исследуется семейство монотонных бинарных классификаторов, имеющее бесконечную емкость (VC-dimension). Показывается, что его эффективная емкость равна длине максимальной антицепи в заданной выборке и принимает небольшие значения на выборках, близких к линейно упорядоченным. Рассматривается еще одна характеристика сложности семейства, зависящая от выборки, и определяемая как длина выборки, разделимой в данном классе функций с вероятностью 50% после случайного перемешивания исходных классификаций. На модельных данных показывается, что обе емкостные характеристики могут быть существенно ниже для семейства монотонных классификаторов, чем для нейронных сетей. Тем самым обосновывается, что монотонность является достаточно сильным ограничением, способным обеспечить высокое качество обучения.
[337] Blum A., Burch C., Langford J.
On learning monotone boolean functions // IEEE Symposium on Foundations of Computer Science. — 1998. — Pp. 408–415.
citeseer.ist.psu.edu/article/blum98learning.html

Решающие деревья и списки (Decision Trees and Lists)

[338] Quinlan J.
Induction of decision trees // Machine Learning. — 1986. — Vol. 1, no. 1. — Pp. 81–106.
[339] Quinlan J. R.
C4.5: Programs for machine learning. — Morgan Kaufmann, San Francisco, CA, 1993.
[340] Rivest R. L.
Learning decision lists // Machine Learning. — 1987. — Vol. 2, no. 3. — Pp. 229–246.
citeseer.ist.psu.edu/rivest87learning.html
Предлагается новый класс бинарных классификаторов — решающие списки k-DL, основанные на последовательном вычислении конъюнкций длины не более k. Показано, что класс k-DL богаче классов k-ДНФ, k-КНФ k-конъюнктивных ДНФ, k-дизъюнктивных КНФ и решающих деревьев глубины не более k. Показано, что достаточно простой «жадный» алгоритм обучения решающих списков является полиномиально обучаемым по Валианту [101].
[341] Норушис А.
Построение логических (древообразных) классификаторов методами нисходящего поиска (обзор) // Статистические проблемы управления. Вып. 93 / Под ред. Ш. Раудис. — Вильнюс, 1990. — С. 131–158.
[342] Донской В. И.
Алгоритмы обучения, основанные на построении решающих деревьев // ЖВМиМФ. — 1982. — Т. 22, N° 4. — С. 963–974.
[343] Донской В. И., Башта А. И.
Дискретные модели принятия решений при неполной информации. — Симферополь: Таврия, 1992. — С. 166.
[344] John G. H., Kohavi R., Pfleger K.
Irrelevant features and the subset selection problem // International Conference on Machine Learning. — 1994. — Pp. 121–129.
citeseer.ist.psu.edu/john94irrelevant.html
[345] Martin J. K.
An exact probability metric for decision tree splitting and stopping // Machine Learning. — 1997. — Vol. 28, no. 2-3. — Pp. 257–291.
citeseer.ist.psu.edu/martin97exact.html
Предлагается критерий ветвления решающих деревьев, основанный на точном тесте Фишера (Fisher's Exact Test). Этот тест использует гипергеометрическое распределение для проверки нулевой гипотезы о независимости двух предикатов. Стандартные информационные критерии (IGain, ORT, Beta, X2, G2) являются асимптотическими аппроксимациями предложенного точного критерия. Данный критерий более точен на малых подвыборках, не приводит к чрезмерному дроблению поддеревьев и не смещен в сторону выбора признаков с бóльшим числом градаций. В работе показано,что он позволяет повысить эффективность процедуры раннего усечения (pre-pruning) дерева.
[346] Breslow L. A., Aha D. W.
Simplifying decision trees: a survey // Knowledge Engineering Review. — 1997. — Vol. 12, no. 1. — Pp. 1–40.
citeseer.ist.psu.edu/breslow96simplifying.html
[347] Chipman H. A., George E. I., McCulloch R. E.
Bayesian CART model search // Journal of the American Statistical Association. — 1998. — Vol. 93, no. 443. — Pp. 935–947.
citeseer.ist.psu.edu/chipman97bayesian.html
[348] Freund Y.
Self bounding learning algorithms // COLT: Proceedings of the Workshop on Computational Learning Theory, Morgan Kaufmann Publishers. — 1998.
citeseer.ist.psu.edu/freund98self.html
[349] Freund Y., Mason L.
The alternating decision tree learning algorithm // Sixteenth International Conference on Machine Learning. — 1999. — Pp. 124–133.
[350] Mansour Y., McAllester D.
Generalization bounds for decision trees // Proc. 13th Annu. Conference on Comput. Learning Theory. — Morgan Kaufmann, San Francisco, 2000. — Pp. 69–80.
citeseer.ist.psu.edu/mansour00generalization.html
[351] Russel S. J., Zilberstein S.
Composing real-time systems // IJCAI. — 1991. — Pp. 212–217.
[352] Nevo Z., El-Yaniv R.
On online learning of decision lists // Journal of Machine Learning Research. — 2002. — Vol. 3. — Pp. 271–301.
citeseer.ist.psu.edu/nevo02online.html
[353] Esmeir S., Markovitch S.
Lookahead-based algorithms for anytime induction of decision trees // Proceedings of the 21st International Conference on Machine Learning (ICML-2004). — 2004.
citeseer.ist.psu.edu/esmeir04lookaheadbased.html
[354] Marchand M., Shawe-Taylor J.
Learning with the set covering machine // Proc. 18th International Conf. on Machine Learning. — Morgan Kaufmann, San Francisco, CA, 2001. — Pp. 345–352.
citeseer.ist.psu.edu/452556.html
[355] Marchand M., Shah M., Shawe-Taylor J., Sokolova M.
The set covering machine with data-dependent half-spaces // Proc. 20th International Conf. on Machine Learning. — Morgan Kaufmann, 2003. — Pp. 520–527.
www.hpl.hp.com/conferences/icml03/titlesAndAuthors.html
[356] Sokolova M., Marchand M., Japkowicz N., Shawe-Taylor J.
The decision list machine // Advances in Neural Information Processing Systems 15. — MIT-Press, Cambridge, MA, USA, 2003. — Pp. 921–928.
citeseer.ist.psu.edu/597803.html
[357] Anthony M.
Generalization error bounds for threshold decision lists // Journal of Machine Learning Research. — 2004. — Vol. 5. — Pp. 189–217.
jmlr.csail.mit.edu
[358] Klivans A. R., Servedio R. A.
Toward attribute efficient learning of decision lists and parities // J. Mach. Learn. Res. — 2006. — Vol. 7. — Pp. 587–602.
[359] Дюличева Ю. Ю.
Стратегии редукции решающих деревьев (обзор) // Таврический вестник информатики и математики. — 2002. — N° 1. — С. 10–17.
[360] Дюличева Ю. Ю.
Оценка VCD r-редуцированного эмпирического леса // Таврический вестник информатики и математики. — 2003. — N° 1. — С. 31–42.
www.ccas.ru/frc/papers/dulicheva03vcdforest.pdf
[361] Дюличева Ю. Ю.
Модели коррекции редуцированных бинарных решающих деревьев. — Диссертация на соискание ученой степени к.ф.-м.н., Симферополь: Таврический национальный университет им. В. И. Вернадского. — 2004.
www.ccas.ru/frc/papers/dulicheva04phd.pdf

Поиск ассоциативных правил (Association Rules Induction)

[362] Agrawal R., Imielinski T., Swami A. N.
Mining association rules between sets of items in large databases // Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data / Ed. by P. Buneman, S. Jajodia. — Washington, D.C.: 1993. — Pp. 207–216.
citeseer.ist.psu.edu/agrawal93mining.html
[363] Agrawal R., Imielinski T., Swami A.
Database mining: A performance perspective // Special Issue on Learning and Discovery in Knowledge-Based Databases / Ed. by N. Cercone, M. Tsuchiya. — Washington, U.S.A.: Institute of Electrical and Electronics Engineers, 1993. — Vol. 6. — Pp. 914–925.
citeseer.ist.psu.edu/agrawal93database.html
[364] Agrawal R., Srikant R.
Fast algorithms for mining association rules // Proc. 20th Int. Conf. Very Large Data Bases, VLDB / Ed. by J. B. Bocca, M. Jarke, C. Zaniolo. — Morgan Kaufmann, 1994. — Pp. 487–499.
citeseer.ist.psu.edu/agrawal94fast.html
[365] Mannila H., Toivonen H., Verkamo A. I.
Efficient algorithms for discovering association rules // AAAI Workshop on Knowledge Discovery in Databases (KDD-94) / Ed. by U. M. Fayyad, R. Uthurusamy. — Seattle, Washington: AAAI Press, 1994. — Pp. 181–192.
citeseer.ist.psu.edu/mannila94efficient.html
[366] Toivonen H.
Sampling large databases for association rules // In Proc. 1996 Int. Conf. Very Large Data Bases / Ed. by T. M. Vijayaraman, A. P. Buchmann, C. Mohan, N. L. Sarda. — Morgan Kaufman, 1996. — Pp. 134–145.
citeseer.ist.psu.edu/toivonen96sampling.html
[367] Srikant R., Agrawal R.
Mining generalized association rules // Future Generation Computer Systems. — 1997. — Vol. 13, no. 2–3. — Pp. 161–180.
citeseer.ist.psu.edu/srikant95mining.html
[368] Hidber C.
Online association rule mining // SIGMOD Conf. — 1999. — Pp. 145–156.
citeseer.ist.psu.edu/hidber98online.html
[369] Zheng Z., Kohavi R., Mason L.
Real world performance of association rule algorithms // Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining / Ed. by F. Provost, R. Srikant. — 2001. — Pp. 401–406.
citeseer.ist.psu.edu/zheng01real.html
[370] Hipp J., Güntzer U., Nakhaeizadeh G.
Algorithms for association rule mining — a general survey and comparison // SIGKDD Explorations. — 2000. — Vol. 2, no. 1. — Pp. 58–64.
citeseer.ist.psu.edu/hipp00algorithms.html

Метрические алгоритмы (Distance Functions methods)

[371] Atkeson C. G., Moore A. W., Schaal S.
Locally weighted learning // Artificial Intelligence Review. — 1997. — Vol. 11, no. 1-5. — Pp. 11–73.
citeseer.ist.psu.edu/atkeson96locally.html
[372] Cost S., Salzberg S.
A weighted nearest neighbor algorithm for learning with symbolic features // Machine Learning. — 1993. — Vol. 10. — Pp. 57–78.
citeseer.ist.psu.edu/cost93weighted.html

Непараметрические методы (Nonparametric methods)

[373] Rosenblatt M.
Remarks on some nonparametric estimates of a density function // Annals of Mathematical Statistics. — 1956. — Vol. 27, no. 3. — Pp. 832–837.
[374] Parzen E.
On the estimation of a probability density function and mode // Annals of Mathematical Statistics. — 1962. — Vol. 33. — Pp. 1065–1076.
citeseer.ist.psu.edu/parzen62estimation.html
[375] Епанечников В. А.
Непараметрическая оценка многомерной плотности вероятности // Теория вероятностей и ее применения. — 1969. — Т. 14, N° 1. — С. 156–161.
[376] Cleveland W. S.
Robust locally weighted regression and smoothing scatter plots // Journal of the American Statistical Association. — 1979. — Vol. 74, no. 368. — Pp. 829–836.
[377] Хардле В.
Прикладная непараметрическая регрессия. — М.: Мир, 1993.
[378] Лапко А. В., Ченцов С. В., Крохов С. И., Фельдман Л. А.
Обучающиеся системы обработки информации и принятия решений. Непараметрический подход. — Новосибирск: Наука, 1996.
[379] Лапко А. В., Лапко В. А., Соколов М. И., Ченцов С. В.
Непараметрические модели коллективного типа. — Новосибирск: Наука, 2000.
[380] Лапко В. А.
Непараметрические коллективы решающих правил. — Новосибирск: Наука, 2002.

Эволюционные и генетические алгоритмы (Evolutionary & Genetic Alrorithms)

[381] Редько В. Г.
Эволюционная кибернетика. — М.: Наука, 2003. — С. 155.
[382] Емельянов В. В., Курейчик В. В., Курейчик В. М.
Теория и практика эволюционного моделирования. — М.: Физматлит, 2003. — С. 432.
[383] Гладков Л. А., Курейчик В. В., Курейчик В. М.
Генетические алгоритмы. — М.: Физматлит, 2006. — С. 320.
[384] Whitley D.
An overview of evolutionary algorithms: practical issues and common pitfalls // Information and Software Technology. — 2001. — Vol. 43, no. 14. — Pp. 817–831.
citeseer.ist.psu.edu/whitley01overview.html
[385] Freitas A.
A survey of evolutionary algorithms for data mining and knowledge discovery. — 2001.
citeseer.ist.psu.edu/freitas01survey.html
[386] Busetti F.
Genetic algorithms overview. — 2002.
citeseer.ist.psu.edu/busetti01genetic.html
[387] Back T.
Optimization by means of genetic algorithms // 36th International Scientific Colloquium / Ed. by E. Kohler. — Technical University of Ilmenau: 1991. — Pp. 163–169.
citeseer.ist.psu.edu/71967.html
[388] Back T., Hoffmeister F., Schwefel H.
A survey of evolution strategies // Proceedings of the 4th International Conference on Genetic Algorithms. San Diego, CA, July 1991 / Ed. by L. B. Belew, R. K. Booker. — Morgan Kaufmann, 1991. — Pp. 2–9.
citeseer.ist.psu.edu/back91survey.html
[389] Baker J. E.
Adaptive selection methods for genetic algorithms // Proceedings of an International Conference on Genetic Algorithms and their Applications / Ed. by J. J. Grefenstette. — Lawrence Erlbaum Associates, Hillsdale, NJ, 1985.
[390] Radcliffe N. J.
The algebra of genetic algorithms: Tech. Rep. TR92-11: 1992.
citeseer.ist.psu.edu/article/radcliffe94algebra.html
[391] Hinterding R., Gielewski H., Peachey T. C.
The nature of mutation in genetic algorithms // Proceedings of the Sixth International Conference on Genetic Algorithms / Ed. by L. Eshelman. — San Francisco, CA: Morgan Kaufmann, 1995. — Pp. 65–72.
citeseer.ist.psu.edu/hinterding95nature.html
[392] Yang J., Honavar V.
Feature subset selection using A genetic algorithm // Genetic Programming 1997: Proceedings of the Second Annual Conference / Ed. by J. R. Koza, K. Deb, M. Dorigo, D. B. Fogel, M. Garzon, H. Iba, R. L. Riolo. — Stanford University, CA, USA: Morgan Kaufmann, 1997. — P. 380.
citeseer.ist.psu.edu/article/yang97feature.html
[393] Giordana A., Neri F.
Search-intensive concept induction // Evolutionary Computation. — 1995. — Vol. 3, no. 4. — Pp. 375–419.
citeseer.ist.psu.edu/article/giordana95searchintensive.html
[394] Fidelis M. V., Lopes H. S., Freitas A. A.
Discovering comprehensible classification rules a genetic algorithm // Proceedings of the 2000 Congress on Evolutionary Computation CEC00. — La Jolla Marriott Hotel La Jolla, California, USA: IEEE Press, 2000. — Pp. 805–810.
citeseer.ist.psu.edu/fidelis00discovering.html
[395] Horn J.
Finite Markov Chain Analysis of Genetic Algorithms with Niching // Proceedings of the Fifth International Conference on Genetic Algorithms / Ed. by S. Forrest. — San Mateo, California: Morgan Kaufmann Publishers, 1993. — Pp. 110–117.
citeseer.ist.psu.edu/article/horn93finite.html
[396] Wright A. H., Zhao Y.
Markov chain models of genetic algorithms // Proceedings of the Genetic and Evolutionary Computation Conference / Ed. by W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela, R. E. Smith. — Vol. 1. — Orlando, Florida, USA: Morgan Kaufmann, 13-17 1999. — Pp. 734–741.
citeseer.ist.psu.edu/wright99markov.html
[397] Sloman A.
The ”semantics” of evolution: Trajectories and trade-offs in design space and niche space // Lecture Notes in Computer Science. — 1998. — Vol. 1484. — Pp. 27–??
citeseer.ist.psu.edu/75107.html
[398] Ficici S. G., Melnik O., Pollack J. B.
A game-theoretic investigation of selection methods used in evolutionary algorithms // Proceedings of the 2000 Congress on Evolutionary Computation CEC00. — La Jolla Marriott Hotel La Jolla, California, USA: IEEE Press, 6-9 2000. — P. 880.
citeseer.ist.psu.edu/ficici00gametheoretic.html
[399] Hancock P. J. B.
An empirical comparison of selection methods in evolutionary algorithms // Evolutionary Computing, AISB Workshop. — 1994. — Pp. 80–94.
citeseer.ist.psu.edu/hancock94empirical.html
[400] Angeline P. J.
Adaptive and self-adaptive evolutionary computations // Computational Intelligence: A Dynamic Systems Perspective / Ed. by M. Palaniswami, Y. Attikiouzel. — IEEE Press, 1995. — Pp. 152–163.
citeseer.ist.psu.edu/angeline95adaptive.html
[401] Wiegand R. P.
Applying diffusion to a cooperative coevolutionary model // Lecture Notes in Computer Science. — 1998. — Vol. 1498. — Pp. 560–??
citeseer.ist.psu.edu/442324.html
[402] Coello Coello C. A., Toscano Pulido G.
A Micro-Genetic Algorithm for Multiobjective Optimization // First International Conference on Evolutionary Multi-Criterion Optimization / Ed. by E. Zitzler, K. Deb, L. Thiele, C. A. C. Coello, D. Corne. — Springer-Verlag. Lecture Notes in Computer Science No. 1993, 2001. — Pp. 126–140.
citeseer.ist.psu.edu/444668.html
[403] Whitley D., Rana S. B., Heckendorn R. B.
Island model genetic algorithms and linearly separable problems // Evolutionary Computing, AISB Workshop. — 1997. — Pp. 109–125.
citeseer.ist.psu.edu/whitley97island.html
[404] Paredis J.
Coevolutionary computation // Artificial Life. — 1995. — Vol. 2, no. 4. — Pp. 355–375.
citeseer.ist.psu.edu/158996.html
[405] De Jong K., Potter M. A.
Evolving complex structures via cooperative coevolution // Proc. on the Fourth Annual Conf. on Evolutionary Programming. — Cambridge, MA: MIT Press, 1995. — Pp. 307–317.
citeseer.ist.psu.edu/article/dejong95evolving.html
[406] Eriksson R.
Applying cooperative coevolution to inventory control parameter optimization. — 1996.
citeseer.ist.psu.edu/eriksson96applying.html
[407] Potter M. A., De Jong K.
A cooperative coevolutionary approach to function optimization // Parallel Problem Solving from Nature – PPSN III / Ed. by Y. Davidor, H.-P. Schwefel, R. Männer. — Berlin: Springer, 1994. — Pp. 249–257.
citeseer.ist.psu.edu/potter94cooperative.html
[408] Potter M. A., De Jong K. A., Grefenstette J. J.
A coevolutionary approach to learning sequential decision rules // Proceedings of the Sixth International Conference on Genetic Algorithms / Ed. by L. Eshelman. — San Francisco, CA: Morgan Kaufmann, 1995. — Pp. 366–372.
citeseer.ist.psu.edu/potter95coevolutionary.html
[409] Potter M. A., De Jong K.
Evolving neural networks with collaborative species // Proc. of the 1995 Summer Computer Simulation Conf. — The Society of Computer Simulation, 1995. — Pp. 340–345.
citeseer.ist.psu.edu/potter95evolving.html
[410] Potter M. A.
The Design and Analysis of a Computational Model of Cooperative Coevolution: Ph.D. thesis / George Mason University. — 1997.
citeseer.ist.psu.edu/potter97design.html
[411] Potter M. A., De Jong K. A.
Cooperative coevolution: An architecture for evolving coadapted subcomponents // Evolutionary Computation. — 2000. — Vol. 8, no. 1. — Pp. 1–29.
citeseer.ist.psu.edu/potter00cooperative.html
[412] Rosin C. D., Belew R. K.
New methods for competitive coevolution // Evolutionary Computation. — 1997. — Vol. 5, no. 1. — Pp. 1–29.
citeseer.ist.psu.edu/rosin96new.html
[413] Wiegand R., Liles W., De Jong K.
Analyzing cooperative coevolution with evolutionary game theory // Proceedings of CEC 2002 / Ed. by D. Fogel. — IEEE Press, 2002.
citeseer.ist.psu.edu/wiegand02analyzing.html
[414] Wiegand R. P., Liles W. C., Jong K. A. D.
An empirical analysis of collaboration methods in cooperative coevolutionary algorithms // Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001) / Ed. by L. Spector, E. D. Goodman, A. Wu, W. B. Langdon, H.-M. Voigt, M. Gen, S. Sen et al. — San Francisco, California, USA: Morgan Kaufmann, 7-11 2001. — Pp. 1235–1242.
citeseer.ist.psu.edu/481900.html
[415] Iorio A., Li X.
Parameter control within a cooperative coevolutionary genetic algorithm. — 2002.
citeseer.ist.psu.edu/iorio02parameter.html
[416] Ficici S. G., Pollack J. B.
A game-theoretic approach to the simple coevolutionary algorithm // Parallel Problem Solving from Nature — PPSN VI 6th International Conference / Ed. by H.-P. Schwefel, M. Schoenauer, K. Deb, G. Rudolph, X. Yao, E. Lutton, J. J. Merelo. — Paris, France: Springer Verlag, 16-20 2000.
citeseer.ist.psu.edu/322969.html
[417] Ficici S. G., Pollack J. B.
Pareto optimality in coevolutionary learning // Lecture Notes in Computer Science. — 2001. — Vol. 2159. — Pp. 316+.
citeseer.ist.psu.edu/article/ficici01pareto.html
[418] Bucci A., Pollack J.
Order-theoretic analysis of coevolution problems: Coevolutionary statics. — 2002.
citeseer.ist.psu.edu/article/bucci02ordertheoretic.html
[419] Bucci A., Pollack J.
A mathematical framework for the study of coevolution // FOGA 7: Proceedings of the Foundations of Genetic Algorithms Workshop, San Francisco, CA / Ed. by K. De Jong, R. Poli, J. Rowe. — Morgan Kaufmann Publishers, 2003. — Pp. 221–235.
citeseer.ist.psu.edu/bucci03mathematical.html
[420] Wiegand R., Jansen T.
The cooperative coevolutionary (1+1) ea // MIT Press. — 2003.
[421] Wiegand R. P.
An Analysis of Cooperative Coevolutionary Algorithms: Ph.D. thesis / George Mason University, Fairfax, VA. — 2004.
www.tesseract.org/paul/papers/rpw-dissertation.pdf
[422] Wiegand R. P., Liles W. C., De Jong K. A.
An empirical analysis of collaboration methods in cooperative coevolutionary algorithms // In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO). — 2001.
[423] Luke S., Wiegand R. P.
When coevolutionary algorithms exhibit evolutionary dynamics // In Workshop Proceedings of the 2003 Genetic and Evolutionary Computation Conference. — 2002.
[424] Luke S., Wiegand R. P.
Guaranteeing coevolutionary objective measures // In Foundations of Genetic Algorithms VII. — 2002. — Pp. 237–251.
[425] Minaei-Bigdoli B., Kortemeyer G., Punch W.
Optimizing classification ensembles via a genetic algorithm for a web-based educational system // IAPR International workshop on Syntactical and Structural Pattern Recognition (SSPR 2004) and Statistical Pattern Recognition (SPR 2004), Lisbon, Portugal. — 2004.
[426] Zhou Z.-H., Wu J.-X., Jiang Y., Chen S.-F.
Genetic algorithm based selective neural network ensemble. — 2001.
citeseer.ist.psu.edu/zhou01genetic.html
[427] Stefano C. D., Cioppa A. D., Marcelli A.
Exploiting reliability for dynamic selection of classifiers by means of genetic algorithms // Int. Conf. On Document Analysis and Recognition √ ICDAR▓03, Edinburgh (UK), August 3-6. — 2003. — Pp. 671–675.
citeseer.ist.psu.edu/694137.html
[428] Islam M., Yao X., Murase K.
A constructive algorithm for training cooperative neural network ensembles // IEEE Transactions on Neural Networks. — July 2003. — Vol. 14, no. 4. — Pp. 820–834.
citeseer.ist.psu.edu/islam03constructive.html
[429] Guerra-Salcedo C., Whitley D.
Genetic approach to feature selection for ensemble creation // Proceedings of the Genetic and Evolutionary Computation Conference. — Vol. 1. — Morgan Kaufmann, 1999. — Pp. 236–243.
citeseer.ist.psu.edu/531553.html
[430] Oliveira L., Sabourin R., Bortolozzi F., Suen C.
Feature selection for ensembles: A hierarchical multi-objective genetic algorithm approach // International Conference on Document Analysis and Recognition, Edinburgh-Scotland. — IEEE Computer Society, 2003.
citeseer.ist.psu.edu/oliveira03feature.html
[431] Andre's Pena-Reyes C.
Coevolutionary Fuzzy Modeling. — Springer-Verlag New York, 2004.
citeseer.ifi.unizh.ch/569226.html

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

[432] Теpентьев П. В.
Метод корреляционных плеяд // Вест. Ленингр. ун-та. — 1959. — N° 9. — С. 137–141.
[433] Lance G. N., Willams W. T.
A general theory of classification sorting strategies. 1. hierarchical systems // Comp. J. — 1967. — no. 9. — Pp. 373–380.
[434] Уиллиамс У. Т., Ланс Д. Н.
Методы иерархической классификации // Статистические методы для ЭВМ / Под ред. М. Б. Малютов. — М.: Наука, 1986. — С. 269–301.
[435] Мандель И. Д.
Кластерный анализ. — М.: Финансы и Статистика, 1988.
[436] Jain A., Murty M., Flynn P.
Data clustering: A review // ACM Computing Surveys. — 1999. — Vol. 31, no. 3. — Pp. 264–323.
citeseer.ifi.unizh.ch/jain99data.html

Коллаборативная фильтрация (Collaborative Filtering), Анализ клиентских сред (Customer Environment Analysis)

[437] Goldberg D., Nichols D., Oki B. M., Terry D.
Using collaborative filtering to weave an information tapestry // Communications of the ACM. — 1992. — Vol. 35, no. 12. — Pp. 61–70.
[438] Maltz D. A.
Distributing information for collaborative filtering on usenet net news: Tech. Rep. MIT/LCS/TR-603: 1994.
citeseer.ist.psu.edu/maltz94distributing.html
[439] Resnick P., Iacovou N., Suchak M., Bergstorm P., Riedl J.
GroupLens: An open architecture for collaborative filtering of netnews // Proceedings of ACM 1994 Conference on Computer Supported Cooperative Work. — Chapel Hill, North Carolina: ACM, 1994. — Pp. 175–186.
citeseer.ist.psu.edu/resnick94grouplens.html
[440] Konstan J. A., Miller B. N., Maltz D., Herlocker J. L., Gordon L. R., Riedl J.
GroupLens: Applying collaborative filtering to Usenet news // Communications of the ACM. — 1997. — Vol. 40, no. 3. — Pp. 77–87.
citeseer.ist.psu.edu/konstan97grouplens.html
[441] Pazzani M. J., Billsus D.
Learning and revising user profiles: The identification of interesting web sites // Machine Learning. — 1997. — Vol. 27, no. 3. — Pp. 313–331.
citeseer.ist.psu.edu/pazzani97learning.html
[442] Billsus D., Pazzani M. J.
Learning collaborative information filters // Proc. 15th International Conf. on Machine Learning. — Morgan Kaufmann, San Francisco, CA, 1998. — Pp. 46–54.
citeseer.ist.psu.edu/billsus98learning.html
[443] Breese J. S., Heckerman D., Kadie C.
Empirical analysis of predictive algorithms for collaborative filtering // Fourteenth Annual Conference on Uncertainty in Artificial Intelligence. — 1998. — Pp. 43–52.
citeseer.ist.psu.edu/breese98empirical.html
[444] Nakamura A., Abe N.
Collaborative filtering using weighted majority prediction algorithms // ICML'98: Proceedings of the Fifteenth International Conference on Machine Learning. — Morgan Kaufmann Publishers Inc., 1998. — Pp. 395–403.
[445] Ungar L., Foster D.
A formal statistical approach to collaborative filtering // CONALD'98. — 1998.
citeseer.ist.psu.edu/ungar98formal.html
[446] Ungar L., Foster D.
Clustering methods for collaborative filtering // Proceedings of the Workshop on Recommendation Systems. — AAAI Press, Menlo Park California, 1998.
citeseer.ist.psu.edu/ungar98clustering.html
[447] Kumar S. R., Raghavan P., Rajagopalan S., Tomkins A.
Recommendation systems: A probabilistic analysis // IEEE Symposium on Foundations of Computer Science. — 1998. — Pp. 664–673.
citeseer.ist.psu.edu/kumar98recommendation.html
[448] Condliff M.
Bayesian mixed-effects models for recommender systems // ACM SIGIR Workshop on Recommender Systems: Algorithms and Evaluation, 22nd Intl. Conf. on Research and Development in Information Retrieval. — 1999.
citeseer.ist.psu.edu/condliff99bayesian.html
[449] Schein A. I., Popescul A., Ungar L. H., Pennock D. M.
Generative models for cold-start recommendations // the SIGIR'01 Workshop on Recommender Systems. — 2001.
citeseer.ist.psu.edu/schein01generative.html
[450] Goldberg K., Roeder T., Gupta D., Perkins C.
Eigentaste: A constant time collaborative filtering algorithm // Information Retrieval. — 2001. — Vol. 4, no. 2. — Pp. 133–151.
citeseer.ist.psu.edu/goldberg00eigentaste.html
[451] Pennock D., Horvitz E., Lawrence S., Giles C. L.
Collaborative filtering by personality diagnosis: A hybrid memory- and model-based approach // Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, UAI 2000. — Stanford, CA: 2000. — Pp. 473–480.
citeseer.ist.psu.edu/pennock00collaborative.html
[452] Shani G., Brafman R. I., Heckerman D.
An MDP-based recommender system // Seventeenth Conference on Uncertainty in Artificial Intelligence. — 2002. — Pp. 453–460.
citeseer.ist.psu.edu/shani02mdpbased.html
[453] Lin W., Alvarez S. A., Ruiz C.
Collaborative recommendation via adaptive association rule mining // Web Mining for E-Commerce Workshop (WebKDD'2000), August 2000, Boston. — 2000.
citeseer.ist.psu.edu/lin00collaborative.html
[454] Lin W., Alvarez S. A., Ruiz C.
Efficient adaptive-support association rule mining for recommender systems // Data Mining and Knowledge Discovery. — 2002. — no. 6. — Pp. 83–105.
citeseer.ist.psu.edu/lin02efficient.html
[455] Mobasher B., Dai H., Luo T., Nakagawa M.
Effective personalization based on association rule discovery from web usage data // WIDM '01: Proceedings of the 3rd international workshop on Web information and data management, Atlanta, Georgia, USA. — ACM Press, 2001. — Pp. 9–15.
doi.acm.org/10.1145/502932.502935
[456] ki Leung C. W., fai Chan S. C., lai Chung F.
A collaborative filtering framework based on fuzzy association rules and multiple-level similarity // Knowledge and Information Systems. — 2006. — Vol. 10, no. 3. — Pp. 357–381.
[457] Sarwar B. M., Karypis G., Konstan J. A., Reidl J.
Item-based collaborative filtering recommendation algorithms // World Wide Web. — 2001. — Pp. 285–295.
citeseer.ist.psu.edu/sarwar01itembased.html
[458] Clerkin P., Cunningham P., Hayes C.
Concept discovery in collaborative recommender systems. — 2003.
citeseer.ist.psu.edu/clerkin03concept.html
[459] Montaner M.
Collaborative Recommender Agents Based on Case-Based Reasoning and Trust: Ph.D. thesis / Universitat de Girona. — 2003.
citeseer.ist.psu.edu/montaner03collaborative.html
[460] Pavlov D., Manavoglu E., Pennock D., Giles C. L.
Collaborative filtering with maximum entropy // IEEE Intelligent Systems, Special Issue on Mining the Web Actionable Knowledge. — 2004.
www.algebra.com/simpavlovd/research.html
[461] Deshpande M., Karypis G.
Item-based Top-N recommendation algorithms // ACM Transactions on Information Systems. — 2004. — Vol. 22, no. 1. — Pp. 1–34.
citeseer.ist.psu.edu/deshpande04item.html
[462] Marlin B.
Modeling user rating profiles for collaborative filtering // Advances in Neural Information Processing Systems (NIPS) 16 / Ed. by S. Thrun, L. Saul, B. Schölkopf. — MIT Press, 2004.
[463] Marlin B.
Collaborative filtering: A machine learning perspective: Ph.D. thesis / Master's thesis, University of Toronto. — 2004.
citeseer.ist.psu.edu/marlin04collaborative.html
[464] Hofmann T.
Latent semantic models for collaborative filtering // ACM Transactions on Information Systems. — 2004. — Vol. 22, no. 1. — Pp. 89–115.
www.cs.brown.edu/simth
[465] Hofmann T., Puzicha J.
Latent class models for collaborative filtering // International Joint Conference in Artificial Intelligence. — 1999.
www.cs.brown.edu/simth
[466] Lemire D., Maclachlan A.
Slope one predictors for online rating-based collaborative filtering // SIAM Data Mining (SDM'05). — 2005.
citeseer.ist.psu.edu/lemire05slope.html
[467] Wang J., de Vries A. P., Reinders M. J. T.
Unifying user-based and item-based collaborative filtering approaches by similarity fusion // SIGIR '06: Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, Seattle, Washington, USA. — ACM Press, 2006. — Pp. 501–508.
doi.acm.org/10.1145/1148170.1148257
[468] Meshar O.
Moviematch — a collaborative filtering system for movie recommendations.
citeseer.ist.psu.edu/meshar02moviematch.html
[469] Dhillon I. S., Mallela S., Modha D. S.
Information-theoretic co-clustering // The Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). — 2003. — Pp. 89–98.
citeseer.ist.psu.edu/dhillon03informationtheoretic.html
[470] Papagelis M., Rousidis I., Plexousakis D., Theoharopoulos E.
Incremental collaborative filtering for highly-scalable recommendation algorithms // 15th International Symposium on Methodologies of Intelligent Systems (ISMIS'05). — 2005.
citeseer.ist.psu.edu/papagelis05incremental.html
[471] Symeonidis P., Nanopoulos A., Papadopoulos A., Manolopoulos Y.
Collaborative filtering based on user trends // 30th Annual Conference of the German Classification Societly (GfKl 2006), March 8-10, Berlin, Germany. — 2006.
citeseer.ist.psu.edu/761696.html
[472] Symeonidis P., Nanopoulos A., Papadopoulos A., Manolopoulos Y.
Nearest-biclusters collaborative filtering // 8th ACM SIGKDD Workshop on Web Mining and Web Usage Analysis (WEBKDD'06), Philadelphia, Pennsylvania. — 2006.
citeseer.ist.psu.edu/761593.html
[473] Symeonidis P., Nanopoulos A., Papadopoulos A., Manolopoulos Y.
Collaborative filtering process in a whole new light // 10th International Database Engineering and Applications Symposium (IDEAS'06), New Delhi, India. — IEEE, 2006.
citeseer.ist.psu.edu/761660.html
[474] Symeonidis P., Nanopoulos A., Papadopoulos A., Manolopoulos Y.
Collaborative filtering: Fallacies and insights in measuring similarity // PKDD Workshop on Web Mining (WebMine 2006) , Berlin, Germany. — 2006.
citeseer.ist.psu.edu/symeonidis06collaborative.html
[475] Технология анализа клиентских сред. — ЗАО «Форексис». — 2005.
www.forecsys.ru/cea.php
[476] Воронцов К. В., Рудаков К. В., Лексин В. А., Ефимов А. Н.
Выявление и визуализация метрических структур на множествах пользователей и ресурсов Интернет // Искусственный Интеллект. — 2006. — С. 285–288.
www.ccas.ru/frc/papers/voron05yandex.pdf
Для выявления предпочтений и информационных потребностей огромного числа пользователей по отношению к огромному числу ресурсов простейшая тактика «пользователи ресурса X посещают также множество ресурсов Y» представляется не вполне адекватной. Предлагается более тонкий анализ, основанный на принципе «схожи те пользователи, которые посещают схожие множества ресурсов, и схожи те ресурсы, на которые заходят схожие пользователи». На этом принципе построена технология анализа клиентских сред (АКС), разработанная в компании Форексис (www.forecsys.ru). В данной работе рассматривается применение АКС к обработке логов поисковой машины. Технология АКС позволяет решать задачи персонализации поиска, направленного предложения ресурсов пользователям, поиска схожих ресурсов и визуализации структуры Интернета в виде карт сходства.
[477] Лексин В. А., Воронцов К. В.
Анализ клиентских сред: выявление скрытых профилей и оценивание сходства клиентов и ресурсов // Математические методы распознавания образов-13. — М.: МАКС Пресс, 2007. — С. 488–491.
www.mmro.ru
Технология Анализа клиентских сред (АКС) основана на вычислении оценок сходства между ресурсами и между клиентами согласно принципу согласованности: «ресурсы схожи, если ими пользуются схожие клиенты; клиенты схожи, если они пользуются схожими ресурсами». В данной работе предлагается новый алгоритм АКС, основанный на выявлении интересов (скрытых профилей) клиентов и ресурсов. Алгоритм напоминает генеративные (generative model based) методы коллаборативной фильтрации (collaborative filtering), но отличается от них применением принципа согласованности.

Анализ изображений (Image Analysis)

[478] Mestetskii L. M., Rudakov K. V.
Synthesis of a multizone survey visualization palette on the learning basis // Pattern Recognition and Image Analysis. — 1998. — Vol. 8, no. 4. — Pp. 641–647.
www.ccas.ru/frc/papers/mestetskii98pria-eng.pdf

Прогнозирование (Forecasting)

[479] Thiesing F. M., Middelberg U., Vornberger O.
Short term prediction of sales in supermarkets // Proceedings IEEE International Conference on neural networks. — Vol. 2. — 1995. — Pp. 1028–1031.
citeseer.ist.psu.edu/fm95short.html
[480] Thiesing F. M., Vornberger O.
Forecasting sales using neural networks // Fuzzy Days. — 1997. — Pp. 321–328.
citeseer.ist.psu.edu/104829.html
[481] Thiesing F. M., Vornberger O.
Sales forecasting using neural networks // Proceedings IEEE International Conference on neural networks. — Vol. 4. — 1997. — Pp. 2125–2128.
citeseer.ist.psu.edu/43652.html
[482] Crone S. F.
Training artificial neural networks for time series prediction using asymmetric cost functions // Computational Intelligence for the E-Age. — 2002. — Pp. 2374–2380.
citeseer.ist.psu.edu/crone02training.html
[483] Arminger G., Schneider C.
Frequent problems of model specification and forecasting of time series in goods management systems: Tech. Rep. 21/1999, SFB 475: University of Dortmund, 1999.
citeseer.ist.psu.edu/236345.html
[484] Arminger G., Schneider C.
Asymmetric loss functions for evaluating the quality of forecasts in time series for goods management systems: Tech. Rep. 22/1999, SFB 475: University of Dortmund, 1999.
[485] Schneider C., Klapper M., Wenzel T.
An evaluation of forecasting methods and forecast combination methods in goods management systems: Tech. Rep. 31/1999, SFB 475: University of Dortmund, 1999.
citeseer.ist.psu.edu/schneider99evaluation.html
[486] Воронцов К. В., Егорова Е. В.
Динамически адаптируемые композиции алгоритмов прогнозирования // Искусственный Интеллект. — 2006. — С. 277–280.
www.ccas.ru/frc/papers/students/VoronEgorova05mmro.pdf
В статье рассматриваются три различных метода динамической перенастройки весов в линейных композициях алгоритмов прогнозирования. Экспериментально показано, что требование неотрицательности весов не только улучшает качество прогнозов, но и выступает в роли регуляризатора, повышая устойчивость композиции.

Динамические инвестиционные стратегии (Online Portfolio Selection)

[487] Markowitz H.
Portfolio Selection: Efficient Diversification of Investments. — Wiley, New York, 1959.
[488] Колби Р., Мейерс Т.
Энциклопедия технических индикаторов рынка. — Издательский дом «Альпина», 1998.
[489] Cover T.
Universal portfolios // Mathematical Finance. — January 1991. — Vol. 1, no. 1. — Pp. 1–29.
citeseer.ist.psu.edu/article/cover96universal.html
Вводятся понятия постоянно-балансируемого портфеля (CRP, constant rebalanced portfolio) и универсального портфеля (universal portfolio). Стратегия CRP-портфеля заключается в том, чтобы продавать и покупать активы, поддерживая в каждый момент времени заранее фиксированное распределение капитала по активам. Универсальный портфель есть интегральное среднее всех CRP-портфелей, каждый их которых берется с весом, пропорциональным его доходности на предыстории. Доказывается, что доходность универсального портфеля асимптотически приближается к доходности наилучшего CRP-портфеля. Однако универсальный портфель является динамическим алгоритмом, использующим только информацию о прошлом, в то время как выбор наилучшего CRP-портфеля требует «зяглядывания в будущее».
[490] Kalai A., Vempala S.
Efficient algorithms for universal portfolios // IEEE Symposium on Foundations of Computer Science. — 2000. — Pp. 486–491.
citeseer.ist.psu.edu/kalai00efficient.html
[491] Cover T., Ordentlich E.
Universal portfolios with side information // IEEE Transactions on Information Theory. — March 1996. — Vol. 42, no. 2.
citeseer.ist.psu.edu/cover96universal.html
[492] Blum A., Kalai A.
Universal portfolios with and without transaction costs // COLT: Proceedings of the Workshop on Computational Learning Theory, Morgan Kaufmann Publishers. — 1997.
citeseer.ist.psu.edu/blum97universal.html
[493] Singer Y.
Switching portfolios // 14th Conference on Uncertainty in Artificial Intelligence (UAI98). — 1998. — Pp. 488–495.
citeseer.ist.psu.edu/singer98switching.html
[494] Helmbold D. P., Schapire R. E., Singer Y., Warmuth M. K.
On-line portfolio selection using multiplicative updates // International Conference on Machine Learning. — 1996. — Pp. 243–251.
citeseer.ist.psu.edu/article/helmbold98line.html
Предлагается алгоритм динамической (online) балансировки портфеля EG (Exponential Gradient). Для вычисления текущего вектора портфеля EG используется только предыдущий вектор портфеля и текущий вектор приращений цен. При таком способе балансировки больший вес в портфеле автоматически получают те акции, которые за последнее время давали больший доход. Таким образом, вся необходимая информация о доходности отдельных акций оказывается записанной в самом векторе портфеля, и полное знание всей предыстории не требуется. Идея мультипликативного обновления весов эксплуатируется также в алгоритмах взвешенного голосования [196] и бустинга [217]. Сложность алгоритма линейна по числу акций, в отличие от алгоритма универсального портфеля [489], имеющего экспоненциальную сложность. Тем не менее EG дает асимптотически тот же результат. Нижняя граница доходности выводится без каких бы то ни было статистических предположений о процессе ценообразования. Теоретические оценки несколько хуже [489]. Однако тесты на 22-летнем периоде ежедневных данных NYCE (без учета транзакционных издержек) показывают превосходство данного алгоритма над универсальным портфелем [489].
[495] Borodin A., El-Yaniv R., Gogan V.
On the competitive theory and practice of portfolio selection (extended abstract) // Latin American Theoretical INformatics. — 2000. — Pp. 173–196.
citeseer.ist.psu.edu/borodin02competitive.html
Статья содержит обзор основных концепций сравнительной теории (competitive theory) портфельных стратегий. Рассматриваются следующие алгоритмы: BAH (buy-and-hold — «купи-и-держи»), CBAL (constant rebalanced portfolio — постоянная балансировка), UNI (universal portfolio [489]), EG (exponential gradient [494]), M0 и T0 (предсказание бинарной последовательности), LZ (предсказание бинарной последовательности на основе сжатия Лемпела-Зива). Описана техника доказательства оценок доходности портфельных стратегий, основанная на последовательностях Кэлли. Предлагается новый алгоритм динамической (online) балансировки портфеля DELTA, основанный на анализе матрицы корреляций между ценами акций на предшествующем интервале времени длиной w. Алгоритмы тестируются и сравниваются по доходности на 4 рядах реальных данных, в том числе на 22-летней истории NYCE. Сравнение производится при транзакционных издержках 0%, 0.1% и 2%, а также при ограничении частоты сделок с 1 дня до 1 месяца. Алгоритм DELTA демонстрирует нереально высокую доходность при малых транзакционных издержках, особенно на данных NYCE. При введении ограничений доходность DELTA становится реальной и сравнимой с лучшими результатами других алгоритмов. В качестве основных направлений исследований называются две задачи: оптимальный выбор моментов времени для балансировки портфеля и оптимальный выбор подмножества акций.
[496] Borodin A., El-Yaniv R., Gogan V.
Can we learn to beat the best stock // Advances in Neural Information Processing Systems 16 / Ed. by S. Thrun, L. Saul, B. Schölkopf. — Cambridge, MA: MIT Press, 2004.
citeseer.ist.psu.edu/630049.html
Предлагается алгоритм динамической (online) балансировки портфеля ANTICOR, основанный на анализе матриц кросс-корреляций двух последних интервалов времени длиной w каждый. ANTICOR является усовершенствованным вариантом DELTA [495]. Алгоритм тестируется на 4 рядах реальных данных, в том числе на 22-летней истории NYCE. Две версии ANTICOR сопоставляются с 9 известными портфельными стратегиями. Предлагаемый алгоритм демонстрирует нереально высокую доходность, особенно на данных NYCE, без учета транзакционных издержек.
[497] Hellstrom T.
Outlier removal for prediction of covariance matrices — with an application to portfolio optimization // Theory of Stochastic Processes. — 2000. — Vol. 6(22), no. 3. — Pp. 47–63.
citeseer.ist.psu.edu/485368.html
В рамках теории Марковица строятся оценки ковариационной матрицы и вектора доходностей, устойчивые к выбросам. Предлагается простой алгоритм, исключающий дни с выбросами методом скользящего контроля. Алгоритм тестируется на двухлетних данных американского и шведского рынка акций. Оценки строятся по 200-дневным интервалам и проверяются по 20-дневным. Устранение выбросов понижает ошибку ковариационной матрицы на 9% и повышает значение функционала (Доходность – 2 Риск) на 2.5% на тестовой выборке.
[498] Parkes D., Huberman B. A.
Multiagent cooperative search for portfolio selection.
citeseer.ist.psu.edu/212121.html
[499] Dempster M. A. H., Payne T. W., Romahi Y. S., Thompson G. W. P.
Computational learning techniques for intraday FX trading using popular technical indicators // IEEE Transactions on Neural Networks, special issue on Computational Finance. — 2001. — Vol. 12. — Pp. 744–754.
www.jims.cam.ac.uk
Описывается применение генетического алгоритма для построения логического корректора над набором из 16 технических индикаторов рынка. Предложенная торговая стратегия сравнивается по доходности с алгоритмами, использующими активное обучение (reinforcement learning) и линейное программирование. Сравнительный эксперимент проводится на внутридневных данных валютного рынка.
[500] Dempster M. A. H., Jones C. M.
The profitability of intra-day FX trading using technical indicators. — Working paper No. 35/00, Judge Institute of Management, University of Cambridge. — 2000.
www.jims.cam.ac.uk

Учебники, курсы лекций, обзоры

[501] Бонгард М. М.
Проблема узнавания. — М.: Наука, 1967.
[502] Васильев В. И.
Распознающие системы. — Киев: Наукова думка, 1969.
[503] Дуда Р., Харт П.
Распознавание образов и анализ сцен. — М.: Мир, 1976.
[504] Мерков А. Б.
Основные методы, применяемые для распознавания рукописного текста. — Лаборатория распознавания образов МЦНМО. — 2004.
www.recognition.mccme.ru/pub/RecognitionLab.html/methods.html
[505] Fukunaga K.
Introduction to statistical pattern recognition. — 2 edition. — Academic press, Inc., Boston, USA, 1990.
[506] Грэхем Р., Кнут Д., Паташник О.
Конкретная математика. — М.: Мир, 1998.
Оригинальный учебник по дискретному анализу. Разнообразные технические приемы оперирования с дискретными объектами рассматривается на многочисленных примерах.
[507] Лбов Г. С.
Выбор эффективной системы зависимых признаков // Вычислительные системы. — 1965. — Т. 19. — С. 21–34.
[508] Меерков С. М.
Свойство замедления в задаче поиска глобального экстремума функций // Автоматика и телемеханика. — 1972. — N° 12. — С. 129–139.
[509] Лбов Г. С., Котюков В. И., Манохин А. Н.
Об одном алгоритме распознавания в пространстве разнотипных признаков // Вычислительные системы. — 1973. — Т. 55. — С. 98–107.
[510] Лбов Г. С., Котюков В. И., Машаров Ю. П.
Метод обнаружения логических закономерностей на эмпирических таблицах // Вычислительные системы. — 1976. — Т. 67. — С. 29–42.
[511] Лбов Г. С.
Методы обработки разнотипных экспериментальных данных. — Новосибирск: Наука, 1981.
[512] Загоруйко Н. Г., елкина В. Н., Лбов Г. С.
Алгоритмы обнаружения эмпирических закономерностей. — Новосибирск: Наука, 1985.
[513] Загоруйко Н. Г.
Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999.
[514] Тихонов А. Н., Арсенин В. Я.
Методы решения некорректных задач. — М.: Наука, 1986.
[515] Местецкий Л. М.
Математические методы распознавания образов. — Курс лекций, ВМиК МГУ, кафедра ММП. — 2002.
www.ccas.ru/frc/papers/mestetskii04course.pdf
[516] Журавлев Ю. И., Рязанов В. В., Сенько О. В.
«Распознавание». Математические методы. Программная система. Практические применения. — М.: Фазис, 2006.
[517] Шлезингер М., Главач В.
Десять лекций по статистическому и структурному распознаванию. — Киев: Наукова думка, 2004.
[518] Яблонский С. В.
Введение в дискретную математику. — М.: Наука, 1986.
[519] Пытьев Ю. П.
Возможность. Элементы теории и применения. — М.: Эдиториал УРСС, 2000.
[520] Трауб Д., Васильковскии Г., Вожьняковский X.
Информация, неопределенность, сложность: Пер. с англ. — М.: Мир, 1988.
[521] Лоусон Ч., Хенсон Р.
Численное решение задач метода наименьших квадратов. — М.: Наука, 1986.
[522] Jain A. K., Duin R. P. W., Mao J.
Statistical pattern recognition: A review // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 2000. — Vol. 22, no. 1. — Pp. 4–37.
citeseer.ist.psu.edu/article/jain00statistical.html
[523] Dietterich T. G.
Machine learning research: Four current directions // AI Magazine. — 1997. — Vol. 18, no. 4. — Pp. 97–136.
citeseer.ist.psu.edu/dietterich97machine.html
[524] Mitchell T.
Machine Learning. — McGraw-Hill Science/Engineering/Math, 1997.
[525] Hastie T., Tibshirani R., Friedman J.
The Elements of Statistical Learning. — Springer, 2001.

Теория вероятностей и математическая статистика

[526] von Mises R.
Mathematical Theory of Probability and Statistics. — New York, Academic Press, 1964.
[527] Колмогоров А. Н.
Теория информации и теория алгоритмов / Под ред. Ю. В. Прохоров. — М.: Наука, 1987.
[528] Колмогоров А. Н.
Основные понятия теории вероятностей. — М.: Наука, 1974.
[529] Колмогоров А. Н., Журбенко И. Г., Прохоров А. В.
Введение в теорию вероятностей. — М.: Наука-Физматлит, 1995.
[530] Закс Ш.
Теория статистических выводов. — М.: Мир, 1975.
[531] Большев Л. Н., Смирнов Н. В.
Таблицы математической статистики. — М.: Наука, 1983.
[532] Гаек Я., Шидак З.
Теория ранговых критериев. — М.: Наука, 1971.
[533] Беляев Ю. К., Рыкова Л. В.
Непараметрический критерий Колмогорова для выборок из конечных совокупностей // ДАН СССР. — 1973. — Т. 210, N° 6. — С. 1261–1264.
[534] Рыкова Л. В.
Непараметрический критерий Колмогорова-Смирнова для выборок из конечных совокупностей // ДАН СССР. — 1974. — Т. 214, N° 4. — С. 771–774.
[535] Беляев Ю. К.
Вероятностные методы выборочного контроля. — М.: Наука, 1975.
[536] Смирнов Н. В.
Оценка расхождения между эмпирическими кривыми распределения в двух независимых выборках // Бюлл. Московского ун-та, серия А. — 1939. — N° 2. — С. 3–14.
[537] Алимов Ю. И.
Альтернатива методу математической статистики. — Знание, 1980.
[538] Айвазян С. А., Енюков И. С., Мешалкин Л. Д.
Прикладная статистика: основы моделирования и первичная обработка данных. — М.: Финансы и статистика, 1983.
[539] Айвазян С. А., Енюков И. С., Мешалкин Л. Д.
Прикладная статистика: исследование зависимостей. — М.: Финансы и статистика, 1985.
[540] Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д.
Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989.
[541] Ермаков С. М., Михайлов Г. А.
Курс статистического моделирования. — М.: Наука, 1976.
[542] Шурыгин А. М.
Прикладная стохастика: робастность, оценивание, прогноз. — М.: Финансы и статистика, 2000.
[543] Bauer M., Godreche C., Luck J. M.
Statistics of persistent events in the binomial random walk: Will the drunken sailor hit the sober man? // J.STAT.PHYS. — 1999. — Vol. 96. — P. 963.
www.citebase.org/abstract?id=oai:arXiv.org:cond-mat/9905252
[544] Лагутин М. Б.
Наглядная математическая статистика. — М.: П-центр, 2003.
[545] Орлов А. И.
Нечисловая статистика. — М.: МЗ-Пресс, 2004.
[546] Кобзарь А. И.
Прикладная математическая статистика. — М.: Физматлит, 2006.
[547] Вероятность и математическая статистика: Энциклопедия / Под ред. Ю. В. Прохорова. — М.: Большая российская энциклопедия, 2003.
[548] Лапач С. Н., Чубенко А. В., Н. Б. П.
Статистика в науке и бизнесе. — Киев: Морион, 2002.
[549] Кулаичев А. П.
Методы и средства комплексного анализа данных. — М: ИНФРА-М, 2006.

Учебники и обзоры по Data Mining

[550] Дюк В. А., Самойленко А. П.
Data Mining. Учебный курс. — СПб.: Питер, 2001.
[551] Барсегян А. А., Куприянов М. С., Степаненко В. В., Холод И. И.
Методы и модели анализа данных: OLAP и Data Mining. Учебное пособие. — СПб.: БХВ-Петербург, 2004.
[552] Чубукова И. А.
Data Mining. Учебное пособие. — Питер, 2006.
[553] Брянцев И. Н.
Data Mining. Теория и практика. — БДЦ-Пресс, 2006.

Разное

[554] Asuncion A., Newman D.
UCI machine learning repository: Tech. rep.: University of California, Irvine, School of Information and Computer Sciences, 2007.
www.ics.uci.edu/simmlearn/MLRepository.html
Крупнейший репозиторий реальных задач классификации и восстановления зависимостей, свободно доступный через Интернет.
[555] Воронцов К. В., Кобзева Н. В.
Численные методы обработки данных для высокоэффективной жидкостной хроматографии // Информационные проблемы клинической токсикологии. — Москва, 1993.
www.ccas.ru/frc/papers/voron93remedi.pdf
Рассматривается алгоритм идентификации лекарственных препаратов в биосредах организма по данным жидкостной хроматографии. Алгоритм основан на матричном подходе к обработке числовых данных, поступающих со сканирующего ультрафиолетового детектора. Более полное использование первичных данных в совокупности с математическим моделированием формы хроматографических пиков позволяет существенно улучшить качество идентификации. Алгоритм позволяет корректно выделять спектры веществ, отсутствующих в базе данных системы, эффективно (в сотни раз) сжимать ранее полученные хроматограммы практически без потери точности представления данных, ускорить самообучение системы, повысить чувствительность прибора при предельно низких концентрациях. Все предлагаемые модификации относятся к программному обеспечению и не затрагивают аппаратной части хроматографической установки.
[556] Воронцов К. В.
Предварительная обработка данных для решения задач распознавания в жидкостной хроматографии. — Дипломная работа. Московский физико-технический институт. — 1994.
www.ccas.ru/frc/papers/voron94diplom.pdf
Рассматривается один из подходов к идентификации компонентов смеси химических веществ по данным высокоэффективной жидкостной хроматографии. Предлагаемые алгоритмы ориентированы на обработку исходных данных системы экстренной токсикологии REMEDI (Bio-Rad Laboratories, США), предназначенной для оперативного анализа образцов плазмы крови.
[557] Воронцов К. В.
Предварительная обработка данных для решения специального класса задач распознавания // ЖВМ и МФ. — 1995. — Т. 35, N° 10. — С. 1565–1575.
www.ccas.ru/frc/papers/voron95jvm.pdf
Рассматриваются алгоритмы предварительной обработки данных для прикладной задачи, описанной в [555].
[558] 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 [557].
[559] Воронцов К. В.
Язык и среда для описания и исследования алгоритмических суперпозиций // Искусственный Интеллект. — 2000. — N° 2. — С. 36–41.
Рассматриваются общие концепции нового инструментального средства, предназначенного для решения широкого класса задач обучения по прецедентам — среды и языка для разработки обучаемых алгоритмических композиций ASDIEL. Очерчен класс задач, для решения которых это средство предназначено, описана формальная модель данных, лежащая в его основе.
[560] Воронцов К. В., Пшеничников С. Б.
Имитационное моделирование торгов: новая технология биржевых тренажеров // Индикатор. — 2002. — N° 2(42).
www.ccas.ru/frc/papers/voron02imitrade.pdf
В статье представляется биржевой тренажер Имитрейд, позволяющий освоить навыки биржевых операций в условиях, максимально приближенных к реальным торгам. В тренажере используется имитационная модель торгов, способная в точности воспроизводить реальную торговую сессию и адекватно реагировать на возмущающие воздействия обучаемых.
[561] Воронцов К. В.
Имитационное моделирование реальных биржевых торгов // ИММОД-2003: 1-ая Всеросс. конф.: Докл. — СПб., 2003. — С. 25–29.
www.ccas.ru/frc/papers/voron03imitrade.pdf
Рассматривается имитационная модель биржевых торгов, позволяющая детально воспроизводить реальные торговые сессии ММВБ. Для настройки модели используются методы распознавания образов. В докладе описываются основные свойства и строение модели, рассматривается биржевой тренажер Имитрейд и другие прикладные задачи, решаемые с помощью данной модели.