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가지 파라미터를 사용한다.
- TolS: Tolerance for error
- 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
링크한 문단의 가장 아래 문장을 보자.
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
책에서는 서브루틴을 사용하는 두 가지 방법을 설명하고 있다.
- GO
- PUSHJ/POP
그리고 MMIXAL 이 제공하는 서브루틴 사용을 도와주는 명령 세 개가 있다.
- PREFIX
- LOCAL
- 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 를 고정된 레지스터에 저장하면 몇 가지 문제가 생긴다. 두 번 이상 서브루틴을 부르면 먼저 저장된 주소를 덮어쓰기 때문에
- 중첩해서 부를 수 없다 -> 당연히 재귀호출 불가
- 혹시 다른 서브루틴이 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
서버 코드의 순서를 대강 정리하면,
- Protocol 정의를 Factory 에 알려주고,
- Reactor 에 Endpoint 를 연결 한 후,
- EndPoint 에서 Factory 를 사용하여 Listen 시작하고,
- Reactor 가 IOLoop 을 돌린다.
정도로 정리할 수 있다. 구체적인 코드는 이와 달라질 수 있는데, 기본적으로 각 클래스가 무엇을 하려는건지 알면 이해할 수 있는 범위 내에 있다.
Client
역시 일반적인 소켓 프로그래밍과 위의 단어들을 연결해 보자면,
- Protocol 정의를 Factory 에 알려주고,
- Endpoint 를 Reactor 에 붙이고,
- Endpoint 에서 Factory 를 사용하여 목표 서버에 Connect,
- 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 이다.
A(t) | B(t) | |
---|---|---|
A(t+1) | 0.8 | 0.4 |
B(t+1) | 0.2 | 0.6 |
이 행렬을 M 이라고 하면, N 시간이 지난 후의 결과는 $M^N$ 으로 계산할 수 있다. A, B 의 초기값이 각각 p, 1.0-p 처럼 비율로 주어지면 $N \rightarrow \infty$ 일 때 결과값은 어딘가(Equilibrium)로 수렴하게 된다. 이 때,
- 초기값에 무관하게 항상 같은 지점으로 수렴한다
- 당연히 중간에 값을 어그러뜨려도 확률 자체가 변하지 않는 한 같은 지점으로 수렴한다
- 수렴지점의 평형상태는 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 도 한번 읽어보자.
Comments