• 탐색

  • 상태공간 내에서
  • 시작상태에서 목표상태까지의 경로를 찾는 것
  • 각 상태를 생성하는 것을 연산자 라고 함

• 상태, 연산자, 그리고 상태 트리를 이용해 답을 찾아나가는 것

  • 물론 이를 직접 프로그래밍 하지는 않으며, 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
    }
  }
}

1. 맨왼쪽의 open item 얻어내고
2. 이를 goal state와 비교하고
3. 아니면 children generate하고
4. closed와 비교해 중복제거하며 open의 왼쪽에 넣고
5. 마지막으로 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
    }
  }
}

1. 알고리즘 나머지 다 같고
2. 단지 generated_item을 open의 right에 넣는다는 차이점 만 있다
3. 이건 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를 찾는다고 하자
  • 초기값은 다음과 같다고 가정하고
  • 찾는 과정은 아래와 같음

1. 기반지식 위에서부터 하나씩 진행한다
   • Y & D랑 X & B & E 이거 세 개는 없어서 건너뛴거
2. 사실 A가 있으니, A -> X 진행하고
   • X를 사실DB에 넣으라는 말
3. C 있으니, C -> L
4. L & M은 없으니 일단 건너뛰고
   • 다시 맨 위에서부터 시작
5. X & B & E 있으니, X & B & E -> Y 진행
   • L & M은 마찬가지로 없고
6. Y & D 있으니, Y & D -> Z 진행
   • 이를 통해 Z를 찾아내지

• 이렇게 진행하는 것이다
  • 단, 보다싶이 마구잡이로 사실을 막 생성하기에
  • 좀 비효율적 ㅎ

• 얘는 목표 지향
  • 쓸데없는 상태 만들지 않는다는 말
  • 왜냐고? 애초에 goal에서 시작하걸랑
  • 초기 상태는 동일

1. 목표 사실 Z부터 시작해 역으로 추론을 시작한다
2. Y & C -> Z니까, Y와 C를 찾아줌
   • 참고로 C는 이미 있으니, Y만 찾아주면 되겠지
3. X & A -> Y
   • A는 이미 있고, X만 찾아주면 된다
4. B -> X
   • 이를 통해 Z가 추론가능함을 알 수 있겠지
5. 그대로 추론진행

• AI의 핵심은 지식 인데, 이를 체계적으로 정제한 것

• 지식표현 종류

  • 논리
  • 규칙
  • 의미망
  • 프레임
  • OOR(Object-Oriented Representation)

• 규칙

  • 앞서 전문가시스템에서 봤지
  • (A, B) -> (C, D, E) 로도 표현이 가능하댄다

• 의미망

  • 카나리 is a 새
  • 새 has 날개
  • 배니 is a 카나리
  • 뭐 이런 관계를 명시한 것
  • 전문가 시스템과 함께 사용하곤 한다

• 프레임

  • 속성과 메서드가 합쳐저 있는, 마치 Class 비슷한 애
  • 전문가 시스템과 함께 사용하곤 한다

• 인공지능에서의 논리

  • 명제논리: P, R 이런걸로 추상화하는거
  • 술어논리: 전체 문장을 주어/목적어 이렇게 분리하는 것

• 이 중, 명제논리를 구현해보면 다음과 같음

• 이게 뭘 의미하느냐?

  • 조건 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 -> C
    • A -> B and B -> C => A -> C

• 명제논리를 술어논리로 변환

• 그냥 뭐 그대로 대치되는 것

  • 즉, ~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 (여집합)

• 전건: IF

• 후건: THEN

• 소속 함수: u_A (x)

• 어떠한 일을 진행하는데 있어 정의된 평가 기준에 따라 퍼지값을 구한다

• A

  • u(x = A2) = 0.2
  • u(x = A3) = 0.2

• B

  • u(y = B1) = 0.1
  • u(y = B2) = 0.8

• 위와 같은 규칙 집합 및 아래와 같은 규칙들이 있다고 한다

  • 이 역시 미리 정의된 규칙이겠지

• 규칙1 (C1): x가 A2 OR y가 B1

  • max(u(x = A2), u(y = B1)) = max(0.2, 0.1) = 0.2
  • 즉, 규칙 C1 = 0.2

• 규칙2 (C2): x가 A2 AND y가 B2

  • min(u(x = A2), u(y = B2)) = min(0.2, 0.8) = 0.2
  • 즉, 규칙 C2 = 0.2

• 규칙3 (C3): x가 A1

  • C3 = u(x = A1) = 0

• 이를 통해 위와 같이 구해지겠다

• 이렇게 통합되고

• 다음 수식을 통해 무게중심을 구한다
  • 무게중심의 값은 u_A (x) 안에 있다

• 해 보면 다음과 같음

• 즉, 35%의 확률로 어떠한 일이 발생된다는 것을 암시한다는 말

• 다음을 기반으로 한다

• 위를 통해 다음을 이끌어낼 수 있다
  • A와 B가 함께 일어날 확률은
  • B가 일어난 상태에서 A가 일어날 확률

• 여기서, 교집합의 교환법칙으로 인해 다음과 같음을 알 수 있다

• 따라서, 다음과 같다고 할 수 있다

• A가 일어날 확률을 다음과 같이도 표현할 수 있을 것이다
  • B가 일어난 상태에서 A가 일어날 확률 +
  • B가 일어나지 않은 상태에서 A가 일어날 확률
  • 이를 수식으로 표현하면 다음과 같다

• 이를 통해 위의 식을 다음과 같이 표현할 수 있음

• 인코딩 과정
  • 평가
  • 선택
  • 교차
  • 변이 (이후 다시 평가 반복)

• 언어의 종류
  • 형식언어 => 프로그래밍 언어
  • 자연언어

• 매개변수 종류

  • 형식 매개변수: 파라미터
  • 실 매개변수: 인자

• 매개변수 전달 방법

  • 참조 호출: call by reference
  • 값 호출: call by value
  • 이름 호출: 파라미터 자체가 인자로 치환되는 것

• 다음을 각각 참조, 값, 이름 호출로 호출하면?

Begin Integer A, B:
  Procedure F(X, Y, Z); Integer X, Y, Z;
    Begin
      Y := Y + 2;
      Z := Z + X;
    End F;

  A := 3;
  B := 5;

  F(A + B, A, A);
  PRINT A         // <= 결과무엇?

END

• 참조

  • Y와 Z가 A를 가리킨다는 것만 잘 알고 있으면 된다
  • 따라서 PRINT A는 13을 출력

• 값

  • 이건 뭐... 당연히 3을 출력

• 이름

  • F(X, Y, Z)가 F((A + B), A, A)로 변하는 것
  • 따라서 다음과 같아진다
    • Y := Y + 2 => A := A + 2 => A := 5 + 2
    • Z := Z + X => A := A + (A + B) => A := 5 + (5 + 5)
  • 답은 15

• 어셈블러
  • 대부분 two-pass-assembler 로 구성된다
  • first pass: 어셈블리 코드로 기호표를 작성
  • second pass: 이를 bit로 표시

• 다음 순서로 진행되겠지

  1. 어휘분석: 토큰화
  2. 구문분석: 파스 트리
  3. 의미분석
  4. 중간코드 생성
  5. 최적화
  6. 목적코드 생성
  7. 목적 프로그램

• 구문분석에서 parse tree 만드는거 나온다고