Комитетные решения несовместных систем ограничений и методы обучения распознаванию
Диссертация
Практическая значимость. Результаты работы по большей части носят теоретический характер и могут быть полезны специалистам по теоретической информатике. Тем не менее, некоторые результаты, например, приближенный алгоритм построения минимального разделяющего комитета, нашли применение на практике. Реализованный автором совместно с А. В. Качалковым и А. И. Рыбиным в виде СОМ-объекта qtGUN. dll… Читать ещё >
Содержание
- 1. Комитетные решения несовместных систем ограничений
- 1. 1. Основные понятия и определения
- 1. 2. Условия существования комитетного решения абстрактной системы включений
- 1. 3. Гиперграф максимальных совместных подсистем
- 1. 4. Условия существования комитетного решения системы линейных неравенств
- 1. 5. Эремальноеово гиперграфа мп. однородной системы линейных неравенств
- 1. 6. Равномерно распределенные системы неравенств
- 2. Необходимые условия существования комитета в игровой постановке
- 2. 1. Постановка задачи
- 2. 2. Основная теорема
- 2. 3. Предельные соотношения
- 2. 4. Замечания
- 3. Задача о минимальном комитете
- 3. 1. Элементы теории сложности алгоритмов
- 3. 2. Постановка задачи о минимальном комитете
- 3. 3. Вычислительная сложность задачи о минимальном комитете
- 3. 3. 1. Труднорешаемость задачи MCFS
- 3. 3. 2. Порог аппроксимируемости для задачи MCFS
- 3. 4. Задача о минимальном комитете системы линейных неравенств
- 3. 4. 1. Вычислительная сложность задачи MCLE
- 3. 4. 2. Приближенный алгоритм
- 4. 1. Разделяющие комитетные конструкции
- 4. 2. О минимизации эмпирического риска в классе комитетных решающих правил
- 4. 2. 1. Комитетные решающие правила
- 4. 2. 2. Оценка скорости сходимости частоты к вероятности по классу комитетных событий
Список литературы
- Белецкий Н.Г. Комитетные конструкции в многоклассовых задачах распознавания образов. Дис. на соискание степени к.ф.-м.н. (01.01.09 — мат. кибернетика). -Свердловск. 1984.
- Вапник В.Н., Червоненкис А. Я. Теория распознавания образов. -М.: Наука, 1974.
- Вапник В.Н. Восстановление зависимостей по эмпирическим данным. М.: Наука, 1979.
- Гайнанов Д.Н. О графах максимальных совместных подсистемнесовместных систем линейных неравенств. -Москва, 1981, 46 с. Деп. ВИНИТИ, № 229−81.
- Гайнанов Д.Н., Новокшенов В. А., Тягунов Л. И. О графах, порождаемых несовместными системами линейных неравенств // Мат. заметки. 1983. -Т. 33, вып. 2., С. 293−300.
- Гэри М., Джонсон Д. Вычислительные машины и труднорешае-мые задачи. М.: Мир, 1982.
- Дюкова Е.В., Журавлев Ю. И., Рудаков К. В. Об алгебро-ло-гическом синтезе корректных процедур распознавания на базе элементарных алгоритмов // ЖВМ и МФ. 1996. т.36. № 8. С. 215 223.
- Емеличев В.А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990, 384 с.
- Еремин И.И., Мазуров Вл.Д. Нестационарные процессы математического программирования. М.: Наука, 1979.
- Еремин И. И. Противоречивые модели оптимального планирования- Москва: Наука. 1988.-160 с.
- Еремин И.И. Теория линейной оптимизации. Екатеринбург: УрО РАН, 1998, 248 с.
- Еремин И.И., Мазуров Вл.Д., Скарин В. Д., Хачай М. Ю. Математические методы в экономике. Екатеринбург: «Фактория-Пресс». 2000. — 303 с.
- Журавлев Ю.И. Корректные алгебры над множествами некорректных алгоритмов. I-III // Кибернетика. 1977, № 4, С. 14−21- 1977, № 6, С. 21−27- 1978, № 2, С. 35−43.
- Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики, вып. 33. 1978. С. 5−68.
- Журавлев Ю.И. Об алгоритмах распознавания с представительными наборами (о логических алгоритмах). // ЖВМ и МФ. 2002. т.42. т. С. 1425−1435.
- Зуев Ю.А. Метод повышения надежности классификации при наличии нескольких классификаторов, основанный на принципе монотонности//ЖВМ и МФ. 1981. т.21. № 1. С.157−167.
- Зуев Ю.А. Вероятностная модель комитета классификаторов// ЖВМ и МФ. 1986. т.26. № 2. С.276−292.
- Зуев Ю.А. Наихудший случай для принятия решения большинством голосов//ЖВМ и МФ. 1989. т.29. т. С. 1256−1257.
- Зуев Ю.А., Иванов С. К. Обучение и самообучение в процедурах взвешенного голосования // ЖВМ и МФ. 1995. т.35. № 1. С. 104 121.
- Казанцев B.C. Задачи классификации и их программное обеспечение (пакет КВАЗАР). М.: Наука. 1990. 136 с.
- Качалков А.В., Рыбин А. И., Хачай М. Ю. Технология создания вычислительного сайта «Квазар-Онлайн» // Труды Международной конференции «Распознавание образов и анализ изображений РОАИ-6−2002». Новгород: НовГУ. 2002. С. 258−262.
- Китаев А., Шень А., Вялый М. Классические и квантовые вычисления. М.: МЦНМО ЧеРо. 1999.
- Кривоногов А.И. О некоторых комитетных конструкциях классификации / в сб. Методы оптимизации и распознавания образов в задачах планирования. Свердловск: УНЦ АН СССР. 1980. С. 9298.
- Кривоногов А.И. Некоторые вопросы обоснования комитетных алгоритмов /в сб. Классификация и оптимизация в задачах управления. Свердловск: УНЦ АН СССР. 1981. С. 39−51.
- Лбов Г. С., Неделько В. М. Построение решающей функции на основе вероятностных логических высказываний многих экспертов. //
- Известия высших учебных заведений. Физика. 1995, № 9. С. 119 123.
- Лбов Г. С., Старцева Н. Г. Логические решающие функции и вопросы статистической устойчивости решений. Новосибирск: ИМ СО РАН, 1999. 212 с.
- Мазуров Вл.Д. О построении комитета системы выпуклых неравенств // Кибернетика. 1967. № 2. С. 56−59.
- Мазуров Вл.Д. Комитеты систем неравенств и задача распознавания // Кибернетика. 1971. № 3. С. 140−146.
- Мазуров Вл.Д. Несовместные системы неравенств в задачах распознавания // Метод комитетов в распознавании образов. Свердловск: УНЦ АН СССР, 1974. С. 3−9.
- Мазуров Вл.Д., Тягунов Л. И. Метод комитетов в распознавании образов // Метод комитетов в распознавании образов. -Свердловск: УНЦ АН СССР, 1974. С. 10−40.
- Мазуров Вл.Д. Метод комитетов в задачах оптимизации и классификации М.: Наука, 1990.
- Мазуров Вл.Д., Хачай М. Ю. Комитетные конструкции // Известия УрГУ, 1999, вып. 14. С. 76−108.
- Мазуров Вл.Д., Хачай М. Ю., Некрасов В. П. Реализация диагностики и выбора вариантов в горно-геологических задачах. //Известия ВУЗ-ов. Горный журнал. 2001. № 1. С. 10−15.
- Мазуров Вл.Д., Хачай М. Ю. Комитетные конструкции как обобщение решений противоречивых задач исследования операций // Дискретный анализ и исследование операций. 2003. Т. 10, Сер. 2, № 2. С. 56−66.
- Мазуров Вл.Д., Хачай М. Ю. Комитеты систем линейных неравенств //Автоматика и телемеханика. 2004. вып. 2, С. 43−54.
- Пападимитриу К, Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. -512 с.
- Рудаков К.В. О некоторых классах алгоритмов распознавания. -М.: ВЦ РАН СССР, 1980.
- Рудаков К.В. О некоторых классах алгоритмов распознавания (параметрические модели). М.: ВЦ РАН СССР, 1981.
- Рудаков К.В., Трофимов С. В. Алгоритм синтеза корректных процедур распознавания для задач с непересекающимися классами.// ЖВМ и МФ. 1988. т.28. №. С.1431−1434.
- Рыбин А.И. Об оценках минимального комитета. Москва. 2000. -35с. Деп. в ВИНИТИ 28 ноября 2000 г., 3029-В00.
- Рязанов В.В. Комитетный синтез алгоритмов распознавания и классификации// ЖВМ и МФ. 1981. т.21. № 6. С. 1533−1543.
- Рязанов В.В. О синтезе классифицирующих алгоритмов на конечных множествах алгоритмов классификации (таксономии)// ЖВМ и МФ. 1982. т.22. № 2. С. 429−440.
- Харари Ф. Теория графов. -М.: Мир, 1973.
- Хачай М.Ю. О существовании комитета большинства // Дискретная математика, 1997. т. 9, вып. 3. С. 82−95.
- Хачай М.Ю. Об оценке числа членов минимального комитета системы линейных неравенств // Журнал вычисл. матем. и матем. физики, 1997. т. 37, № 11. С. 1399−1404.
- Хачай М.Ю., Рыбин А. И. О комитетном решении с минимальным числом членов системы линейных неравенств // Труды XI международной Байкальской школы-семинара «Методы оптимизации и их приложения». Иркутск: ИСЭ СО РАН, 1998. С. 26−40.
- Хачай М.Ю. Об оценке емкости класса комитетных решающих функций // Доклады IX Всероссийской конференции «Математические методы распознавания образов». 1999, Москва, ВЦ РАН, С. 121−123.
- Хачай М.Ю. Об одной комбинаторной задаче, связанной с понятием минимального комитета // Труды Международной конференции «Распознавание образов и анализ изображений РОАИ-5−2000». — Самара: ИСОИ РАН. 2000. С. 167−169.
- Хачай М.Ю. О достаточной длине обучающей выборки для комитетного решающего правила // Искусственный интеллект. 2000, №, С. 219−223.
- Хачай М.Ю. Об одном соотношении, связанном с процедурой принятия решений большинством голосов // ДАН. 2001. т. 381, № 6. С. 748−752.
- Хачай М.Ю. Об одном соотношении, связанном с голосованием большинством // Труды Международной конференции «Математическое моделирование (ММ-2001)». Самара: ИСОИ РАН. 2001. С. 41−44.
- Хачай М.Ю. Об одной игре с природой, связанной с принятием решений большинством голосов // Доклады X Всероссийской конференции «Математические методы распознавания образов». -Москва: ВЦ РАН. 2001. С. 149−153.
- Хачай М.Ю. Об одной игре с природой, связанной с принятием решений большинством голосов // ЖВМ и МФ. 2002, т. 42, № 10, С. 1609−1616.
- Хачай М.Ю. Приближенный алгоритм решения задачи о минимальном комитете системы линейных неравенств / в сб. «Алгебра и линейная оптимизация», труды международного семинара, посвященного 90-летию С. Н. Черникова. Екатеринбург: УрО РАН. 2002. С. 314−318.
- Хачай М.Ю. Об эффективном алгоритме построения приближенияк минимальному по числу элементов комитетному решающему правилу // Труды Международной конференции «Распознавание образов и анализ изображений РОАИ-6−2002». — Новгород: НовГУ. 2002. С. 593−596.
- Хачай М.Ю. О вычислительной сложности задачи о минимальном комитете // Доклады XI Всероссийской конференции «Математические методы распознавания образов». Москва: ВЦ РАН. 2003. С. 198−201.
- Хачай М.Ю. Об апроксимационной сложности задачи о минимальном комитете // Таврический вестник информатики и математики. 2004, т. С. 78−82.
- Хачай М.Ю. О вычислительной сложности задачи о минимальном комитете // Труды Международной конференции «Распознавание образов и анализ изображений РОАИ-7−2004" — — С.-Петербург: ЛЭТИ. 2004.
- Черников С.Н. Линейные неравенства. М.: Наука, 1968.
- Эндрюс Г. Теория разбиений. М.: Наука, 1982. -255 с.
- Ablow С.М., Kaylor D.J. Inconsistent Homogeneous Linear Inequalities // Bull. Amer. Math. Soc., 1965, vol. 71, no. 5, p. 724.
- Amaldi E., Капп V. The complexity and approximability of finding maximum feasible subsystems of linear relations // Theoretical Computer Science. 1995, vol. 147, pp. 181−210.
- Amaldi E., Pfetsch M.E., Trotter L.E. (Jr.) On the maximum feasible subsystem problem, IISs and HS-hypergraphs // Mathematical programming. 1995. Ser. A. pp. 533−554.
- Amaldi E., Pfetsch M.E., Trotter L.E. (Jr.) Some Structural and Algorithmic Properties of the Maximum Feasible Subsystem Problem //In Procs. ofIPCO'99, LNCS 1610, pp. 45−59, 1999.
- Amaldi E., Mattavelli M. The MIN PFS problem and piecewise linear model estimation // Discrete Applied Mathematics. 2002. 118, pp. 115—143.
- Arora S. Probabilistic checking of proofs and the hardness of approximation problems. Ph.D. thesis. UC Berkeley. 1994.
- Arora S., Safra M. Probabilistic Checking of Proofs: A new Characterization of NP // Journal of ACM. 1998. 45(1), pp. 70−122.
- Bar-Yehuda R. One for the Price of Two: a Unified Approach for Approximating Covering Problems. // Algorithmica. 2000. no. 27, pp. 131—144.
- Blum A., Rivest R. L. Training a 3-node neural network is NP-complete. In: D. S. Touretzky (Ed.), Advances in neural information processing systems, Morgan Kaufmann, 1988.
- Borda J.C. Memoire sur les elections au scrutin. Historia de Vacademie des sciences pour. Paris, 1781.
- Chernov V.M. The „modular perceptron“: A linear classes separability in the non-Archimedean features spaces. //In Proc. of the 10th Scandinavian Conference on Image Analysis (SCIA '97). Lappeenranta, 1997. v.2. pp. 803−808.
- Condorcet I. A. Essai sur Vapplication de Vanalyse a la probabilite des decisions vendues a la pluralite des voix. Paris, 1785.
- Cook S.A. The complexity of theorem-proving procedures// Proc. 3rd Ann. ACM Symp. on Theory of Computing. ACM. New York. 1971. pp.151−158.
- DasGupta В., Hammer B. On Approximate Learning by Multi-layered Feedforward Circuits// In Procs. of ALT-2000, LNAI-1968, pp. 264 278, 2000.
- Dinur I., Regev O. and Smyth C. The hardness of 3-uniform hypergraph coloring. In: Proc. of the 43rd Annual IEEE Symposium on Foundations of Computer Science, November 2002.
- Feige U. A Threshold of Inn for Approximating Set Cover. Journal of the ACM. 1998, 45(4).
- Freund Y., Schapire R.E. A decision-theoretic generalization of on-linelearning and application to boosting. //In Procs of 2nd Eur. Conf. on Сотр. Learn. Theory. 1995.
- Gale D. Neighboring vertices on a convex polyhedron. In: Linear inequalities and related systems, edited by H.W.Kuhn and A.W.Tucker, Princeton, 1956 pp. 255 263.
- Guruswami V. Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses // Algorithmica. 2004, vol. 38, pp. 451—469.
- Hachai M.Yu. Classification of Committee Solutions of Majority // Pattern Recognition and Image Analysis. 1997. V.7. N2. pp.260−265.
- Hastad J. Clique is Hard to Approximate within nl~e. Acta Mathemat-ica. 1999, vol. 182, pp. 105−142.
- Hammer B. Training a Sigmoidal Network is Difficult// In Procs. of ESANN'1998. Bruges. 1998. pp. 255−260.
- Ibarra O.H., Kim C.E. Fast Approximation Algorithms for the Knapsack and Sum of Subsets Problems // Journal of ACM. 1975, vol. 22, pp. 463−468.
- Johnson D.S. Approximation algorithms for combinatorial problems // Journal of Computer and System Sciences. 1974, vol. 9(3), pp. 256−278.
- Johnson D.S., Preparata F.P. The Densest Hemisphere Problem // Theoretical Computer Science. 1978, no. 6. pp. 93−107.
- Kachalkov A.V., Rybin A.I., Khachay M.Yu. Development of the Quasar-Online Computational Site // Pattern Recognition and Image Analysis. 2003, vol. 13, no 2. pp. 217−220.
- Khachai M.Yu., Rybin A.I. A New Estimate of the Number of Members in a Minimum Committee of a System of Linear Inequalities // Pattern Recognition and Image Analysis, 1998. Vol. 8. No. 4. pp. 491−496.
- Khachai M.Yu. On the Combinatorial Problem Concerned with the Notion of Minimal Committee // Pattern Recognition and Image Analysis. 2001. V. ll no.l pp. 45−46.
- Khachay M.Yu. On an Efficient Approximation Algorithm for the Minimal Committee Problem // Pattern recognition and Image Analysis. 2003. Vol.13, no 1. pp. 43−44.
- Khachay M.Yu. On Approximate Algorithm of a Minimal Committee of a Linear Inequalities System// Pattern Recognition and Image Analysis. 2003, vol. 13, no 3. pp. 459−464.
- Khachay M.Yu. On Computational Complexity of the Minimal Committee of Finite Sets Problem // In: Proc. of the 2nd International Workshop 'Discrete Optiomization Methods in Production and Logistics'. Omsk-Irkutsk. 2004, pp.176−179.
- Kobylkin K.S. Necessary Condition for Committee Existence // Pattern Recognition and Image Analysis. 2002. vol. 12, no. 1, pp. 26−31.
- Lin J., Vitter J.S. Complexity Results on Learning by Neural Nets // Machine Learning. 1991. 6, pp. 211−230.
- Lovasz L. Coverings and Colorings of Hypergraphs //In Proc. of 4th Southeastern Conference of Combinatorics, Graph Thery and Computing. 1973. Utilitas Mathematica Publishing. Winnipeg, pp. 3−12.
- Lovasz L. On the ratio of optimal integral and fractional covers 11 Discrete. Mathematics. 1975. vol. 13, pp.383−390.
- Lund C., Yannakakis M. On the hardness of approximationg minimization problems // In: Proc. of the 33rd IEEE Symposium on Foundations of Computer Science. 1992. pp. 960−981.
- Mazurov VI.D. Duality in Pattern Recognition // Pattern Recognition and Image Analysis. 1991. v. 1, no. 2. pp. 81−87.
- Mazurov VI.D. Recognition and Choice in a Multistage Procedure of Modeling Complex Systems.// Pattern Recognition and Image Research. 1994. v.4, no. 2. pp. 87−92.
- Mazurov VI.D. Generalized Existence in Nonequilibrium Models of Choice in Modeling Complex Systems.// Pattern Recognition and Image Research. 1995. v.5, no. 1. pp. 7−12.
- Mazurov V1, D. The Capabilities of Collective Rules of Decision Making, Diagnostics, and Forecasting and Their Use in Engineering and Economic Problems // Pattern Recognition and Image Analysis. 1996. vol. 16, no. 3, pp. 461−469.
- Mazurov VI.D., Potanin N.I. The Analysis and Interpretation of Textures by Committee Methods of Pattern Recognition // Pattern Recognition and Image Analysis. 1997. vol. 17, no. 2, pp. 260−265.
- Mazurov V.D., Plotnikov S.V., Rybin A.I., Tyutin A.N., Hachai M.Yu. Algorithms of the KVAZAR+ Package // Pattern Recognition and Image Analysis. 1998. v.8, no.3. pp. 374−375.
- Mazurov VI.D., Khachai M.Yu., Rybin A.I. Committee Constructions for Solving Problems of Selection, Diagnostics and Prediction. Proceedings of the Steklov Institute of mathematics. Suppl. 1, (2002), S67-S101.
- Osborne M.L. The Senjority Logic: A Logic for a Committee Machine // IEEE Trans, on Сотр. 1977. v. C-26, no. 12, pp. 1302−1306.
- Papadimitriou Ch. Computational Complexity. Addison-Wesley. 1993.
- Raz. R. A parallel repetition theorem // SIAM Journal of Computing. 1998, vol 27, no. 3, pp. 763−803.
- Ryazanov V.V. On the Construction of Collective Solutions in Taxonomy Problems // Pattern Recognition and Image Analysis. 1998. Vol.8, no. 2. pp. 146−147.
- Rybin A.I. On Some Sufficient Conditions of Existence of a Majority Committe // Pattern Recognition and Image Analysis. 2000. vol. 10, no. 3, pp. 297−302.
- Schwaighofer A., Tresp V. The Bayessian Committee Support Vector Machine // Lecture Notes in Computer Science. 2001. vol. 2130, pp. 411−417.
- Sima J. On the Complexity of Training a Single Perceptron with Programmable Synaptic Delays // Lecture Notes in Artificial Intelligence. 2003. vol. 2842, pp. 221−233.
- Tresp V. A Bayesian Commitee Machine // Neural Computation. 2000. 12, pp. 2719−2741.» ' ' .' «» ' • * Д, — ' iff'
- Williamson D.P. The Primal-Dual Method for Approximation Algorithms // Mathematical Programming. 2002. Vol. 91. No. 3. Series В., pp. 447−478.