46
|
|
|
|
|
|
|
|
|
- |
, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ВХОД |
|
|
Рис. 1.11
ПРОВЕРКА АЛГОРИТМА
Глава 1. Обзор алгоритмов
ВЫХОД
В процессе проверки алгоритма мы должны убедиться, что он действительно предоставляет математическое решение для нашей задачи. Необходимо про верить результаты для максимального числа возможных значений и типов входных данных.
Точные, приближенные и рандомизированные алгоритмы
Для различных типов алгоритмов используются разные методы тестирования. Сначала выявим различие между детерминированными и рандомизированными
алгоритмами.
Проверка алгоритма |
47 |
В случае детерминированных алгоритмов конкретные входные данные всегда порождают одинаковые выходные данные. Но для ряда классов алгоритмов в качестве входных данных используется последовательность случайных чисел, что делает выходные данные разными при каждом запуске алгоритма. Алгоритм k-средних, который подробно описан в главе 6, является хорошим примером (рис. 1.12).
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
Рис. 1.12 |
|
|
Иногда, чтобы упростить логику и ускорить выполнение алгоритма, использу ются некоторые допущения. Таким образом, алгоритмы также делятся на два типа:
zz Точный алгоритм (exact algorithm). Ожидается, что такой алгоритм даст точное решение без каких-либо допущений или приближений.
zzПриближенный алгоритм (approximate algorithm). Когда сложность задачи слишком велика для имеющихся ресурсов, мы упрощаем нашу задачу, делая допущения. Алгоритмы, основанные на этих упрощениях или до пущениях, называются приближенными алгоритмами и дают не совсем точное решение.
Чтобы понять разницу между точными и приближенными алгоритмами‚ рас смотрим знаменитую задачу коммивояжера (TSP — travelling salesman problem), впервые представленную в 1930 году. Задача состоит в том‚ чтобы найти крат чайший маршрут для торговца‚ при котором он посетит каждый город из списка, а затем вернется в исходную точку (поэтому она и называется задачей комми вояжера). Для ее решения нужно рассмотреть все возможные комбинации го родов и выбрать наименее затратную. Сложность этого подхода составляет O(n!),
48 |
Глава 1. Обзор алгоритмов |
где n — количество городов. Очевидно, что временная сложность при n > 30 слишком велика.
Если число городов превышает 30, одним из способов снижения сложности является введение ряда приближений и допущений.
При описании требований к приближенному алгоритму важно задать ожидаемую точность. Во время проверки такого алгоритма мы должны убедиться, что по грешность результатов остается в допустимом диапазоне.
Объяснимость алгоритма
Если алгоритм применяется в особо важной ситуации, мы должны иметь воз можность объяснить причину того или иного результата. Необходимо убе диться, что вследствие использования алгоритма было принято справедливое решение.
Возможность четко определить признаки, которые прямо или косвенно повлия ли на конкретное решение, называется объяснимостью алгоритма. Алгоритмы, используемые в жизненно важных ситуациях, оцениваются с точки зрения обоснованности результатов. Этический анализ стал стандартной частью про цесса проверки алгоритмов, влияющих на принятие решений, которые касают ся жизни людей.
В случае с алгоритмами глубокого обучения достичь объяснимости бывает трудно. Например, если алгоритм используется для отказа в заявлении на ипо теку, важны его прозрачность и возможность объяснить причину.
Алгоритмическая объяснимость — это область активных исследований. Один из эффективных методов LIME (Local Interpretable Model-Agnostic Explanations) был предложен в материалах Ассоциации вычислительной техники (ACM) на 22-й международной конференции по извлечению знаний из данных Special Interest Group on Knowledge Discovery (SIGKDD) в 2016 году. Согласно этому методу, во входные данные каждого экземпляра вносятся небольшие изменения, а затем предпринимается попытка отобразить локальную границу принятия решений для этого экземпляра. После этого можно количественно оценить влияние каждой переменной для этого экземпляра.