XI Международная студенческая научная конференция Студенческий научный форум - 2019

На сегодняшний день соревнования по спортивному программированию становятся все более популярными. Участие в таких соревнованиях позволяет расширить свои знания в области математики, алгоритмов, языков программирования, а также улучшить составление эффективных программ за ограниченное время.

Конкуренция в спортивном программировании - это интеллектуальная конкуренция в решении различных проблем на компьютере, где необходимо изобретать и применять алгоритм или программу на одном из языков программирования. Как правило, участникам предоставляется множество задач. Задача считается решенной, если участники смогли создать программу, которая правильно работает на тестах, подготовленных жюри. Испытания участникам заранее неизвестны.

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

Большое количество любителей спортивного программирования, в которых несколько команд или участников соревновались друг с другом, рано или поздно проявляли интерес к прогнозированию своих результатов, делали это систематически или нерегулярно, пытаясь не только доверять своей интуиции, но и разработать некоторый алгоритм, который позволяет правильно предсказать результат какого-либо соревнования в максимальном количестве случаев.

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

Кластеризация − это задача распределения большого количества доступных данных в группы (кластеры) на основе общих или, в случае их количественного измерения, аналогичных по размерным атрибутам. Таким образом, отдельно взятые векторы данных (примеры), которые сформировали кластер в результате работы искусственной нейронной сети, во-первых, должны действительно быть похожими друг на друга, а во-вторых, сами они определяют свойства, сформированного ими кластера. Процедура описания качественных и количественных свойств кластеров называется кластерным анализом. Полученное описание является ценным само по себе, но может также использоваться для последующей работы с уже обученной нейронной сетью, когда новый пример присваивается одному из уже существующих кластеров. Если процесс настройки сети и процедура кластерного анализа выполняются качественно, при достаточно большом количестве правильных данных обучения, можно с высокой степенью уверенности утверждать, что описание соответствующего кластера будет соответствовать этому новому примеру.

Решая проблему предсказания результата спортивного программирования, нужно знать, что ответ никогда не должен быть предсказанием одного результата. Единственный вопрос − частота реализации события. Таким образом, в результате решения проблемы должны быть получены вероятности каждого из возможных результатов контеста, и их сумма должна быть строго равна единице.

Среди методов кластеризации нейронных сетей чаще всего используются три следующих:

1. Нейронные сети Кохонена;

2. Нейронные сети адаптивного резонанса АРТ-2;

3. Нейронные сети, основанные на радиально-симметричных (радиальных) функциях.

Решение конкретной проблемы предсказания результата соответствия спортивного программирования может быть представлено в виде последовательности следующих шагов:

1. Сбор базовых данных о соревнованиях по спортивному программированию;

2. Выбор архитектуры нейронной сети для решения проблемы;

3. Выбор или разработка программного продукта для решения проблемы;

4. Формирование учебного набора и его структурирование в соответствии с требованиями используемого программного обеспечения;

5. Установка алгоритма обучения;

6. Обучение и кластерный анализ;

7. Практическое использование обученной нейронной сети для прогнозирования вероятностей возможных исходов.

Рассмотрим более подробно каждый из этапов.

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

Соответственно, если предсказатель планирует предсказать результаты матчей в различных видах спортивного программирования, на разных соревнованиях он должен учитывать это на этапе выбора учебных данных и, при необходимости, формировать несколько различных учебных образцов.

Другим важным фактором является качественный состав данных в обучающих векторах. Чем больше факторов будет учитываться, тем глубже можно выполнять кластеризацию, пока не будут получены очень неожиданные, но действительно действующие прогнозы. Ниже приведены некоторые примеры групп факторов, которые могут быть рассмотрены:

оперативная информация: сила соревнующихся команд / участников в настоящий момент и динамика ее изменения;

история участия этой команды / участников.

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

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

Альтернативный способ - разработать собственное программное обеспечение, в котором можно принять во внимание все нюансы решаемой проблемы, настроить ее самостоятельно. Однако очевидно, что этот путь требует гораздо больших усилий и времени. Но также очевидно, что полученный результат будет более точным. Естественно, чтобы идти по этому пути, нужно не только иметь достаточную квалификацию в области искусственного интеллекта, но и в области программирования.

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

Этап настройки алгоритма обучения и следующие этапы, как правило, повторяются много раз, но в строгой последовательности до тех пор, пока синоптик не будет удовлетворен результатом или не потеряет терпения.

Алгоритмическая настройка подразумевает прямое или косвенное управление размером сети, скоростью обучения и, возможно, в зависимости от выбранной архитектуры нейронной сети, рядом других параметров.

Если выполняется самообучающаяся сеть фиксированной структуры (сеть Кохонена или на основе радиально-базисных функций), то мы говорим об определении размера сети (количество кластеров). В результате некоторые из кластеров могут вообще не участвовать, а некоторые могут быть переполнены. Неиспользованные кластеры мешают только в процессе обучения сети, поскольку они замедляют работу алгоритма. Переполненные кластеры намного опаснее, так как их присутствие означает, что нейронная сеть не смогла должным образом разделить примеры обучения на функции, данные будут усреднены, а точность прогноза на примерах, попадающих в такие кластеры, очень низкая.

Если нейронная сеть не только самообучающаяся, но и самоорганизующаяся, что возможно для всех ранее перечисленных архитектур, то в результате пустые кластеры просто не будут, и переполненные кластеры в принципе могут управляться путем деления их на меньшие во время обучения.

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

Анализ кластеров также может выполняться автоматически, если программное обеспечение обеспечивает соответствующую функцию или выполняется вручную. Анализ состава одного кластера может включать получение следующих количественных характеристик:

- размер кластера (количество примеров, которые его сформировали);

- средние значения обучения и описания переменных;

- дисперсия этих переменных.

Если мы представим результат любого соревнования по спортивному программированию из учебного образца в виде двоичного вектора, состоящего, например, из трех переменных: «выиграть 1-ю команду», «выиграть вторую команду» и «провести», затем возможны только три комбинации результатов: (1, 0, 0), (0, 1, 0), (0, 0, 1). Посредством усреднения соответствующих переменных примеров, образующих кластер, в первом приближении можно получить вектор вероятности результатов любого нового соответствия, присвоенного этому кластеру. Вероятности результатов можно уточнить, введя для каждого примера весовой коэффициент в зависимости от расстояния до центра кластера: чем ближе к центру, тем значительнее вклад примера.

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

Код для цитирования: Скопировать