Study 2014/02/16

TSG: TAOCP Vol. 1 MMIX(2014/1Q)

책에 있는 find max 를 이해하고 튜토리얼 두번째 문서를 작성하는 것이 목표였지만 문서는 완성하지 못했다. 스터디에서 falsetru 님과 PUSHJ/POP 동작에 대해서만 한시간 정도 논의하느라 시간을 다 써버렸다. 그나마 PUSHJ/POP 동작은 이해한 것이 수확이라면 수확이다.

MMIX 머신은 적당한(충분한) 크기의 레지스터 스택(Register stack)을 가지고 있다. PUSHJ \$N, Function 명령을 실행하면 현재 로컬 레지스터의 하위 N개(\$0~\$N-1)가 레지스터 스택에 들어가고 접근할 수 없게 된다. 그리고 \$N+1 이 \$0 으로 조정된다. Scope 가 한칸 깊어진다고 볼 수 있다. 여기서 잘 보면 \$N-1, \$N+1 사이에 \$N 이 비게 되는 것을 알 수 있는데, 이 레지스터는 나중에 main return value 를 받기 위한 곳이다.

이렇게 새로 생성된 스코프에서 작업을 하고 나서 원래 문맥으로 돌아가기 위해서 POP M, X 명령을 사용한다. 이 명령을 사용하면 현재 스코프의 \$0 부터 \$M-1 까지 M 개의 값을 반환하고, 원래 돌아가야 하는 주소(rJ)에서 X 개만큼의 명령을 건너뛴 곳으로 돌아간다. (X 는 보통 0 이다) 값의 반환 부분이 중요한데, M 개의 레지스터 중 마지막 레지스터(\$M-1)가 가장 중요하다. POP 이 불린 순간 레지스터 스택에서 이전에 PUSHJ 되었던 레지스터들을 복구하는데, 복구되고 나면 현재 스코프의 \$0 ~ \$M-1 은 복구된 레지스터들과 리턴값을 위해 예약된 레지스터 바로 위쪽에 위치하게 된다. 이 때 \$M-1 레지스터의 값을 반환값을 위해 예약된 레지스터 \$N 에 복사한다.

이렇게 되면

  • PUSHJ \$N, Function: N 개의 로컬 레지스터를 스택에 넣고, \$N 에 Function 의 메인 반환값을 받겠다.
  • POP M, 0: \$M-1 을 메인 반환값으로 사용하고, \$0~\$M-2 는 그대로 유지하고 이전 스코프로 돌아간다.

는 뜻으로 설명할 수 있다. 더 자세히 경우의 수를 나누면 고려할게 많지만, 일단 이렇게 대강만 이해하고 더 자세한 내용은 책이나 문서를 참고하자.

png

MLDSS: Machine Learning In Action 6장

이번주는 MIA 6장 Support Vector Machine(SVM in Wikipedia | SVM in Scikit-learn) 이었다. 수학적 기초가 부족하여 전체적으로 멘붕.

  • SVM은 기본적으로 고차 공간에서 동작하는 이진 분류기다.

  • 트레이닝 데이터를 나누는 Hyperplane 이 가지는 간격이 최대가 되는 방향이 아마도 좋을 것. (Image from Wikipedia)

png

  • 우리가 찾은 Hyperplane 위에 있는 데이터를 Support Vector 라고 한다.

  • CostFunction 은 아래와 같은데, 풀기가 매우 까다롭게 생겼다. 그래서 support vectors 에 대해서 $label(w^{T}x+b)=1$ 이라는 조건을 걸고 ${||w||}^{-1}$ 최대화 문제로 바꾼 후에, 조건 부분을 라그랑주 승수법으로 식에 포함시켜 푼다. (자세한건 이해하지 못했음)

$$ \arg\max_{w,b} (\min_{n}(label \cdot (w^{T}x+b)) \cdot \frac{1}{||w||}) $$

  • 트레이닝 데이터를 임의의 고차 공간으로 보낸 후에 SVM 을 적용하면 non-linear hyperplane 을 얻을 수 있는데, 자주 쓰이는 “임의의 고차 공간으로 보내는 함수” 를 커널이라고 한다. POLY, RBF 등이 있다. 아래 영상으로 컨셉은 한방에 이해가 될… 것 같다.


SVM 모델 학습 과정의 자세한 수학적 내용은 아직 이해가 부족한 상태이다. 공부하다보면 더 알게 되겠지.

Scikit learn 에서는(SVM)아래와 같이 사용한다. Scikit learn 에 있는 Classifier들은 대부분 그냥 fit 만 외우면 쓸 수는 있다. 위의 레퍼런스 링크를 확인하면 알 수 있지만, SVC 분류기 생성자는 여러가지 옵션을 받고 그 중에 kernel 도 있다.

from sklearn import svm
X = [[0, 0], [1, 1]]
y = [0, 1]
clf = svm.SVC()
clf.fit(X, y)

Coursera Model Thinking

Ch 3. Aggregation

“More is different”

우리는 무엇을 aggregate 하는가?

  1. Actions
  2. Single rule
  3. Family of rules
  4. Preference

Aggregate 하면 무엇을 할 수 있는가?

  1. Predict points, Understand data
  2. Understand patterns
  3. Understand class of outcome: Equilibrium, Pattern, Chaotic(random), Complex
  4. Work through logic
Probability distribution

  • Central limit theorem:

    • Decisions which are Independent and Finite variance make bell-shaped curve.
    • If the number of decisions are finite, it is Normal distribution.
    • If Binomial distribution, Mean = pN, stddev = $\sqrt{p(1-p)N}$.
      • p=0.5: Mean = N/2 and stddev = $\frac{\sqrt{N}}{2}$.

우리는 이 중에서도 특히 정규/이항 분포를 주로 고려한다.

  • Standard deviation in Normal/Binomial Distribution

    • N-$\sigma$s can be markers for specific probability points.
    • 항공사의 over booking 등에 이러한 확률 모델이 사용된다.

    • ex) 좌석 380개, 예약한 손님이 실제로 비행기를 탈 확률이 90%이다. 400 개의 좌석을 팔았다. 좌석이 부족할 가능성은?

       N=400, P=0.9, Mean = 400*0.9 = 360, stddev = sqrt(0.9*0.1*400) = 6
 평균 360, 표준편차 6인 분포이다. 380은 360에서 표준편차 3이상 떨어져 있다.
 Right tailed p-value: 0.00135 => 좌석이 부족할 가능성은 0.135% 미만이다.
Game Of Life

간단한 규칙으로부터 여러가지 복잡한 패턴이 발생한다. 그 규칙은:

  1. 지뢰찾기같은 GRID 세상
  2. 셀의 상태는 생존(1), 죽음(0) 두 가지
  3. 주변 8개의 셀 중에 살아있는 셀이 2개 미만이면 중심 셀은 죽는다
  4. 주변 8개의 셀 중에 살아있는 셀이 2개나 3개이고 중심 셀이 살아있다면, 중심 셀은 계속 생존한다.
  5. 주변 8개의 셀 중에 살아있는 셀이 4개 이상이면 중심 셀은 죽는다
  6. 주변 8개의 셀 중에 살아있는 셀이 3개이고 중심 셀이 죽어있다면, 중심 셀은 다음 세대에 살아난다.

아래는 위의 규칙으로 만들어지는 계의 한 예다.

gif

png(Glider) 는 일부(?) 사람들에게 해커의 상징으로도 알려져 있다. http://blog.dgoon.net 파비콘도 이거

Elementary Cellular Automata

위의 Game Of Life 보다 단순한 1차원 오토마타. Stephen Wolfram 이 제안했다.

  1. 월드는 한줄로 늘어선 셀의 벡터
  2. 셀의 상태는 0, 1 두 가지
  3. 셀의 다음 상태는 현재 셀과 양쪽의 이웃, 이렇게 3개의 셀에 의해 결정된다
  4. 3개의 셀이 만들 수 있는 경우의 수 8개 각각에 대해서 다음 상태가 0, 1 중 하나 $\rightarrow$ 가능한 규칙 조합의 총 개수는 $2^8$=256 개.
  5. 모든 규칙에 0부터 255 까지 번호를 붙일 수 있다.

그리고 모든 규칙을 다 테스트 해볼 수 있었다 … 예를 들어 110번 규칙 이라던가.

규칙이 비슷한 수의 on, off 를 포함하고 있을수록 Chaotic, Complex 패턴이 등장하는 빈도가 높다.

It From Bit.
Complexity and Randomness require interdependency.

나름 철학적인 대답이다. 과학적, 공학적으로도 어떤 종류의 통찰을 줄 것만 같다.

Preference Aggregation
  • 개개인의 성향은 이행성(Transitivity)이 있다. (A > B and B > C implies A > C)
  • 이행성이 있는 개개의 성향을 모은 집단 성향은 이행성을 만족함이 보장되지 않는다. (A > B and B > C and C > A can happen)

Condorcet paradox

놀랍지 아니한가. 투표할 때 이상한 일들이 발생하는 것이 바로 이 때문일지도!

Ch 4. Decision Theory

Multi Criterion, Spatial Model
  • Multi Criterion: 비교 대상들의 속성 항목을 정의하고 각 항목별 승점을 weighted sum 하여 최종선택.
  • Spatial Model: 비교 대상들이 위치할 공간을 정의하고, 내가 생각하는 이상적인 포인트를 지정. 이상적인 포인트에 가까울수록 좋은 선택.

자명한 이야기들이다.

Decision Tree and Value of Information

선택이나 결과의 분기가 생길 수 있는 부분을 브랜치로 나누고, 결과의 분기 부분의 확률을 고려하여 선택의 가치를 결정한다.

png

흥미로운 것은 이 방법으로 정보의 가치를 측정할 수 있다는 점. 정보의 가치는 “정보가 없을 때와 있을 때 결정의 가치 차이” 로 정의한다.

그런데, 강의에서 설명하는 자동차 캐시백 문제는 잘 이해가 안된다. 캐시백 가능성을 알더라도 결정의 가치 차이는 없는 것 같은데!? 이건 여기서 좀 더 보고 공부한 다음에 예를 적어봐야겠다.

Comments