-
탐색
- 상태공간 내에서
- 시작상태에서 목표상태까지의 경로를 찾는 것
- 각 상태를 생성하는 것을 연산자 라고 함
-
상태, 연산자, 그리고 상태 트리를 이용해 답을 찾아나가는 것
- 물론 이를 직접 프로그래밍 하지는 않으며, DFS/BFS 를 사용해 풀어나감
-
알고리즘
- 맹목적인 탐색
- 임의의 경로: BFS, DFS
- 최적의 경로: 균일 비용 탐색
- 경험적 탐색(휴리스틱)
- 임의의 경로: 언덕오르기, 최적 우선
- 최적 경로: A* 알고리즘
- 맹목적인 탐색
-
이를 8-Puzzle 예제를 통해 보도록 하겠다
- 8-puzzle에서의 시작, 목표 상태는 다음과 같음
- 연산자는 총 4개가 있으며, 다음과 같음
- UP: 공백을 위로
- RIGHT: 공백을 우측으로
- BOTTOM: 공백을 아래로
- LEFT: 공백을 좌측으로
- Stack을 이용
- 알고리즘 보면 알겠지만, FIFO
// define arrays
open := [start]
closed := []
while (open != []) { // while open has items
item := open.unshift() // get item (when left end of open)
if (item == goal) { // check item is goal state
return SUCCESS
}
closed.push(item) // put item on closed
for(generated_item : generate_children(item)) { // generate children of item
if ((open or closed) not contain generated_item) { // check duplicated
open.shift(generated_item) // left end of open
}
}
}- 맨왼쪽의 open item 얻어내고
- 이를 goal state와 비교하고
- 아니면 children generate하고
- closed와 비교해 중복제거하며 open의 왼쪽에 넣고
- 마지막으로 item을 closed에 넣어주고
- Queue 이용하는 것
- LIFO
open := [start]
closed := []
while (open != []) {
item := open.unshift()
if (item == goal) {
return SUCCESS
}
closed.push(item)
for (generated_item : generate_children(item)) {
if ((open or closed) not contain generated_item) {
open.push(generated_item) // right end of open
}
}
}- 알고리즘 나머지 다 같고
- 단지
generated_item을open의 right에 넣는다는 차이점 만 있다 - 이건 LIFO로 구현해야 하니 이러하게 된 것
- 효율은 BFS가 더 좋다
-
그러나 이들은 가능한 노드를 모두 탐색해대니 느릴 수 밖에 없다
- 경험적 탐색은 경험적(휴리스틱) 정보 를 사용해 좀 더 효율적인 동작이 가능하다
-
8-puzzle에 대한 휴리스틱 정보는 다음 두 가지로 나눌 수 있다
h1: 현재 제 위치에 있지 않은 타일의 개수h2: 각 타일의 목표 위치까지의 거리
-
이들을 이용해 각각의 휴리스틱 탐색을 진행할 수 있는 것
- 휴리스틱 정보. 즉, 평가함수의 값을 원하는 상태(goal)로 향하도록 진행하는 탐색
- 가령
h1은 값이 낮은 방향으로 진행하는... 그런 것을 말한다 - 이렇게 평가함수는 문제에 따라 종속적이라고 할 수 있음
-
이는 언덕오르기 알고리즘 을 이용해 진행한다
- 자신이 목표로 하는 상태에 더 가까운 것을 선택하는 알고리즘
- 선택되지 않은 상태는 저장되지 않음 = 중복허용
- 더 이상 선택할 것이 없을 때, 그 곳을 정상이라고 판단
- 이 때문에, local maxima 이슈가 발생될 수 있고
-
알고리즘은 다음과 같음
open := [{ start, eval_value }]
closed := []
while (open != []) {
item := open.unshift()
if (item == goal) {
return SUCCESS
}
closed.push(item)
for (generated_item : generate_children(item)) {
if ((open or closed) not contain generated_item) {
eval_value := calc_eval(generated_item) // calc eval_function value
open.push({ generated_item, eval_value })
open.sort('eval_value') // sort by 'eval_value'
}
}
}- 그러나 local maxima같은 문제가 발생하게 된다
-
너무 깊이는 들어가지 않도록 하는 것
- 평가함수
f(n) = g(n) + h(n) h(n): 현재 노드에서 목표까지의 거리g(n): 초기 상태에서 현재까지의 비용(깊이)
- 평가함수
-
알고리즘은 비슷한
open := [{ start, eval_value }]
closed := []
while (open != []) {
item := open.unshift()
if (item == goal) {
return SUCCESS
}
closed.push(item)
for (generated_item : generate_children(item)) {
if ((open or closed) not contain generated_item) {
// eval_value = h + g
eval_value := calc_h(generated_item) + calc_g(gengerated_item)
open.push({ generated_item, eval_value })
open.sort('eval_value') // sort by 'eval_value'
}
}
}-
지금까지 한 탐색은 '전향추론'
- 전향추론: 초기상태 => 목표상태 탐색
- 후향추론: 목표상태 => 초기상태 탐색
-
문제에 따라 후향추론이 더 알맞은 경우도 있다
-
두 명 이상의 상대가 서로 겨룰 때 사용할 수 있는 알고리즘
- depth를 진행할 때 마다 서로 번갈아가며
- 자신에게 최적인(자신이 원하는) 결과를 취하도록 한다
- 위의 그림에서는 짝수는 Max, 홀수는 min 값을 취하도록 함
-
마지막 node에 도착해야만이 중간 node의 값을 알 수 있음
- 아래부터 올라오는 구조이기 때문
- 따라서 비효율적
- 또한, 너무 깊이 들어갈 수가 있기에 max-depth를 잡곤 함
-
a,b를 이용해 가지쳐서 Mini-Max 알고리즘을 좀 더 빠르게 진행할 수 있도록 하는 방법a는 Max (init:a := -inf)b는 min 을 가리킴 (init:b := inf)
-
진행하며 가지치는 것
- 방법은 유튜브 참고
-
생성규칙:
IF-THEN으로 표현한 문장IF: 조건THEN: 결과
-
전문가 시스템은 info와 생성 규칙을 이용하는 것
- 정보(info): 의미가 있게 체계화된 것
- 데이터: 의미가 없는 그냥 사실
- 지식(knowledge): 더욱 일반화되고 모호해진, 정제된 정보
-
이런 전문가 시스템은 사실로 새로운 사실을 만들어 내는 것이기에
- 결과에 대한 이유를 설명할 수 있다
-
전문가 시스템의 세 파트
- 지식 베이스
- 추론엔진
- 인터페이스
-
다음과 같이 동작하는 것
- 점화를 이용해 추론을 진행하는데
- 이 떄, 순방향/역방향이 가능
- 사실
Z를 찾는다고 하자- 초기값은 다음과 같다고 가정하고
- 찾는 과정은 아래와 같음
- 기반지식 위에서부터 하나씩 진행한다
Y & D랑X & B & E이거 세 개는 없어서 건너뛴거
- 사실
A가 있으니,A -> X진행하고X를 사실DB에 넣으라는 말
C있으니,C -> LL & M은 없으니 일단 건너뛰고- 다시 맨 위에서부터 시작
X & B & E있으니,X & B & E -> Y진행L & M은 마찬가지로 없고
Y & D있으니,Y & D -> Z진행- 이를 통해
Z를 찾아내지
- 이를 통해
- 이렇게 진행하는 것이다
- 단, 보다싶이 마구잡이로 사실을 막 생성하기에
- 좀 비효율적 ㅎ
- 얘는 목표 지향
- 쓸데없는 상태 만들지 않는다는 말
- 왜냐고? 애초에 goal에서 시작하걸랑
- 초기 상태는 동일
- 목표 사실
Z부터 시작해 역으로 추론을 시작한다 Y & C -> Z니까,Y와C를 찾아줌- 참고로
C는 이미 있으니,Y만 찾아주면 되겠지
- 참고로
X & A -> YA는 이미 있고,X만 찾아주면 된다
B -> X- 이를 통해
Z가 추론가능함을 알 수 있겠지
- 이를 통해
- 그대로 추론진행
-
AI의 핵심은 지식 인데, 이를 체계적으로 정제한 것
-
지식표현 종류
- 논리
- 규칙
- 의미망
- 프레임
- OOR(Object-Oriented Representation)
-
규칙
- 앞서 전문가시스템에서 봤지
(A, B) -> (C, D, E)로도 표현이 가능하댄다
-
의미망
카나리 is a 새새 has 날개배니 is a 카나리- 뭐 이런 관계를 명시한 것
- 전문가 시스템과 함께 사용하곤 한다
-
프레임
- 속성과 메서드가 합쳐저 있는, 마치 Class 비슷한 애
- 전문가 시스템과 함께 사용하곤 한다
-
인공지능에서의 논리
- 명제논리:
P,R이런걸로 추상화하는거 - 술어논리: 전체 문장을 주어/목적어 이렇게 분리하는 것
- 명제논리:
-
이 중, 명제논리를 구현해보면 다음과 같음
| C | D | | C -> D |
|---|---|---|---|
| T | T | | T |
| T | F | | F |
| F | T | | T |
| F | F | | T |
-
이게 뭘 의미하느냐?
- 조건
C가 참이면, 결과D도 참 - 물론,
C가 참이 아니어도, 결과D는 참이 될 수 있음 - 그러나,
C가 참이나 결과D가 거짓일 수는 없음
- 조건
-
기억해야하는 규칙들 (위의 구현과 함께 보면 좋겠지)
- Modus Tollens(부정식)
A -> B일 때,~B면~A- 결과가 false면, 가정도 false
(A -> B) and ~B => ~A
- Modus Ponens
A -> B일 때,A면B- 가정이 true면, 결과도 true
(A -> B) and A => B
- Chain Rule (삼단논법):
A -> B, B -> C일 때,A -> CA -> B and B -> C => A -> C
- Modus Tollens(부정식)
- 명제논리를 술어논리로 변환
p |
q |
| ~p |
| ~p v q |
| p -> q |
|---|---|---|---|---|---|---|---|
T |
T |
| F |
| T |
| T |
T |
F |
| F |
| F |
| F |
F |
T |
| T |
| T |
| T |
F |
F |
| T |
| T |
| T |
-
그냥 뭐 그대로 대치되는 것
- 즉,
~p v q <=> p -> q
- 즉,
-
예시
forall(x): DOG(x) -> MAMML(x)~DOG(x) v MAMML(x)
-
fuzzy: 확실하지 않은... 확률의 세계 (
0.0 ~ 1.0)- fuzzy logic: 명확히 정의할 수 없는 지식을 표현하는 방법
- fuzzy set: 이런 애매모호한 값들의 집합을 나타내기 위한 방법
-
일반 집합
A = { x | x > 6 }
-
퍼지 집합
A = { x, u A(x) | x in A }u는 비율
A = { u A (x_i) / x_i | x in A }(참고로/는 나누는 게 아니라, 그냥 구분기호임)A = {u_A (x_1) / x_1}, {u_A (x_2) / x_2}, ...- 이렇게 비율별로 나타내는 것
-
설정한 Fuzzy set에 대해, 이를 좀 더 집중화 할 수가 있다
- 이를 헤지 라고 하며, 좀 더 모호한?표현을 할 수 있도록 함
-
일반적인 퍼지 집합
- 헤지를 적용한 퍼지 집합(초록색)
- 이러한 헤지는 기존의 퍼지 집합에 대해 다음과 같은 연산을 통해 가능하겠지
[u_A (x)]^{n}n < 1: 볼록해짐n > 1: 오목해짐 (위 그림과 같음)
-
규칙에 대해
- OR:
max - AND:
min - NOT:
1 - value(여집합)
- OR:
-
전건:
IF -
후건:
THEN -
소속 함수:
u_A (x)
-
어떠한 일을 진행하는데 있어 정의된 평가 기준에 따라 퍼지값을 구한다
-
A
u(x = A2) = 0.2u(x = A3) = 0.2
-
B
u(y = B1) = 0.1u(y = B2) = 0.8
-
위와 같은 규칙 집합 및 아래와 같은 규칙들이 있다고 한다
- 이 역시 미리 정의된 규칙이겠지
-
규칙1 (
C1):x가A2ORy가B1max(u(x = A2), u(y = B1)) = max(0.2, 0.1) = 0.2- 즉, 규칙
C1 = 0.2
-
규칙2 (
C2):x가A2ANDy가B2min(u(x = A2), u(y = B2)) = min(0.2, 0.8) = 0.2- 즉, 규칙
C2 = 0.2
-
규칙3 (
C3):x가A1C3 = u(x = A1) = 0
- 이를 통해 위와 같이 구해지겠다
- 이렇게 통합되고
- 다음 수식을 통해 무게중심을 구한다
- 무게중심의 값은
u_A (x)안에 있다
- 무게중심의 값은
- 해 보면 다음과 같음
- 즉,
35%의 확률로 어떠한 일이 발생된다는 것을 암시한다는 말
- 다음을 기반으로 한다
- 위를 통해 다음을 이끌어낼 수 있다
A와B가 함께 일어날 확률은B가 일어난 상태에서A가 일어날 확률
- 여기서, 교집합의 교환법칙으로 인해 다음과 같음을 알 수 있다
- 따라서, 다음과 같다고 할 수 있다
A가 일어날 확률을 다음과 같이도 표현할 수 있을 것이다B가 일어난 상태에서A가 일어날 확률 +B가 일어나지 않은 상태에서A가 일어날 확률- 이를 수식으로 표현하면 다음과 같다
- 이를 통해 위의 식을 다음과 같이 표현할 수 있음
- 인코딩 과정
- 평가
- 선택
- 교차
- 변이 (이후 다시 평가 반복)
- 지식, 정보, 데이터
- 낫피오큐
- modus tollens
- modus ponens
- 소속 함수
- 평가, 선택, 교차, 변이
네트워크