Помощь студентам в учебе
Решение задачи сильной отделимости как задачи классификации в машинном обучении
|
АННОТАЦИЯ 2
ВВЕДЕНИЕ 5
1. ОБЗОР ПРЕДМЕТНОЙ ОБЛАСТИ 10
1.1. Основные этапы решения задачи распознавания 11
1.2. Отделимость непересекающихся многогранников 13
2. ПОСТАНОВКА ЗАДАЧИ СИЛЬНОЙ ОТДЕЛИМОСТИ 15
3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ СИЛЬНОЙ ОТДЕЛИМОСТИ 17
3.1. Метод на основе операции проектирования 17
3.2. Метод опорных векторов 19
3.3. Метод с использованием теоремы об альтернативах 21
4. Фейеровские отображения 25
4.1. Однозначное фейеровское отображение 25
4.2. Многозначное фейеровское отображение 26
4.3. Фейеровский процесс 26
4.4. Теорема сходимости 26
4.5. Определение псевдопроекции 27
5. ИТЕРАЦИОННЫЙ АЛГОРИТМ С ИСПОЛЬЗОВАНИЕМ ФЕЙЕРОВСКИХ
ОТОБРАЖЕНИЙ 28
6. НЕСТАЦИОНАРНЫЕ ЗАДАЧИ 30
6.1. Задача о портфеле ценных бумаг 30
6.2. Задача о спам-фильтре 31
6.3. Задача определения морфологии и генезиса облаков 32
6.4. Задача о мезомасштабных конвективных системах 33
7. РАЗРАБОТКА ПРОГРАММЫ 35
7.1. Архитектура программы 35
7.2. Реализация алгоритма 37
7.3. Вычисление однозначного фейеровского отображения 39
7.4. Вычисление многозначного фейеровского отображения 41
7.5. Интерфейс 43
8. ГЕНЕРАЦИЯ СЛУЧАЙНЫХ МНОГОГРАННИКОВ 46
8.1. Архитектура программы 46
8.2. Цикл генерации гиперплоскостей для одного многогранника 50
9. ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ 54
9.1. Эксперименты на модельных задачах 54
9.2. Эксперименты на случайных задачах 57
9.3. Эксперименты с коэффициентом релаксации 59
ЗАКЛЮЧЕНИЕ 65
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 67
ПРИЛОЖЕНИЕ 1 72
ПРИЛОЖЕНИЕ 2 73
ВВЕДЕНИЕ 5
1. ОБЗОР ПРЕДМЕТНОЙ ОБЛАСТИ 10
1.1. Основные этапы решения задачи распознавания 11
1.2. Отделимость непересекающихся многогранников 13
2. ПОСТАНОВКА ЗАДАЧИ СИЛЬНОЙ ОТДЕЛИМОСТИ 15
3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ СИЛЬНОЙ ОТДЕЛИМОСТИ 17
3.1. Метод на основе операции проектирования 17
3.2. Метод опорных векторов 19
3.3. Метод с использованием теоремы об альтернативах 21
4. Фейеровские отображения 25
4.1. Однозначное фейеровское отображение 25
4.2. Многозначное фейеровское отображение 26
4.3. Фейеровский процесс 26
4.4. Теорема сходимости 26
4.5. Определение псевдопроекции 27
5. ИТЕРАЦИОННЫЙ АЛГОРИТМ С ИСПОЛЬЗОВАНИЕМ ФЕЙЕРОВСКИХ
ОТОБРАЖЕНИЙ 28
6. НЕСТАЦИОНАРНЫЕ ЗАДАЧИ 30
6.1. Задача о портфеле ценных бумаг 30
6.2. Задача о спам-фильтре 31
6.3. Задача определения морфологии и генезиса облаков 32
6.4. Задача о мезомасштабных конвективных системах 33
7. РАЗРАБОТКА ПРОГРАММЫ 35
7.1. Архитектура программы 35
7.2. Реализация алгоритма 37
7.3. Вычисление однозначного фейеровского отображения 39
7.4. Вычисление многозначного фейеровского отображения 41
7.5. Интерфейс 43
8. ГЕНЕРАЦИЯ СЛУЧАЙНЫХ МНОГОГРАННИКОВ 46
8.1. Архитектура программы 46
8.2. Цикл генерации гиперплоскостей для одного многогранника 50
9. ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ 54
9.1. Эксперименты на модельных задачах 54
9.2. Эксперименты на случайных задачах 57
9.3. Эксперименты с коэффициентом релаксации 59
ЗАКЛЮЧЕНИЕ 65
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 67
ПРИЛОЖЕНИЕ 1 72
ПРИЛОЖЕНИЕ 2 73
Четвертая промышленная революция (Индустрия 4.0) - это текущий тренд автоматизации производства и развития технологий обмена данными [1]. Наименование и начало публичных обсуждений этого явления в научном сообществе связано с Ганноверской промышленной выставкой -ярмаркой 2011 года.
Предыдущий промышленный переворот (Цифровая революция) ознаменовал переход от индустриального к постиндустриальному обществу: повсеместное введение цифровых технологий и вычислительной техники, появление сети Интернет и распространение портативных коммуникационных устройств (в частности смартфонов). Индустрия 4.0 является логическим продолжением этих тенденций на новом техническом и информационном уровне. В ее рамках развиваются такие технологии, как киберфизические системы [2], интернет вещей [3], облачные вычисления [4], когнитивные вычисления [5] и т.д.
Киберфизическая система - это система, состоящая из вычислительной компоненты и физического объекта биологического или искусственного происхождения, взаимно влияющих друг на друга. Вычислительные приборы отслеживают и управляют физическими процессами, причем обратная связь настроена так, что происходящее в физической системе оказывает влияние на вычисления и наоборот. Киберфизические системы могут быть использованы для предотвращения дорожных инцидентов путем мониторинга транспортной сети, отслеживания состояния пациентов медицинских учреждений и т.п.
Интернет вещей - это концепция сети физических предметов со встроенными вычислительными технологиями, обменивающихся информацией и иными способами взаимодействующими друг с другом и с внешней средой без участия человека. Ее внедрение в реальную жизнь стало устойчивой тенденцией с распространением беспроводных сетей и протокола IPv6, появлением облачных вычислений и развитием технологий межмашинного взаимодействия.
Облачные вычисления - это модель обеспечения сетевого (через «облако») доступа к общим вычислительным службам, таким как сервера, хранилища, базы данных, приложения, сервисы и др. В краткосрочной и среднесрочной перспективе совместное использование вычислительных ресурсов может значительно уменьшить нагрузку на инфраструктуру информационных технологий.
Раздел когнитивных вычислений появился сравнительно недавно, вместе с необходимостью обрабатывать постоянно растущие потоки
неструктурированных данных. Технология когнитивных вычислений базируется на дисциплине искусственного интеллекта и теории обработки сигналов. Она охватывает машинное обучение, экспертные системы, обработку естественного языка, распознавание речи и компьютерное зрение (распознавание образов), а также человеко-машинное взаимодействие [6]. Это автоматизация задач, решение которых, как считалась ранее, невозможно без участия человека.
Искусственный интеллект и машинное обучение являются одними из основных направлений четвертой промышленной революции [7], а классификация - одна из важнейших задач машинного обучения. Задача классификации заключается в определении класса, к которому принадлежит новый элемент на основе обучающего набора данных, состоящего из элементов, чей класс известен [8]. В качестве примеров применения алгоритмов классификации в реальной жизни можно назвать широкий спектр задач: распознавание текста и речи, создание экспертных систем для медицинской диагностики, предсказания местоположения полезных ископаемых или оценки кредитоспособности заемщика [9].
Исследователи заинтересовались данной задачей во второй половине XX века, к тому же временному периоду относятся первые наработки по ней, такие как теоремы отделимости непересекающихся множеств, которые сейчас являются одним из фундаментальных разделов математики [10]. При этом как теоремы о существовании отделимости, так и разделяющие алгоритмы представляют равную ценность. Инструменты, позволяющие решить задачу разделения двух выпуклых многогранников слоем наибольшей толщины, широко применяются в распознавании образов (задачи дискриминации, классификации и др. [11]).
Один из наиболее известных методов решения данной задачи можно описать как итерационное применение операции проектирования. Однако на практике не всегда удается вывести конструктивную формулу для вычисления проекции точки на выпуклое множество [12], из-за чего применение метода на реальных данных ограничено. Эту проблему можно решить, если заменить операцию проектирование на последовательность фейеровских отображений [13]. Данный метод был предложен И.И. Ереминым [14].
Фейеровские методы были введены венгерским математиком Липотом Фейером. Их можно описать как методы итерации проекционного типа, обобщающие операции метрического проектирования [15]. Фейеровские методы применяются в линейном программировании при решении систем линейных неравенств и несобственных (противоречивых) задач оптимизации. К преимуществам этих методов относятся хорошая распараллеливаемость, возможность динамической корректировки их работы и простота их программной реализации [16].
Сами фейеровские операторы строятся из суперпозиций элементарных проектирований на полупространствах, описываемых линейными неравенствами.
В отличие от других известных методов, алгоритмы разделения выпуклых многогранников, основанных на фейеровских отображениях, применимы к нестационарным задачам, что является важным преимуществом . Особенность нестационарных задач заключается в том, что их исходные данные непостоянны, то есть, могут изменяться в процессе решения . Как пример можно привести задачу о формировании портфеля ценных бумаг, задачу о распознавании спам-сообщений или задачи о классификации облаков для прогноза погоды.
Таким образом, задача разделения двух выпуклых многогранников слоем наибольшей толщины является актуальной и имеет широкое практическое применение в разных областях жизни, а рассматриваемый метод решения данной задачи с помощью фейеровских отображений, так как другие современные методы применимы не во всех случаях, несет большую практическую ценность.
Цель и задачи
Целью данной работы являлось изучение задачи разделения двух выпуклых многогранников слоем наибольшей толщины и алгоритма ее решения с использованием фейеровских отображений.
В ходе достижения поставленной цели необходимо было решить следующие задачи:
1) провести обзор предметной области задачи сильной отделимости и выполнить ее постановку,
2) рассмотреть различные методы решения данной задачи,
3) изучить два типа фейеровских отображений;
4) изучить алгоритм решения данной задачи с использованием фейеровских отображений,
5) спроектировать и разработать программу, реализующую данный алгоритм,
6) провести ряд вычислительных экспериментов.
7) провести анализ полученных результатов.
Новизна работы
Впервые получены результаты решения задачи сильной отделимости для модельного и случайного примера с размерностью n=140.
Теоретическая значимость
В работе исследован итерационный алгоритм построения слоя максимальной толщины, разделяющего два выпуклых непересекающихся многогранника, базирующийся на фейеровских отображениях как аналогов операции проектирования. Решена задача сильной отделимости как задачи классификации.
Практическая значимость
Результаты работы могут быть использованы на практике в случаях, когда при моделировании необходимо решить задачу сильной отделимости. В качестве примеров можно привести задачу о портфеле ценных бумаг, задачу о спам-фильтре или метеорологическую задачу классификации для прогноза погоды.
Материалы данной работы и полученные результаты доложены на международной конференции Global Smart Industry Conference (CloSIC 2018). Основные результаты работы опубликованы в издании [51], индексируемом в международных базах данных Scopus и Web of Science.
Структура и объем работы
В работу входит введение, девять разделов, заключение,
библиографический список и два приложения. Объем работы составляет 71 страницу, объем приложений - 2 страницы, объем библиографического списка - 51 источник.
Предыдущий промышленный переворот (Цифровая революция) ознаменовал переход от индустриального к постиндустриальному обществу: повсеместное введение цифровых технологий и вычислительной техники, появление сети Интернет и распространение портативных коммуникационных устройств (в частности смартфонов). Индустрия 4.0 является логическим продолжением этих тенденций на новом техническом и информационном уровне. В ее рамках развиваются такие технологии, как киберфизические системы [2], интернет вещей [3], облачные вычисления [4], когнитивные вычисления [5] и т.д.
Киберфизическая система - это система, состоящая из вычислительной компоненты и физического объекта биологического или искусственного происхождения, взаимно влияющих друг на друга. Вычислительные приборы отслеживают и управляют физическими процессами, причем обратная связь настроена так, что происходящее в физической системе оказывает влияние на вычисления и наоборот. Киберфизические системы могут быть использованы для предотвращения дорожных инцидентов путем мониторинга транспортной сети, отслеживания состояния пациентов медицинских учреждений и т.п.
Интернет вещей - это концепция сети физических предметов со встроенными вычислительными технологиями, обменивающихся информацией и иными способами взаимодействующими друг с другом и с внешней средой без участия человека. Ее внедрение в реальную жизнь стало устойчивой тенденцией с распространением беспроводных сетей и протокола IPv6, появлением облачных вычислений и развитием технологий межмашинного взаимодействия.
Облачные вычисления - это модель обеспечения сетевого (через «облако») доступа к общим вычислительным службам, таким как сервера, хранилища, базы данных, приложения, сервисы и др. В краткосрочной и среднесрочной перспективе совместное использование вычислительных ресурсов может значительно уменьшить нагрузку на инфраструктуру информационных технологий.
Раздел когнитивных вычислений появился сравнительно недавно, вместе с необходимостью обрабатывать постоянно растущие потоки
неструктурированных данных. Технология когнитивных вычислений базируется на дисциплине искусственного интеллекта и теории обработки сигналов. Она охватывает машинное обучение, экспертные системы, обработку естественного языка, распознавание речи и компьютерное зрение (распознавание образов), а также человеко-машинное взаимодействие [6]. Это автоматизация задач, решение которых, как считалась ранее, невозможно без участия человека.
Искусственный интеллект и машинное обучение являются одними из основных направлений четвертой промышленной революции [7], а классификация - одна из важнейших задач машинного обучения. Задача классификации заключается в определении класса, к которому принадлежит новый элемент на основе обучающего набора данных, состоящего из элементов, чей класс известен [8]. В качестве примеров применения алгоритмов классификации в реальной жизни можно назвать широкий спектр задач: распознавание текста и речи, создание экспертных систем для медицинской диагностики, предсказания местоположения полезных ископаемых или оценки кредитоспособности заемщика [9].
Исследователи заинтересовались данной задачей во второй половине XX века, к тому же временному периоду относятся первые наработки по ней, такие как теоремы отделимости непересекающихся множеств, которые сейчас являются одним из фундаментальных разделов математики [10]. При этом как теоремы о существовании отделимости, так и разделяющие алгоритмы представляют равную ценность. Инструменты, позволяющие решить задачу разделения двух выпуклых многогранников слоем наибольшей толщины, широко применяются в распознавании образов (задачи дискриминации, классификации и др. [11]).
Один из наиболее известных методов решения данной задачи можно описать как итерационное применение операции проектирования. Однако на практике не всегда удается вывести конструктивную формулу для вычисления проекции точки на выпуклое множество [12], из-за чего применение метода на реальных данных ограничено. Эту проблему можно решить, если заменить операцию проектирование на последовательность фейеровских отображений [13]. Данный метод был предложен И.И. Ереминым [14].
Фейеровские методы были введены венгерским математиком Липотом Фейером. Их можно описать как методы итерации проекционного типа, обобщающие операции метрического проектирования [15]. Фейеровские методы применяются в линейном программировании при решении систем линейных неравенств и несобственных (противоречивых) задач оптимизации. К преимуществам этих методов относятся хорошая распараллеливаемость, возможность динамической корректировки их работы и простота их программной реализации [16].
Сами фейеровские операторы строятся из суперпозиций элементарных проектирований на полупространствах, описываемых линейными неравенствами.
В отличие от других известных методов, алгоритмы разделения выпуклых многогранников, основанных на фейеровских отображениях, применимы к нестационарным задачам, что является важным преимуществом . Особенность нестационарных задач заключается в том, что их исходные данные непостоянны, то есть, могут изменяться в процессе решения . Как пример можно привести задачу о формировании портфеля ценных бумаг, задачу о распознавании спам-сообщений или задачи о классификации облаков для прогноза погоды.
Таким образом, задача разделения двух выпуклых многогранников слоем наибольшей толщины является актуальной и имеет широкое практическое применение в разных областях жизни, а рассматриваемый метод решения данной задачи с помощью фейеровских отображений, так как другие современные методы применимы не во всех случаях, несет большую практическую ценность.
Цель и задачи
Целью данной работы являлось изучение задачи разделения двух выпуклых многогранников слоем наибольшей толщины и алгоритма ее решения с использованием фейеровских отображений.
В ходе достижения поставленной цели необходимо было решить следующие задачи:
1) провести обзор предметной области задачи сильной отделимости и выполнить ее постановку,
2) рассмотреть различные методы решения данной задачи,
3) изучить два типа фейеровских отображений;
4) изучить алгоритм решения данной задачи с использованием фейеровских отображений,
5) спроектировать и разработать программу, реализующую данный алгоритм,
6) провести ряд вычислительных экспериментов.
7) провести анализ полученных результатов.
Новизна работы
Впервые получены результаты решения задачи сильной отделимости для модельного и случайного примера с размерностью n=140.
Теоретическая значимость
В работе исследован итерационный алгоритм построения слоя максимальной толщины, разделяющего два выпуклых непересекающихся многогранника, базирующийся на фейеровских отображениях как аналогов операции проектирования. Решена задача сильной отделимости как задачи классификации.
Практическая значимость
Результаты работы могут быть использованы на практике в случаях, когда при моделировании необходимо решить задачу сильной отделимости. В качестве примеров можно привести задачу о портфеле ценных бумаг, задачу о спам-фильтре или метеорологическую задачу классификации для прогноза погоды.
Материалы данной работы и полученные результаты доложены на международной конференции Global Smart Industry Conference (CloSIC 2018). Основные результаты работы опубликованы в издании [51], индексируемом в международных базах данных Scopus и Web of Science.
Структура и объем работы
В работу входит введение, девять разделов, заключение,
библиографический список и два приложения. Объем работы составляет 71 страницу, объем приложений - 2 страницы, объем библиографического списка - 51 источник.
В научном исследовании были рассмотрены методы решения задачи сильной отделимости, основанные на фейеровских отображениях как аналога операции проектирования. Были использованы фейеровские отображения двух типов: однозначное и многозначное. Выполнена программная реализация итерационного алгоритма, реализующего указанные методы. Проведены вычислительные эксперименты по исследованию скорости сходимости алгоритма и подбору параметров алгоритма. Эксперименты проведены для двух классов задач: модельных масштабируемых Model-N и случайных, сгенерированных специальным алгоритмом, Random. Результаты экспериментов описаны в виде графиков и таблиц.
В ходе работы были решены поставленные задачи и достигнуты следующие результаты:
1) произведен обзор предметной области задачи сильной отделимости, включающий в себя основные задачи распознавания,
2) осуществлена математическая постановка задачи сильной отделимости,
3) рассмотрены три метода решения задачи сильной отделимости: метод на основе операций проектирования, метод опорных векторов и метод с использованием теоремы об альтернативах,
4) рассмотрены два типа фейеровских отображения: однозначное и многозначное,
5) рассмотрен алгоритм решения задачи сильной отделимости с использованием фейеровских отображений,
6) рассмотрены реальные нестационарные задачи, к которым может быть применима разрабатываемая программа,
7) спроектирована и разработана программа, реализующая данный алгоритм и позволяющая проводить вычисления в пространстве произвольной размерности и с использованием обоих типов фейеровских отображений,
8) проведены три серии вычислительных экспериментов: с модельными задачами, со случайными задачами и с коэффициентом релаксации, влияющим на скорость сходимости алгоритма. Размерность задачи варьировалась в диапазоне n=10 до n=140. По результатам экспериментов подобраны хорошие значения рассматриваемых параметров алгоритма. Проведенные вычислительные эксперименты подтвердили корректность алгоритма и эффективность предложенных подходов.
В ходе работы были решены поставленные задачи и достигнуты следующие результаты:
1) произведен обзор предметной области задачи сильной отделимости, включающий в себя основные задачи распознавания,
2) осуществлена математическая постановка задачи сильной отделимости,
3) рассмотрены три метода решения задачи сильной отделимости: метод на основе операций проектирования, метод опорных векторов и метод с использованием теоремы об альтернативах,
4) рассмотрены два типа фейеровских отображения: однозначное и многозначное,
5) рассмотрен алгоритм решения задачи сильной отделимости с использованием фейеровских отображений,
6) рассмотрены реальные нестационарные задачи, к которым может быть применима разрабатываемая программа,
7) спроектирована и разработана программа, реализующая данный алгоритм и позволяющая проводить вычисления в пространстве произвольной размерности и с использованием обоих типов фейеровских отображений,
8) проведены три серии вычислительных экспериментов: с модельными задачами, со случайными задачами и с коэффициентом релаксации, влияющим на скорость сходимости алгоритма. Размерность задачи варьировалась в диапазоне n=10 до n=140. По результатам экспериментов подобраны хорошие значения рассматриваемых параметров алгоритма. Проведенные вычислительные эксперименты подтвердили корректность алгоритма и эффективность предложенных подходов.
