Алгоритм

Материал из MachineLearning.

Версия от 20:49, 28 сентября 2008; Vokov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Содержание

1 Общие определения
- 1.1 Формальные признаки алгоритмов
2 Алгоритмы анализа данных
3 Литература
4 Ссылки

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

Общие определения

Единого «истинного» определения понятия «алгоритм» нет. Наиболее известные варианты определения опираются на интуитивное понятие «задачи»:

Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность (Д. Э. Кнут).
Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи (А. Н. Колмогоров).
Алгоритм — это последовательность действий, либо приводящяя к решению задачи, либо поясняющая, почему это решение получить нельзя.

Формальные признаки алгоритмов

Детерминированность: в каждый момент времени следующий шаг работы однозначно определяется состоянием исполнителя. Алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных.
Понятность: алгоритм должен включать только команды из заранее оговоренной системы команд исполнителя.
Завершаемость (конечность): при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов.
Массовость: алгоритм должен быть применим к разным наборам исходных данных.

Алгоритмы анализа данных

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

В машинном обучении понятие алгоритм может употреблять в трёх смыслах.

Алгоритм как функция $a:\: X\times W \to Y$ , преобразующая входные данные (описание одного или нескольких объектов из пространства объектов $X$ ) и вектор параметров $w\in W$ в выходные данные (ответы или прогнозы из множества допустимых ответов $Y$ для каждого из входных объектов). В зарубежной литературе эта функция практически никогда не называется алгоритмом; употребляются термины function, classifier.
Алгоритм как функция, преобразующая обучающую выборку $\{x_i\}_{i=1}^m \in X^m$ в вектор параметров $w\in W$ . В зарубежной литературе эта функция называется алгоритмом обучения (learning algorithm).
Алгоритм как функция, преобразующая обучающую выборку $\{x_i\}_{i=1}^m \in X^m$ и тестовую выборку $\{x'_i\}_{i=1}^k \in X^k$ в выходные данные $\{y_i\}_{i=1}^k \in Y^k$ для каждого из тестовых объектов. Тем самым подразумевается, что обучение вектора параметров $w\in W$ «скрыто» внутри алгоритма. Такой взгляд принят в теории универсальных и локальных ограничений К. В. Рудакова, а также в трансдуктивном обучении (transductive learning).