MLDSS: Tree-based regression, Machine Learning in Action 9장

이 앞 장, Linear Regression 에서는 데이터를 설명하는 (Weight vector 에 대한) 1차식으로 모델을 만드는 Regression(Locally Weighted Linear Regression 은 빼고)을 공부했다. 하지만 세상은 그리 호락호락하지 않아 이것만으로 표현하기 힘든 데이터가 많이 있다. 이 장에서는 트리에 기반한 Regression 방법을 알아본다. Linear Regression 보다 만들어진 모델을 해석하기는 어렵지만 보다 복잡한 데이터를 다룰 수 있다.

먼저 설명하는 CART는 Top 10 algorithms in data mining 중 하나로 당당히 이름을 올려놓고 있다.

CART(Classification And Regression Tree)

트리 노드는 다음의 4개를 들고 있다.

• Feature: 이 노드에서 데이터를 오른쪽/왼쪽으로 쪼개는데 사용된 피처
• Value: 위 피처의 값
• Right: 위 피처로 쪼개진 오른쪽 트리. 쪼개지 않는다면 값 하나.
• Left: 위 피처로 쪼개진 왼쪽 트리. 쪼개지 않는다면 값 하나.

노드 구성이 말해주듯 CART는 언제나 Binary split 으로 데이터를 나눈다. 어떤 피처 의 어떤 값을 사용해서 오른쪽 왼쪽으로 나눌 것인가? 만 정해지면 구현은 자명하다. Split 을 결정하는 데에는 2가지 파라미터를 사용한다.

1. TolS: Tolerance for error
2. TolN: Tolerance for number of item

아래는 스플릿을 찾는 함수 chooseBestSplit 의 개략적인 설명이다.

For every feature:
    For every unique value:
        Split the data in two
        Measure the error of the two splits
        If the error is less than best_erro so far -> Update best_error
If best_error is less than TolS:
    return Leaf node
If one of two splits with best_error has fewer items than TolN
    return Leaf node
Ok, we found best split!

Leaf Node 의 값은 포함된 모든 노드의 평균으로, 에러는 Squared Error 를 사용한다.

Predict with Regression Tree

Feature vector 가 주어졌을 때 어떻게 결과값을 예측할까? 입력 피처 벡터로 트리의 스플릿을 따라 Leaf node 까지 가서 거기 있는 값을 쓰면 된다. 책에도 뒤쪽에 코드가 있긴 하지만(195p, treeForeCast) 거기까지 읽기 전에 해보고 싶어서 그냥 만들었다. 아래 테스트는 책의 ex0.txt 를 사용한 값이다.

def predictWithRegressionTree(tree, feat):
    if not isinstance(tree, dict):
        return tree
    feat_index = tree['spInd']
    v = feat[feat_index]
    sv = tree['spVal'].getA1()[0]
    if v>sv:
        return predictWithTree(tree['left'], feat)
    if v<=sv:
        return predictWithTree(tree['right'], feat)
print(predictWithTree(tree1, [1, 0.5]))
print(predictWithTree(tree1, [1, 0.0]))
print(predictWithTree(mytree, [0.3]))
print(predictWithTree(mytree, [0.8]))1
-----
1.98003507143
-0.0238381555556
-0.0446502857143
1.01809676724

Model Tree

CART 와 단 한가지만 빼고 똑같다.

Leaf Node 에서 평균 대신 Linear Model 을 만든다.

그래서 이름도 Model Tree. 당연히 Predict 도 Leaf Node 의 값을 쓰는게 아니라 Leaf Node 에 가서 거기 있는 지역 모델에 피처를 집어넣어 예측하는 것이다. 이 앞 장인 Linear Regression 을 잘 읽었다면 위의 CART 를 Model Tree 로 수정하는 것은 별로 어렵지 않다.

Scikit-learn

• http://scikit-learn.org/stable/modules/tree.html#tree-algorithms-id3-c4-5-c5-0-and-cart

링크한 문단의 가장 아래 문장을 보자.

scikit-learn uses an optimised version of the CART algorithm.

라고 한다. Model Tree 는 없음. DecisionTreeRegressor 에 ex0.txt 을 넣으면 아래와 같은 값을 내뱉는다.

from sklearn.tree import DecisionTreeRegressor

# Ok, DecisionTreeRegressor in sklearn is same as what we coded justago.
regressor = DecisionTreeRegressor(max_depth=1)
regressor.fit(myMat[:, 0], myMat[:, 1])
print(regressor.predict([0.3]))
print(regressor.predict([0.8]))

regressor = DecisionTreeRegressor()
regressor.fit(myMat[:, 0], myMat[:, 1])
print(regressor.predict([0.3]))
print(regressor.predict([0.8]))
-----
[-0.04465029]
[ 1.01809677]
[ 0.317135]
[ 0.924033]

max_depth=1 을 넣었을 때 위의 predictWithRegressionTree 함수로 테스트 한 경우와 정확히 같은 값이 나온다.

Pruning

해봤자 별로 좋아지지 않는다고 한다. 자세한 내용은 생략 …

P.S.책의 Figure 9.2 의 두번째 그래프는 거짓말이다. 저렇게 안나온다.

TSG: MMIX 1.4.1 Subroutines (1)

이번주는 1.4.1 Subroutines 부분을 읽었다.

• Subroutines are used to save space in a program.
• They make it easier to visualize the structure of a large and complex program
• They form a logical segmentation of the entire problem -> Easier debugging

책에서는 서브루틴을 사용하는 두 가지 방법을 설명하고 있다.

1. GO
2. PUSHJ/POP

그리고 MMIXAL 이 제공하는 서브루틴 사용을 도와주는 명령 세 개가 있다.

1. PREFIX
2. LOCAL
3. BSPEC .. ESPEC

시간이 부족하여 PREFIX, LOCAL, BSPEC .. ESPEC 은 다 읽지 못한 관계로 다음 주에 정리한다.

GO

GO $X,$Y,$Z

\$X 에 바로 다음 명령의 주소(@+4)를 저장하고 \$Y+\$Z 로 날아간다. \$X 에 Return address 가 저장되는 것.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

     LOC  Data_Segment
     GREG @
kk   GREG
txt  BYTE "Hello world!",10,0

     LOC #100
     GREG @
Sub1 LDA $255,txt
     TRAP 0,Fputs,StdOut
     GO $0,$0,0

Main GO $0,Sub1
     LDA $255,txt
     TRAP 0,Fputs,StdOut
     TRAP 0,Halt,0

위 예제 코드는 \$0 에 돌아올 주소를 저장하여 Main->Sub1->Main 이렇게 이동한다. 한 가지 주의할 점은 Sub1 이 Main 뒤에 나오면 위 코드가 컴파일 되지 않는다는 것.

예제에서처럼 Return address 를 고정된 레지스터에 저장하면 몇 가지 문제가 생긴다. 두 번 이상 서브루틴을 부르면 먼저 저장된 주소를 덮어쓰기 때문에

1. 중첩해서 부를 수 없다 -> 당연히 재귀호출 불가
2. 혹시 다른 서브루틴이 return address 를 덮어쓸 가능성도 있다

… 등등. 이를 회피하기 위해서 우리가 잘 알고 있는 스택, 그 중에서도 메모리 스택 이 등장한다. Stack Pointer(sp) 를 증가/감소시키며 필요한 값을 저장해두는 방법으로 중첩된 서브루틴 호출 과정에서 Return address 를 보존할 수 있다.

1
2
3
4
5
6

Sub STO $0,sp,0
    ADD sp,sp,8
    ...
    SUB sp,sp,8
    LDO $0,sp,0
    GO  $0,$0,0

이렇게 서브루틴의 가장 앞에서 스택에 \$0(Return address)를 저장하고, 돌아가기 직전에 $0를 복구하는 스킴을 지켜주면 재귀나 다른 함수들을 통한 깊은 호출에도 문제없이 동작한다. 당연히 스택을 다루는 명령어는 추가적인 오버헤드를 가지고 있다. 서브루틴 호출 트리의 Terminal node 가 확실한 경우 스택에 주소를 저장하는 것은 생략하여 명령어 몇 개 정도의 시간을 절약할 수는 있다. 또한, 주소 외에 로컬변수 등을 저장하는 용도로도 쓸 수 있다.

PUSHJ/POP

MMIX 는 메모리 스택 말고도 레지스터 스택 이라는 것도 가지고 있다. 이전에 설명 했던 PUSHJ/POP 명령이 레지스터 스택을 사용하여 위의 메모리 스택과 비슷한 일을 해 준다. 아무래도 전용 명령이다 보니 위에서 GO 를 사용할 때 메모리 스택에 접근하는 것 보다 더 효율적이다.

설명은 위 링크를 따라가서 읽어보자. (Don’t Repeat Yourself!)

아무래도 레지스터 스택의 크기는 메모리 스택보다 제한적일테니 서브루틴 호출이 중첩되는 정도에는 제한이 있지 않을까 생각한다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

     LOC  Data_Segment
     GREG @
kk   GREG
txt  BYTE "Hello world!",10,0

     LOC #100
     GREG @

Main PUSHJ $0,Sub1
     LDA $255,txt
     TRAP 0,Fputs,StdOut
     TRAP 0,Halt,0

Sub1 LDA $255,txt
     TRAP 0,Fputs,StdOut
     POP 0,0

위의 GO 를 사용한 예제 코드를 PUSHJ/POP 을 사용한 것으로 바꿔 보았다.

Sub1이 Main 아래에 있어도 된다 는 것이 특이하다. 왜 GO는 안되고 PUSHJ/POP은 되는지는 아직 모른다. 스펙이라기보단 MMIXAL 의 구현 문제일 것 같은데 …

몇 가지 꼭지만 더 남겨보자면,

• Global registers are not part of register stack
• scalar 값에 대해서만 register stack 이 의미가 있겠지
• register stack 이 너무 커지면 보이지 않는 곳에서 stack segment 에 SAVE 명령으로 저장해버린다
• $0 \le L \le G \le 255$, $32 \le G$
• Initially, $L=2$, $\tau=2$

Twisted

필요한 일이 있어서 Twisted 튜토리얼-WritingServer, WritingClient-을 읽고 간단한 ProxyServer 를 만들어 보았다. 예전엔 어렵다고 생각했는데, 다시 보니 그렇게 못할 짓은 아니다 싶다.

잊기 전에 몇 가지만 적어놓자. 잘못 이해했을지도 모르지만, 틀린게 있으면 나중에 정정하는걸로 한다.

현재 Twisted의 안정 버전은 13.2.0 이다.

Basic units

• reactor: Reactive Pattern 의 reactor다. Nuclear reactor 가 아님!! (Epoll, Select…)
• endpoint: ServerEndpoint, ClientEndpoint 가 따로 있다. Host, Port 를 받아 커넥션을 열고 닫는 등의 일을 한다. (Socket)
• protocol: 커넥션 하나의 Send/Recv 를 담당하는 객체. 프로토콜 타입에 따라 LineReceiver 같이 유용한 기본 구현체가 있다. dataReceived, lineReceived 등의 콜백 메소드를 구현하면 된다. (Connection Handler)
• factory: endpoint 에 붙어서 연결이 오면 protocol 을 생성해 붙여주는 일을 한다. (Connector/Acceptor)

뒤의 괄호 안에 있는 단어가 내가 지금까지 서버 코드를 만들 때 일반적으로 썼던 비슷한 일을 하는 단위의 이름이다.

Server

서버 코드의 순서를 대강 정리하면,

1. Protocol 정의를 Factory 에 알려주고,
2. Reactor 에 Endpoint 를 연결 한 후,
3. EndPoint 에서 Factory 를 사용하여 Listen 시작하고,
4. Reactor 가 IOLoop 을 돌린다.

정도로 정리할 수 있다. 구체적인 코드는 이와 달라질 수 있는데, 기본적으로 각 클래스가 무엇을 하려는건지 알면 이해할 수 있는 범위 내에 있다.

Client

역시 일반적인 소켓 프로그래밍과 위의 단어들을 연결해 보자면,

1. Protocol 정의를 Factory 에 알려주고,
2. Endpoint 를 Reactor 에 붙이고,
3. Endpoint 에서 Factory 를 사용하여 목표 서버에 Connect,
4. Reactor 가 IOLoop 을 돌린다.

… 위와 같다.

Asynchronous

기본적으로 대부분의 처리는 비동기로 일어난다. Connect, Recv 는 콜백 함수를 통해 처리되고, reactor.callLater(second, function) 으로 임의의 함수를 지정된 시간 후에 실행되도록 할 수 있다. 예를 들어 아래 예처럼 타임아웃을 구현할 수 있다.

class Dummy(protocol):
    def A(self):
        self.transport.write("Please send me back reply in 3.0 seconds")
        self.timeout_defer = reactor.callLater(3.0, self.timeout)

    def lineReceived(self, line):
        self.timeout.cancel()
        print('Ok, I got a reply: %s' % line)

    def timeout(self):
        print('No reply within 3.0 seconds...')
        self.transport.loseConnection()

그 외에도 여러가지 Blocked 일 것 같은 일들을 Deferred Object 로 만들어서 콜백지옥(..)을 펼쳐 놓았다. 그 한 예로 DeferredQueue 가 있다.

Deferred Queue

Twisted 를 사용한건 프락시 서버를 만들기 위해서였다. 간단하게, 연결 요청이 오면 그 때 대기중인 여러 서버중 하나를 잡아서 연결하고 받은 것을 그대로 넘기고 다시 온 것을 그대로 돌려주도록 구현했다. Telnet 으로 붙여서 손으로 데이터를 넣을 때에는 문제가 없었는데 실제 클라이언트를 붙이면서 문제가 생겼다. 프락시 뒤쪽 서버에 연결이 만들어지기 전에 클라이언트가 패킷을 보내오는 것 이다.

...
    def lineReceived(self, line):
        self.backend.transport(line)
...

아직 백엔드에 연결되기 전이라면 self.backend.transport 가 None일 수 있는 상황이다. 클라이언트한테 연결될때까지 기다려달라고 할 수도 없고 …

그래서 일단 클라이언트가 보내는 패킷을 바로 뒤로 보내지 않고 큐에 담아놓기로 했다. 그런데 그냥 Queue 에 넣으면 언제 꺼낼 것이며 하는 등의 비동기 처리가 또 머리 아파진다. 다행히도 twisted 가 제공하는 모듈 중에 deferredQueue 라는게 있다.

DeferredQueue 는 get() 메소드가 아이템을 리턴하는게 아니라 deferred item 을 리턴한다. Deferred 는 그냥 lazy evalution 하는 아이 라고 생각하자. get() 이 리턴한 객체에 addCallback(real_get) 을 사용해서 실제로 get 할게 생겼을 때 처리할 함수가 실행되게 할 수 있다. 오오, 비동기 큐!! 콜백 뒤에 다시 get().addCallback() 해주는 것을 놓치지 말자.

그리하여 DeferredQueue 를 사용하면 대충 아래와 같은 구조를 만들 수 있다.

...
    def __init__(self):
        self.queue = defer.DeferredQueue()

    def lineReceived(self, line):
        self.queue.put(line)

    def write_to_backend(self, line):
        self.backend.transport(line)
        self.queue.get().addCallback(self.write_to_backend)

    def backend_conn_made(self):
        self.queue.get().addCallback(self.write_to_backend)
...

Delimiter in LineReceiver

중간에 프로토콜을 훔쳐볼 필요가 생겼는데, 그 프로토콜은 줄 단위로 구성된다. 그런데 Twisted 의 LineReceiver 는 줄 바꿈을 ‘\r\n’ 으로 처리하는데 내가 사용하는 프로토콜에서는 ‘\n’ 으로 처리한다. 이 미묘한 차이 때문에 LineReceiver 비슷한걸 다시 만들기도 좀 그렇다. 다행히도 API Document 를 보면 앞쪽에,

Class Variable  delimiter   The line-ending delimiter to use. By default this is b'\r\n'.

이렇게 delimiter 를 고칠 수 있다고 되어 있다. self.delimiter='\n' 로 문제 해결.

스펠링을 delimeter 로 착각해서 한참 고생했다.

defer.inlineCallbacks

콜백지옥이 펼쳐지기 전에 파이썬의 yield 를 사용해 코드의 흐름을 하나의 함수에 넣을 수 있다.

이 포스팅 이 잘 설명하고 있다. 참고로 저 블로그의 AN INTRODUCTION TO ASYNCHRONOUS PROGRAMMING AND TWISTED은 비동기 프로그래밍에 익숙하지 않은 사람에게 굉장히 훌륭한 입문서다.

Coursera Model Thinking

이번에도 역시 노트에 낙서 하며 수업을 들었다. 적어둔게 뭐 도움이 되겠냐마는.

9, 10장이 각각 Problem Solving, Markov Process 를 다룬다. 이거 사회과학 수업 맞아???

Ch 9. Problem Solving

• Perspectives

  • 해공간을 모델링하는 방법에 따라 Local optima 의 수가 달라진다.
  • Local optima 의 수가 적을수록 좋은 Perspective 다.
  • ex) Sum to fifteen 과 Tic-Tac-Toe 는 사실 똑같은 게임을 다른 Perspective 로 바라본 것.
  • Convex 가 좋은것은 Local optima 가 단 하나 = Global optima 라는거지

• Heuristic

  • No Free Lunch Theorem: 어떤 방법도 모든 문제를 다 잘 풀수는 없다.
  • 특정 휴리스틱(방법)은 특정 문제에 한해 효과적일 수는 있다. 범위제한.
  • Heuristic is how to search

• Teams

  • 여러 (Perspective+Heuristic) 조합은 각기 서로 다른 Local optima 를 가진다.
  • 팀 멤버들이 각기 다른 방식으로 문제 풀기를 시도한다면, 모든 팀 멤버가 공유하는 Local optima 에서만 막힌다.
  • 팀이 크면 클수록 Local optima 에 막힐 확률이 낮아진다.
  • 물론, Communication cost 나 Error 등을 고려하면 좀 다른 얘기가 되긴 함.

• Recombination

  • 여러개의 문제를 조합하면 문제의 난이도는 지수적으로 상승한다
  • ex) [1 2 3 5 _ 13 …] + [1 4 _ 16 25 36 …] => [1 2 6 42 _ 1806 …]

Ch 10. Markov process

• 여러개의 States
• States 간의 Transitions
• 각 Transition은 고정된 확률을 가짐

이런 조건이 갖추어지면 Transition matrix 를 만들어서 어떤 일이 일어나는지 관찰할 수 있다. 이 Transition matrix 는 column 의 합이 1.0 이 되어야 한다. 확률이니까. 아래는 A->B, B->A 의 확률이 각각 0.2, 0.4 인 시스템의 Transition matrix 이다.

이 행렬을 M 이라고 하면, N 시간이 지난 후의 결과는 $M^N$ 으로 계산할 수 있다. A, B 의 초기값이 각각 p, 1.0-p 처럼 비율로 주어지면 $N \rightarrow \infty$ 일 때 결과값은 어딘가(Equilibrium)로 수렴하게 된다. 이 때,

1. 초기값에 무관하게 항상 같은 지점으로 수렴한다
2. 당연히 중간에 값을 어그러뜨려도 확률 자체가 변하지 않는 한 같은 지점으로 수렴한다
3. 수렴지점의 평형상태는 Statistical Equilibrium 이다. 개체들이 Transition 을 계속 하지만 그 분포 비율이 일정하게 유지되는 상태이다.

위의 Transition matrix 가 어디에 수렴하나 계산해보자:

0.8p + 0.4(1-p) = p
0.8p + 0.4 - 0.4p = p
0.4 = 0.6p
p = 2/3

어떻게 시작하더라도 A 가 2/3, B 가 1/3 인 상태에 도달하게 된다. 확인해볼까? Numpy 로 여러가지 초기 상태에 대해서 대충 100번쯤씩 돌려보았다.

>>> import numpy as np
>>> transition_matrix = np.matrix([[0.8, 0.4], [0.2, 0.6]])
>>> initial_states = [np.matrix([[0.5],[0.5]]), np.matrix([[1.0],[0.0]]), np.matrix([[0.0], [1.0]]), np.matrix([[0.123], [1.0-0.123]])]
>>> for init in initial_states:
...     print transition_matrix**100*init
...
[[ 0.66666667]
 [ 0.33333333]]
[[ 0.66666667]
 [ 0.33333333]]
[[ 0.66666667]
 [ 0.33333333]]
[[ 0.66666667]
 [ 0.33333333]]
>>>

실제로 계산 결과 A->0.66666667, B->0.33333333 로 수렴하는 것을 볼 수 있다.

이건 PageRank 와도 관련이 있다. PageRank가 왜 수렴하는가? Random Surfer 를 왜 넣었나? … 결과적으로 PageRank 알고리즘에서 PowerIteration 시키는 행렬을 잘 보면 여기서 다루는 Markov process 의 Transition matrix 와 같은 꼴이다. Stochastic Process 도 한번 읽어보자.