О средней временной сложности деревьев решений тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

1 Введение

1.1 Общая характеристика работы.

1.2 Основные определения и обозначения.

1.3 Основные результаты работы.

2 Деревья решений для тестовых таблиц

2.1 Оценки средней взвешенной глубины

2.2 О возможности декомпозиции задачи.

2.3 Алгоритм Л построения деревьев решений.

3 Некоторые приложения

3.1 О средней глубине деревьев решений, реализующих булевы функции

3.2 О бинарных программах с минимальной средней глубиной

4 Задачи над системами проверок

4.1 Об оценках средней глубины деревьев решений, зависящих только от энтропии.

4.2 Критерий полиномиальности алгоритма Л.

1.1 Общая характеристика работы

Деревья решений используются для представления знаний и описания алгоритмов решения различных прикладных задач. Многие из них могут быть сформулированы как задача идентификации, которая характеризуется универсумом объектов, множеством проверок и разбиением множества объектов на классы, и состоит в нахождении класса, к которому принадлежит объект, путем вычисления для него значений проверок. Сложность деревьев решений и алгоритмы их построения исследуются в теории тестов [3, 4, 10, 11, 13, 20, 23, 27, 43], теории грубых множеств [50, 51, 52, 53, 61], теории вопросников [18, 54], теории таблиц решений [39, 55], теории поиска [29], теории машинного обучения [38, 44, 58]. Из приложений, в которых широко используются деревья решений, следует отметить непроцедурные языки программирования [39], анализ сложности алгоритмов [5], дискретную оптимизацию [7, 8, 9, 12], распознавание образов [2, 20, 27, 42], диагностику неисправностей [16, 19, 23, 60], вычислительную геометрию [57]. Средняя временная сложность деревьев решений исследована для многих частных случаев задач идентификации.

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

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

Во второй главе рассматриваются оценки минимальной средней временной сложности деревьев решений и алгоритм построения оптимальных деревьев решений. Эта глава состоит из трех параграфов. В первом параграфе приведены нижняя оценка средней взвешенной глубины дерева решений для некоторых типов задач, верхняя оценка средней взвешенной глубины, а также более точная оценка средней глубины. Ранее были известны верхняя и нижняя оценки минимальной средней временной сложности деревьев решений для задач идентификации с полным набором проверок. Эти оценки зависят только от энтропии распределения вероятностей, они следуют из результатов теории кодирования [6, 59] и хорошо известны в теории поиска (см., например, [29]). В этом параграфе данные оценки обобщены на случай средней взвешенной глубины деревьев решений для произвольной задачи идентификации. Во втором параграфе описано достаточное условие декомпозиции задачи, при выполнении которого оптимальное дерево решений для задачи может быть получено из оптимальных деревьев решений для нескольких подзадач с помощью простых преобразований. Также этот параграф содержит результат, свидетельствующий о том, что верхняя оценка средней глубины из параграфа 2.1 близка к неулучшаемой. В третьем параграфе приведен алгоритм Л построения оптимального (в смысле одной из нескольких мер сложности) дерева решений по задаче, представленной в форме тестовой таблицы. Идея алгоритма близка к дескриптивным методам оптимизации [7, 8, 9, 12].

Третья глава посвящена некоторым приложениям, в которых может быть эффективно использован аппарат деревьев решений. Эта глава состоит из двух параграфов. В первом параграфе изучается средняя глубина деревьев решений, реализующих булевы функции. Для каждого замкнутого класса булевых функций [28] получены верхняя и нижняя оценки значения функции шенноновского типа, характеризующей рост средней глубины деревьев решений в худшем случае с ростом числа переменных функции. Также проведено сравнение полученных результатов с аналогичными результатами для глубины деревьев решений, приведенными в работах [14, 41]. Используемое в доказательствах понятие разбиения таблицы функции сходно с понятием системы непересекающихся покрытий булева куба, использующимся в спектральных методах цифровой логики [30], но для оценки вида покрытия используются не спектральные свойства функции, а информация о принадлежности функции к конкретному замкнутому классу. В некоторых случаях это позволяет улучшить нижние оценки средней глубины деревьев решений (например, для функции голосования и функции логической суммы). Во втором параграфе показано, что каждая бинарная программа, имеющая минимальную среднюю глубину, обладает свойством бесповторности. Этот факт позволяет для ряда комбинаторных задач перенести экспоненциальные нижние оценки числа вершин бесповторных бинарных программ ([17, 56, 62, 63, 64]) на случай бинарных программ с минимальной средней глубиной.

В четвертой главе рассмотрен один из классов систем проверок -т.н. ограниченные системы проверок. Эта глава состоит из двух параграфов. В первом параграфе показано, что условие ограниченности системы проверок является необходимым и достаточным для существования верхних оценок средней глубины, зависящих только от энтропии. Во втором параграфе приведены необходимые и достаточные условия того, что временная сложность рассмотренного выше алгоритма А ограничена сверху полиномом от числа столбцов в таблице (в работах [37, 40] показано, что задача построения дерева решений с минимальной средней глубиной в общем случае является TVP-трудной). Эти условия включают требование ограниченности системы проверок. В работе [29] изучается средняя глубина двоичных деревьев поиска для некоторых задач (например, задачи о нахождении утечки в нефтепроводе), которым соответствуют ограниченные системы проверок. Полученные результаты обобщают оценки из [29] на случай произвольной ограниченной системы проверок, и дают полиномиальные алгоритмы построения оптимальных деревьев решений.

1. Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. - М.: Изд-во Наука, 1977.

2. Журавлев Ю. И. Об одном классе не всюду определенных функций алгебры логики // В сб. Дискретный анализ. Вып. 2 / Под ред. Ю. И. Журавлева. Новосибирск: Изд-во ИМ СО АН СССР, 1964. - С. 23-27.

3. Коспанов Э. Ш. Об одном алгоритме построения достаточно простых тестов // В сб. Дискретный анализ. Вып. 8 / Под ред. Ю. И. Журавлева. Новосибирск: Изд-во Наука, 1966. - С. 4347.

4. Кнут Д. Э. Искусство программирования. Т. 3. Сортировка и поиск, 2-е изд. М.: Издательский дом "Вильяме", 2000.

5. Марков Ал. А. Введение в теорию кодирования. М.: Изд-во Наука, 1982.

6. Марков Ал. А. Схемная сложность дискретной оптимизации // Дискретная математика. 1992. - Т. 4. N 3. - С. 29-46.

7. Моржаков Н. М. О сложности решения дискретных экстремальных задач в классе схемных алгоритмов // В сб. Математические вопросы кибернетики. Вып. 6 / Под ред. С. В. Яблонского. М.: Изд-во Наука, 1996. - С. 215-238.

8. Мошков М. Ю. Об условных тестах // ДАН СССР. 1982. - Т. 265. N 3. - С. 550-552.

9. Мошков М. Ю. Условные тесты //В сб. Проблемы кибернетики. Вып. 40. / Под ред. С. В. Яблонского. М.: Изд-во Наука, 1983.- С. 131-170.

10. Мошков М. Ю. О задаче минимизации линейной формы на конечном множестве // Комбинаторно-алгебраические методы в прикладной математике. Межвуз. сб. научн. трудов / Под ред. Ал. А. Маркова. Горький: Изд-во Горьковского ун-та, 1985. -С. 98-119.

11. Мошков М. Ю. Деревья решений. Теория и приложения. Нижний Новгород: Изд-во Нижегородского ун-та, 1994.

12. Мошков М. Ю. Оценки глубины деревьев решений, вычисляющих булевы функции // Доклады РАН. 1996. - Т. 350. N 1. - С. 22-24.

13. Мошков М. Ю., Чикалов И. В. Об эффективных алгоритмах построения деревьев решений // Тезисы докладов XII Международной конференции "Проблемы теоретической кибернетики". -Нижний Новгород, 1999. Часть 2. - С. 165.

14. Мошкова А. М. Диагностика "сохраняющих"неисправностей схем из функциональных элементов // Вестник ННГУ. Математическое моделирование и оптимальное управление. Вып. 2. Нижний Новгород: Изд-во Нижегородского ун-та, 1998. - С. 204-213.

15. Окольнишникова Б. А. Нижние оценки сложности реализации характеристических функций двоичных кодов ветвящимися программами // В сб. Методы дискретного анализа. Вып. 51 / Под ред. А. Д. Коршунова. Новосибирск: Изд-во ИМ СО АН СССР,1991. С. 61-83.

16. Пархоменко П. П. Теория вопросников // Автоматика и телемеханика. 1970,- N 4. - С. 140-159.

17. Редькин Н. П. Надежность и диагностика схем. М.: Изд-во МГУ,1992.

18. Соловьев Н. А. Тесты (теория, построение, применение). Новосибирск: Изд-во Наука, 1978.

19. Чашкин А. В. О среднем времени вычисления значений булевых функций // Дискретный анализ и исследование операций. 1997.- N 4. С. 60-78.

20. Чашкин А. В. Среднее время вычисления значений элементарных булевых функций // Дискретная математика. 2000. - N 3. -С. 114-123.

21. Чегис И. А., Яблонский С. В. Логические способы контроля электрических схем // Труды МИ АН СССР. 1958. - Т. 51. - С. 270360.

22. Чикалов И. В. Алгоритм построения деревьев решений с минимальным суммарным весом вершин // Вестник ННГУ. Математическое моделирование и оптимальное управление. Вып. 1(22). -Нижний Новгород: Изд-во Нижегородского ун-та, 2000. С. 200204.

23. Яблонский С. В. Тесты //В Энциклопедии Кибернетики. Т. 2 / Под ред. В. М. Глушкова. Киев: Главная редакция Украинской Советской Энциклопедии, 1975. - С. 431-432.

24. Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. М.: Изд-во Наука, 1966.

25. Ahlswede R., Wegener I. Suchprobleme. Stuttgart: B.G. Teubner, 1979.

26. Brandman Y., Orlitsky A., Hennessy J. A spectral lower bound technique for the size of decision trees and two-level AND/OR circuits // IEEE Transactions on Computers. 1990. - V. 39. - P. 282-287.

27. Chikalov I. V. On average time complexity of decision trees and branching programs // Fundamenta Informaticae. 1999. - V. 39. - P. 337-357.

28. Garey M. R., Jonson D. S. Computers and intractability. A guide to the theory of ./VP-completeness. San-Francisco: W. N. Freeman and Company, 1979.

29. Hegediis T. Generalized teaching dimensions and the query complexity of learning // Proceedings of the 8th Annual ACM Conference on Computational Learning Theory. -Santa Cruz, USA, 1995. New-York: ACM. - P. 108-117.

30. Humby E. Programs from Decision Tables.- London: Macdonald and New York: American Elsevier, 1973.

31. Hyafil L., Rivest R. L. Graph partitioning and constructing optimal decision trees are polynomial complete problems. Report N 3. - Roc-quencourt: IRIA - Laboratoria. - 1973.

32. Moshkov M. Ju. About the depth of decision trees computing Boolean functions // Fundamenta Informaticae. 1995. - V. 22 N 3. - P. 203215.

33. Moshkov M. Ju. Complexity of decision trees for regular language word recognition // Preproceedings of the Second International Conference Developments in Language Theory. Magdeburg. Germany. 1995.

34. Moshkov M. Ju. Test theory and problems of machine learning /7 Труды Международной школы-семинара "Дискретная математика и математическая кибернетика". Ратмино, 2001. М.: МАКС Пресс. - С. 6-10.

35. Moshkov М. Ju., Chikalov I. V. On the average depth of decision trees over information systems // Proceedings of the Fourth European Congress on Intelligent Techniques and Soft Computing. Aachen, Germany, 1996. - V. 1. - P. 220-222.

36. Moshkov M. Ju., Chikalov I. V. Upper bound on average depth of decision trees over information systems // Proceedings of the Fourth International Workshop on Rough Sets, Fuzzy Sets and Machine Discovery. Tokyo, Japan, 1996. - P. 139-141.

37. Moshkov M. Ju., Chikalov I. V. Bounds on average depth of decision trees // Proceedings of the Fifth European Congress on Intelligent Techniques and Soft Computing. Aachen, Germany, 1997. - P. 226230.

38. Moshkov M. Ju., Chikalov I. V. Bounds on average weighted depth of decision trees // Fundamenta Informaticae. 1997. - V. 31. N 2 -P. 145-156.

39. Moshkov M. Ju., Chikalov I. V. On algorithm for constructing of decision trees with minimal depth // Fundamenta Informaticae. -2000. Y. 41 N 3. - P. 295-299.

40. Nguen H. S., Nguen S. H. From optimal hyperplanes to optimal decision trees: rough set and boolean reasoning approaches / / Proceedingsof the Fourth International Workshop on Rough Sets, Fuzzy Sets and Machine Discovery. Tokyo, Japan, 1996. - P. 82-88.

41. Wegener I. On the complexity of branching programs and decision trees for clique functions // J. ACM. 1988. - V. 35 N 2. - P. 461-471.

42. Zak S. An exponential lower bound for one-time-only branching programs // Mathematical Foundations of Computer Science, 1984. -Lecture Notes in Computer Science V. 176. Springer-Verlag. P. 562566.