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

• Автор: Лысёнок, Евгений Игоревич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 93 с.

Оглавление
Введение
Глава 1
Глава 2
Глава 3
Заключение

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

применяли и развивали стандартные математические, .методы. Например, широкое распространение в решении задач распознавания, получили методы математической статистики. Это удавалось не для каждой из практических задач, либо класс задач сужался до тех; которые могли быть подвержены формализации. В случае расширения класса задач при практическом применении иногда приходилось отступать, от принципов строгого математического доказательства, который применялся в теоретических исследованиях.
Представители второй школы пришли к выводу, что задачи распознавания требуют новых подходов в прикладной математике. В разработке таких подходов помогло появление первых ЭВМ, что позволило математикам проводить широкий спектр математических экспериментов. Этот метод исследования во многом похож на экспериментальные методы исследования физика-естественника, которые позволяют ему строить различные гипотезы об изучаемых им явлениях, а затем проверять их'экс-периментальным путём. Точно также математик может выдвинуть гипотезу и, не проводя строгих математических доказательств, проверить гипотезу, проведя математический эксперимент.
Таким образом, на первом этапе собирается экспериментальный материал проверки той или иной гипотезы о методе решения конкретной задачи. Изучается класс задач, приводящих к задаче распознавания, например, задача прогнозирования в геологии. Изучение описаний месторождений и участков местности, где месторождения не обнаружены, приводит к гипотезе: множества описаний первого и второго класса разделяются достаточно простой поверхностью. Простейшей поверхностью является гиперплоскость. Уточнённая гипотеза: описания, выполненные набором числовых признаков и принадлежащие разным классам, разделяются гиперплоскостью. Проводится эксперимент на ЭВМ и показывается, что в 99 случаях из 100 гипотетическое разделение действительно имеет место.
Появляется так называемый эвристический алгоритм: по описаниями объектов двух разных классов строится разделяющая гиперповерхность, а процесс распознавания сводится к определению полупространства относительно построенной гиперплоскости, к которой относится описание предъявленного для распознавания объекта.
В развитие теории распознавания можно выделить этап, связанный с появлением большого числа принципиально разных эвристических алгоритмов. Так как эти алгоритмы основаны лишь на экспериментально

где а1,..., ап — столбцы матрицы А.
Легко видеть, что если для столбца матрицы а', г Є {1,2,..., гг.} выполняется 5аг = • -+<5ПОі„ > 0, т.е. среди номеров единиц в векторе
6 и г-м столбце матрицы А есть общие номера, то второй элемент г-го столбца матрицы Є} равен 0, так как знаменатель стремится к бесконечности, иначе все единицы а1 не содержатся во множестве номеров единиц вектора 5, а значит, 6а1 = дд — б2 = |Л| — норма Хемминга ( см. [18]) для вектора 5, т.е. число его единиц.
Если же есть общие номера единиц в векторе 5 и единиц в векторе а‘, т.е. номера нулей в г-м столбце матрицы А, то первый элемент г-го столбца матрицы равен 0. В обратном случае, когда все единицы вектора а а следовательно, нули о* содержатся среди нулей вектора <5, или, что одно и то же, все единицы вектора 5 содержатся среди единиц вектора аг, то элемент г-го столбца первой строки матрицы равен 5аг = 55 = |й|.
Таким образом, имеем

где [<)( — число единиц в векторе 6, а => Ь - для произвольных булевых векторов одинаковой длины конъюнкция поэлементных импликаций имеет вид
а =Ф 6 = («і 6і)&... &(а„ =>- Ь„) Є {0,1 },а{,Ьі Є В = {0,1), (42)
где х => у = х V г/, х,у Є В, а для произвольных булевой матрицы А Є Втхп и вектора Ь Є Вт :
А => Ь — (а1 => 6,... ,ап => 6), (43)
где а1,... ,ап — столбцы матрицы А.
Далее, используя (36) для Л/о, рассмотрим
т — Л12(7лг) — пт —
-*+оо ІУ N—*+оо
і :. ./у —
1+(Яб+-Ьб)а'