형태소분석기

1. 형태소란?

    - 일정한 음성에 일정한 뜻이 결합되어 있는 말의 가장 작은 단위
     즉, 최소의 유의적 단위(minimum meaningful unit) {KimDB90, indirect reference}

2. 형태소 분석이란?

    - 주어진 입력 문장으로부터 최소 의미 단위인 형태소를 추출하는 과정을 말한다.{KimSY87}

3. 형태소 분석기란?

    - 입력을 받아서
   - 어절을 구성하고 있는 각 형태소를 인식하여
   - 관련 정보를 사전으로부터 탐색 및 선정하여
   - 결과를 적절한 구조로 출력시키는 프로그램의 총칭.

4. 형태소 분석기의 부류(classification)?

    - 일반적으로(처리 알고리즘; 특히 한국어에 대해)
       1) two-level
       2) longest matching
       3) shortest matching
       4) head-tail
       5) tabular (CYK)
       6) syllable-based
       7) pattern matching
     이 중 특히 7번은 얼마 전(1993년) 연세대 학생이 발표한 것으로
     corpus를 분석해서 어절의 구성형태를 모두 모아 놓고
     그냥~~~하는 것임.

    - 입력 방식에 따라 나누어진 것은 아직 없음

    - 입력 대상은 현재 특정 분야(sublanguage?)에 한정된 것들

    - 입력 단위
       1) 어절 단위
       2) 문장 단위
       3) 문단 단위
     대부분의 분석기는 문장 단위를 입력으로 하지만
     실제 내용을 살펴 보면 어절 단위를 가정한 것들임

    - 구현 언어
       1) C
       2) Prolog
       3) ?있을까
     완전한 프로그램을 위해서는 역시 C로 짜야겠고
     rapid prototyping을 위해서는 ?

    - 구현 OS and HW
       1) UNIX family -- SUN family
       2) MSDOS -- PC
       3) HangulTalk -- Mac
     외국의 경우 다양한 하드웨어에 실험 및 구현이 되었다고
     들었으나 국내의 경우에는 주로 1)에 대해...

5. 형태소 분석기의 구조

        1) 프로그램 (한글코드; 불규칙/음운현상 처리; 언어)
       2) 입력(interactive from keyboard ...,
               batch)
       3) 출력(stdout, file)
       4) 사전(사전 엔트리 수; 사전 구조)
       5) 기타?

6. 형태소 분석기의 용도?

      어디에 어떻게 쓸 것인가에 따라 형태소 분석기의
     설계 및 구현이 약간씩 달라질 것

7. 해석과 분석의 차이?

    - 영어로 해석은 interpretation; construction(한영 사전 참조)
     예) 문법적 해석: a grammatical interpretation
         잘못 해석하다: misinterprete, misconstrue
   - 분석은 analysis; assaying(한영 사전 참조)
     예) 원소로 분석하다: analyze ~ into its elements
         실패의 원인을 분석하다: analyze the cause of failure

8. 형태소 분석의 목표
   {cite CSLAB1}
   - 입력문에서 형태소 분리
   - 각 형태소간의 결합 관계 밝힘

9. 형태소 분석에서 다루어야 할 현상들
   {cite CSLAB1}
   - 접속 관계 처리(형태소 분리)
   - 불규칙 및 음운 현상 처리
   - 복합어 처리
   - 미등록어 처리

10. 입력 단위
   - 단어
   - 문장
   - 문단
   - 텍스트

11. 내부코드
   - n-byte,
   - 2-byte
   - 3-byte

12. 어절을 벗어난 형태소 분석을 고려
   - 현재까지는 접속정보가 단순히 한 어절 내 형태소간의 관계로 한정되어
     있었다.
   - 어절 내에서 접속정보를 이용, 미등록어 추정 및 적절한 형태소
     결합현상을 인식할 수 있었던 반면
     두 어절이어야 할 어절이 붙여쓰임으로써 한 어절로 된 경우
     이에 대한 처리를 제대로 하지 못한다.
   ==> 이는 "문법적인 접속정보" 즉 구문정보를 현재의 접속정보에 포함
     시킴으로써 가능하다.
   - 이와 반대로 한 어절이어야 할 어절 사이에 공백이 있어 두 어절로
     되어 있는 경우 이를 해결하는 방법은?

13. 처리 방식
   - interactive
   - batch

14. 입력 대상 문자
   - 한글
   - 한자: 한자임을 나타내는 표지(flag 등)와
     한자->한글 변환기 필요
   - 영자
   - 숫자: 숫자의 처리 루틴
   - 문장부호: 문장부호 처리 루틴
     . 특히 쌍으로 나오는 문장부호의 처리 기법
   - 심볼 및 특수문자
   - 사용자 정의 문자

15. 선행 처리기
   {cite CSLAB1}
   - 문서 편집기에 종속적인 요소의 처리(축소, 확대, 특수문자 등)
   - 포매팅 명령어를 무시
   - 쌍으로 이루어진 문자의 처리(괄호, 따옴표 등)
   - 한자를 한글로 치환(한자의 독음 처리)
   - 한자나 영어로 구성된 어절을 별도의 화일에 저장
   - 미완성 한글 검사
   - 도표화 같은 그래픽 문자 처리
   - 맞춤법 검사에서 틀린 것으로 판단된 어절에 대한 사용자 인터페이스
   - 틀린 어절에 대하여 사용자가 원하는 경우 올바른 어절 후보 제시
   - 한글 코드의 변환

16. 형태소에 대한 alternatives가 있을 때(예: 한 형태소가 여러 품사를 가지거나
여러 의미를 가질 때)
   - 형태소간 접속 가능성에 대해 현재와 같이 0/1로 하지 않고
   - weighted connectability information을 부여 <- corpus engineering
   - 그러한 alternative들 간에 priority 또는 weight를 설정 <-- corpus engineering
   - 가능한 형태소 결합열이 둘 이상일 때
     . 모든 가능한 결합열을 생성시키되
     . 결합열 간의 우선순위 계산, 구문 분석시 best-first strategy 사용 가능

17. 형태소간 결합 관계에 정확도(결합의 적합성)에 대한 probability
  또는 likelihoodness를 부여한다면
   - 기존의 접속정보표 수정
   - 접속정보에서 결합 가능성을 검사시에 현재의 True/False의 이진 구조에서
     multi-valued structure로 전환
   - likelihood는 9단계(UNIX Consultant에서 사용한 값과 동일)로 설정
     TRUE -> VERY-LIKELY -> LIKELY -> SOMEWHAT-LIKELY
     -> UNCERTAIN
     -> SOMEWHAT-UNLIKELY -> UNLIKELY -> VERY-UNLIKELY -> FALSE
   - certainty factor들의 combination 방법 필요 [LeeHJ93]
  ==> 1) 다양한 후보 형태소 열 사이의 ranking 가능, reasonable ranking.
     2) 미등록어, 오류 등의 교정시에도 적용 가능

18. 축약현상 및 불규칙 현상의 처리
   - 규칙으로 처리: rule description language + compiler
   - 규칙으로 처리 불가능한 것은 사전에 등록

19. 미등록어의 품사 결정
   - heuristic 정보를 이용
     . 관형사 다음의 형태소는 명사? 등과 같은 ...

20. 사전: 통합 사전
   - 품사 정보
   - 접속 정보
   - 구문 정보
   - 의미 정보

21. 형태소 분석기에는 다음의 모듈이 기본적으로 필요할 것 [LeeMS93]
   - 형태소 결합 테이블 (접속정보표 또는 품사간 결합정보 또는 세분화된
     category들간의 결합 정보)
     . 문제: 어느 정도로 결합 정보가 구체화되어야 하는가
     . 문제: 어떻게 정보를 이해 및 관리가 쉽도록 encoding할 것인가
   - 불규칙 변형 테이블
     . 문제: 불규칙 현상을 어떻게 분류할 것인가 (어학적 측면에서 문법에
             따른 분류에 맞출 것인지, 아니면 보다 상세한 나름대로의
             분류를 정할 것인지)
     . 문제: Procedural vs. Declarative
             .. 장단점의 비교
     . 문제: 어떤, 어느 정도의 방법을 사용하여 over-generation을 최소화
             할 것인가
             .. Lookahead의 숫적 증가 [KimSY87]
             .. 음절 정보의 이용 [KangSS93]
   - 준말 변형 테이블
     . 규칙으로 (procedurally) 처리할 수 있는 것들은 규칙으로
     . 문제: "생각지", "괜찮치" 등의 처리 방법

22. 형태-구문 해석(morphosyntactic analysis) {cite KimDB92}
   - 관용어구 처리
     . 숙어 사전을 이용하거나 숙어 정보가 첨가된 일반 사전을 이용
     . 숙어를 이루는 중심 형태소에 숙어의 가능성이 있다는 정보를 표시
   - 수 표현의 인식
     . 기수인 경우 명사, 형용사, 대명사로 쓰일 수 있음
     . 서수인 경우 형용사, 명사, 부사로 쓰일 수 있음
     . 두 경우 모두 속성값 "FORM {number}"를 준다.

23. 수, 소수, 분수, 년도, 전화번호 등 처리
   - eg. one-eighth --> 1/8

24. 수식의 처리: 숫자와 더불어 사칙연산 기호, 등호, 부등호 등의
   - 수학기호가 연속하여 결합되어 있을 때, 이 형태소들을 하나의
     처리 단위로 결합하여 하나의 수식으로 처리(체언으로?)

25. 단위 명사
   - 숫자와 더불어 단위를 나타내는 명사가 나오면
     두 형태소를 결합하여 하나의 구문 단위로 결합
     eg. 5m 30cm, 10 feet 6 inch, 120 kg 500g, 120.5 kg
   - 복합 단어들을 인식하고 이에 대한 적절한 품사와 약간의 의미 정보를 부가

26. 오류 보정
   - 전거 화일
     . 표준어 규정에 어긋나는 오류
     . 표기법 오류
        .. 한글 맞춤법
        .. 한자 표기
        .. 외래어 표기법
   - 형태소 분석기의 추가적 기능
     . 붙띄 오류: 붙여 써야 할 어절을 띄어 쓰는 오류
       .. 이웃한 두 어절이 모두 어휘 분석 오류 어절인 경우
       .. 앞 어절은 어휘 분석 오류 어절, 뒤 어절은 오류 어절이 아닌 경우
       .. 앞 어절은 오류 어절이 아니고 뒤 어절은 어휘 분석 오류 어절인 경우
     . 띄붙 오류 : 띄어써야 할 어절을 붙여 쓰는 오류
       .. 오류 어절인 경우
       .. 오류 어절이 아닌 경우
   - spell checker 기능
     . 체언 + 조사 오류
       (3) 윗어른을 모시고 사니까 (윗어른 -> 웃어른 : 체언 오류)
       (4) 김정일이가 머리를 짧게 깎으라고 지시를 내려
          (김정일이가 -> 김정일이 : 조사 오류)
       (5) 주의력을 집중하여 열심으로 익혀 왔기 때문에
          (열심으로 -> 열심히 : 체언과 조사의 결합 오류)
     . 어간 + 어미 오류
       (6) 변덕스럽고 괴퍅한 일면은 있지만 (괴퍅한 -> 괴팍한 : 형용사 오류)
       (7) 목을 길게 늘리면 키가 커지고 (늘리면 -> 늘이면 : 동사 오류)
       (8) 목돈을 마련하기에 알맞는 예금 (알맞는 -> 알맞은 : 어미 오류)
       (9) 깨끗하고 아름다와야 할 부엌
          (아름다와야 -> 아름다워야 : 형용사와 어미가 결합하여 발생하는 오류)
       (10) 자유를 향하여 나르는 새
           (나르는 -> 나는 : 동사와 어미가 결합하여 발생하는 오류)

27. 오류의 발견 및 교정 {cite KangSS90}
   - 조사 오류(제3형 오류): 체언과 조사의 결합 정보에 의해 발견 및 교정
   - 어미 오류1(제4형 오류): "알맞는"(-->"알맞은"), "주시구료"(-->"주시구려")처럼
     어미에 오류가 있는 경우. 용언과 어미의 결합 정보나 그릇된 어미 규칙에 의해
     오류 발견 및 교정
   - 어미 오류2(제5형 오류): "들었을라 싶어"(-->"들었을까 싶어")처럼 용언의
     활용어미에 오류가 있는 경우, 용언과 보조용언의 결합시 어미에 대한 제약조건
     규칙에 의해 오류 발견 및 교정.
     한자어의 영향으로 어미가 잘못 쓰인 "조직화한다"(-->"조직한다"),
     "해석되어진다"(-->"해석된다")와 같은 오류도 여기에 속한다.
   - 어간 변형 오류1(제6형 오류): "아름다와야"(-->"아름다워야"), "낯설은"(-->"낯선")
     과 같이 불규칙 용언의 변형 부분이 잘못된 경우. 그릇된 변형 규칙과 불규칙
     동사의 어간 변형 규칙에 의해 발견 및 교정
   - 어간 변형 오류2(제7형 오류): "믿기지"(--> "믿어지지")와 같이 용언의 피동형이
     잘못된 오류. 용언의 피동형 정보에 의해 오류 발견 및 교정.
   - 어간 변형 오류3(제8형 오류): 용언 + 어미 + 보조동사 형태로 용언의 어미와
     보조동사가 서로 어울리지 않는 경우.(예: "끼어 주다" --> "끼워 주다").
     모든 동사와 보조동사의 결합 정보 필요

28. 품사의 애매성 해소 방법   {cite KimDB92}
   "...지금까지 연구된 품사의 애매성 해소 방법은 크게 통계적인
   방법과 규칙 기반형(rule-based) 방법이 있다
   (1) 통계적인 방법은 대량의 코퍼스로부터 품사의 애매성 해소를 하는 데 필요한 정보를
       객관적으로 구하고 이를 쉽게 이용할 수 있는 방법을 제공한다.
       Church가 제안한 방법은 .. 어휘적 확률(lexical probabilities: 코퍼스에서 어떤
       단어에 대하여 특정 품사가 나올 확률 P(tag | word))와 문맥적 확률(contextual
       probabilities: 코퍼스에서 어떤 단어의 특정 품사가 그 단어 다음에 나오는 단어들의
       특정 품사들과 함께 나올 수 있는 확률 P(tag1 | tag2 tag3))의 곱을 최대로 하는 쪽으로
       품사를 지정한다. 이러한 방법의 정확율은 95% 이상을 보장한다.
   (2) 규칙 기반형 방법은 언어학적인 현상에 바탕을 두어 문제의 해결을 시도한다.
       이 방법은 통계적인 방법에서의 필수적인 요소라 할 수 있는 코퍼스가 없이도
       직관적으로 규칙을 만들 수 있고, 통계적인 방법에서 범하기 쉬운 오류(국부적인
       정보만을 이용하므로써 일어나는 오류)의 가능성을 거의 없앨 수 있는 장점이
       있지만, 도메인에 의존하는 경향이 상당히 높고, 수천 개의 규칙들을 가지고
       행하는 것이 보통이기 때문에 규칙들 사이의 제어가 복잡하고, 또 정확율도
       통계적인 방법에 비해 낮다는 단점을 지니고 있다. 그러나, 최근에 Marcus(1991)가
       제안한 방법은 상당히 객관적인 방법에 의해 규칙을 구할 뿐만 아니라 그 규칙
       수도 상당히 작고, 정확율도 95% 정도까지 나온다...두 방법 모두 기본적으로
       대량의 태깅된 코퍼스를 필요로 한다. 또 .. LDOCE(Longman Dictionary of
       Contemporary English)와 같은 전자 사전을 이용하지 않으며 단지 약간의
       접사 테이블과 단어와 품사의 쌍으로 된 테이블만을 이용한다. 이러한 테이블들은
       품사의 애매성을 해소하는데 없어서는 안될 정보, 즉 한 단어가 특정 품사로
       쓰일 확률(lexical probabilities) 정보와 한 단어가 가질 수 있는 품사들에 관한
       정보를 준다. 따라서, 전자 사전을 이용하는 기계번역과 같은 응용분야에서 이
       두 방법을 적용하기 위해서는 한 단어가 특정 품사로 쓰일 수 있는 확률을
       사전에 두어야 한다. 그 이유는 보통의 전자사전은 한 단어에 대해서 자주 쓰이는
       품사와 아주 드물게 쓰이는 품사의 구분이 없기 때문이다."

29. 사전

    - 요구사항
     . 형태소, 구문, 의미 정보
     . 모든 단어를 포함?
     . 범용적 구조 vs. 특정 응용에 맞게 customized?
     . knowledge base와의 연관 관계
     . 일반 용어와 전문 용어의 구분?
   - 분석과 생성에 bidirectional?
   - knowledge base
     . appropriate representation
     . grouping/navigating, etc.
   - cooccurrence db?
     . 단어 사용 정보
   - corpus
     . tagged (lexical, syntactic, semantic)
     . standard format
   - dictionary management utility
     . 저장 및 검색
     . 표준 format
     . converting format
     . browse editor
     . extraction/merge
     . user interface

30. 형태소 분석기의 성능 평가

    1) 속도(speed)

      가) 일반사항
         - 모든 alternatives를 찾아내고
         - alternatives의 ranking까지 할 때
           . 사전 구조 및 access 과정에 따라 달라지고
           . hardware speed에 따라 달라지므로
         - timer를 이용하여 CPU time을 측정하는 방법에는 무리가 있고
         - 알고리즘의 best, average, worst case performance에서
           order of time을 고려할 수밖에 없을 것
         - 현재 제안된 기능을 수행하는 해석기의 경우 O(n**3)??
     나) 하나의 방법
         - 가정A: hardware platform은 4-8MB memory와 충분한 HD space를 가진
                  33MHz 486DX
         - 가정B:
           . 한 단어가 평균 2.5개의 형태소로 되어 있고
           . string의 평균 길이가 8 바이트 정도이며
           . 불규칙 및 음운 현상 검사, 사전 검색 횟수 등이 한 단어당
             평균 1.5회인 경우를 가정하면
         - 사전 검색은 단어당 10회 정도
         - 알고리즘 수행 시간은 negligible??
         - 단어당 시간은 <사전 access time> * 10회 + alpha
         - 초당 10-20 개 정도의 입력 단어 처리, 이를 화일에 출력까지 하는 정도의 성능이면?

    2) 정확도
         - speller 측면에서는 100%를 달성하기는 불가능
         - 형태소 분석기 자체에서 오류가 없는 입력을 가정할 경우 100% 가능
           단, 사전에 해당 형태소 및 관련 정보가 모두 등록되어 있는 경우를 전제
         - 각종 format 변환 등 선행 및 후행 처리기 부분에 대한 기준은 별도 고려 필요

    3) 성능 평가 방법

      가) 일반사항
         test와 examination을 병행
         - test: sample data로부터 주어진 성능 규격을 만족하는지 검사
         - examination: hardware/software 환경, 기타 inspection 수행
     나) test 방법
         1) 단어(word) 단위 성능 평가
            . corpus: 표준어 규정/맞춤법 규정 등에 있는 모든 단어 예를 수집
            . 초기 : 95% 정도의 정확도
            . 최종 : 100%의 정확도
         2) 구(phrase) 단위의 성능 평가
            . corpus : 보조 용언 리스트 및 관용어구 리스트 등
            . 초기 : 95% 정도의 정확도
            . 최종 : 98-100% 의 정확도
            . 단, 띄어쓰기 등 여러가지 오류를 배제한 상황을 전제
         3) 문장(sentence) 이상 단위의 성능 평가
            . corpus:
              .. 신문 사설 00건
              .. 국민학교, 중학교, 고등학교 교과서 00건
              .. 대학교 작문 교재에 실려 있는 (대표적인) 소설 및 수필 00건
              .. 각 분야별 학술지 (컴퓨터, 산업공학, 경제, 법률, 무역, ... 등)는
                 사전 엔트리의 성격에 따라 선별 사용

이 글은 스프링노트에서 작성되었습니다.

유전자 알고리즘

유전자 알고리즘 - Genetic Algorithms

 

 개요 ( What are Genetic Algorithms? )

유전자 알고리즘(Genetic Algorithm, GA)은 적자 생존과 유전의 메카니즘을 바탕으로 하는 탐색 알고리즘이다. 다시 말해 주어진 환경에 잘 적응하는 유전자만을 selection)하고 교배(crossover)하고 때에 따라서는 돌연변이(mutation)도 하며 다음 세대에 우수한 유전 형질이 전달(reproduction)되게 된다. 따라서 진화(evolution)가 거듭될수록 주어진 환경에 더 적합한 유전자들만이 남아있게 될 것이다.

유전자 알고리즘은 미시간대학의 홀랜드(John Holland)에 의해 탄생하였으며. 당시 연구원들의 연구 목표는

[1] 자연시스템의 적응적 과정을 추상화시키며 철저하게 분석하여,
[2] 그러한 시스템을 소프트웨어적으로 디자인하는 것이었다.

유전자 알고리즘(GA)은 그러한 배경에서 만들어졌으며, 근본적으로 다른 탐색이나 최적화 알고리즘과는 세 가지 정도가 다르다.

[1] GA는 하나의 개체(변수 등)가 아닌 개체들의 군(pool) 단위로 탐색한다.
[2] GA는 적합성 함수(fitness function)를 사용한다.
[3] GA는 확률적인 변이 규칙을 사용한다.

간단한 예를 들어보자. f(x) = x2[0 ≤ x ≤ 31] 이라는 환경이 있으며, 환경에 살아가는 개체(유전자)가 x인 셈이다. 그리고 환경에 잘 적응하는 정도를 함수값으로 정의하자. 그러므로 x = 0이라는 개체보다 x = 4라는 개체가 f(x) = x2[0 ≤ x ≤ 4]라는 환경에서 더 잘 적응하는 것이다.

환경	: f(x) = x2[0 ≤ x ≤ 31]
개체	: 0 ≤ x ≤ 31
적합성(fitness)	: f(x)

01101
11000
01000
10011

위의 네 개체가 오손도손(^_^) 살고 있는 군(집단)에서 과연 f(x) = x2이라는 환경에서 누가 더 잘 적응할 것으로 생각되는가? 위의 이진수를 십진수로 바꾸어 생각하면 쉽게 알 수 있다. 위의 예에서 01000은 살기 어렵고, 11000은 그나마 가장 잘 적응할 것이다. 그러므로 다음 세대에서는 01000은 도태를 하고, 11000은 자손을 생산하게 된다. 이와 같은 과정을 거친 먼 훗날의 개체는 바로 11111이라는 개체가 탄생할 것이고, 이 넘(^_^)이 바로 주어진 환경을 지배할 것이다.

11111
11111
11111
11111

군(pool)이 위와 같은 개체(gene)로 구성되었을 때 '환경에 적응하였다'라고 말한다. 또는 '해를 찾았다'라고 말하기도 한다. 이와 같이 유전자 알고리즘은 자연의 적자 생존 원칙에 기반을 하고 있는 탐색 알고리즘이다. 다음 내용에서는 유전자 알고리즘의 단계별 과정들인 재생산(reproduction), 교배(crossover), 돌연변이(mutation)들을 알아보겠다.
--------------------

유전자 알고리즘에서의 개체 재생산

유전자 알고리즘은 기본적으로 세 가지의 연산자(operator)로 구성된다. [1] 재생산(reproduction) [2] 교배(Crossover) [3] 돌연변이(Mutation) 이번 내용에서는 재생산이라는 연산자(operator)에 대해 알아보자. 근데 operator를 연산자라고 번역하니까 좀 이상하군요.(^_^)  개요 유전자 알고리즘에서 재생산(reproduction)이란 적합함수(fitness function)에 따라서 개체들을 복사하는 과정이다. 쉽게 말해서 개체들이 속해 있는 군에서 잘난 넘(nom?)은 다음 세대를 더 많이 생산할 수 있는 기회를 주고, 물론 못난 놈은 자기와 닮은 개체를 생산할 수가 없어 그 형질이 다음 세대에 전달되지 않는다. 그렇다면 과연, 우수 형질의 개체를 어느 정도 개체를 생산할 수 있고, 열등 형질은 무조건 없어져야 하는가? 그렇지만은 않다. 왜냐면 열등 형질도 부분적으로는 우수 형질의 기질을 가지고 있기 때문이다. 따라서 유전자 알고리즘에서는 어떤 개체에게 어느 정도의 우수성을 부여하고 어떤 방식으로 재생산이 행해지느냐는 중요한 요소이다. 무작정 우수 형질의 개체를 재생산하다보면 전체 해(global point)를 찾지 못할 가능성도 커진다. 결론적으로 우수 형질의 개체 생산과 열등 형질의 개체 생산비율을 적절히 설정할 필요가 있다. 이를 실현하는 데 있어 유전자 알고리즘에서 기본적으로 roulette wheel이라는 확률개념을 사용한다. 지금은 많이 사라졌지만, roulette wheel을 돌려서 뽑기하는 장사를 기억할 것이다. 원판(roulette wheel을 원판이라 번역, ^_^)에서 할당된 영역이 넓으면 그만큼 걸릴 확률이 많은 것이다. 우수 형질은 그만큼 원판에서의 면적 할당이 넓게 함으로써 다음 세대의 개체 생산의 가능성을 크게 하는 것이다. 아래 그림을 보면 이해가 될 것이다. 군(pool)에 개체들이 있고, 그 개체들은 우수 정도에 따라 영역을 할당받는다. 우수 개체는 아래 그림에서 (2) 영역을 할당받을 것이고, 열등 형질은 (1) 영역을 할당받을 것이다. 이제 재생산의 남은 과정은 원판을 돌리고 화살만 쏘면 되는 것이다. 걸리면 살아남는 개체가 되는 것이다. 냉혹함이 숨겨져 있는 알고리즘이다. 그림. 유전자 알고리즘에서의 재생산(Reproduction)  예제(example) f(x) = x2이라는 환경에서 살아가는 개체가 시간 t일 때 01101 11000 01000 10011 와 같이 네 개체만이 있다면 개체들의 적합도(fitness)와 전체에 대한 우수성의 비율을 아래 표에 나타내었다. No. 개체 Fitness % of Total 1 01101 169 14.4 2 11000 576 49.2 3 01000 64 5.5 4 10011 361 30.9 Total   1170 100.0 표. f(x) = x2에서의 개체와 적합함수(fitness function) 원판위에 적합함수(fitness function)에 따라 다음 세대에서의 생존 가능성을 그리면 앞의 원판 그림이다. No. 2라는 개체가 f(x) = x2이라는 환경에서는 가장 잘 적응되고 원판에서도 가장 넓은 영역을 차지하고 있다. 따라서 다음 세대를 재생산(reproduction) 하기 위해 화살을 네 번 쏜다면, No. 2라는 개체는 살아남아서 다음 단계인 교배(crossover)를 할 가능성이 가장 높다. 이상으로 roulette wheel이라는 확률 기반의 재생산(reporduction) 방법에 대해 알아보았다. 다음은 교배(crossover)에 대해 알아볼 차례다. 교배는 실제 재생산된 개체들끼리의 연산으로 좀 더 나은 개체를 발생시키고자 하는 데 목적이 있다. 유전자 알고리즘은 재생산(reproduction), 교배(crossover), 돌연변이(mutation)에 대해서 확실히 알면 그 다음은 그것들의 응용이다. -------------------------------------------------- 교배와 돌연변이    교배(crossover) 개체의 진화는 물론 돌연변이에 의해, 확률적으로 적지만, 발생할 수도 있지만, 주로 개체들끼리의 교배(crossover)에 의해 발생한다. 교배(crossover) 연산자는 개체들끼리 유전자 배열을 섞는 과정이다. 자연 환경에 대한 인간들의 적응도 근본적으로는 교배, 즉 성 관계를 통하여 이루어졌다. 유전자 알고리즘(GA)에서 교배는 두 단계로 구성된다. [1] 교배대상의 개체(들)를 선택한다. ( 하나 혹은 2개 이상의 개체 ) [2] 유전자 배열 중의 임의의 위치 k를 선택하고, 개체들간의 유전자 배열을 바꾼다.(swap) 아래 그림은 두 개체(01101, 11001)간의 교배를 나타낸 것이다. 너무나도 간단하다! 하지만 교배 연산을 통해 개체군(pool)이 세대가 지날수록 환경에 적응하는 개체들이 늘어나게 된다. 그림. 교배(crossover) 과정  돌연변이(mutation) 교배는 개체군 내에서의 개체 진화에 한계가 존재한다. 다시 말해, 주어진 환경에 어느 한계까지는 진화하여 적응할 수 있지만, 개체군내의 개체의 유전자 schema를 극복할 수 없다. 예를 들어 11110 11100 두 개체가 아무리 교배를 한다하더라도 11111이라는 개체는 생길 수가 없다. 이를 보완하기 위해 돌연변이(mutation) 연산자를 사용한다. 돌연변이(mutation)은 유전자 배열 중의 유전자(gene)를 바꾸는 연산자이다. 하지만 돌연변이가 발생하는 확률을 너무 높게 설정하면 무작위 탐색이 될 수 있기에, 적절한 돌연변이의 발생이 요구된다. ( 일반적으로, 돌연변이 발생 확률 = 0.01 ) 그림. 돌연변이(mutation) 이상으로 유전자 알고리즘의 기본적인 연산자에 대하여 알아보았다. 재생산(reproduction), 교배(crossover), 돌연변이(mutation)이라는 기본적인 연산자를 이용하여 개체군 내에서의 개체를 변화시켜며, 또 적응해가도록 하며, 그러한 연산자는 다윈의 자연 선택(natural selection)의 원칙을 그 모델로 삼고 있다. 유전자 알고리즘에서의 스키마(schema) 이론 이해    스키마 이론(schema theorem) 유전자 알고리즘의 세 연산자(operator)인 재생산(reproduction), 교배(crossover), 돌연변이(mutation)은 너무나 간단하다. 결국 n개의 문자열(strings, 개체)로 구성되어 있는 개체군(population)에서 적합 함수(fitness function)에 따라 몇 개의 개체를 선택하고, 몇 개의 부분 문자열을 바꿈으로써 교배를 시키고, 확률에 따라서 돌연변이를 발생함으로써 환경에 진화하는 것이다. 간단하지만 수학적 근거가 없었다면 끝났다면, 아마도 유전자 알고리즘이 이처럼 유용한 알고리즘이 되지는 못하였을 것이다. 위의 방법론은 누구나가 제시할 수 있지만, 수학적 근거를 제시하기는 쉽지만은 않다. 이런 점에서 스키마 이론은 유전자 알고리즘의 수학적 배경을 제시한다는 점에서 유전자 알고리즘의 근본되는 이론이라 할 수 있다. 원서(참조)에서는 스키마 이론을 'The fundamental theorem'이라고 말하고 있다. 먼저 스키마가 무엇인지를 언급하고, 그 스키마가 환경에 적응하는 정도를 제시함으로써, 그 스키마에 속하는 개체들의 적응력(?)도 그 스키마의 적응력과 결국 같은 것이기 때문에, 유전자 알고리즘이 무작위 탐색과는 다르다라는 것을 말하고자 한다.  스키마타(schemata) f(x) = x2이라는 환경에서 아래와 같은 개체군이 존재한다고 가정하자. 01101 11000 01000 10011 이 예제에서는 0**** 보다는 1**** (* = 0 or 1)의 형태를 띠는 개체들이 더 높은 적합 함수값을 가진다. 일반적으로 환경을 모르더라도 개체들의 유전자 구성에 따른 일정한 법칙이나 배열규칙에 따라 적합 함수값이 비슷한 값들을 알 수 있다. 다시 말해, 개체의 특정한 유전자 배열 규칙이 개체의 우수성을 지니게 하는 하는 것이다. 스키마는 0****, 또는 1****처럼 표현한 것을 말하고 스키마의 복수가 스키마타이다. 0**** = 01101, 01000 1**** = 11000, 10011 을 각각 표현하는 것이다. 예제처럼개체군내에서 부분 개체 집단의 일반적 적합성을 표현하는 데 있어 *(0 or 1) 이란 기호를 사용하여 스키마타(schemata)를 사용한다. 스키마타의 적합 함수값은 그 스키마타로 표현되는 개체들의 평균 적합함수값으로 표현된다. 개체군에 대단히 많은 개체들이 존재한다고 가정하자. 각각의 개체들은 유전자 알고리즘의 연산자에 따라 선택되고, 교배되고, 돌연변이 하면서 적응을 하겠지만, 겉으로 드러나지 않은 어떤 법칙에 따라 유전자 배열이 주어진 개체들만이 적응을 하게 되고, 그 드러나지 않는 공통적 법칙이 스키마타로 표현이 될지도 모른다. 스키마타는 개체들의 부분군을 대표하며, 또한 개체들의 병렬적 처리라고 생각하면 된다. 이해가 되었으리라 생각되지만 또 하나의 인간군을 예를 들어보자. 스키마타는 집단의 대표자라고 할 수 있다. 집단의 대표자는 그 집단의 평균적 우수성을 지니고 있다고 가정하자. 집단 A와 집단 B가 있을 경우, 집단 A의 대표자가 집단 B의 대표자보다 우수하면 집단 A는 적응하고, 집단 B는 도퇴하는 것이다. 각각의 개체 각각의 적합성보다는 집단 대표자의 적합성을 보고 그 개체들의 적합성을 추측하는 것이다. 그만큼 처리속도(적응하는 데 소요되는 시간)가 빨라 질 수 있다. 스키마타를 이용한 환경에 대한 개체 적응은 [1] 처리 속도를 올릴 수 있지만 [2] 반면, 열등 부분 집합에 속해있는 우수 개체를 도퇴시킬 수 있다는 부작용(side effect)도 존재한다.  Order, Length의 개념 먼저 정의부터 확인해보자. order라는 것을 우리말로 번역하면 이상할 것 같아 원어 그대로 사용한다. 스키마 H에 대하여 order와 definig length의 정의는 아래와 같다. 정의 표기 설명 order ο(H) H의 유전자 구성에서 고정된 위치의 갯수 length δ(H) H의 고정된 위치에서 처음과 끝의 거리 예를 들어, 스키마 H = 011*1** 인 경우 ο(H) = 4, δ(H)= 5-1 = 4이다. 위와 같은 order와 length는 스키마에서 어떤 의미를 지니고 있는 것인가? 우선 '스키마타가 생존한다'라는 의미부터 정확히 알아야 될 것 같다. 특정 스키마 H가 교배나 돌연변이를 하여도 그 스키마가 생존한다는 의미는 소속집단(?)이 바뀌지 않는다는 말로 이해하면 될 것이다. 아래 그림을 보자. 그림. 스키마(schema) 생존의 의미 그림에서 스키마 H1과 H2 가 개체 A와 교배(crossover)를 하였다고 가정하면, 교배의 결과 스키마 H1C는 H1의 배열 규칙을 벗어나게 되고 H2C는 H2의 규칙에서 벗어나지 않고 다만 좀 더 한정적인 스키마가 될 뿐이다. 생존의 의미는 바로 규칙에서 벗어나지 않음을 의미한다. 그럼 스키마가 생존할 확률(survival probability, SP)은 어떻게 표현될 수 있을까? 바로 order와 length가 밀접한 관계가 있다. length가 짧을수록 그만큼 교배후에도 스키마가 생존할 확률이 크고, order가 작을수록 돌연변이 이후에도 스키마가 생존할 확률이 크다. 즉, SP(H) ∝ (1 - c1 * ο(H) - c2 * δ(H)) 단, c1 = f(pc, t) , c2 = f(pm), pc : prob. of crossover, pm : prob. of mutation, t : total length of schema (ex. 0**011 = 6) 위의 개념을 바탕으로 스키마 이론(schema theorem)을 적어보면 - Schema theorem is fundamental theorem 와 같다. 위의 식을 풀어쓰면, '주어진 환경에 적응하는 스키마는 기하급수적으로 증가하며, length가 짧을수록, order가 작을수록 더 빠르게 증가한다.' 라는 것을 말한다. 물론 적응하지 못하는 스키마는 기하급수적으로 감소한다라는 것도 뜻한다. 쉽게 말하면, 유전자 알고리즘의 탐색 능력은 단순한 무작위 탐색과는 비교가 안된다라는 것을 수학적으로 증명한 이론이 스키마 이론(schema theorem)이다.

죄수의 딜레마(prisoner's dilemma)

배신과 협력의 게임(1라운드의 죄수의 딜레마) 물주(게임 진행자) 한 명과 두 사람이 게임을 한다. 게임을 하는 두 사람의 손에는 '협력'과 '배신'의 카드 2장이 있으며 단 1라운드만 진행이 된다. 카드의 조합은 아래 표의 네 가지가 되며, 각각의 경우에서 이득과 손해는 아래와 같다.   A가 선택한 카드 B가 선택한 카드   협력 배신 협력 보수 (상호 협력에 대한) 예) 300달러 매우 나쁨 매우 나쁨 예) 100달러 징수 배신 매우 좋음 유혹료 (배신으로) 예) 500 달러 꽤 나쁨 벌금 (상호 배신에 대한) 예) 10 달러 징수 표1. '협력'과 '배신'의 이득과 손해 가령 위의 예에서 상호 협력의 카드를 제출할 때는 상호 협력에 대한 보상으로 물주로부터 300달러를 받는 것이다. 이 때 배신에 대한 유혹료는 상호 협력의 보수보다 높아야 하고, 상호 협력의 보수는 상호 배신의 벌금보다는 좋아야 한다. 이 밖에 여러 가지 설정이 있지만 생략한다. 그럼 왜 '딜레마'일까? 누구든 낼 수 있는 카드는 '협력'과 '배신'이라는 카드 2장 밖에 없다. 만일 A가 '배신'을 냈다면 B는 최선의 카드로 '배신'을 내야 할 것이다. 만일 '협력'의 카드를 낸다면 B는 100 달러를 게임 진행자에게 줘야 한다. A가 '협력'의 카드를 냈을 경우에도 당신이 얻을 수 있는 최대의 이득은 '배신'의 카드를 내는 것이고 그 때 유혹료로 500달러를 얻을 것이다. 결론은 타인이 어느 카드를 내든 상관없이 당신의 최선 행동은 '항상' 배신이라는 것이다. 그러므로 두 사람의 이성적인 경기자가 만나면 모두 배신하여 같이 벌금 또는 운 좋으면 유혹료를 받게 될 것으로 끝난다. 두 사람 모두 만일 쌍방이 '협력'만을 낸다면 상호 협력으로 비교적 높은 보수를 받을 것을 확실히 알고 있다. 하지만 '배신'의 카드를 내는 것이 최선의 행동이라는 것이다. 쌍방이 서로 연락하거나 정보를 주고 받을 수 있다면, 서로 연락해서 '협력'의 카드를 제출하겠지만, 그렇지 않을 경우에는 '배신'을 하는 것이 합리적인 게임 진행이 될 것이다. 그러니 딜레마인 것이다. 딜레마 (dilemma) ①(논리학) ＝양도 논법(兩刀論法). ②선택해야 하는 길은 2개뿐인데 그 어느 쪽도 바람직하지 못한 결과를 초래하는 상황.  반복 죄수의 딜레마 '죄수'란 하나의 특별한 상징적인 예에서 유래한다. 이 경우는 돈이 아닌 죄수의 형기이다. 가령 A군과 B군이 자신들이 저지른 범죄 때문에 공범 혐의로 투옥되어 있다. 그 죄수들은 각각 독방 속에서 공범자에 대한 불리한 증언을 함으로써 동료를 배신하도록 유혹당했다. 처분은 두 사람의 죄수가 어떻게 하는가에 따라 결정되며, 어느 쪽도 상대가 어떻게 했는지 모른다. 만일 각각이 배신하면 양자 모두 죄가 인정되나 증거를 제공한 점으로 약간의 신용을 얻어 어느 정도 경감된 형기, 즉 상호 배신의 벌을 받게 된다. 만일 양자가 협력하여 증언을 거부하면 유죄가 될 충분한 증거가 없으므로 보다 경미한 죄로 짧은 형기, 즉 상호 협력의 보수를 받는다. '지불'이 돈이 아니라 형기였지만 이 게임을 기본적 특징이 보전되어 있는 것을 느낄 것이다. 1라운드의 게임에서는 상호 배신으로 끝나게 될 운명이 되고 만다. 그러나 그것이 '반복'된다면 그 때에도 '배신'을 할 것인지 생각해보자. 반복 게임은 동일한 경기자에 의해 제한없이 반복되어 행해질 뿐만 아니라 또한 두 사람은 서로 바라보고 있으며 그 사이에는 게임 진행자(판사)가 앉아 있다. 두 사람은 두 카드의 어느 한쪽을 냄으로써 승부를 내고 게임 진행자(판사)는 먼저 제시한 규칙에 따라 형기를 결정한다. 이제는 1 라운드의 게임으로 끝나는 대신에 우리는 또 다시 카드를 집어서 다음의 승부에 대비한다. ( 이와 같은 반복은 두 사람이 반복적으로 공범자로 잡힌다고 가정하면 간단히 설명된다. 단 서로의 연락은 되지 않는다.) 몇 번 승부를 계속하는 사이에 두 사람에게는 신용, 또는 불신이 쌓여 협력 또는 배신을 할 수 있는 기회가 주어진다. 제한없이 긴 게임에서 중요한 점은 서로가 손해를 볼 것 없이 쌍방이 협력의 보수를 받을 수가 있다는 것이다.  전략 과연 위와 같은 게임을 할 경우 어떤 전략을 가진 자가 장기적으로 승리를 거둘 수 있을 것인가를 생각해보자. 몇 개의 교묘한 전략이 가능하나 승리를 거든 전략은 놀랍게도 가장 단순하고 표현적으로는 모든 것 중에서 가장 교묘함이 부족했다. 그것은 '당하면 갚는다(tit for tat)'라는 전략으로 불렸고 최초의 카드는 협력으로 시작하고 그 이후는 단순히 바로 전에 상대가 낸 카드를 흉내내는 것뿐이다. 즉, 상대가 배신을 하면 내가 배신을 하는 것이다. 다음은 '소박한 시험꾼(naive prober)'으로 '당하면 갚는다'와 같으나 10회중에 1회는 함부로 이유없이 배신하여 유혹료로서 높은 득점을 기대하는 전략이다. 그리고 '원한파'는 한번 상대방이 배신하면 끝까지 배신하는 전략이고, '항상 배신은 항상 배신만 하는 전략이다. 그 밖에 수많은 전략들이 생겨날 수 있어 이 게임의 다양성은 증가된다. 다음은 대표적 전략들을 간략히 설명한 표이다. 유형 전략 이름 전략 마음씨 좋은 (nice) 항상 협력 항상 협력의 카드만 제시 두 발에 한발 갚기. 최초 협력, 상대방이 두 번 연속 배신을 하면 배신 당하면 갚는다. (tit for tat) 최초의 카드는 협력으로 시작, 상대가 배신을 하면 내가 배신 원한파 최초 협력, 상대가 한번 배신하면 계속 배신 간악 항상 배신 항상 배신 소박한 시험꾼 (naive prober) 최초 협력, 가끔 배신 표2. 죄수의 딜레마에서 대표적인 전략 이러한 게임을 '액셀로드'라는 사람이 전략을 하나의 공통 프로그램 언어로 번역하여 대형 컴퓨터로 서로 대전시켰다. 각각의 전략은 다른 모든 전략과 순차적으로 짝지어져서 반복 죄수의 딜레마 게임을 하는 것이다. 액셀로드가 인정하고 있는 가장 중요한 범주는 '마음씨 좋은(nice)'이다. 마음씨 좋은 전략은 최초로 배신하는 일이 결코 없는 것으로 정의된다. '당하면 갚는다 (tit for tat)' 가 그 일례이다. 소박한 시험꾼은 때때로 배신을 하므로 간악한 전략이다. 토너먼트에 참가한 15개의 전략 중 득점이 높은 쪽부터 상위 8위까지 모두 8개의 '마음씨 좋은(nice)' 전략이 차지하고 있다는 사실이 의미 깊다고 할 수 있다.  관용 전략이란 것은 보복하는 일은 있으나 단기의 기억밖에 없다. 그것은 오래된 나쁜 일을 바로 잊어버린다. '당하면 갚는다(tit for tat)'는 하나의 관용 전략이다. 배신자에 대해 즉시 한 때 보복으로 갚고 그 후에는 과거를 씻듯이 잊는다. 하지만 원한파는 절대로 용서하지 않는다. 그 기억은 게임의 전기간을 통해 지속된다. 한 번이라도 자기에게 배신한 적이 있는 상대에 대한 원한을 결코 잊지 않는다. 원한파와 같은 전략이 프리드만(friedman)이라는 호칭으로 대전이 되었지만 게임 성적이 별로 좋지 않다. 우리는 승리하는 전략에 두 가지 특징이 있다는 것을 상정할 수 있다. 즉 '마음씨 좋기'와 관용함이다. 다시 말해, 처음부터 배신하지 않는 전략과 단기의 기억밖에 없는 관용 전략이 그것이다. 거의 유토피아적인 경향의 이 결론은 '마음씨 좋은 사람이 성공한다' 라는 문구와 비슷한 의미를 담고 있다. 윤리가 논리로써 이끌어지는 순간이다. 위와 같은 전략은 평균적이고 반복적인 전략끼리의 대전이며, 여기가 중요한 사실은 그러한 전략의 성공은 어떤 전략이 서로 대전하는가에 달려 있다라는 것이다. 다시 말해 다른 모든 전략이 '항상 배신'이면 '마음씨 좋은' 전략이 당하기만 한다. 그러므로 '최초 구성이 어떤 전략으로 구성되었는가' 라는 요소와 전략들의 구성 비율도 각각의 전략에 대한 성공, 실패에 대한 영향을 미친다.  ESS(Evolutionarily stable strategy, ESS) 위에서 언급한 것처럼 각 전략의 순위는 어떤 전략이 제출되었는가에 의존한다. 가령 대부분의 전략이 간악한 것이었다면 '당하는 갚는다'는 이기지 못 했을 것이다. 바꾸어 말하면 전략의 순위가 인간의 불안정하고 자의적인 것에 의존하고 있다. ( 인간이 어떤 전략을 대전시키느냐에 따라 전략의 순위가 결정될 수 있다.) 이 자의성을 어떻게 하면 줄일 수 있을 것인가? 그것은 ESS로 해결될 수 있다. ESS라는 메이나드-스미스가 제창하고 있는 중요한 개념은 '진화적으로 안정된 전략'이라는 불리는 것이며, 여기서 전략이라는 것은 미리 프로그램되어 있는 행동 방침이다. 쉽게 말하면, 정확치는 않지만 각각의 전략을 이루는 제 1세대를 만들고, 유전자 알고리즘으로 세대를 거쳐가면서 최종적으로 살아남는 전략들이 ESS가 될 수 있다. 액셀로드는 63개의 전략을 취하여 그것을 또 다시 컴퓨터에 입력해서 그것들을 제 1세대로 만들었다. 따라서 제 1세대의 풍토는 63개의 모두의 전략을 균등히 대표하는 것으로 되어 있었다. 제 1세대의 끝에 각 전략의 승자는 돈이나 득점이 아닌 그의 부모와 동일한 전략을 취하는 후손의 수로 지불된다. 세대가 진행함에 따라 어떤 전략은 수가 적어져서 최종적으로는 절멸한다. 다른 전략은 점점 수가 많아진다. 따라서 그 비율이 변함에 따라 전략들의 대전이 일어나는 풍토(전략들의 구성 비율)도 변한 것이다. 대전의 결과는 몇 개의 전략은 최초부터 절멸로 향하고 대부분은 200세대에 가서야 절멸한다. 재미난 사실은 해링턴(Harrington)이라 불리는 간악한 전략은 최초의 150세대쯤 급격하게 상승했다. 그것은 '두 발에 한발 갚기' 등의 연약한 상대가 주위에 있는 한은 그들을 착취했다. 그 후 연약한 상대가 절멸 당하게 되면 '해링턴(Harrington)'은 그들만의 포획물이 없게 되어 그들의 뒤를 쫓아 절멸하게 됐다. 싸움터는 '당하면 갚는다'처럼 마음씨 좋은 전략의 독무대로 됐다. 진화가 거듭되어 모든 간악한 전략이 절멸에 임박하게 되면 아무리 마음씨 좋은 다른(두 발에 한발 갚기) 전략도 '당하면 갚는다(tit for tat)'와 서로 상호간에 구별하는 방법이 없어지게 된다. 왜냐하면 그것들은 모두 마음씨가 좋기 때문에 서로 협력의 카드를 내놓기 때문이다. 이런 최종적인 전략들의 구성은 ESS와 닮았지만 엄밀하게는 ESS가 아니라는 것이다. 어떤 전략이 ESS가 되려면, 그것이 희소한 돌연변이의 전략에 변경되어서는 안 된다는 것을 생각해 주기 바란다. 프로그램적인 ESS는 마음씨 좋은 전략이 우세를 점하지만, 거의 무조건인 마음씨 좋은 전략( 두발에 한발 갚기, 세발에 한발 갚기 등) 이 숨어 있게 되어, 간악한 전략의 침입에 쉽게 변할 수 있기 때문에 액설로드는 다음과 같은 결론을 내린다. "아마도 조금 간악한 전략과 마음씨 좋은 매우 관용한 전략과 그리고 당하면 갚는다(tit for tat)와의 전략들의 혼합으로 ESS가 구성된다" 그런 전략들이 구성된 ESS는 어떤 다른 전략이 들어와도 ESS가 쉽게 변하지 않음을 알 수 있다. 다시 말해 전략들의 진화가 안정화되었다고 볼 수 있다. 최종적인 진화 상태임을 암시한다. 이것이 인간 생활에 흔한 양상을 반영하는 거울임을 알 수 있다. 즉, 어느 정도의 간악한 사람과 '당하면 갚는다(tit for tat)'와 같은 전략을 가진 사람들이 이 세상에 우세한 이유도 죄수의 딜레마라는 게임에서 유추할 수 있다. 여기서 제 나름대로의 재미난 결론은 가장 이상적인 전략은 '당하면 갚는다(tit for tat)'이라는 전략이다. 한번 상대방이 배신을 하면 바로 배신을 하는 전략이 우리의 인생을 최소의 실패율을 가져다 줄 수 있는 전략이라는 것이다. 두 번을 참아서도 안 된다. 오직 한번만이 참을 뿐이다. 대신 관용을 유지해야 한다. 상대방의 잘못은 단기 기억으로 잊어버린다. 이제부터는 이것을 내 인생 전략으로 삼을까 싶다. ㅋㅋㅋ

유전자 알고리즘의 개요

2. GA의 구조및 요소 위에서 설명한 GA의 절차를 정리하면 다음과 같다. t : 세대 P(t) : t 세대의 모집단 GeneticAlgorithm { t = 0; initialize P(t); // 모집단 생성및 초기화 evaluate P(t); // 평가 while(종료조건이 만족되지 않으면) { t = t + 1; select P(t) from P(t-1); // 새로운 새대 선별 alter P(t); // 유전연산(교차,돌연변이) evaluate P(t); // 적응도 평가 } } 특정 문제를 해결하기 위한 GA를 구현하기 위해서는 다음 5가지의 요소가 결정되어야 한다. 1) 표현(representation) : 문제의 해를 개체로 표현하는 방법, 2) 초기모집단(initial population) : 초기모집단을 형성하는 방법, 3) 평가함수(evaluation function) : 개체의 적응도(fitness)를 평가하는 함수, 4) 유전연산자(genetic operators) : 자손 개체를 생산하기 위한 유전연산자, 5) 유전파라미터(genectic parameters) : 모집단의 크기, 각 유전연산의 적용확률 등). 3. 빌딩블럭 가설(building block hypothesis) GA의 가장 중요한 개념이며, 알고리즘 구현의 핵심인 빌딩블럭 가설에 대해 살펴보자. A genetic algorithm seeks near-optimal performance through the juxtaposition of short, low-order, high performance schemata, called the building blocks.[1] GA는 빌딩블럭의 병렬적 결합을 통하여 해를 탐색한다. 빌딩블럭은 짧고 고정인자 갯수가 적은 우수한 스키마(정현철님의 글 참조)를 말한다. 스키마는 개체의 특성을 결정하는 유전 형질로 볼 수 있다. 짧고 고정인자 수가 적은 스키마는 유전연산에 의해 잘 파괴되지 않고 계속 다음 세대의 개체로 유전될 수 있으며, 우수한 스키마를 가진 개체는 살아 남아 다음 세대의 생산에 참여하게 된다. GA는 우수한 개체(해)를 탐색하는 알고리즘이 아니다. GA는 다양한 형질들을 만들어내고, 여러 세대의 재생산과 유전연산을 통하여 개체의 특성을 결정하는 우수한 형질들을 자연스럽게(?) 추출하고, 이들의 병렬적인 결합을 시도해 보는 알고리즘이다. 따라서 GA의 구현에 있어서, 가장 먼저 고려해야 할 것은 개체의 특성을 결정짓는 유전 형질을 어떻게 표현할 것인가 하는 것이다. 해의 정보라고 할 수 있는 유전 형질의 추출이 용이한 표현 방법을 선택해야 한다. 또한 다양한 형질들을 만들어 낼 수 있고, 유전 형질을 크게 파괴하지 않는 유전연산자가 만들어져야 한다. 전통적인 GA에서는 2진 형태로 개체를 표현하기 때문에 short, low-order schemata가 빌딩블럭의 조건을 만족하였지만, 많은 문제에서 2진 형태로 해를 표현하기 어렵다. 2진 형태의 표현이 아니라면, 그에 맞는 빌딩블럭이 정의되어야 할 것이다. 이것이 GA의 구현에 있어서 핵심이라고 할 수 있다. 1. 유전알고리즘(Genetic Algorithm :GA) GA는 생태계의 진화과정, 즉 자연선별(natural selection)과 유전법칙을 모방한 확률적 최적해 탐색 기법이다. GA는 1975년 J. Holland의 논문 "Adaptation in Natural and Artificial Systems" 에서 처음 소개되었다. GA에서는 해결하고자 하는 문제의 해가 DNA형태의 개체(individual, string, chromosome, genome)로 표현(representation)된다. GA에서는 여러 개체로 이루어진 모집단(population)을 운용하여 최적해를 탐색한다. 매 세대마다 모집단의 각 개체들의 적응도(fitness)가 평가(evaluation)되고, 이를 기준으로 운 좋은 개체들은 자연 선별(natural selection)되고, 다음 세대를 생산할 행운(?)을 획득한 개체들은 서로 결합하여 서로의 유전형질이 교차(crossover)된 새로운 자손 개체(offspring)을 생산한다. 또한 주어진 확률로 개체의 특정 인자(gene)에 돌연변이(mutation)가 발생되어 유전형질에 변화가 일어난다. 이러한 과정 속에서 세대교체(replacement)가 이루어지고 새롭게 탄생한 개체들은 다시 평가된다. 이러한 과정이 특정 조건이 만족될 때가지 계속되어 모집단의 개체들은 진화한다.

이 글은 스프링노트에서 작성되었습니다.

라이센스 종류

BSD License

버클리 소프트웨어 배포 라이센스입니다. 진정한 의미에서의 Free가 어울리는 오픈소스 라이센스로, 소스 사용에 대한 어떠한 제약도 없습니다. 소스 수정 및 재배포, 바이너리 제품판매 등에 대해서도 아무런 제약이 없습니다. 소스 공개에 대한 조건도 없습니다. 한마디로 BSD로 배포되는 소스 및 바이너리에 대해서는 완벽한 자유가 보장된다고 보시면 됩니다.
예전에는 제작자의 이름을 명시하는 것이 요구되었으나, 프로젝트가 장기화, 거대화 되면서 이름이 엄청나게 길어지면서 그 조항도 현재는 없어졌습니다.
대표적으로 BSD계열의 유사 유닉스와 아파치 계열 라이센스가 있으며, 아파치 라이센스는 거의 동일한 내용입니다.

GPL(General Public License)

유명한 리쳐드 스톨만이 만든 오픈소스 라이센스입니다. 여러가지 복잡한 내용이 있지만, 요약하면 자유롭게 소스를 사용하고 배포하되 GNU GPL라이센스 조항을 반드시 포함해야 하며, 해당 소스를 사용해서 만든 것은 GPL을 따라야 하며 소스배포를 강요하게 됩니다.
이 조항들이 적용되는 범위가 상당히 넓은데다, 실질적으로 상용 라이센스로서의 의미를 가지기 힘들기 때문에 소프트웨어 제조사에서는 사용을 기피하는 편입니다. 레드햇 등의 유명 리눅스 제조사가 OS를 무료로 배포하고 서비스로 수익을 얻는 구조를 가지는가의 이유이기도 합니다.
기본적으로 이상적으로 봐서는 모든 소프트웨어가 GPL을 따르면 누구나 우수하고 좋은 프로그램을 무료로 쓸 수 있을 것 같지만, 반대로 수익 모델이 그렇게 매력적이지 못하기 때문에 회사들에게서 전폭적 지지를 받지는 못할 라이센스가 아닌가 생각됩니다.(우리나라 회사들도 GPL에 데어서 벌금 낸 회사가 부지기수입니다)
한마디로 무료로 받아서 무료로 배포하는 것이 전제라 하겠습니다.
대표적인 프로젝트로 리눅스와 GNU툴들이 있겠습니다.

모질라 라이센스(MPL)

불여우로 유명한 모질라 재단의 라이센스로, GPL과 비슷하지만 GPL이 너무 강성 노선이라면 MPL은 조금 그 영역을 좁혀서 소스 코드의 공개는 강제하되, 바이너리의 상용화 및 비공개에 대해서 보장하기 때문에 GPL에 비해서는 그 활용 영역이 넓다 하겠습니다. 즉 GPL과 달리, MPL을 따르는 프로젝트의 소스를 얻어 그 소스의 특정 부분을 변경하여 상용 프로젝트를 만들었다면, 해당 소스의 변경점을 공개하고 바뀐 부분을 알려야 하지만, 결과물에 대해서 상용화 및 소유권을 인정하는 형태입니다.
GPL과 BSD를 잘 섞은 듯한 느낌의 라이센스입니다.

LGPL(Lesser GPL)

GPL이 앞서 얘기했듯 GPL과 관계되면 모두 GPL을 따라야 하다보니 사람들이 오픈소스 진영을 제외하고는 기피하는 경향이 강했기 때문에, 그 상황을 호전시키기 위해서 나온 것으로, 라이브러리 등을 LGPL을 따르게 하면 해당 라이센스를 따르는 라이브러리를 상용 및 다른 라이센스와 연계해 사용하고 배포하는 것이 가능합니다. GPL과 마찬가지로 배포시 해당 라이브러리가 LGPL을 따른다는 것을 알리는 내용을 첨부해야 하며 해당 라이브러리를 수정 및 재배포시 소스를 공개하고 LGPL을 따라야 합니다. (해당 모듈 및 라이브러리만)
FFMPEG등에서 사용되고 있으며, FFMPEG가 사용된 곰플레이어 등은 상용소프트웨어임을 생각하시면 이해가 쉽겠습니다.

이 글은 스프링노트에서 작성되었습니다.

Viterbi Algorithm

Viterbi Algorithm

 

Viterbi algorithm definition

1. Formal definition of algorithm

The algorithm may be summarised formally as:

For each i,, i = 1, ... , n, let :

 

 

 

- this intialises the probability calculations by taking the product of the intitial hidden state probabilities with the associated observation probabilities.

 

For t = 2, ..., T, and i = 1, ... , n let :

 

 

 

- thus determining the most probable route to the next state, and remembering how to get there. This is done by considering all products of transition probabilities with the maximal probabilities already derived for the preceding step. The largest such is remembered, together with what provoked it.

 

Let :

 

 

- thus determining which state at system completion (t=T) is the most probable.

 

For t = T - 1, ..., 1

Let :

 

 

- thus backtracking through the trellis, following the most probable route. On completion, the sequence i₁ ... i_T will hold the most probable sequence of hidden states for the observation sequence in hand.

 

2. Calculating individual 's and 's

The calculation of 's is similar to the calculation of partial probability ('s) in the forward algorithm. Compare this diagram showing 's and 's being calculated with the diagram at the end of section 2under the forward algorithm.

 

 

The only difference is that the summation (  ) in the forward algorithm is replaced with max to calculate the 's - this important difference picks out the most likely route to the current position, rather than the total probability. We also, for the Viterbi algorithm remember the best route to the current position by maintaining a `back-pointer', via the argmax calculation of the 's.

 

 

Finding most probable sequence of hidden states

We often wish to take a particular HMM, and determine from an observation sequence the most likely sequence of underlying hidden states that might have generated it.

1. Exhaustive search for a solution

We can use a picture of the execution trellis to visualise the relationship between states and observations.

We can find the most probable sequence of hidden states by listing all possible sequences of hidden states and finding the probability of the observed sequence for each of the combinations. The most probable sequence of hidden states is that combination that maximises

 

Pr(observed sequence | hidden state combination).

 

For example, for the observation sequence in the trellis shown, the most probable sequence of hidden states is the sequence that maximises :

 

Pr(dry,damp,soggy | sunny,sunny,sunny), Pr(dry,damp,soggy | sunny,sunny,cloudy), Pr(dry,damp,soggy | sunny,sunny,rainy), . . . . Pr(dry,damp,soggy | rainy,rainy,rainy)

 

This approach is viable, but to find the most probable sequence by exhaustively calculating each combination is computationally expensive. As with the forward algorithm, we can use the time invariance of the probabilities to reduce the complexity of the calculation.

 

2. Reducing complexity using recursion

We will consider recursively finding the most probable sequence of hidden states given an observation sequence and a HMM. We will first define the partial probability , which is the probability of reaching a particular intermediate state in the trellis. We then show how these partial probabilities are calculated at t=1 and at t=n (> 1).

 

These partial probabilities differ from those calculated in the forward algorithm since they represent the probability of the most probable path to a state at time t, and not a total.

2a. Partial probabilities ( 's) and partial best paths

Consider the trellis below showing the states and first order transitions for the observation sequence dry,damp,soggy;

For each intermediate and terminating state in the trellis there is a most probable path to that state. So, for example, each of the three states at t = 3 will have a most probable path to it, perhaps like this;

We will call these paths partial best paths. Each of these partial best paths has an associated probability, the partial probability or . Unlike the partial probabilities in the forward algorithm,  is the probablity of the one (most probable) path to the state.

 

Thus  (i,t) is the maximum probability of all sequences ending at state i at time t, and the partial best path is the sequence which achieves this maximal probability. Such a probability (and partial path) exists for each possible value of i and t.

In particular, each state at time t = T will have a partial probability and a partial best path. We find the overall best path by choosing the state with the maximum partial probability and choosing its partial best path.

2b. Calculating  's at time t = 1

We calculate the  partial probabilities as the most probable route to our current position (given particular knowledge such as observation and probabilities of the previous state). When t = 1 the most probable path to a state does not sensibly exist; however we use the probability of being in that state given t = 1 and the observable state k1 ; i.e.

 

 

- as in the forward algorithm, this quantity is compounded by the appropriate observation probability.

2c. Calculating  's at time t ( > 1 )

We now show that the partial probabilities  at time t can be calculated in terms of the 's at time t-1.

Consider the trellis below :

We consider calculating the most probable path to the state X at time t; this path to X will have to pass through one of the states A, B or C at time (t-1).

Therefore the most probable path to X will be one of

 

 

	(sequence of states), . . ., A, X
	(sequence of states), . . ., B, X
or	(sequence of states), . . ., C, X

 

 

We want to find the path ending AX, BX or CX which has the maximum probability.

 

Recall that the Markov assumption says that the probability of a state occurring given a previous state sequence depends only on the previous n states. In particular, with a first order Markov assumption, the probability of X occurring after a sequence depends only on the previous state, i.e.

Pr (most probable path to A) . Pr (X | A) . Pr (observation | X)

 

Following this, the most probable path ending AX will be the most probable path to A followed by X. Similarly, the probability of this path will be

Pr (most probable path to A) . Pr (X | A) . Pr (observation | X)

So, the probability of the most probable path to X is :

where the first term is given by  at t-1, the second by the transition probabilities and the third by the observation probabilities.

Generalising the above expression, the probability of the partial best path to a state i at time t when the observation kt is seen, is :

Here, we are assuming knowledge of the previous state, using the transition probabilites and multiplying by the appropriate observation probability. We then select the maximum such.

2d. Back pointers, 's

Consider the trellis

At each intermediate and end state we know the partial probability,  (i,t). However the aim is to find the most probable sequence of states through the trellis given an observation sequence - therefore we need some way of remembering the partial best paths through the trellis.

Recall that to calculate the partial probability,  at time t we only need the 's for time t-1. Having calculated this partial probability, it is thus possible to record which preceding state was the one to generate (i,t) - that is, in what state the system must have been at time t-1 if it is to arrive optimally at state i at time t. This recording (remembering) is done by holding for each state a back pointer  which points to the predecessor that optimally provokes the current state.

 

Formally, we can write

 

 

 

Here, the argmax operator selects the index j which maximises the bracketed expression.

Notice that this expression is calculated from the 's of the preceding time step and the transition probabilites, and does not include the obervation probability (unlike the calculation of the 's themselves). This is because we want these 's to answer the question `If I am here, by what route is it most likely I arrived?' - this question relates to the hidden states, and therefore confusing factors due to the observations can be overlooked.

2e. Advantages of the approach

Using the Viterbi algorithm to decode an observation sequence carries two important advantages:

 

1. There is a reduction in computational complexity by using the recursion - this argument is exactly analogous to that used in justifying the forward algorithm.

1. The Viterbi algorithm has the very useful property of providing the best interpretation given the entire context of the observations. An alternative to it might be, for example, to decide on the execution sequence

    

   

   where

    

   

   Here, decisions are taken about a likely interpretation in a `left-to-right' manner, with an interpretaion being guessed given an interpretation of the preceding stage (with initialisation from the  vector).

   
   This approach, in the event of a noise garble half way through the sequence, will wander away from the correct answer.

    

   Conversely, the Viterbi algorithm will look at the whole sequence before deciding on the most likely final state, and then `backtracking' through the  pointers to indicate how it might have arisen. This is very useful in `reading through' isolated noise garbles, which are very common in live data.

3. Section Summary

The Viterbi algorithm provides a computationally efficient way of analysing observations of HMMs to recapture the most likely underlying state sequence. It exploits recursion to reduce comuputational load, and uses the context of the entire sequence to make judgements, thereby allowing good analysis of noise.

 

In use, the algorithm proceeds through an execution trellis calculating a partial probability for each cell, together with a back-pointer indicating how that cell could most probably be reached. On completion, the most likely final state is taken as correct, and the path to it traced back to t=1 via the back pointers.

 

 

출처:> http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/viterbi_algorithm/s1_pg1.html

이 글은 스프링노트에서 작성되었습니다.