DNA Implementation of Version Space Learning

Version Space Learning? Concept Learning 건물 내의 각 office를 돌아다니면서 recycling bin을 수거하는 로봇이 다음의 concept를 학습하고자 할 때… “An office that has recycling bins?” 주어진 concept를 다음에 주어진 attribute들을 이용하여 conjunction form으로 표현할 수 있다고 가정 Dept, {ee, cs} Status,{faculty, staff} Floor, {four, five}

예를 들어 5층에 있는 cs department의 faculty office  <cs, faculty, five> 4층에 있는 staff의 office  <?, staff, four> 그리고 주어지는 example 또한 위의 attribute들의 conjunction form으로 표현 된다. 이진 분류 : (+) or (-) Version space learning의 목적은 위와 같이 표현 가능한 concept 가운데 학습 데이터와 모순되지 않는 것을 찾아내는 것!  탐색문제

DNA Implementation 그러나 가능한 가설 공간의 크기는 exponential하므로 기존의 전자식 컴퓨터로는 실제 구현이 불가능 DNA 분자들을 이용하여 가설공간 전체를 표현하여, 초기의 전체 가설 공간에서 주어지는 example과 모순되는 가설들을 제거해 나간다. Concept 한 개  한 종류의 DNA 분자

cs faculty four <cs, faculty, four> cs ?status four <cs, ?status, four>

실험 과정 TUBE1  Initial Global Hypotheses Positive example? New Example TUBE2  All Hypotheses that classify the new example as positive TUBE1  TUBE1 ∩ TUBE2 TUBE1  TUBE1 - TUBE2 YES NO Repeat for every example

전체 가설 공간 생성 TUBE1(0) faculty four cs cs’ faculty’ four’ ee staff five ?dept ?dept’ ?status ?status’ ?floor ?floor’ Double strand에서 한쪽 single strand만 골라냄 TUBE1(0)

교집합 & 차집합(1) 교집합 현재 TUBE1에 들어있는 가설 가운데 각각의 attribute 값으로 Don’t care symbol을 갖거나, 입력으로 들어온 example의 attribute 값을 갖는 가설만 골라낸다. 예) <cs, faculty, four>의 경우 1.TUBE1 에서 ‘cs’나 ‘?dept’를 가진 것들만 취한다. 2. 1의 결과물에서 ‘faculty’나 ‘?status’를 가진 것들만 취한다. 3. 2의 결과물에서 ‘four’나 ‘?floor’를 가진 것들만 취한다. 이상의 과정에서 남은 결과물이 교집합의 결과이다.

교집합 & 차집합(2) 교집합 현재 TUBE1에 들어있는 가설 가운데 각각의 attribute 값으로, Don’t care symbol이나 입력으로 들어온 example의 attribute 값 이외의 값을 포함하고 있는 가설만 골라낸다. 예) <cs, faculty, four>의 경우 TUBE1에서 ‘faculty’ or ‘staff’ or ‘five’를 포함하고 있는 가설들만을 골라낸다.

교집합 & 차집합(3) 특징 장점 단점 실제로 TUBE2를 생성해 내지 않고 다만 BEAD를 이용하여 동일한 효과를 낸다. 매 example마다 consistent한 hypotheses들을 새로 만들 필요가 없다. Bead를 사용하여 각각의 attribute단위로 실험하므로 실험의 정확도를 높일 수 있다. 단점 교집합 연산에서 attribute 종류 수 만큼의 단계를 거쳐야 하므로 attribute의 종류가 많아질 경우 실험이 번거로워 진다.

교집합 & 차집합(4) 참고 A, B TUBE1 ee ?status, faculty TUBE1 ∩ TUBE2 ?floor, four ?dept, cs TUBE1 - TUBE2 staff five 차집합 연산을 수행할 때 교집합 연산에서 수행되고 남은 결과를 취하지 않고 다시 한번 나머지 attribute 값으로 걸러내는 이유는 실험의 정확도를 위함이다. A, B A나 B를 포함하고 있는 것 A와 B가운데 어느 것도 가지고 있지 않은 것 참고