Machine Learning : Herbert Schildt

지능과 밀접히 관계된 것이 학습이다. 사실상, 지능은 배우는 능력 없이는 존재할 수가 없는데 왜냐하면 학습의 주요한 장점은 새로운 지식을 습득하는 수단이기 때문이다. 학습은 장점을 여러 가지 상황과 사건에 적용하고 사용하게 한다. 그러므로, 배우는 능력은 강력한 도구이다. 많은 프로그래머들이, 사람이 하는 것과 같은 방식으로 이 도구를 사용할 수 있는 프로그램을 만들고 싶어하는 것은 놀라운 일이 아니다. 이를 할 수 있는 프로그램은 단지 배움으로써 자신이 여러 가지 일을 수행하도록 배울 수 있기 때문에 이론상 좀처럼 작성될 것 같지 않은 프로그램이다.

이 장에서, 컴퓨터가 배울 수 있는 여러 가지 방법을 연구한다. 더우기, 이 장에서는 기계학습을 이루는 복잡한 방법을 설명하는 아주 단순한 프로그램을 개발한다.

1. 두 종류의 학습 (TWO KINDS OF LEARNING)

놀라운 모순은, 컴퓨터가 배우기는 아주 쉽기도 하고 아주 어렵기도 하다는 사실이다. 이 이유는 두가지 다른 유형의 학습 : 되풀이 학습과 인지학습이 있기 때문이다. 이 점에서, 여러 가지 다른 유형의 학습 - 유추에 의한 학습, 예에 의한 학습, 관찰에 의한 학습 등등 - 이 있다고 제안하고 싶을지도 모른다. 그러나, 이런 것들은 그것에 의해 지식이 습득될 수 있는 방법을 말하는 것이지, 학습이 일어나게 하는 실제 메커니즘을 말하는 것은 아니다. 이 절의 핵심이 되는 것은 학습의 기초이다.

1.1. 반복에 의한 학습 (Learning by Rote)

배우는 것들 중 많은 것이 단지 기억을 통해 얻어지는 사실들로 구성된다. 이 과정을 반복에 의한 학습이라고 한다. 이 방법을 통해 배울 수 있는 사실들 중 몇가지 예는 일리노이의 수도는 스프링필드이고, 1 + 1 은 2 이다. 또는 뉴욕에서 시카고까지의 거리는 1500 마일이다 라는 것들이다. 그러나, 반복 학습은 사실에만 제한되는 것이 아니다 ; 또한 어떤 일을 구성하는 것과 같은 일련의 행위를 배우기 위해서도 적용될 수 있다. 예를들어, 공장 노동자는 조립 라인에서 빨간 상자와 노란 상자를 제거하고, 그것들을 적당한 통 속에 넣도록 배울 수 있다. 기억된 순서는 다음과 같다.

1. 빨갛거나 노란 상자를 집어들어라.

2. 해당 통 속에 넣어라.

대부분의 아이들이 긴 나눗셈이나 곱셈을 배우는 방법에도 같은 생각이 적용된다 : 어린이는 행위의 특정한 순서를 기억해서 그 순서를 요구대로 적용한다.

반복 학습에서 중요한 것은 전문화이다. 필요에 의해, 반복에 의해 배울 수 있는 모든 것들은 정보의 특정한 항목들이다. 일리노이의 수도는 특정한 도시이다. 뉴욕에서 시카고까지의 거리는 특정한 거리이다. 비슷하게, 공장 노동자의 업무와, 긴 나눗셈을 해결하기 위하여 사용된 방법은 행위의 특정한 순서이다. 비록 일련의 행위들이, 어떤 두 숫자도 나눌 수 있는 긴 나눗셈과 같은 매우 다양한 문제에 적용될 수 있지만, 업무를 구성하는 단계의 실제 순서는 일반화되지 않는다. 그러므로, 반복에 의해 학습된 순서들은 더 적절히 프로시져라고 불린다.

컴퓨터는 반복에 의해 배울 수 있는 어떤 것도 쉽게 배울 수 있다. 사실상, 컴퓨터가 동작하는 정상적인 방법이다 : 프로그램 된다! 컴퓨터는 지시를 따르는 데에 아주 익숙해 있기 때문에, 프로시져를 쉽게 따라 갈 수 있거나 또는 정보의 어떤 항목을 데이터베이스에 쉽게 저장할 수 있다. 예를들어, 물은 32 도와 212 도 사이에서 액체다 라고 선생님이 학생에게 가르치는 것과 똑같이, 같은 정보를 데이터베이스 프로그램에 넣을 수 있고, 물이 언제 액체냐고 물으면, 학생과 컴퓨터는 같은 방법으로 반응할 것이 또 따른 예로서, 6 장에서 개발된 로봇 시뮬레이터는 여러 가지 행위를 배울 수 있다. 로봇이 배울 때, 개개의 인스트럭션들을 기억했다. 더우기, 로봇은 후에 그 지식에 따라 행동할 수 있었다 - 배운 것을 증명할 수 있었다.

요약하면, 반복 학습은 특정 사실이나 과정 (프로시져) 를 기억하는 것과 관련이 있다. 파생된 어떤 일반화도 요구하지 않고 고수준의 사고도 연구하지 않는다. 컴퓨터는 이미 반복에 의해 쉽게 배울 수 있기 때문에, 다음 절에서는 학습의 또 다른 방법을 살펴본다.

1.2. 인지학습 (Cognitive Learning)

사람들이 배우는 가장 중요한 방법은 컴퓨터에서 구현하기에 가장 어려운 것인데, 인지학습이다. 이러한 형태의 학습에서, 특정 지식을 분석하고 조직하고 상호연관시키기 위하여 추론을 사용한다. 이러한 정신적 노력의 산물은 class 묘사의 생성이다.

class 묘사 (class description) 는 몇가지 특별한 예를 조사함으로써 파생되는 일반화이다. 예를들어, 몇몇 특별한 개에 의한 지식을 통해, 어떤 개도 가상적으로 개로 인정할 수 있게 하는 개에 대한 일반화된 개념을 만들어 낼 수 있다. 요점은 개에 대한 class 묘사를 배웠다는 것이다. 일반적으로, class 묘사는 그 유형의 모든 대상들을 정의한다.

사람이 일반화를 얼마나 빨리 배울 수 있는지는 놀라울 정도이다. 그림 1 에서 발견되는 네가지 물체를 생각하자. 그것들 중 하나는 class 에 들지 않는다. 분명히, 사각형이 비록 세 개의 서로 다른 크기이긴 하지만 삼각형은 사각형과 같은 class 가 아니다. 세 개의 사각형 모두에 맞는, 하지만 삼각형에는 적용되지 않는 class 를 쉽게 만들 수 있기 때문에, 삼각형과, 사각형이 아닌 어떤 것도 그 class 에 속하지 않는다는 것을 알았다. 이와같은 간단한 상황에서, 그것에 대하여 생각조차 하지 않고 일반적인 class 를 만들었다.

그림 1. 어느 물체가 속하지 않는가?

또한 프로시져에 대한 class 묘사를 형성할 수 있다. 그리고 나서 이 일반화된 프로시저들을 여러 가지 비슷한 상황에 적용할 수 있다. 예를들어, 비로 마루를 청소하는 일반적인 과정을 안다. 더우기, 차를 운전하기 전에 비록 그 도로를 본 적이 없지만 어떤 도로에도, 어떤 경로를 따라서도 쉽게 운전해 갈 수 있다.

이 일을 정의하는 기본 절차적 요소들을 일반화할 수 있기 때문에 그것들을 할 수 있다. 현재 인간을 로봇과 구별하는 것은 프로시져 (과정) 들을 일반화하는 능력이다. 로봇은 특정한 업무만 알 수 있다 ; 업무를 일반화할 수는 없다.

class 를 학습하는 능력은 물체나 과정에만 제한되는 것이 아니라, 생각과 개념에도 적용될 수 있다. 예를들어, 대부분의 철학과 종교는 그들의 추종자들에게 행동과 신앙에 대한 일반화된 코드를 주려고 시도하며, 개인이 이 코드에 따라 특정한 일을 해석하도록 하려고 한다. 선과 악의 개념을 생각하자. 이것들은 특정한 사건을 묘사하기 위하여 사용되는 일반적인 class 이다. 이 개념들은 도덕적인 의미를 갖는 어떤 행위들의 class 묘사를 표현한다.

명백히, class 묘사를 학습하는 능력은 인간이 생각하는 방식대로 생각하는 컴퓨터를 만드는데 기본이 된다. 이 장에서 다루어지는 것은 이러한 유형의 학습에 대한 에뮬레이션이다.

2. class 묘사는 어떻게 학습하는가? (HOW CLASS DESCRIPTIONS ARE LEARNED?)

종종 이 책에서는 프로그래머가 지적인 컴퓨터를 만들려고 할 때 극복해야 할 가장 큰 장애물들 중의 하나는 사람들이 자신의 사고과정을 거의 이해하지 못한다는 사실이라고 지적했다. 같은 것이 인지 학습에 대해서도 성립한다. 일반적으로, 개개의 물체에 대한 일반화된 class 묘사를 어떻게 만들 수 있는지 사실상 모른다. 그러나, 이런 유형의 학습을 컴퓨터에 에뮬레이트하는 방법을 찾아내려고 애쓰는 과정에서, 인간의 사고 과정에 대한 어떤 통찰이 다루어지는지 알아내려고 애쓰는 과정에서, 인간의 사고 과정에 대한 어떤 통찰은 다루어지지 않았을지도 모른다.

MIT 의 인공지능 연구실장인 Patrick Henry Winston 교수는 인지 학습을 이해하는데 주요한 돌파구를 만들었다. 그는 AI 에 관해 세계적으로 탁월한 권위자 중의 한 사람이고 그의 저서인 Artificial Intelligence (Menro Park, Calif:Addison-Wesley, 1984) 는 AI 를 진지하게 공부하는 학생에게 추천되는 서적이다. class 묘사를 학습하는 그의 방법은 곧 보게 될 이유 때문에 때때로 "hit-and-near-miss" 라고 불리운다.

2.1. 예와 Near-Misses (Examples and Near-Misses)

Hit-and-near-miss 프로시져를 이해하도록 돕기 위해, 여기서 그 프로시저의 요점 (key point) 을 설명해주는 전통적인 예를 보인다. 누군가에게 블록들로 구성된 아치를 인식하도록 가르치고 있다고 상상해야 한다. 먼저 그림 2a 에 있는 아치를 만들고, 그리고나서 그 사람에게 이것이 아치다 라고 말해준다. 다음, 위에 있는 블록을 없애고 그림 2b 에 있는 것처럼 다른 두 블록의 옆에 그것을 놓는다. 그리고 그 학생에게 이것은 아치가 아니다 라고 알려준다. 이 단계는, 아치는 꼭대기에 블록이 하나 있어야 함을 의미한다. 다음 그림 2c 에 있는 것과 같은 아치를 만들고 그 사람에게 이것이 아치다 라고 말한다. 그리고나서, 그림 2d 에 있는 구조를 만들고 이것은 아치가 아니다라고 말한다. 이것은 측면의 지주가 닿아서는 안된다는 것을 의미한다. 마지막으로, 그림 2e 에 있는 아치를 만든다. 이것은 맨 꼭대기에 블록 대신 원 기둥을 놓는다. 그리고 이것도 여전히 아치라는 것을 나타낸다. 이 점에서, 학생은 아치에 대하여 다음의 class 묘사를 할 것이다 : 서로 닿지 않는 두 개의 블록 꼭대기에 블록이나 원기둥이 있어야 하고, 지주 블록들은 세워져 있거나 눕혀 있을 수 있다.

그림 2. 전형적인 hit-and-near 프로시저 예

a 는 아치, b 는 꼭대기가 없는 near miss, c 는 아치, d 는 블록이 맞붙은 near-miss, e 는 아치

이 예는 다음의 요점을 설명해 준다 : class 묘사는 그 class 의 일부이거나 몇가지 방법만 다른, (또는 개념 또는 생각, 또는 과정) 들의 선택된 예를 사용하여 만들어질 수 있다. 학생이 어떤 물체들이 class 의 일부이고, 어느 물체들이 near-misses 인지 듣기만 하면, 그 학생은 각 예와 관련된 유사성과 차이점을 관찰함으로써 class 묘사를 구성할 수 있다.

class 묘사가 만들어질 때, 올바른 예에 의해 행해진 역할은 near-misses 가 한 역할과 다르다. 각 올바른 예는 현재의 묘사가 확장되거나 일반화 되게 한다. 예를들어, 아치의 경우, 학생에게 지주 블록이 누워있는 아치를 보여줄 때, 학생은 이 새로운 구조 역시 아치라는 사실을 어떤 아치가 받아들여야 하는 묘사를 일반화해야 한다. 학생이 원기둥을 갖는 아치를 볼 때에도 같은 것이 적용된다.

그러나, 각 near-miss 는 만들어지는 묘사가 제한되게 한다. 그림 2b 에 있는 물체가 아치가 아니라는 사실로 제시될 때, 학생은 이 물체와 현재의 class 묘사 사이의 차이점을 결정해야 한다. 둘 사이에 유일한 분명한 차이는 세 번째 블록이 다른 두 블록의 꼭대기에 있지 않다는 것이다. 그러므로, 학생은 모든 아치들은 꼭대기에 블록이 하나 있어야 한다는 제약 조건을 class 묘사에 첨가한다. 그리고나서 학생은 측면이 닿는 near-miss 에 직면할 때 같은 과정을 따른다 : 측면은 닿지 않아야 한다는 제약조건이 class 묘사에 첨가된다.

class 묘사가 전개될 때, 앞의 제약조건은 일반화 될 수 있고, 앞의 일반화는 제한될 수 있음을 명심해야 한다. 예를들어, 학생에게 꼭대기에 원기둥이 있는 아치를 보일 때, 학생은 블록이 꼭대기에 있을 것을 요구하는 제약 조건을, 이제는 블록이나 원기둥이 꼭대기에 있을 것을 요구하도록 변경해야 한다. 만약, 꼭대기에 다른 유형의 블록들을 갖는 많은 아치를 보여주었다면, 결국 학생은 아치가 꼭대기에 어떤 것을 가질 것을 요구하도록 제약조건을 변경했을 것이다. 이런 경우에, 또다른 class 묘사가 긴 or 리스트를 대체하게 된다.

이 과정을 약간 다른 관점에서 보면, 각 올바른 물체는 학생에게 그 class 의 물체가 가질 수 있는 일련의 속성들을 제시한다는 것을 알 수 있다. 그러므로, 학생은 어떤 특정 물체가 어떤 class 의 일부라는 것을 들었기 때문에, 그 학생의 class 묘사는 이런 유형의 물체들을 포함해야 한다. 학생이 그 class 의 물체가 무엇을 가져야 하고 무엇을 가져서는 안되는지 (must have or must not) 배울 수 있는 것은 near-misses 의 사실을 통해서이다.

이 학습 과정에 기본이 되는 것은 near-misses 가 단 몇가지 분명한 방법만으로 - 아마도 하나 - 실제 물체와 달라야 한다는 사실이다. 그렇지 않으면, 학생은 제한 요소가 무엇인지 구별할 수 없을 것이다. 예를들어, 첫 번째 아치를 보이고, 그리고나서 창문 밖으로 날아가는 새를 가리키고 그 새는 아치가 아니라고 말한다면, 학생은 아치의 class 묘사에 의미없는 정보를 첨가할 수도 있다.

2.2. Hit-and-Near-Miss 프로시저 (The Hit-and-Near-Miss Procedure)

이제, class 묘사를 학습하는 hit-and-near-miss 방법에 대한 방금 주어진 설명을 컴퓨터가 사용할 수 있는 알고리즘으로 변역할 때다. hit-and-near-miss 알고리즘은 두 가지 가정을 한다. 먼저 class 의 일부이거나 near-miss 인 예를 제시하고, 그 예들에 대하여 절대 거짓말을 하지 않는 선생님이 있다. 두 번째로, 첫 번째 예는 초기 모델을 형성하는 것이기 때문에 유효해야 한다. 이러한 가정이 주어져 있을 때, hit-and-near-miss 알고리즘은 다음과 같다 :

observe sample and form initial model

repeat

observe sample

if hit then generalize

else restrict

until done

이 점에서, observe sample 이나 form initial model 프로시저들이 어떻게 구현되는 가에 중요하지 않다. 그러나, generalize 와 restrict 가 어떻게 작동하는지 이해하는 것은 알고리즘에는 중요하다. 여기 이 두 프로시저들이 가장 간단한 형태로 있다. (이 프로시저들의 완벽한 형태에 대해서는, 앞에서 언급되었던 Winston 의 책을 참조해야 한다)

procedure restrict :

determine the difference between the near-miss and the evolving model

if the model has an attribute not found in the near-miss, then require this attribute

if the near-miss has an attribute not found in the model, then forbid this attribute

procedure generalize :

determine the difference between the example and the evolving model

reconcile the difference by enlarging the model

추측할 수 있듯이, generalize 와 restrict 프로시저들은 설명하기는 쉽지만 구현하기가 복잡하다. 가장 어려운 면은 generalize 프로시저에 의해 요구된 것처럼, 차이점들을 조정하고 모델을 크게 하는 것이다. 이것이 왜 그런가 알기 위하여, 다시 예로 돌아가 생각해야 한다.

컴퓨터에게 원기둥이 있는 아치를 보였다면, 그 구조는 generalize 프로시저를 호출했을 것이다. 현재의 묘사와 예 사이의 차이는 꼭대기에 놓인 것의 모양이기 때문에, generalize 프로시저는 원기둥이나 블록이 꼭대기에 놓일 수 있도록 모델을 변형해야 한다. 그러나, 이를 하기 위한 최상의 방법은 무엇인가?

두가지 접근 방식이 있다. 첫 번째 방식은 or 리스트를 만드는 것이다. 이 경우에, 아치의 꼭대기를 다루는 모델의 부분은 "꼭대기에 블록이나 (or) 원기둥을 가져야 한다" 가 된다. 이 방식은 가장 쉽지만, 컴퓨터가 많은 변형을 만날 때 분명해지는 심각한 결정을 가진다. 두 번째 방식은 속성들의 새로운 class 를 만들어서 그 모델의 class 이름을 사용하는 것인데, 반면 class 를 형성하는 실제 속성들은 다른 곳에 저장된다. 이 경우에, 모델의 "꼭대기에 있는 것 (what's-on-top)" 이라는 부분은 "꼭대기에 BC 를 가져야 한다" 가 되는데, 여기서 BC 는 꼭대기에 있을 수 있는 물체들의 class 를 일컫는 class 이름이다. 이 점에서, BC 는 단순히 "block" 과 "cylinder" 만을 포함한다 : 그러나, 아치에 대한 묘사를 바꾸지 않고 BC 를 확장할 수 있다.

2.3. 두가지 중요한 원리 (Two Important Principles)

Hit-and-near-miss 프로시저의 적당한 동작 (operation) 에 완전히 필요한 것은 아니지만, 적용될 때 효율과 읽기 쉽게 하는 성질 (readability) 을 크게 향상시키는 두 가지 원리가 있다. 첫 번째 것은 "no guessing" 이라 불리고, 컴퓨터가 현재 모델과 near-miss 사이의 차이를 자신있게 구별할 수 없을 때 호출된다. - 즉, 무엇이 학습되어야 하는지 의심스러우면 컴퓨터는 learn nothing 을 해야 한다. 이것이 비록 보수적으로 들릴지는 모르지만, 에러를 피하는데 도움이 된다. 이 원리는 교사가 항상 명확한 차이를 갖는 near-miss 를 제공하면 호출될 필요가 없다.

두 번째 원리는 "no altering" 이라고 불린다. 교사가 현재의 정의와 일치 (match) 하지 않는 올바른 예를 제공하면, 컴퓨터는 그것을 다루기 위하여 올바른 분류를 확장하려고 하기 보다는 별개의 특별한 경우에 대한 class 를 만든다. 예를들어, 자동차의 정의는 내연기관 (internal combustion motor) 을 갖는다는 제약조건을 포함해야 한다. 그러므로 컴퓨터는 전차를 특별한 경우에 대한 class 의 한 구성원으로 다루어야 한다.

이 두 원리 모두 교사가 예에 대하여 주의하면 피해질 수 있는 충돌 상황에서만 호출되기 때문에, 이 장에서 나중에 개발되는 프로그램에 첨가되지 않을 것이다. 그러나, 어떤 프로그램도 개발할 수 있기 전에, 컴퓨터가 지식을 표현하고 저장할 수 있는 여러 가지 방법들을 이해해야 한다.

3. 지식 표현 (KNOWLEDGE REPRESENTATION)

학습할 수 있는 프로그램을 고안하는 명백한 어려움을 제외하고, 부차적인 문제는 습득된 지식을 컴퓨터 내부에 저장하는 방법을 만드는 것이다. 지식의 특성과 프로그래머의 선호도가 지식이 표현되는 방법을 결정한다. 지식표현 분야에서 발달한 여러 가지 기법들이 있고 가장 중요한 것은 다음과 같다 :

트리 (Trees)
리스트
네트워크

이 절에서는 이 기법들 각각에 대하여 연구한다.

3.1. 트리 (Trees)

후진 연쇄 (backward-chaining) 전문가시스템이 동작하는 방법으로 되돌아가 생각해 보자. 분명히, 이런 유형의 시스템에 대한 지식을 표현하는 가장 효율적인 방법은 트리이다. 전문가시스템이 트리를 통해 진행할 때, 큰 부분들 (large sections) 을 잘라내고 적당한 지식을 빨리 발견한다. 지식이 트리로서 어떻게 표현될 수 있는가 이해하기 위해서, 그림 3 에 보여진, 삼각형, 사각형, 사다리꼴에 대한 정보를 저장하기 위하여 사용된 트리를 생각해 보자. 그림에서 보여주듯이, 이 지식 트리를 사용하는 전문가시스템은 트리를 통해 이동함에 따라 사용자에게 항상 적절한 질문을 할 것이다.

그림 3. 삼각형, 사각형, 사다리꼴 의 지식 트리

트리는 특성상 계층적 (hierarchical) 이다. 그래서, 계층적 지식만 저장할 수 있다. 그러나, 많은 지식이 이 범주에 속하기 때문에 이것은 그다지 큰 제약은 아니다. 트리를 사용할 때의 가장 큰 단점은 트리가 효율적이도록 구성하고 유지하는 어려움이다. 트리와 연관된 오버헤드의 수준 (level) 은, 아주 적은 양의 지식을 저장하기 원할 때 트리를 매력적이지 못하게 만들 수도 있다.

3.2. 리스트 (Lists)

리스트는 항상, 지식을 표현하기 위하여 AI 의 전통적 방법이다. 이것의 주된 이유는, 최초의 AI 언어인 Lisp 이 리스트를 효율적으로 다루도록 설계되었기 때문이다. 리스트를 지식표현에 특히 매력적이게 하는 것은, 리스트가 C 로 처리하기에 매우 쉽다는 것이다.

지식이 리스트로 어떻게 표현되는지 이해하기 위해서, 도서관의 카드 카탈로그를 생각해보자. 만약 특정한 주제에 대한 책을 찾고 있다면, 각 카드를 훑어가면서 당신이 찾고 있는 것에 속하지 않는 것들은 버리고, 원하는 책을 발견할 때 멈출 것이다. 다시 말하면, 리스트로 저장된 지식은 그것을 찾아내기 (retrieve) 위해서 순차 탐색 (sequential search) 을 요구한다. 그림 4 는 삼각형, 사각형, 그리고 사다리꼴에 대한 지식을 리스트로서 어떻게 저장할 수 있는지를 보여준다.

그림 4. 삼각형, 사가형, 사다리꼴의 지식 트리

리스트들은 비록 순차적으로만 처리될 수 있지만, 모든 유형의 지식을 표현하기 위하여 그것을 사용할 수 있기 때문에 중요하다. 리스트를 처음에 AI 에 중요하게 만든 것이 바로 이 커다란 융통성이다. 또한 여러 인덱싱 기법을 사용함으로써 리스트를 거의 트리만큼 효율적으로 만들 수 있음을 기억해야 한다.

3.3. 네트워크 (Network)

네트워크로 지식을 표현하는 것은 복잡한 만큼 매력적이고 강력하다! 언젠가, 지식의 네트워크 표현이 표준이 될 가능성이 있지만, "블랙박스" 루틴들이 일반적으로 사용될 수 있은 후 라야 한다. 지식 네트워크는 두가지 조건에 기초를 둔다. 첫 번째 조건은, 네트워크에 있는 지식이 계층적이 아닌 (non-hierarchical) 그래프의 노드로 표현된다는 것이다 : 트리와는 달리 네트워크에서 모든 노드는 같은 중요성을 가지며 어떤 노드도 시작점으로 사용될 수 있다. 두 번째 조건은 유사한 유형의 지식은 서로 가깝게 그룹지어지도록 노드들이 배열된다는 것이다 : 그러므로, 이웃 노드들은 near-miss 관계를 갖는다. 예를들어, 그림 5 는 기하학적 모양들에 대한 네트워크를 보인다.

그림 5. 기하학적 모양 네트워크

네트워크를 적당한 위치에 넣고, 그리고나서 적당한 노드에 도착할 때까지 네트워크를 따라 진행함으로써 네트워크 모델을 액세스할 수 있다. 이론상, 이 방법은 새로운 노드로의 전이 (transition) 가 유사히 증가하는 방향 - 언덕 오르기 (Hill Climbing) 탐색의 한 형태 - 에 있기 때문에 만들어지게 되므로, 아주 효율적이어야 한다.

(실제로, 그 방법은 현재 노드에 연결하는 각 노드를 테스트하고, 증거와 가장 일치하는 노드를 선택한다). 네트워크를 어느 곳에 넣던 간에 이 프로시저는 작동할 것이지만, 목표에 다소 가까운 노드에 넣는 것이 가장 좋다. 그러므로, 대부분의 네트워크 모델들은 또한, 각 상황에 대한 엔트리 노드를 선택하는 것을 돕는 인덱스들의 리스트를 포함한다. 최악의 경우로, 만약 우연히 가장 닮지 않은 노드를 선택하면, 네트워크는 리스트로 퇴보한다.

지식을 표현하기 위한 네트워크 모델의 장점은 계층적인 지식과 계층적이 아닌 지식을 모두 쉽고 효율적으로 다룰 수 있다는 것이다. 계층적이 아닌 지식은 네트워크의 바깥 가장자리에 놓이려는 경향이 있고, 계층적인 지식은 중심 (추상적인 의미에서) 근처에 놓이려는 경향이 있다.

많은 AI 연구가들은 네트워크 모델이 인간의 지식 표현 방법과 가장 밀접하게 닮았다고 믿는다. 그러나 물론 이것은 여기서는 결론적으로 알려지지 않는다.

4. Hit-and-Near-Miss 프로시저 구현 (IMPLEMENTING THE HIT-AND-NEAR-MISS PROCEDURE)

지식이 표현될 수 있는 세가지 가능한 방법들 중에서, 가장 쉽고 가장 빠른 방법은 리스트를 사용함으로써이다. 따라서, 여기서 개발된 hit-and-near-miss class 묘사 학습 프로그램의 구현에 의해 사용될 것은 바로 이 방법이다. hit-and-near-miss 알고리즘의 묘사 중에 언급된 것처럼, 이 장에서 설명된 프로그램은 가장 간단한 버전이다. 그러나, 이 간단한 버전조차도 가장 일반적인 방법으로 구현하면 매우 도전적인 몇가지 문제를 제시한다. 불행히도 이 몇가지 문제들로의 해결은 많은 양의 코드를 요구하고 많은 루틴들의 명확성을 흐르게 한다. 그러므로, 여기서 개발된 버전은 교사가 뒤에 설명될 엄격한 형식 (format) 을 따른다고 가정하면, class 묘사를 정확히 학습할 것이다.

class 묘사 학습과정 (procedure) 를 구현할 때 중요한 것은 각 분류에 대하여 두 개의 리스트를 유지하는 것이다. 첫 번째 리스트는 분류가 가져야 하는 (must have) 그런 속성들을 포함하고, 두 번째 리스트는 가질 수 있는 (may have) 속성들을 유지한다. class 를 정의하기 위해서는 "must-have list" 만이 요구되지만, "may-have list" 는 모델을 개발하기 위하여 사용된다. 컴퓨터가 새로운 속성들을 학습할 때, 컴퓨터는 그것들을 먼저 may have 리스트에 놓고, near-miss 를 공부하고 있으면, 그 속성들이 class 묘사의 일부이어야 한다고 학습할 때에만 must have 리스트로 이동시킨다.

hit-and-near-miss 프로시저의 이 버전에 대하여, 모든 예 (sample) 들과 near-miss 들은 다음 구조를 갖는 문장에 의해 묘사될 것이다 :

주어구 (subject phrase) 동사구 (verb phrase) 목적어구 (object phrase)

그러므로, 아치의 예는 다음으로써 표현될 수 있다.

side one left of side two

주어구 동사구 목적어구

그것의 near-miss 쪽은 다음과 같이 표현될 수 있다.

side one not left of side two

주어구 동사구 목적어구

프로그램의 동작에 대한 중요한 점 (key) 은 (그리고 그것을 책 속에 맞을 만큼 충분히 간단하게 유지시키는 주요 제약조건), 동사구에 "not" 을 더하는 것은 모든 near-miss 를 형성한다는 점이다. 그러므로, 방금 주어진 예와 near-miss 에 대하여, near-miss 의 동사구에 있는 "not" 은 측면 1 이 측면 2 의 왼쪽에 있어야 (must be) 한다는 것을 결정하기 위하여 사용된다.

이러한 형식 (format) 하에서, must-have 데이터베이스와 may-have 데이터베이스는 다음 구조를 갖는 배열일 것이다 :

struct attribute {

char subject[80];

char verb[80];

char object[80];

char active;

};

프로그램은 모델이 전개됨에 따라 필요하지 않은 예들을 불활성하기 위하여 active 필드를 사용한다. generalize() 와 restrict() 프로시저들과 함께, 그것들을 구동시키는 (drive) learn() 프로시저가 여기에 보여진다.

/* learn a class description for an object */

learn()

{

char sub[80], verb[80], obj[80];

char msub[80], mverb[80], mobj[0];

for (; ;) {

printf("Enter an example. ＼n");

if (!get_example(sub, verb, obj)) {

return ;

}

if (find_may(sub, verb, obj)==-1) {

assert_may(sub, verb, obj);

generalize(sub, verb, obj);

}

printf("Enter a near-miss (CR to skip). ＼n");

get_example(msub, mverb, mobj);

restrict(msub, mverb, mobj);

}

/* restrict the description of an object i.e., remove from may-have list and place in must-have list. */

restrict(ms, mv, mo)

char *ms, *mv, *mo;

{

register int t;

char temp[4];

for (t=0; t<3; t++) temp[t]=tolower(mv[t]);

temp[3]='＼0';

if (strcmp(temp, "not")) return;

for (t=0; t<may_pos; t++) {

if (!strcmp(&mv[4], may[t].verb &&

!strcmp(may[t].subject, ma) &&

!strcmp(may[t].object, mo) && may[t].active) {

assert_must(may[t].subject, may[t].verb, may[t].object);

may[t].active=0; /* remove from list */

return ;

}

/* generalize new examples */

generalize(n, v, o)

char *n, *v, *o;

{

register int t, i;

/* check may-have list */

for (t=0; t<may_pos; t++) {

if (strcmp(may[t].subject, n) && /* not same subject */

!strcmp(may[t].verb, v) &&

!strcmp(may[t].object, o) && may[t].active) {

strcat(may[t].subject, " or ");

strcat(may[t].subject, n);

}

for (t=0; t<may_pos; t++) {

if (!strcmp(may[t].subject, n) &&

!strcmp(may[t].verb, v) &&

strcmp(may[t].object, o) && /* not same object */

may[t].active) {

strcat(may[t].subject, " or ");

strcat(may[t].object, o);

}

/* check must-have list */

for (t=0; t<must_pos; t++) {

if (strcmp(must[t].subject, n) && /* not same subject */

!strcmp(must[t].verb, v) &&

!strcmp(must[t].object, o)) {

strcat(must[t].subject, " or ");

strcat(must[t].subject, n);

i=find_may(n, v, o);

may[i].active=0; /* remove from may-have list */

}

for (t=0; t<must_pos; t++) {

if (!strcmp(must[t].subject, n) &&

!strcmp(must[t].verb, v) &&

strcmp(must[t].object, o)) { /* not same object */

strcat(must[t].object, " or ");

strcat(must[t].object, o);

i=find_may(n, v, o);

may[i].active=0; /* remove from may-have list */

}

이 프로시저들은 다음과 같이 동작한다. 사용자, 또는 교사가 예를 넣을 때마다 이미 거기에 있지 않으면, 컴퓨터는 그것을 may-have 데이터베이스에 놓는다. 그리고나서 generalize() 가 호출되는데, 이것은 예를 든 세 개의 구를, may-have 데이터베이스와 must-have 데이터베이스에 모두 들어있는 엔트리들과 비교한다. 만약 같은 동사구와 목적어구를 갖고 다른 주어구를 갖는 엔트리를 generalize() 가 찾으면, generalize() 는 단어 "or" 를 사용하여 두 개의 각 주어를 결합하고 엔트리를 변화 (update) 시킨다. 대안으로, 한 엔트리가 같은 주어와 동사를 갖지만 같은 목적어를 갖지 않으면, generalize() 는 두 개의 목적어를 결합하고 엔트리를 변화시킨다. 이런 방법으로, 새로운 분류가 만들어진다.

비록 있다 하더라도 모든 일반화가 이루어진 후에, 사용자는 near-miss 를 넣는다. 그러나, near-miss 가 이전에 넣은 예와 일치할 필요는 없다. 사실상, 사용자는 원한다면 near-miss 를 생략할 수 있다. near-miss 가 입력되면, 프로그램은 restrict() 를 호출한다. restrict() 프로시저는 may-have 데이터베이스에 있는 각 엔트리를 near-miss 구와 비교한다. "not" 을 제외하고 엔트릭 일치하면, restrict() 는 그 엔트리를 may-have 리스트에서 must-have 리스트로 옮긴다. 이 단계는 class 를 제한한다.

전체 프로그램이 여기에 보여진다. 이번에는 그것을 컴퓨터에 입력해야 한다.

/* Learning class descriptions by using the "hit-and-near-miss" method */

#define MAX 100

struct attribute {

char subject[80];

char verb[80];

char object[80];

char active;

};

struct attribute may[MAX]; /* may-have database */

struct attribute must[MAX]; /* must-have database */

int may_pos=0; /* index into may-have database */

int must_pos=0; /* index into must-have database */

main()

{

for (; ;) {

printf("(L)earn, (D)isplay, or (Q)uit ? ＼n");

switch(tolower(getch())) {

case 'l' : learn();

break;

case 'd' : display();

break;

case 'q' : exit();

}

printf("＼n");

}

/* learn a class description for an object */

learn()

{

char sub[80], verb[80], obj[80];

char msub[80], mverb[80], mobj[0];

for (; ;) {

printf("Enter an example. ＼n");

if (!get_example(sub, verb, obj)) {

return ;

}

if (find_may(sub, verb, obj)==-1) {

assert_may(sub, verb, obj);

generalize(sub, verb, obj);

}

printf("Enter a near-miss (CR to skip). ＼n");

get_example(msub, mverb, mobj);

restrict(msub, mverb, mobj);

}

/* place an entry into the may-have database */

assert_may(n, v, o)

char *n, *v, *o;

{

if (may_pos<MAX) {

strcpy(may[may_pos].subject, n);

strcpy(may[may_pos].verb, v);

strcpy(may[may_pos].object, o);

may[may_pos].active=1;

may_pos++;

}

else printf("out of memory ＼n");

}

/* place an entry into the must-have database */

assert_must(n, v, o)

char *n, *v, *o;

{

if (must_pos<MAX) {

strcpy(must[must_pos].subject, n);

strcpy(must[must_pos].verb, v);

strcpy(must[must_pos].object, o);

must_pos++;

}

else printf("out of memory ＼n");

}

/* find an entry in the may-have database */

find_may(n, v, o)

char *n, *v, *o;

{

register int t;

for (t=0; t<may_pos; t++)

if (!strcmp(may[t].subject, n) && !strcmp(may[t].verb, v) && !strcmp(may[t].object, o) && may[t].active)

return;

return -1;

}

/* restrict the description of an object i.e., remove from may-have list and place in must-have list. */

restrict(ms, mv, mo)

char *ms, *mv, *mo;

{

register int t;

char temp[4];

for (t=0; t<3; t++) temp[t]=tolower(mv[t]);

temp[3]='＼0';

if (strcmp(temp, "not")) return;

for (t=0; t<may_pos; t++) {

if (!strcmp(&mv[4], may[t].verb &&

!strcmp(may[t].subject, ma) &&

!strcmp(may[t].object, mo) && may[t].active) {

assert_must(may[t].subject, may[t].verb, may[t].object);

may[t].active=0; /* remove from list */

return ;

}

/* generalize new examples */

generalize(n, v, o)

char *n, *v, *o;

{

register int t, i;

/* check may-have list */

for (t=0; t<may_pos; t++) {

if (strcmp(may[t].subject, n) && /* not same subject */

!strcmp(may[t].verb, v) &&

!strcmp(may[t].object, o) && may[t].active) {

strcat(may[t].subject, " or ");

strcat(may[t].subject, n);

}

for (t=0; t<may_pos; t++) {

if (!strcmp(may[t].subject, n) &&

!strcmp(may[t].verb, v) &&

strcmp(may[t].object, o) && /* not same object */

may[t].active) {

strcat(may[t].subject, " or ");

strcat(may[t].object, o);

}

/* check must-have list */

for (t=0; t<must_pos; t++) {

if (strcmp(must[t].subject, n) && /* not same subject */

!strcmp(must[t].verb, v) &&

!strcmp(must[t].object, o)) {

strcat(must[t].subject, " or ");

strcat(must[t].subject, n);

i=find_may(n, v, o);

may[i].active=0; /* remove from may-have list */

}

for (t=0; t<must_pos; t++) {

if (!strcmp(must[t].subject, n) &&

!strcmp(must[t].verb, v) &&

strcmp(must[t].object, o)) { /* not same object */

strcat(must[t].object, " or ");

strcat(must[t].object, o);

i=find_may(n, v, o);

may[i].active=0; /* remove from may-have list */

}

/* input description */

get_example(n, v, o)

char *n, *v, *o;

{

printf("＼nsubject : ");

gets(n);

if (!*n) return 0;

printf("verb : ");

gets(v);

printf("object : ");

gets(o);

display()

{

int t;

printf("＼nmay have : ＼n");

for (t=0; t<may_pos; t++) {

if (may[t].active)

printf(" %s %s %s ＼n", may[t].subject, may[t].verb, may[t].object);

}

printf("must have : ＼n");

for (t=0; t<must_pos ; t++) {

printf(" %s %s %s ＼n", must[t].subject, must[t].verb, must[t].object);

}

return 1;

}

4.1. 프로그램 사용 (Using the Program)

앞에서 언급했듯이, 이 프로그램은 당신 (교사) 이 컴퓨터 (학생) 을 혼란시키지 않도록 엄밀한 형식 (format) 을 따를 것을 요구한다. 먼저, 모든 묘사는 앞에서 묘사된 subject, verb, object 형식을 따라야 한다. 예를들어, 여기에 몇가지 유효한 묘사가 있다 :

프로그램은 시스템을 혼란시키는 두려움없이 각 부분에 대하여 일련의 단어들을 사용할 수 있도록 subject, verb, object 에 대하여 따로따로 프롬프트를 내보낼 것이다. 주어에 대한 프롬프트에 반응이 없으면 엔트리는 멈춘다.

두 번째, 올바른 예와 near-misses 사이의 차이는 NOT 관계로서 표현되어야 한다. 예를들어, 만약 보기가 빨간색을 갖고 class 묘사가 빨간색을 요구하면, near-miss 는 빨간색을 포함해서는 안된다 : 그러므로, 컴퓨터에서 "빨간 블록은 빨간색이다" 라고 가르치기 위하여, 먼저 "빨간 블록은 빨간색이다" 라고 알릴 수 있으며, 그리고나서, near-miss 에 대하여, "빨간 블록은 빨갛지 않다" 라고 말할 것이다. 이런 식으로, 컴퓨터는 빨간색 (red) 이 빨간 블록의 필요한 속성이라는 것을 알 수 있을 것이다.

프로그램이 실제로 어떻게 작동하는가를 보기 위하여, 이번에는 프로그램을 수행시키고 아래처럼 정보를 입력해야 한다.

(L)earn, (D)isplay, (Q)uit ? L

Enter an example.

subject : block

verb : on top of

object : sides

Enter a near-miss (CR to skip)

subject : block

verb : not on top of

object : sides

Enter an example.

subject : side 1

verb : left of

object : side 2

Enter a near-miss (CR to skip) :

subject : <CR>

Enter an example.

subject : cylinder

verb : on top of

object : sides

Enter a near-miss (CR to skip) :

subject : <CR>

Enter an example.

subject : <CR>

(L)earn, (D)isplay, (Q)uit ? L

Enter an example.

subject : sides

verb : made of

object : wood

Enter a near-miss (CR to skip).

subject : sides

verb : not made of

object : wood

Enter an example.

subject : sides

verb : made of

object : metal

Enter a near-miss (CR to skip)

subject : <CR>

Enter an example.

subject : <CR>

(L)earn, (D)isplay, (Q)uit ? D

may have :

side 1 left fo side 2

must have :

block or cylinder on top of sides

sides made of wood or metal

4.2. 더 개발하기 위한 방향 (Directions for Further Development)

현재 쓰여진 것처럼, 프로그램은 class 내에서 class 를 만들기 위하여 or 리스트 방식을 사용한다. 프로그램이 이러한 이차적 class 에 대하여 기호 이름 (symbolic names) 을 사용하도록 프로그램을 다시 작성하도록 해 보라.

첨가하면 재미있다고 알게 될 또 다른 향성은 must-not-have 관계를 유지하는 세 번째 리스트를 만드는 것이다. 비록 기술적으로 요구되지는 않지만, 이 관계는 교사가 지식베이스에 정보를 넣는 것을 더 쉽게 만들 것이다.

앞에서 언급했듯이, 프로그램을 이 책에서의 예로서 기능을 하도록 짧게 유지하는 것은 엄격한 가르치는 형식 (teaching format) 을 요구한다. 재미있는 변형은 프로그램이 제한이나 일반화를 발견할 수 있는 방법을 확장하는 것이다.

마지막으로, 매우 야망이 있다면, 제 3 장에서 개발된 전문가시스템에서 사용하기 위하여 정보를 모으는 수단으로서 hit-and-near-miss 프로시저를 사용하려고 해야 한다.

이 장을 읽을 때, 기계학습이란, 컴퓨터 프로그래머의 언어에서, "할 수 있는 (do-able) 일이다 라고 생각했을 지도 모른다. 주요 문제는 크기 문제이다 : 단순히 배울 것이 너무 많아서 현대의 컴퓨터 저장 기능과 교사의 인내를 너무 요구한다. 아마도 기계학습은 컴퓨터가 복잡한 자연언어 처리기를 사용하여 혼자서 배울 수 있을 때 더 흔해질 것이다. (이런 일이 이루어진후, 우리는 컴퓨터에게 도서관 열쇠를 주고 - 모든 것을 알 때 되돌아 오게 할 수 있다.)