| HTML5 [1] |
| CSS3 [1] |
| JavaScript [3] |
| JS in HTML5 [4] |
| Canvas (Context2D) [1] |
| Canvas (WebGL) [0] |
| Browser Technologies [2] |
| jQuery [1] |
| ExtJS [0] |
| Prototype.js [2] |
| SVG [2] |
| Browsers [2] |
|
Mozilla Plugins
[0]
XUL, Jetpack, etc.
|
| Web [2] |
| MeowW [4] |
| iOS [0] |
| Алгоритмы [0] |
| Криптография [0] |
| Теория игр [0] |
| Теория вероятностей [0] |
| Математика [1] |
| Мат. анализ [0] |
| Алгебра [0] |
| Дискретная математика [0] |
| Теория графов [0] |
| Комбинаторика [0] |
| Теория чисел [0] |
| Комплексный анализ [0] |
|
Матлогика
[0]
Математическая логика, её связь с теорией алгоритмов и т.п.
|
| Тензоры [0] |
| Геометрия [0] |
| Топология [0] |
| Дифференциальная геометрия [0] |
| Дифференциальные уравнения [0] |
01:08:19 Алгоритмы искусственного интеллекта |
Приветики. Начинаю новый uCozerer со статьи об алгоритмах ИИ. $_IMAGE1$
Встретил на просторах ВК (точнее, потрясающего Physics.Math.Code.Books) 6 видеолекций от МЭИ про алгоритмы ИИ, не мог не заинтересоваться. Поскольку слушать видеолекции - менее интересно, чем читать статьи, решил скомпоновать это в статью, дополнив некоторыми интересными вещами и, конечно же, своим повествованием. Поехали что ли.
Сеть ХопфилдаНачнём с простейшей задачи: распознавание монохромной картинки. Монохромная - значит, каждый пиксель либо белый, либо чёрный (серый, красный, серо-буро-малиновый - какой хочется). Например, буква F:
Всё элементарно. Пробегаем по всем пикселям, сравниваем. Проблема в том, что картинка может быть повреждена:
Всё до сих пор элементарно, достаточно посчитать количество расхождений и посмотреть, превышает ли оно заранее заданный порог. Если картинка цветная, нужно ещё учесть разницу цветов каждого пикселя (благо, разных разниц цветов придумали предостаточно). Но, т.к. мы хотим попонтоваться генетическими алгоритмами, будем изучать сеть Хопфилда. Но для начала рассмотрим чуть более короткую задачу. Есть три вектора `x_1`, `x_2`, `x_3` и один вектор `y`. Вполне обычный случай.
$$ x_1 = [-1,1,-1,1]$$
$$ x_2 = [1,-1,1,1]$$
$$ x_3 = [-1,1,-1,-1]$$
$$ y = [1,-1,1,-1]$$
Внимание, вопрос. На какой из `x`-ов больше всего похож `y`? На этот вопрос нам и ответит сеть Хопфилда (или, точнее, у нас будет сеть Литтла). Составляем матрицу памяти: $$W=\sum_{i=1}^3 x_i^T\cdot x_i$$
$$\Downarrow$$
$$W= \begin{bmatrix} -1 \\ 1 \\ -1 \\ 1 \end{bmatrix}\cdot\begin{bmatrix} -1 & 1 & -1 & 1 \end{bmatrix}+\begin{bmatrix} 1 \\ -1 \\ 1 \\ 1 \end{bmatrix}\cdot\begin{bmatrix} 1 & -1 & 1 & 1 \end{bmatrix}+\begin{bmatrix} -1 \\ 1 \\ -1 \\ -1 \end{bmatrix}\cdot\begin{bmatrix} -1 & 1 & -1 & -1 \end{bmatrix}$$
$$\Downarrow$$
$$W= \begin{bmatrix} 3 & -3 & 3 & 1 \\ -3 & 3 & -3 & -1 \\ 3 & -3 & 3 & 1 \\ 1 & -1 & 1 & 3 \end{bmatrix}$$
Теперь нужно просто занулить диагональ. Не знаю пока, зачем, алгоритм такой. $$W^*= \begin{bmatrix} 0 & -3 & 3 & 1 \\ -3 & 0 & -3 & -1 \\ 3 & -3 & 0 & 1 \\ 1 & -1 & 1 & 0 \end{bmatrix}$$
Ну и, наконец, ударяемся в рекурсию, умножая полученную матрицу `W` на вектор `y^T`. $$y_1^*= W^* \cdot y=\begin{bmatrix} 0 & -3 & 3 & 1 \\ -3 & 0 & -3 & -1 \\ 3 & -3 & 0 & 1 \\ 1 & -1 & 1 & 0 \end{bmatrix}\cdot\begin{bmatrix} 1 \\ -1 \\ 1 \\ -1 \end{bmatrix}=\begin{bmatrix} 5 \\ -5 \\ 5 \\ 3 \end{bmatrix}$$
Ну и действуем на него покомпонентно так называемой функцией активации, в качестве неё возьмём обычную функцию `tt "sgn"`. $$\operatorname{sgn}(x)=\cases{
1 & для x > 0\cr
-1 & для x < 0
}$$
$$\operatorname{sgn}(y_1^*) = \begin{bmatrix} 1 \\ -1 \\ 1 \\ 1 \end{bmatrix}$$
Получили `tt"sgn"(y_1^**) = x_2`, похоже? Ура! С первой же итерации подошло. Но давайте убедимся, что процесс установился, посчитаем `y_2^**`. $$y_2^*= W^* \cdot \operatorname{sgn}(y_1^*)$$
Убедились. Разве не прекрасно? Наша сеть работает. Возвращаемся к задаче распознавания монохромных картинок. Достаточно все картинки кодировать в вектора-строки, вот и всё. Я решил написать небольшую сеть на JS / canvas, умеющую распознавать буквы. А теперь матчасть... К сожалению, на это всё обрывается. Это черновик статьи, который я вынес из черновиков для посетителей одного сайтика. Можно надеяться, что продолжение скоро будет ;) Гетероассоциативная памятьМуравьиный алгоритмМетод отжигаГенетический алгоритмГенетический алгоритм. Размещение графа на линейке |
|
|
| Всего комментариев: 0 | |