컴퓨터과학 CS50 2020 Lecture : Artificial Intelligence

 

<강의 필기>

 

 

Introduction
Artificial intelligence는 사람처럼 지능을 가지고 이성적으로 컴퓨터를 프로그래밍하여 구현되는 것이다.
예를 들어 게임 tic-tac-toe에서 컴퓨터는 상대 플레이어의 움직임에 대한 최적의 대응을 하며 게임 플레이를 진행한다.

 

 

 

Decision-Making
동영상 추천 시스템, 스팸 필터링, 게임 플레이 등 현명한 의사결정을 위해서 컴퓨터를 훈련시킨다.

Decision trees
질문에 대한 답변에 기반을 두어 하나씩 의사결정을 진행하는 방식이다.

Minimax
상대방의 수를 예측하며 게임을 플레이하는 알고리즘이다.
자신에게는 유리한 최고의 점수를 부여하고 상대방은 자신에게 최악의 점수를 부여하려고 할 것이다.
이에 따라 게임 플레이어들의 점수가 변동된다.
Depth-Limited Minimax으로 알고리즘의 성능을 향상시킬 수 있다.

 

 

 

Search
출발점 A에서 도착점 B로 향하는 미로를 그려보자.
Uninformed Search(Blind Search) : Depth-First Search(DFS). Breadth-First Search(BFS)
Heuristic(Informed Search) : Manhattan Distance. Greedy Best-First Search. A* search

 

Uninformed Search(Blind Search)
현재 상태에서 목표 상태까지 도달하는 stepd의 개수를 모르는 것이다.

Depth-First Search(DFS)
길을 따라 랜덤으로 선택하여 가능한 길을 찾는 알고리즘이다.
시간이 오래걸린다는 단점이 있다.

Breadth-First Search(BFS)
하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다.
하나의 루트가 끝나면 그 정점에서 다시 시작해 다른 루트를 고른다.



Heuristic(Informed Search)
어떤 상태가 목표 상태에 이르기 유리한지를 아는 것이다.
출발점 A에서 도착점 B로 향하는 미로에서 정점 C와 D를 거치면 이동거리가 짧아진다는 것을 안다.

Manhattan Distance
Manhattan Distance와 Euclidean Distance는 두 좌표 간의 거리를 계산한다.
Manhattan Distance는 L1 Distance로 |x1 - x2| + |y1 - y2|를 계산한다.
Euclidean Distance는 L2 Distance로 sqrt[ (x2-x1)^2 + (y2-y1)^2 ]를 계산한다.

Greedy Best-First Search
목적지에 가까운 Node 정점을 선택하고 그 Node 아래에 속하는 Node 정점을 선택한다.
경로 검색은 빠르지만 검색 결과는 최적의 이동 거리가 아닐 수 있다.

A* search(Best-First Search)
Node n에 도달하기 위해 실제 비용 g(n)과 Node n에서 목적지까지의 최소 비용을 예측한 추정 비용을 더한다.

 

 

 

 

Reinforcement Learning
step에서 긍정인지 부정인지를 선택하며 특정 경험을 강화하는 것이다.

epsilon = 0.10
if random() < epsilon:
    make a random move
else:
    make the move with the highest value

 

10% 내에 무작위로 새로운 행동을 선택하여 시도할 것이다.

 

 

 

Genetic Algorithms
생물학적 진화를 모방하여 자연 선택 과정을 기반으로 하여 최적화 문제를 풀 수 있는 방법이다.
더이상 random mutation이 벌어지지 않는 곳에서 bottleneck 현상이 일어나거나 local maximum을 구한다.
추천 시스템에서 Genetic Algorithms를 사용한다.

 

 

 

Neural Networks
저장한 값을 연산해가며 neuron을 거쳐간다.
Deep learning은 선형대수학과 결합해 Neural Networks의 문제를 풀어가는 방식이다.
픽셀의 조합으로 image의 세부사항을 표현하며 사람의 모습에 가까운 이미지를 생성한다.

 

 

 

 

 

 

 

 

강의 자료

Artificial Intelligence - CS50

 

 

 

CS50 Sandbox

CS50 Sandbox

 

 

 

 

Minimax algorithm, 미니맥스 알고리즘 (Tistory Blog 끝까지간다)

Minimax algorithm, 미니맥스 알고리즘

 

 

 

[알고리즘] 너비 우선 탐색(BFS)이란 (Heee's Development Blog)

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog

 

 

 

[인공지능 강좌] 7.Uniformed Search(Blind Search) 설명과 예시 (Naver Blog 안경잡이개발자)

[ 인공지능 강좌 ] 7. Uninformed Search(Blind Search) 설명과 예시

 

 

 

맨하탄 거리(Manhattan Distance) 개념과 구현해보기 (Tistory Blog 자비스가 필요해)

맨하탄 거리(Manhattan Distance) 개념과 구현해보기

 

 

Informed search, Greedy Best-first Search, A* Search (Tistory Blog abyong_log)

Informed search, Greedy Best-first Search, A* Search

 

 

 

유전 알고리즘 (Genetic Algorithm) (Mathworks)

유전 알고리즘 (Genetic Algorithm)