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

지난 주에 MMIXAL 로 짧으나마 간단한 프로그램을 만들 수 있게 되었으니, 익힌 것을 정리하는 겸 하여 간단한 튜토리얼을 작성했다. Hello World 로 시작하여 기본적인 MMIXAL 명령어들의 사용 예, 숫자<->문자열 변환 함수 작성, 명령줄 입력 처리 등을 더하여 내가 좋아하는 N 번째 피보나치 수를 찾는 프로그램을 만드는 것 까지가 일차 목표이다.

TAOCP::MMIX

• MMIXAL Hello World
• MMIXAL Find Max - MMIXAL 명령어들
• MMIXAL Subroutine - 숫자<->문자열 변환
• MMIXAL Command Line Argument - 명령줄 입력
• MMIXAL Fibonacci - 최종 목표

이렇게 예정하고 있다. 대강 빠르게 작성한 후에 스터디 다른 분들에게 감수를 받으면 될 것 같다.

Stratum protocol

비트코인을 비롯한 여러가지 수학적 화폐들을 획득하기 위해서는 매우 많은(..) 컴퓨팅 파워를 소모해야 한다. 개인 컴퓨터로는 아주 운이 좋지 않은 이상 몇 년 이상 아무 결과도 얻지 못할 정도이다. 그래서 사람들이 컴퓨팅 파워를 모아 공동 마이닝을 하고 얻은 보상을 참여율에 따라 나누는 식으로 풀을 구성하여 조금씩 자주 보상을 얻어가는 전략을 취하고 있다.

공동 코인 마이닝을 위해 고안된 프로토콜이 몇 있는데 stratum 은 그 중 하나로, 사실상 디팩토라고 보아도 무리가 없다. 이 전에 longpoll, getwork 등의 방식도 있었는데 요새 대부분 stratum 으로 대체되거나 프락시가 사용되는 추세이다.

• http://mining.bitcoin.cz/stratum-mining

자세한 설명은 위 링크에 있다. 프로토콜의 전송 레이어는 매우 단순해서,

1. 소켓을 열고
2. 요청을 JSON 형식으로 쏘고
3. 개행문자로 마무리
4. 응답도 JSON + 개행

이렇게 끝난다. 바이너리 인코딩이 없어서 눈으로 바로 읽을 수 있으며, (아마도) 대부분의 언어에서 무리 없이 구현이 가능하다. github 에 예제 구현체도 프로토콜 제안자가 올려 두었다.

• 마이닝 프락시: https://github.com/slush0/stratum-mining-proxy
• 마이닝 풀 데모: http://mining.bitcoin.cz/stratum-mining

일단 프로토콜 제안 문서를 한번 읽어보았다. 아직 모르는 단어가 많아서 정리하긴 어려운데, 다음주에는 stratum 프로토콜을 다른 사람에게 설명할 수 있는 자료를 만드는 것이 목표이다.

MLDSS: Machine Learning In Action 5장

5장은 logsitic regression 을 다루고 있다.

Logistic Regression

피처 벡터의 선형 변환을 Sigmoid 함수에 넣은 후, 0.5를 기점으로 위쪽은 1, 아래쪽은 0 으로 구분한다. 이름에 regression 이 들어가지만 사실은 binary classifier다. x 가 피처벡터, w 가 피처벡터의 선형변환을 나타내는 weights 라고 하면 아래와 같은 식으로 설명할 수 있다.

• $ z = w^{T}x $
• $ h(z) = \frac{1}{1+{e}^{-z}} $
• $ \hat{y} = 1 $ if $ h(z) >= 0.5 $, $ 0 $ otherswise

우리가 알고 싶은 것은, m 개의 트레이닝 데이터가 주어졌을 때 이를 바탕으로 w 를 알아내는 것이다.

Gradient Descent(or Ascent)

해석적으로 Weights 를 구하는 것은 매우 어렵거나, 때로는 불가능하다. 이에 우리는 최적화(Optimization) 기법을 사용하여 원하는 값이나 혹은 근사값을 찾아간다. MIA 05 장에서는 Gradient Descent 를 사용해서 w 벡터를 구하고 있다. 정확히 코드로 표현된 식이 어떻게 나오는지에 대해서는 설명하지 않고 두리뭉실하게 넘어가고 있어서 스터디 당일 이 부분에 대해서 꽤 많은 이야기가 나왔다. 수학에 약한 우리들 ㅠㅠ

우리가 알고싶은 w 라는 미지의 벡터가 있고, w를 인자로 받는 함수가 J 가 있다. J 가 최소값을 가지는 w 를 찾고 싶은데, 함수를 미분해서 감소하는 방향으로 따라가 보자는 것이 기본 컨셉이다. 스텝별로 정리해보면,

1. w 를 파라미터로 받는 Cost Function, J(w) 을 만든다.
2. J(w) 를 w 벡터에 대해 (편)미분한다
3. $ w \leftarrow w - \alpha J’(w) $ 를 반복한다.

산에서 아래로 내려가다보면 언젠가 다 내려갈 수 있겠지, 정도의 아이디어이기 때문에 답이 아닌 곳에 웅덩이(Local minimum)가 있으면 우리의 목적지(Global minimum)에 영영 닿지 못할 수 있다는 위험이 있다. 그래서 이 기법을 쓰는 경우 우리가 탐색하는 공간을 convex 한 공간으로 만들기 위한 트릭을 많이들 쓴다. 그 외의 이 방법의 한계나 특성, 응용 등은 위키피디아와 Scikit-learn 관련 페이지 참조.

책에 나오진 않았지만, 여기서 사용된 Cost Function 은 아마도

$$J(w) = -\frac{1}{m}[\sum\limits_{i=1}^m {y^{(i)}\log(h_{w}(x^{(i)}))+(1-y^{(i)})\log(1-h_{w}(x^{(i)}))]}$$

이것으로 추정된다. 이 함수는 다행히도 convex 라서, gradient descent 로 항상 답을 찾을 수 있다. 자세한건 coursera ml-004 참고. 이 외에 Online learning 을 위한 변형이나 randomized 시도도 있었는데 이런건 그냥 책을 읽으면 된다.

책에서는 logistic regression, gradient descent 를 모두 직접 구현하고 있는데 Scikit Learn 을 사용해서도 해보았다.

from sklearn import linear_model
dataMat, labelMat = loadDataSet()
lrc = linear_model.LogisticRegression(fit_intercept=False,C=1)
lrc.fit(dataMat, labelMat)
w = lrc.coef_
plotBestFit( w[0] )

특히 LogisticRegression 분류기를 만들 때 fit_intercept=False 부분이 있어야 책과 동일한 그래프가 나온다. Scikit learn 레퍼런스를 보면

fit_intercept : bool, default: True

Specifies if a constant (a.k.a. bias or intercept) should be added the decision function.

이렇게 설명하는데, 이미 식($ w_{0} + w_{1}x_{1} + w_{2}x_{2} $)에 constant 가 더해져 있으므로 분류기에서 중복해서 더해주면 안된다.

Coursera Model Thinking

ml-004, comp-004 를 이어서 Model Thinking 을 등록했다. 이번에는 10주짜리 꽤 긴 호흡의 강의다. 이전 두 수업과는 달리 프로그래밍과 직접적으로 관계는 없다. 코스의 목표는 한 마디로, Clear thinker 가 되는 것.

주변에 흔히 볼 수 있는 현상을 받아들일 해석할 때 모델을 만들어 사고하는 것을 배운다.

• Understand class of outcome

  • Equilibrium
  • Cycle
  • Random
  • Complex

• Model type

  • Equation-based model
  • Agent-based model

Schelling’s Segregation model

미국 대도시의 Race, Income 등에 따른 거주지의 분리 경향에 대한 모델을 세우고 NetLogo 로 시뮬레이션을 한다. 상당히 흥미로웠다.

1. 지뢰찾기와 비슷한 Grid 로 공간을 단순화
2. 내 주변에 일정 비율은 나와 비슷한 소득 수준의 이웃이 있기를 원함
3. 2가 만족되지 않으면 이동

이런 모델을 가정한다. 내 주변 8칸 중 3칸 정도면 절반 이하로 나머지는 자신이 원하지 않는 사람이 있을 수도 있으니 이런 조건은 사실 크게 의미없거나 영향이 미미할 것이다 - 라고 생각했다. 하지만 모두가 이런 생각을 하게 되면 임계점이 낮아도 전체적으로는 상당히 강력하게 분리되어 버린다. 더우기, 이 임계점이 높아져 주변 8칸 모두가 나와 같은 소득수준이길 원하게 되면 전혀 특정 상황에 수렴하지 못하고 모두가 대혼란에 빠지게 된다.

이런 Segregation 정도를 측정하는 방법도 언급되었는데, 전체 그룹을 계층으로 분리하고 각 구획별+그룹별 비율의 차를 사용한다. 자세한 내용은 생략한다. …

Peer effect

사람마다 특정 행동을 시작하게 되는 조건, 임계치가 다르다. 특히 다른 사람들이 하면 나도 한다 는 심리가 크게 작용하는 경우가 있다. 예를 들어 어떤 봉사활동 V 를 할까 말까 하는 다섯명 모임 두 개가 있다고 해 보자. 각 사람들에게는 “다른 사람 n 명이 봉사활동을 하면 나도 한다” 라는 n 값이 존재한다. 각 모임에 있는 사람들의 n 값이 아래와 같으면,

• ㄱ 모임: 0 / 1 / 2 / 3 / 4 = average 2.0
• ㄴ 모임: 0 / 0 / 1 / 4 / 4 = average 1.8

어떤 일이 생길까? 다른 사람을 따라가는 심리의 수치 평균은 ㄴ 모임이 낮다. 하지만, ㄱ모임의 5명은 모두 봉사활동을 하는데 반해 ㄴ 모임에서는 3명만 봉사활동을 하게 된다. 이렇게 사람들의 행동 그 자체가 행동의 기제로 작용하는 경우 전체 평균보다는

• Lower threshold
• Higher diversity

가 중요하다. 5.18 이나 4.19 등의 혁명, 혹은 학교에서의 아이들의 단체활동 등에서 자주 확인할 수 있을 것 같다.

Standing ovation

공연을 마치고 일어서서 박수갈채를 보내는 행동을 위의 peer effect 를 가지고 설명하면서, Standing ovation 을 더 많은 사람들에게서 받으려면 어떤 조건을 고려해야 할지를 이야기한다.

공연의 수준이 높아야 한다거나, peer effect 를 일으키기 위한 임계치가 낮아야 한다는 점 이외에도 사람들이 공연을 인지하는 정도의 차이 - variance - 에 대한 통찰이 중요했다. 위의 봉사활동 예에서처럼 사람들이 공연을 느끼는 정도의 variance 가 클수록 standing ovation 이 더 잘 일어날 수 있다.

1. 공연에 다양한 성별/나이/직업/인종의 사람들이 섞이게 하는 것이 유리하다.
2. 공연 자체도 여러가지 해석이 가능한 다면적인 것이 유리할 수 있다.

Peer effect 로부터 이런 이야기를 이끌어낼 수 있다는 것이 매우 재미있다.

Sorting vs Peer effect

Segregation 은 Sorting, Standing ovation 은 Peer effect 이다.

• Sorting: 구성 단위가 조건에 맞추어 자리를 옮기며 패턴을 형성
• Peer effect: 구성 단위가 조건이 갖추어지면 상태를 바꿈

간단하게 이렇게 이해할 수 있다. 예를 들어 어떤 학생 A의 주변을 볼 때,

1. 한달 전에는 흡연자가 A 뿐이었다.
2. 현재 A 주변에는 흡연자가 매우 많아졌다

이런 현상이 관찰되었다고 하자. 이 전/후 상태만으로는 A 주변 친구들이 A 때문에 담배를 피게 되었는지, 아니면 비흡연자 친구들이 떠나고 흡연자 친구들이 A 주변으로 오게 된 것인지 알 수 없다. Sorting, Peer effect 를 구분하기 위해서는 그 전이 과정을 구체적으로 살펴봐야 한다.

강사 말이 좀 빨라서 집중하지 않으면 놓치곤 하는게 좀 문제지만 듣다보면 익숙해지겠지 생각한다 … 안그럼 곤란 일단 첫 퀴즈는 첫 시도에 6.0/6.0 을 받았다. 두번까지 시도 가능하고, 한번에 10분 제한이 있으니 살떨린다. 돈내고 듣는거니 with distinction 까지 받아야 할텐데 앞으로 이렇게 아홉 주를 더 보내야 하다니.

ipython/ijulia notebook

IPython notebook 에서 움직이는 그림을 수 있지 않을까 해서 좀 검색을 해보니 역시나 이것저것 많이 나왔다. 일단 matplotlib 을 1.3.1 로 업그레이드 하고, JSAnimation 을 가져다가 놓았다.

내가 정확히 원하던 것이 2차원 그리드의 변화를 보여주는 것인데(위의 segregation 시뮬레이션을 직접 해서 찍어보고 싶은 것), 마침 위에 링크걸어둔 설명+예제가 GameOfLife를 들고 있으니 코드를 참고하면 될 듯 싶다.

Julia 라는 언어가 있다. 자세히 보진 않았지만 matlab, ipython notebook, R 등과 포지션이 조금 겹치는 것 같다. 살짝 익혀 보기 위해서 개인 서버에서 dgoon/ipy 를 포크해서 dgoon/ij 를 만들고 IJulia Notebook 을 설치해 컨테이너를 띄워 두었다. 일단 기본적인 계산, 그래프 그리기 등이 동작하는 것은 확인했고 이제 튜토리얼을부터 살펴보면 되겠다.