Гарвард CS50: Введение в Искусственный Интеллект с Python 2020
Click to viewЭтим видео мы начинаем цикл лекций "CS50: введение в искусственный интеллект с Python".
Этот курс начинается там, где заканчивается основной курс CS50 и он посвящен концепциям и алгоритмам, находящимся в основе современного ИИ.
Мы затронем такие темы как: поиск оптимальных решений, оптимизация, анализ данных, нейронные сети, обработка естественного языка и многое другое.
Это легендарный Гарвардский курс CS50 на русском языке: основы искусственного интеллекта с Python.
Этот курс познакомит нас с концепциями и алгоритмами, лежащими в основе современного искусственного интеллекта, мы погрузимся в идеи, которые лежат в основе таких технологий как игровые движки, распознавание рукописного ввода и машинный перевод.
В первой лекции посвященной задачам поиска, мы ознакомимся с такими алгоритмами как: Поиск в ширину, Поиск в глубину, Жадный алгоритм поиска по первому лучшему, Минимакс, A * (A star) и посмотрим на их практическое применение к решению задач нахождения выхода из лабиринта или игр с нулевой суммой, таких например, как крестики-нолики и все это на примере популярного языка программирования - Python.
Тайм-коды:
0:24 в уроке идеи, техники и алгоритмы, которые лежат в основе Искусственного Интеллекта (Artificial Intelligence)
0:30 Небольшое описание курса
3:13 алгоритм поиска. Что компьютеру делать в определенной ситуации. Проблемы различных типов и форматов
3:34 примеры: пятнашки, лабиринт, гугл карты
4:41 что из себя представляет задача поиска. Из чего состоит её алгоритм обучения
4:49 Терминология: агент (agent), состояние (state), начальное состояние (initial state),
6:16 действия (actions),
7:28 модель перехода состояний (transition model),
9:34 пространство состояний (state space),
10:04 представление в виде Графа
10:56 проверка цели (goal test),
11:51 стоимость пути (path cost),
13:41 задача поиска (search problems),
14:18 цель-решение (solution),
14:28 оптимальное решение (optimal solution),
14:46 представление набора данных, связанных с задачей:
15:07 структура данных Узел (node),
16:34 Подход, с которого надо начать решать задачу. фронтир (frontier). Все варианты решения
18:21 проверка цели
18:37 развёртывание узла - оценка всех его соседей
19:29 применение в задаче поиска
22:06 возможные проблемы. Зацикливание
24:01 улучшенный способ решить задачу поиска
25:58 Структура данных Стэк (Stack) для добавления и удаления элементов last-in first-out
26:22 применение стэка к задаче
27:51 Алгоритм поиска Depth-First Search Поиск в глубину
28:37 Алгоритм поиска Breadth-First Search Поиск в ширину
29:04 Структура данных Очередь (Queue) first-in first-out
29:12 применение очереди к задаче
30:36 эти 2 алгоритма поиска на практике. Лабиринт
36:22 код
44:00 работа кода
44:37 пример 2 maze2
48:31 пример 3 maze3
51:58 выбор при нескольких возможных вариантах
53:13 2 типа поисковых алгоритмов. Это были неинформированные поиски
53:54 информированный поиск (informed search):
54:29 Алгоритм Greedy Best-First Search Жадный поиск по первому лучшему совпадению
56:36 с помощью эвристической функции Манхэттанское расстояние
57:40 на практике
1:01:39 хорошая эвристика
1:03:43 оценка пути (расстояния) до цели
1:04:31 улучшение
1:05:23 Алгоритм A* Search Астар. Учитывает 2 вида информации
1:09:30 находит оптимальный путь, при 2 условиях
1:11:51 Алгоритмы с 2 агентами. Состязательный поиск. Adversarial Search. Крестики нолики
1:14:11 Алгоритм Minimax Минимакс
1:17:15 описание кода Game
1:23:08 вычисление алгоритма минимакс
1:23:42 рекурсия в минимакс
1:28:20 диаграмма дерево минимакс
1:30:39 псевдо-код
1:36:40 оптимизация
1:39:57 Алгоритм Alpha-Beta Pruning Альфа-Бета обрезка
1:45:25 Алгоритм Depth-Limited Minimax минимакс с ограничением глубины. Для этого добавляется функция оценки
1:48:18 на следующем уроке о Знаниях, учитываемых ИИ
В этой лекции: Законы ДеМоргана, Логика предикатов, Пропозициональная логика, Логика первого порядка, Импликация, Конъюнкция, Дизъюнкция, Эквиваленция, Доказательство от противного, Инженерия знаний, Кванторы всеобщности, Кванторы существования и много практических примеров, где мы можем применить работу искусственного интеллекта с знаниями.
Тайм коды:
0:48 Knowledge Знания. Способность делать выводы на их основании
4:25 sentence высказывания. Язык представления знаний
4:51 Propositional Logic Пропозициональная логика. Логика Высказываний, основанная на утверждениях о мире
5:03 proposition symbols пропозициональные переменные (какой-либо факт о мире)
5:51 logical connectives логические союзы
6:38 Таблица истинности. Not (Не)
7:56 Конъюнкция (логическое и) And
9:33 Дизъюнкция (логическое или) Or
11:09 Импликация (подразумевает, приводит) Implication
13:13 Эквиваленция (условие равносильно в обе стороны, двухусловие) Biconditional
14:51 model модель
16:15 knowledge base база знаний. Представление знаний
17:05 entailment следствие
18:26 inference умозаключение
21:48 механизмы выводов
22:45 Model Checking Проверка Модели
27:16 код пример
34:28 алгоритм проверки модели
40:07 Knowledge Engineering Инженерия Знаний
40:59 пример Clue
45:31 код clue.py
54:04 пример Logic Puzzles
54:47 комбинированные переменные
56:58 код puzzle.py
1:01:39 пример Mastermind
1:03:28 асимптотика полного перебора в проверке модели
1:04:32 Inference Rules Правила Вывода:
1:05:12 modus ponens применение импликации
1:06:53 and elimination устранение конъюнкции
1:07:47 double negative elimination устранение двойного отрицания
1:08:36 implication elimination устранение импликации
1:10:18 biconditional elimination устранение эквиваленции
1:11:14 De Morgan's law Закон ДеМоргана
1:13:42 distributive property распределительный закон, распределительное свойство
1:14:53 обобщение выводов
1:15:57 Theorem Proving Доказательство Теоремы, как разновидность задачи поиска
1:17:43 Правило резолюции, правило вывода
1:18:06 контрарные литералы (литералы, которые дополняют друг друга)
1:19:19 clause клауза. Дизъюнкция литералов
1:23:03 Conjunctive Normal Form (CNF) Конъюнктивная Нормальная Форма (это конъюнкции дизъюнкций)
1:23:54 conversion to CNF преобразование любого логического выражения к выражению, содержащему только логические и и или
1:27:55 inference by resolution вывод на основе правила резолюции. Новый дизъюнкт. Резольвента
1:29:28 пустая клауза = ложь
1:30:34 rule of contraries Доказательство От противного
1:34:15 пример выводов на основе правила резолюции
1:38:29 First-Order Logic Логика Первого Порядка. Логика Предикатов. Предикатные символы Predicate Symbol
1:42:50 дополнительные 2 операции (кванторы):
1:43:01 1) universal quantification Квантор Всеобщности
1:44:20 2) existential quantification Квантор Существования
1:47:18 на следующей лекции понятие неопределённости
Добро пожаловать вновь на введение в искусственный интеллект с Python.
В прошлый раз мы рассматривали концепции и методики представления знаний, эта лекция посвящена подходам и методикам, благодаря которым ИИ может принимать решения в условии неопределенности.
Мы поговорим о таких вещах как: условная вероятность, правило Байеса, байесовская сеть, цепи Маркова, и о многом другом.
Добро пожаловать вновь на введение в искусственный интеллект с Python.
В прошлый раз мы говорили о таких вещах как: условная вероятность, правило Байеса, байесовская сеть, цепи Маркова, и о многом другом.
На этот раз мы рассмотрим основные принципы оптимизации задач, рассмотрим графы, алгоритмы локального поиска, задачи удовлетворения ограничений, линейные программы, поиск с возвратом (backtracking search), а также многое другое.
Тайм-коды:
0:55 оптимизация - выбор наилучшего варианта из набора возможных вариантов
1:25 алгоритм Локальный поиск (local search) те случаи, когда выяснение того, что именно является решением и как именно выглядит цель - суть задачи
2:34 пример на практике: дома и больницы
4:07 задачи поиска в пространстве состояний (state-space landscape). Целевая функция. Функция стоимости
7:26 алгоритм Восхождение к вершине (hill climbing)
14:41 ограничение этого алгоритма - не всегда результат - самое оптимальное решение
17:51 разновидности hill climbing: 1) Наискорейшее восхождение к вершине
18:34 2) Стохастическое восхождение к вершине
19:11 3) Восхождение к вершине по первому лучшему совпадению
19:39 случайное возобновление
20:23 4) Локальный лучевой поиск
20:57 код наискорейшее восхождение к вершине hospitals.py
29:25 алгоритм Имитация отжига (simulated annealing)
37:04 варианты использования. Задача коммивояжера
40:23 Линейное программирование (linear programming)
43:11 пример: минимизация затрат при том, что есть ограничения, надо наколбасить 90 единиц продукции
46:48 есть ряд алгоритмов для решения таких типов задач (линейные неравенства с ограничениями). Популярные алгоритмы: Симплекс метод (simplex), Метод внутренней точки (interior-point)
47:26 код production.py
50:58 Задачи удовлетворения ограничений (constraint satisfaction problem) CSP
51:37 пример: студенты. Граф Ограничений
55:00 пример: игра судоку
56:49 разные формы ограничений: жёсткие, мягкие
58:04 классификация ограничений: 1) унарные ограничения (зависят от констант), 2) бинарные (двоичные) ограничения (зависят от 2 величин)
59:07 условия: 1) проблемный узел сделать согласованным (удовлетворять всем унарным ограничениям)
1:03:06 другой тип согласованности - 2) согласованность дуги (удовлетворять всем бинарным ограничениям)
1:06:43 псевдокод: согласованность дуги
1:09:01 алгоритм AC-3 (задача удовлетворения всем ограничениям)
1:13:33 Граф ограничений
1:14:40 задача поиска состоит из частей...
1:15:07 формулировка CSP как подтип задач поиска
1:16:18 способы улучшить алгоритм, используя структуру задачи
1:16:53 алгоритм Поиск с возвратом (backtracking search). Рекурсивная функция. Псевдокод
1:20:21 пример на практике: поиск с возвратом
1:25:00 код поиск с возвратом scheduling -- schedule0.py
1:27:44 существуют библиотеки, реализующие этот алгоритм
1:29:33 алгоритм Поддержания согласованности дуги. Идеи логического вывода (inference). Использование согласованности дуг, без возврата
1:33:34 псевдокод
1:35:10 улучшенные варианты (select-unassigned-var). Какую переменную рассматривать дальше
1:37:17 пример на практике
1:39:25 функция domain_values Значения домена. Для какой переменной (выбор переменной, оставляющей наименьшее количество таких же вариантов в других переменных)
1:43:07 Вывод. Есть несколько различных способов сформулировать задачу. 1) задача в виде локального поиска, 2) в виде линейных программ, 3) задача удовлетворения ограничений
Смотрите также:
Весь гарвардский курс по основам программирования (CS50 2015 год)
Нейросеть сделала компьютерную игру
Игра «Маг кода» для изучения Python, JavaScript, анализа данных, машинного обучения и нейронных сетей