Алгебраические байесовские сети: поиск канонического представителя
-
1 курс
ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ И НАУКА О ДАННЫХ
-
Абрамов Максим Викторович
Научный руководитель
-
Вяткин Артем Андреевич
Куратор
"Алгебраическая байесовская сеть (АБС) — модель искусственного интеллекта, позволяющая описывать логико-вероятностные связи между утверждениями. Как и для других моделей, в теории алгебраических байесовских сетей является важным поиск методов, позволяющих ускорить работу алгоритмов. Одним из подходов к ускорению может быть переход к более простым, быстрее обрабатываемым объектам, что и лежало в основе идеи, рассматриваемой в данной работе.
Логико-вероятностные связи в АБС задаются с помощью оценок, которые могут быть точечными и интервальными. Алгоритмы, работающие с первым типом оценок, требуют выполнение простых матричных операций, для работы же со вторым, интервальным типом, необходимо решать более трудоемкие с точки зрения времени вычисления задачи линейного программирования. Таким образом, поиск канонического представителя, то есть переход от объектов с интервальными оценками к объектам со скалярными оценками, позволил бы ускорить работу с АБС. Однако, такой переход осуществляется за счет потери части информации о предметной области, поэтому он может быть полезен при дефиците времени или в случае наличия ограниченных вычислительных мощностей.
АБС состоят из меньших элементов — моделей фрагментов знаний (ФЗ), и для них поиск канонического представителя был уже ранее описан. Это же работа посвящена поиску канонического представителя всей сети. В результате было предложено два алгоритма: точный и приближенный. Точный алгоритм рассматривает погружение АБС в один объемлющий ФЗ, и потому также требует решения задач линейного программирования. Приближенный алгоритм работает быстрее и основан на методе цепной генерации, итеративно генерирующий канонического представителя для всех ФЗ в сети. Доказана корректность работы алгоритмов, в первом случае для любых сетей, во втором — для ациклических.
Практическая часть работы — соответствующие алгоритмы были автоматизированы, добавлены в веб-приложение по работе с АБС — https://abn.dscs.pro/."
Артём Андреевич Вяткин