이번 글에서는 이항분포, 다항분포, 베타분포, 디리클레분포에 대해 살펴보도록 하겠습니다. 이번 글 역시 고려대 강필성 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

이항분포

성공확률이 $p$인 베르누이시행을 $n$번 반복시행할 때 성공횟수를 나타내는 확률변수 $X$의 분포를 이항분포(binomial distribution)이라고 합니다. 이항분포의 확률질량함수는 다음과 같습니다.

[p(x)=\begin{pmatrix} n \ x \end{pmatrix}{ p }^{ x }{ (1-p) }^{ n-x },\quad x=0,1,…n]

이항분포의 확률질량함수를 시각화하면 다음 그림과 같습니다. (출처 : 위키피디아)

$X$의 기대값과 분산은 다음과 같습니다.

[E(X)=np\ Var(X)=np(1-p)]

베타분포

베타분포(beta distribution)란 두 매개변수 $α$와 $β$에 대해 $[0,1]$에서 정의되는 연속확률분포들의 가족을 가리킵니다. 베타분포의 확률밀도함수는 다음과 같습니다.

[f(x;\alpha ,\beta )=\frac { \Gamma (\alpha +\beta ) }{ \Gamma (\alpha )\Gamma (\beta ) } { x }^{ \alpha -1 }{ (1-x) }^{ \beta -1 }]

베타분포의 확률밀도함수인 감마함수 $Γ$는 다음과 같이 정의됩니다.

[\Gamma (n)=(n-1)!]

$α$, $β$ 값에 따라 베타분포의 모양 또한 달라지는데요. 다음 그림을 참고하시면 좋을 것 같습니다. (출처)

다항분포

다항분포(Multinomial)란 여러 개의 값을 가질 수 있는 독립 확률변수들에 대한 확률분포를 가리킵니다. 여러 번의 독립시행에서 각각의 값이 특정 횟수가 나타날 확률을 말합니다.

어떤 시행에서 $k$가지의 값이 나타날 수 있고, 그 값이 나타날 확률을 각각 $p_1, p_2, …,p_k$라고 할 때 $n$번의 시행에서 $i$번째 값이 $x_i$회 나타날 확률은 다음과 같습니다. 즉 다항분포의 확률질량함수는 아래와 같습니다.

[p({ x }{ 1 },{ x }{ 2 },…,{ x }{ k };n,{ p }{ 1 },…,{ p }{ k })=\frac { n! }{ { x }{ 1 }!{ x }{ 2 }!…{ x }{ k }! } { p }{ 1 }^{ { x }{ 1 } }{ p }{ 2 }^{ { x }{ 2 } }…{ p }{ k }^{ { x }{ k } }]

예를 들어보겠습니다. 전체 말뭉치의 단어 개수가 $v$개이고, 첫번째 단어가 말뭉치에 등장할 확률이 $p_{v1}$, 두번째 단어는 $p_{v2}$,…,$v$번째 단어는 $p_{vv}$라고 가정해보겠습니다. 여기에서 말뭉치에서 단어를 $n$개 뽑을 때 첫번째 단어가 나타날 횟수는 $x_1$,…$v$번째 단어는 $x_v$가 됩니다.

디리클레분포

디리클레분포란 $k$차원의 실수 벡터 중 벡터의 요소가 양수이며 모든 요소를 더한 값이 1인 경우에 확률값이 정의되는 연속확률분포입니다. 2이상의 자연수 $k$와 양의 상수 $α_1,…,α_k$에 대하여 디리클레분포의 확률밀도함수는 다음과 같이 정의됩니다.

[\begin{align} &{ x }_{ 1 },…,{ x }_{ k }가\quad모두 \quad양의 \quad실수이며 \quad\sum _{ i=1 }^{ k }{ { x }_{ i } } =1을 \quad만족할 \quad때,\ &f({ x }_{ 1 },…{ x }_{ k };{ \alpha }_{ 1 },…,{ \alpha }_{ k })=\frac { 1 }{ B(\alpha ) } \prod _{ i=1 }^{ k }{ { { x }_{ i } }^{ { \alpha }_{ i }-1 } } \&그 \quad외의 \quad경우는 \quad0이다. \end{align}]

$B(α)$는 다음과 같습니다.

[B(\alpha )=\frac { \prod { i=1 }^{ k }{ \Gamma ({ \alpha }{ i }) } }{ \Gamma (\sum { i=1 }^{ k }{ { \alpha }{ i } } ) }]

3차원 디리클레 분포의 모양은 다음과 같습니다. 왼쪽 위에서부터 시계방향으로 $α$=(6, 2, 2), (3, 7, 5), (6, 2, 6), (2, 3, 4)

켤레사전분포

사후확률 분포 $p(θ$|$x)$가 사전확률 분포 $p(θ)$와 같은 가족군으로 묶일 때 그 사후확률/사전확률을 모두 묶어 켤레분포(conjugate distributions), 그 사전확률 분포를 켤레사전분포(Conjugate prior distribution)라고 합니다. 사전확률과 사후확률이 동일한 분포를 따른다면 계산이 매우 편해지기 때문에 베이즈 통계학에서 많이 쓴다고 합니다. 그 관계를 따지면 다음과 같습니다.

이번 글에서는 딥러닝이 주목받기 전인 2000년대 초반까지의 문서 분류 방식에 대해 살펴보도록 하겠습니다. AK Nassirtoussi(2015)는 금융 관련 문서들로 주가를 예측하는 연구를 했었는데요, 도메인이 금융에 특화돼 있긴 하지만 기존 문서 분류 연구들을 잘 정리해놓은 것 같다는 생각에 이를 인용해봤습니다. 그럼 시작하겠습니다.

문서 전처리

2000년대 초반 연구에서는 비정형데이터를 정형데이터로 변환하는 데 TF-IDF가 많이 쓰인 점을 확인할 수 있습니다. 토픽모델링 기법인 Latent Dirichlet Allocation을 입력 벡터로 만든 연구도 눈에 띕니다. 요즘엔 구글에서 2013년 개발한 Word2Vec이나 미국 스탠포드에서 개발한 GloVe 등을 주로 쓰고 있다는 점을 생각하면 격세지감이네요. TF-IDF에 대해 자세한 내용은 이곳을, Word2Vec에 대해서는 이곳, GloVe는 이곳을 참고하시면 좋을 것 같습니다.

분류 모델

분류 모델로는 서포트 벡터 머신(SVM) 계열 비중이 압도적입니다. 그도 그럴 것이 딥러닝 이전 뛰어난 성능으로 많은 주목을 받았던 모델 때문이 아닌가 생각합니다. 이밖에 선형회귀, 나이브 베이지안, K-NN 같은 비교적 간단한 모델도 분류기로 많이 쓰였습니다. 요즘에는 Convolutional Neural Networks, Recurrent Neural Networks, Recursive Neural Networks 등 딥러닝 모델들이 각광받고 있습니다.

SVM에 대한 자세한 내용은 이곳을, 나이브 베이지안 모델은 이곳, K-NN은 이곳을 참고하면 좋을 것 같습니다. 아울러 CNN은 이곳, Recurrent Neural Networks는 이곳, Recursive Neural Networks는 이곳을 보시면 좋을 것 같습니다.

Appendix

제가 인용한 논문입니다.

Nassirtoussi, A. K., Aghabozorgi, S., Wah, T. Y., & Ngo, D. C. L. (2015). Text mining of news-headlines for FOREX market prediction: A Multi-layer Dimension Reduction Algorithm with semantics and sentiment. Expert Systems with Applications, 42(1), 306-324.

표에 언급된 논문 목록입니다.

Wuthrich, B., Cho, V., Leung, S., Permunetilleke, D., Sankaran, K., & Zhang, J. (1998). Daily stock market forecast from textual web data. In 1998 IEEE international conference on systems, man, and cybernetics (Vols. 3 and 2723, pp. 2720–2725).

Peramunetilleke, D., & Wong, R. K. (2002). Currency exchange rate forecasting from news headlines. Australian Computer Science Communications, 24, 131–139.

Werner, A., & Myrray, Z. F. (2004). Is all that talk just noise ? The information content of internet stock message boards. Journal of Finance, 1259–1294.

Mittermayer, M. A. (2004). Forecasting intraday stock price trends with text mining techniques. In Proceedings of the 37th annual Hawaii international conference on system sciences, 2004 (p. 10).

Das, S. R., & Chen, M. Y. (2007). Yahoo! for Amazon: Sentiment extraction from small talk on the web. Management Science, 53, 1375–1388.

Soni, A., van Eck, N. J., & Kaymak, U. (2007). Prediction of stock price movements based on concept map information. In IEEE symposium on computational intelligence in multicriteria decision making (pp. 205–211).

Zhai, Y., Hsu, A., & Halgamuge, S. K. (2007). Combining news and technical indicators in daily stock price trends prediction. In Proceedings of the fourth international symposium on neural networks: advances in neural networks, Part III (pp. 1087–1096). Nanjing, China: Springer-Verlag.

Rachlin, G., Last, M., Alberg, D., & Kandel, A. (2007). ADMIRAL: A data mining based financial trading system. In IEEE symposium on computational intelligence and data mining, 2007. CIDM 2007 (pp. 720–725).

Tetlock, P. C., Saar-Tsechansky, M., & Macskassy, S. (2008). More than words: Quantifying language to measure firms’ fundamentals. The Journal of Finance, 63, 1437–1467.

Mahajan, A., Dey, L., & Haque, S. M. (2008). Mining financial news for major events and their impacts on the market. In IEEE/WIC/ACM international conference on web intelligence and intelligent agent technology, 2008. WI-IAT ‘08 (Vol. 1, pp. 423–426).

Butler, M., & Kešelj, V. (2009). Financial forecasting using character N-gram analysis and readability scores of annual reports. In Y. Gao & N. Japkowicz (Eds.). Advances in artificial intelligence (Vol. 5549, pp. 39–51). Berlin, Heidelberg: Springer.

Schumaker, R. P., & Chen, H. (2009). Textual analysis of stock market prediction using breaking financial news: The AZF in text system. ACM Transactions on Information Systems, 27, 1–19.

Lugmayr, A., & Gossen, G. (2012). Evaluation of methods and techniques for language based sentiment analysis for DAX 30 stock exchange – a first concept of a ‘‘LUGO’’ sentiment indicator. In Lugmayr, A., Risse, T., Stockleben, B., Kaario, J., Pogorelc, B., & Serral Asensio, E. (Eds.). SAME 2012 – fifth international workshop on semantic ambient media experience.

Yu, Y., Duan, W., & Cao, Q. (2013). The impact of social and conventional media on firm equity value: A sentiment analysis approach. Decision Support Systems.

Hagenau, M., Liebmann, M., & Neumann, D. (2013). Automated news reading: Stock price prediction based on financial news using context-capturing features. Decision Support Systems, 55, 685–697.

Jin, F., Self, N., Saraf, P., Butler, P., Wang, W., & Ramakrishnan, N. (2013). Forexforeteller: Currency trend modeling using news articles. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 1470–1473). Chicago, IL, USA: ACM.

Chatrath, A., Miao, H., Ramchander, S., & Villupuram, S. (2014). Currency jumps, cojumps and the role of macro news. Journal of International Money and Finance, 40, 42–62.

Bollen, J., Huina, M., & Zeng, Xiao-Jun (2010). Twitter mood predicts the stock market. Journal of Computational Science, 2, 1–8.

Vu, T. T., Chang, S., Ha, Q. T., & Collier, N. (2012). An experiment in integrating sentiment features for tech stock prediction in twitter. In Proceedings of the workshop on information extraction and entity analytics on social media data (pp. 23–38). Mumbai, India: The COLING 2012 Organizing Committee.

Pui Cheong Fung, G., Xu Yu, J., & Wai, L. (2003). Stock prediction: Integrating text mining approach using real-time news. In Proceedings. 2003 IEEE international conference on computational intelligence for financial engineering (pp. 395–402).

Schumaker, R. P., Zhang, Y., Huang, C.-N., & Chen, H. (2012). Evaluating sentiment in financial news articles. Decision Support Systems, 53, 458–464.

Li, F. (2010). The information content of forward-looking statements in corporate filings—a Naïve Bayesian machine learning approach. Journal of Accounting Research, 48, 1049–1102.

Li, C. H., Yang, J. C., & Park, S. C. (2012). Text categorization algorithms using semantic approaches, corpus-based thesaurus and WordNet. Expert Systems with Applications, 39, 765–772.

Huang, C.-J., Liao, J.-J., Yang, D.-X., Chang, T.-Y., & Luo, Y.-C. (2010). Realization of a news dissemination agent based on weighted association rules and text mining techniques. Expert Systems with Applications, 37, 6409–6413.

Groth, S. S., & Muntermann, J. (2011). An intraday market risk management approach based on textual analysis. Decision Support Systems, 50, 680–691.

이번 글에서는 말뭉치에 내재해 있는 토픽들을 추론해 내는 확률모델인 Probabilistic Latent Semantic Analysis(pLSA)에 대해 살펴보도록 하겠습니다. 이번 글 역시 고려대 강필성 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

LSA

pLSA는 기존 잠재의미분석(Latene Semantic Analysis)과는 아예 다른 기법이지만 개념을 공유하는게 많아서 먼저 설명해볼까 합니다. LSA에 대한 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다. 어쨌든 LSA는 말뭉치 행렬 $A$를 다음과 같이 분해하는 걸 말합니다.

LSA 수행 결과로 $n$개 문서가 원래 단어 개수보다 훨씬 작은 $q$차원의 벡터로 표현된 걸 확인할 수 있습니다. 마찬가지로 $m$개 단어는 원래 문서 수보다 훨씬 작은 $q$차원 벡터로 변환됐습니다. $q$가 3이라면 전체 말뭉치가 3개의 토픽으로 분석됐다고도 말할 수 있을 것입니다.

위 그림에서 행렬 $L$의 열벡터는 각각 해당 토픽에 대한 문서들의 분포 정보를 나타냅니다. $R$의 행벡터는 각각 해당 토픽에 대한 단어들의 분포 정보를 나타냅니다. 중간에 대각행렬은 $q$개 토픽 각각이 전체 말뭉치 내에서 얼마나 중요한지 나타내는 가중치가 될 겁니다.

pLSA

pLSA는 단어와 문서 사이를 잇는, 우리 눈에 보이지 않는 잠재구조가 있다는 가정 하에 단어와 문서 출현 확률을 모델링한 확률모형입니다. pLSA는 아래 그림처럼 Latent concepts가 존재하고 이것이 문서와 단어를 연결한다고 가정합니다. 문서들의 주제(토픽)이라고 생각하면 좋을 것 같습니다.

왼쪽부터 차례로 살펴보겠습니다. P(z|d)는 문서 하나가 주어졌을 때 특정 주제(토픽)가 나타날 확률을 의미합니다. P(w|z)는 주제가 정해졌을 때 특정 단어가 나타날 확률을 가리킵니다.

예컨대 위 그림 기준에서 네번째 문서는 trade라는 주제로만 구성돼 있습니다. 그런데 trade라는 주제는 economic, imports, trade 따위의 단어를 선호하네요.

결과적으로 네번째 문서에는 economic, imports, trade 등의 단어가 출현할 가능성이 높다고 할 수 있겠습니다. pLSA의 가정에 문제가 없다면 해당 문서에 실제 등장하는 단어의 출현 확률은 높아야 할 겁니다.

그럼 pLSA가 가정하는 단어-문서 생성 과정을 살펴보겠습니다. 아래 그림을 볼까요?

(a) 먼저 보겠습니다. 우선 문서를 뽑습니다. 그 다음 이 문서의 주제를 뽑습니다. 마지막으로 해당 주제별로 단어를 뽑습니다. 사람이 글 쓸 때도 글을 쓰기로 마음을 먹고 나서 주제, 단어를 차례대로 결정하기 때문에 직관적으로 이해가 가능합니다.

그런데 (b)는 좀 이해하기 까다롭습니다. 주제(z)를 뽑은 뒤 이 주제에 해당하는 문서와 단어를 뽑는 방식입니다. pLSA는 바로 이 방식으로 모델이 구성돼 있습니다.

LSA와 pLSA

LSA는 행렬 인수분해(matrix factorization), pLSA는 확률모형입니다. 아예 그 종류가 다르다고 할 수 있죠. 하지만 개념상 연결되는 부분이 있습니다. 그래서일까요? 이름도 좀 많이 비슷해요. 어쨌든 아래 그림을 보겠습니다.

LSA 결과물인 행렬 $U_k$의 열벡터는 각각 해당 토픽에 대한 문서들의 분포 정보를 나타냅니다. 이는 pLSA의 P(d|z)에 대응합니다.

행렬 $V_k$의 행벡터는 각각 해당 토픽에 대한 단어들의 분포 정보를 나타냅니다.이는 pLSA의 P(w|z)에 대응합니다.

$Σ_k$의 대각성분은 토픽 각각이 전체 말뭉치 내에서 얼마나 중요한지 나타내는 가중치가 됩니다. 이는 pLSA의 P(z)에 대응합니다.

pLSA의 결과물은 확률이기 때문에 각 요소값이 모두 0 이상, 전체 합이 1이 됩니다. 하지만 LSA는 이런 조건을 만족하지 않습니다.

pLSA의 목적식

pLSA는 $m$개 단어, $n$개 문서, $k$개 주제(토픽)에 대해 아래 우도함수를 최대화하는 걸 목표로 합니다. \(\begin{align*} L&=\coprod _{ i=1 }^{ m }{ \coprod _{ j=1 }^{ n }{ { p({ w }_{ i },{ d }_{ j }) }^{ n({ w }_{ i },{ d }_{ j }) } } } \\ &=\coprod _{ i=1 }^{ m }{ \coprod _{ j=1 }^{ n }{ { \left\{ \sum _{ l=1 }^{ k }{ p({ d }_{ j }|{ z }_{ l })p({ z }_{ l })p({ w }_{ i }|z_{ l }) } \right\} }^{ n({ w }_{ i },{ d }_{ j }) } } } \end{align*}\)

위 식에서 $n(w_i,d_j)$는 $j$번째 문서에 $i$번째 단어가 등장한 횟수를 나타냅니다. $p(w_i, d_j)$는 $k$개 주제(토픽)에 대해 summation 형태로 돼 있는데요. 같은 단어라 하더라도 여러 토픽에 쓰일 수 있기 때문입니다. 예컨대 정부(government) 같은 흔한 단어는 정치, 경제, 외교/국방 등 다양한 주제에 등장할 수 있습니다.

pLSA의 학습 : EM 알고리즘

EM알고리즘은 동시에 최적화할 수 없는 복수의 변수들을 반복적인 방식으로 계산하는 기법입니다. 우선 모든 값을 랜덤으로 초기화합니다. 이후 하나의 파라메터를 고정시킨 다음에 다른 파라메터를 업데이트하고, 이후 단계에선 업데이트된 파라메터로 고정시킨 파라메터를 다시 업데이트합니다. 다음과 같습니다.

분석 예시

다음과 같은 Term-Document Matrix를 분석해 보겠습니다.

pLSA 수행 결과로 계산된 P(z)는 다음과 같습니다.

P(d|z)는 다음과 같습니다. 이 결과로 미루어 짐작해볼 때 Topic1은 정치, Topic2는 경제, Topic3는 스포츠인 것 같습니다.

P(w|z)는 다음과 같습니다.

pLSA 수행 결과로 나온 표들은 겉보기에는 LSA의 행렬 인수분해 결과와 흡사해 보입니다. 하지만 주의할 것은 도출되는 과정 자체가 확률모형을 전제했다는 것입니다.

코드

pLSA를 R로 직접 구현해 봤습니다. 다음과 같습니다.

이번 글에서는 딥러닝 이전 뛰어난 성능으로 많은 주목을 받았던 서포트 벡터 머신(Support Vector Machine)에 대해 살펴보도록 하겠습니다. 이번 글 역시 고려대 강필성 교수님과 같은 대학의 김성범 교수님 강의, 그리고 이곳을 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

margin

두 범주를 나누는 분류 문제를 푼다고 가정해 보겠습니다. 아래 그림에서 직선 $B_1$과 $B_2$ 모두 두 클래스를 무난하게 분류하고 있음을 확인할 수 있습니다.

좀 더 나은 분류경계면을 꼽으라면 $B_1$일 겁니다. 두 범주를 여유있게 가르고 있거든요. 위 그림에서 $b_{12}$을 minus-plane, $b_{11}$을 plus-plane, 이 둘 사이의 거리를 마진(margin)이라고 합니다. SVM은 이 마진을 최대화하는 분류 경계면을 찾는 기법입니다. 이를 도식적으로 나타내면 아래와 같습니다.

그럼 마진의 길이가 얼마인지 유도해보겠습니다. 우선 우리가 찾아야 하는 분류경계면을 $w^Tx+b$라고 둡시다. 그러면 벡터 $w$는 이 경계면과 수직인 법선벡터가 됩니다.

이해하기 쉽도록 $w$를 2차원 벡터 $(w_1,w_2)^T$라고 두겠습니다. $w$에 대해 원점과의 거리가 $b$인 직선의 방정식은 $w^Tx+b=w_1x_1+w_2x_2+b=0$이 됩니다. 이 직선의 기울기는 $-w_1/w_2$이고, 법선벡터 $w$의 기울기는 $w_2/w_1$이므로 두 직선은 수직입니다. 이를 차원을 확장하여 생각해도 마찬가지입니다.

어쨌든 이 사실을 바탕으로 plus-plane 위에 있는 벡터 $x^+$와 $x^-$ 사이의 관계를 다음과 같이 정의할 수 있습니다. $x^-$를 $w$ 방향으로 평행이동시키되 이동 폭은 $λ$로 스케일한다는 취지입니다.

[{ x }^{ + }={ x }^{ - }+\lambda w]

그럼 $λ$은 어떤 값을 지닐까요? $x^+$는 plus-plane, $x^-$는 minus-plane 위에 있다는 사실과 $x^+$와 $x^-$ 사이의 관계식을 활용하면 다음과 같이 유도해낼 수 있습니다.

[\begin{align} { w }^{ T }{ x }^{ + }+b&=1\ { w }^{ T }({ x }^{ - }+\lambda w)+b&=1\ { w }^{ T }{ x }^{ - }+b+\lambda { w }^{ T }w&=1\ -1+\lambda { w }^{ T }w&=1\\ \lambda =\frac { 2 }{ { w }^{ T }w } \end{align}]

마진은 plus-plane과 minus-plane 사이의 거리를 의미합니다. 이는 $x^+$와 $x^-$ 사이의 거리와 같습니다. 둘 사이의 관계식과 $λ$값을 알고 있으므로 식을 정리하면 마진을 다음과 같이 유도할 수 있습니다.

[\begin{align} Margin&=distance({ x }^{ + },{ x }^{ - })\ &={ \left| { x }^{ + }-{ x }^{ - } \right| }_{ 2 }\ &={ \left| { x }^{ - }+\lambda w-{ x }^{ - } \right| }_{ 2 }\ &={ \left| \lambda w \right| }_{ 2 }\ &=\lambda \sqrt { { w }^{ T }w } \ &=\frac { 2 }{ { w }^{ T }w } \sqrt { { w }^{ T }w } \ &=\frac { 2 }{ \sqrt { { w }^{ T }w } } \ &=\frac { 2 }{ { \left| w \right| }_{ 2 } } \end{align}]

목적식과 제약식 정의

SVM의 목적은 마진을 최대화하는 경계면을 찾는 것입니다. 계산상 편의를 위해 마진 절반을 제곱한 것에 역수를 취한 뒤 그 절반을 최소화하는 문제로 바꾸겠습니다. 이렇게 해도 문제의 본질은 바뀌지 않습니다.

[max\frac { 2 }{ { \left| w \right| }{ 2 } } \rightarrow \min { \frac { 1 }{ 2 } { \left| w \right| }{ 2 }^{ 2 } }]

여기엔 다음과 같은 제약조건이 관측치 개수만큼 붙습니다. 식의 의미는 이렇습니다. plus-plane보다 위에 있는 관측치들은 $y=1$이고 $w^Tx+b$가 1보다 큽니다. 반대로 minus-plane보다 아래에 있는 점들은 $y=-1$이고 $w^Tx+b$가 -1보다 작습니다. 이 두 조건을 한꺼번에 묶으면 아래와 같은 제약식이 됩니다.

[{ y }{ i }({ w }^{ T }{ x }{ i }+b)\ge 1]

라그랑지안 문제로 변환

라그랑지안 승수법(Lagrange multiplier method)은 제약식에 형식적인 라그랑지안 승수를 곱한 항을 최적화하려는 목적식에 더하여, 제약된 문제를 제약이 없는 문제로 바꾸는 기법입니다. 이에 대해 추가적인 내용은 이곳을 참고하면 좋을 것 같습니다.

우리가 이미 정의한 목적식과 제약식을 라그랑지안 문제로 식을 다시 쓰면 다음과 같습니다.

[{\min{ L_{p}(w,b,{ \alpha }{ i }) } } =\frac { 1 }{ 2 } { \left| w \right| }{ 2 }^{ 2 }-\sum { i=1 }^{ n }{ { \alpha }{ i }({ y }{ i }({ w }^{ T }{ x }{ i }+b)-1) }]

원 문제의 제약식의 범위가 0 이상이므로 $L_p$의 제약은 다음과 같습니다.

[{ \alpha }_{ i }\ge 0,\quad i=1,…,n]

Dual 문제로 변환

KKT 조건에서는 $L_p$를 미지수로 각각 편미분한 식이 0이 되는 지점에서 최소값을 갖습니다. 다음과 같습니다.

[\begin{align} \frac { \partial L(w,b,{ \alpha }_{ i }) }{ \partial w } =0\quad &\rightarrow \quad w=\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i }{ x }_{ i } } \ \frac { \partial L(w,b,{ \alpha }_{ i }) }{ \partial b } =0\quad &\rightarrow \quad \sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i } } =0 \end{align}]

위 식을 $L$에 넣어 정리해 보겠습니다. 우선 첫번째 항부터 보겠습니다.

[\begin{align} \frac { 1 }{ 2 } { \left| w \right| }_{ 2 }^{ 2 }&=\frac { 1 }{ 2 } { w }^{ T }w\ &=\frac { 1 }{ 2 } { w }^{ T }\sum _{ j=1 }^{ n }{ { \alpha }_{ j }{ y }_{ j }{ x }_{ j } } \ &=\frac { 1 }{ 2 } \sum _{ j=1 }^{ n }{ { \alpha }_{ j }{ y }_{ j }{ ({ w }^{ T }x }_{ j }) } \ &=\frac { 1 }{ 2 } \sum _{ j=1 }^{ n }{ { \alpha }_{ j }{ y }_{ j }{ (\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i }{ x }_{ i }^{ T }{ x }_{ j } } }) } \ &=\frac { 1 }{ 2 } \sum _{ i=1 }^{ n }{ \sum _{ j=1 }^{ n }{ { \alpha }_{ i }{ { \alpha }_{ j }y }_{ i }{ y }_{ j }{ x }_{ i }^{ T }{ x }_{ j } } } \end{align}]

이번엔 두번째 항입니다.

[\begin{align} -\sum _{ i=1 }^{ n }{ { \alpha }_{ i }({ y }_{ i }({ w }^{ T }{ x }_{ i }+b)-1) } &=-\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i }({ w }^{ T }{ x }_{ i }+b) } +\sum _{ i=1 }^{ n }{ { \alpha }_{ i } } \ &=-\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i }{ w }^{ T }{ x }_{ i } } -b\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i } } +\sum _{ i=1 }^{ n }{ { \alpha }_{ i } } \ &=-\sum _{ i=1 }^{ n }{ \sum _{ j=1 }^{ n }{ { \alpha }_{ i }{ { \alpha }_{ j }y }_{ i }{ y }_{ j }{ x }_{ i }^{ T }{ x }_{ j } } } +\sum _{ i=1 }^{ n }{ { \alpha }_{ i } } \end{align}]

지금까지 도출한 결과를 토대로 $L_p$를 정리하면 다음과 같습니다. 식을 변형하는 과정에서 $α$에 관한 식으로 간단해졌습니다. $α$의 최고차항의 계수가 음수이므로 최소값을 찾는 문제가 최대값을 찾는 문제로 바뀌었습니다. 이로써 Dual 문제로 변환된 것입니다.

[\max { { L }{ D }({ \alpha }{ i }) } =\sum { i=1 }^{ n }{ { \alpha }{ i } } -\frac { 1 }{ 2 } \sum { i=1 }^{ n }{ \sum _{ j=1 }^{ n }{ { \alpha }{ i }{ { \alpha }{ j }y }{ i }{ y }{ j }{ x }{ i }^{ T }{ x }_{ j } } }]

KKT 조건에 의해 $L_D$의 제약식은 다음과 같습니다.

[\sum { i=1 }^{ n }{ { \alpha }{ i }{ y }{ i } } =0 \{ \alpha }{ i }\ge 0,\quad i=1,…,n]

SVM의 해

우리가 찾고자 한 답은 마진이 최대화된 분류경계면 $w^Tx+b$입니다. $w$와 $b$를 찾으면 SVM의 해를 구할 수 있게 됩니다. KKT 조건을 탐색하는 과정에서 $w$는 다음과 같이 도출됐습니다.

[w=\sum { i=1 }^{ n }{ { \alpha }{ i }{ y }{ i }{ x }{ i } }]

$x_i​$와 $y_i​$는 우리가 가지고 있는 학습데이터이므로 라그랑지안 승수인 $α​$값들만 알면 $w​$를 찾을 수 있습니다. 그런데 여기에서 $α_i​$가 0인 관측치들은 분류경계면 형성에 아무런 영향을 끼치지 못합니다. 바꿔 말해 $i​$번째 관측치에 대응하는 라그랑지안 승수 $α_i​$가 0보다 커야 마진 결정에 유의미하다는 이야기입니다.

아울러 KKT 조건에 의해 해당 함수가 최적값을 갖는다면 아래 두 개 가운데 하나는 반드시 0입니다.

(1) $α_i$

(2) $y_i(w^Tx_i+b)-1$

$α_i$가 0이 아니라면 $y_i(w^Tx_i+b)-1$이 반드시 0입니다. 따라서 $x_i$는 plus-plane 또는 minus-plane 위에 있는 벡터가 됩니다. 이렇게 마진 결정에 영향을 끼치는 관측치들을 서포트 벡터(support vectors)라고 합니다. 아래 그림(출처)과 같습니다.

한편 $b$는 이미 구한 $w$와 학습데이터, $y_i(w^Tx_i+b-1)=0$ 식을 활용해 바로 구할 수 있게 됩니다. 새로운 데이터가 들어왔을 때는 해당 관측치를 $y_i(w^Tx_i+b-1)$에 넣어서 0보다 크면 1, 0보다 작으면 -1 범주로 예측하면 됩니다.

이번 글에서는 회귀계수들에 제약을 가해 일반화(generalization) 성능을 높이는 기법인 Regularized Linear Regression에 대해 살펴보도록 하겠습니다. 이번 글 역시 고려대 김성범 교수님, 같은 대학의 강필성 교수님 강의, 미국 스탠포드 대학의 CS231n 강의 노트 일부를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

정규화의 목적

정규화(regularization)란 회귀계수가 가질 수 있는 값에 제약조건을 부여하는 방법입니다. 미래데이터에 대한 오차의 기대값은 모델의 Bias와 variance로 분해할 수 있는데요. 정규화는 variance를 감소시켜 일반화 성능을 높이는 기법입니다. 물론 이 과정에서 bias가 증가할 수 있기는 하지만요. 정규화의 이론적 배경인 Bias-Variance Decomposition에 대해 살펴보시려면 이곳을 참고하시기 바랍니다.

정규화의 결과를 직관적으로 나타낸 그림은 아래와 같습니다. 하단좌측 그림은 학습데이터를 정말 잘 맞추고 있지만, 미래 데이터가 조금만 바뀌어도 예측값이 들쭉날쭉할 수 있습니다. 반면 우측 그림은 가장 강한 수준의 정규화를 수행한 결과인데요. 학습데이터에 대한 설명력을 다소 포기하는 대신 미래 데이터 변화에 상대적으로 안정적인 결과를 냅니다.

일반 선형회귀 모델

정규화는 일반 선형회귀 모델(Ordinary Linear Regression Model)에서 도출된 회귀계수들에 제약을 가하는 방법론입니다. 일반 선형회귀 모델은 종속변수($y$)의 실제값과 모델의 예측값 사이의 평균제곱오차(Mean Square Error)를 최소화하는 회귀계수들의 집합을 가리킵니다. 이러한 회귀계수를 뽑는 데 쓰는 기법을 최소자승법(Least Squares Method)라고 합니다.

우리가 가진 학습데이터의 독립변수가 $k$개, 관측치가 $n$개라고 칩시다. 그러면 이로부터 도출할 수 있는 일반 선형회귀 모델을 행렬 형태로 나타내면 다음과 같습니다. 아래 행렬에서 1은 회귀모델의 상수항에 대응하는 값입니다.

[\begin{bmatrix} \hat{ y }{ 1 } \ \hat{ y }{ 2 } \ … \\hat { y }{ n } \end{bmatrix}=\begin{bmatrix} 1 & { x }{ 11 } & … & { x }{ 1k } \ 1 & { x }{ 21 } & … & { x }{ 2k } \ … & … & … & … \ 1 & { x }{ n1 } & … & { x }{ nk } \end{bmatrix}\begin{bmatrix} { \beta }{ 0 } \ { \beta }{ 1 } \ … \ { \beta }{ k } \end{bmatrix}]

이를 행렬식으로 간단히 나타내면 다음과 같습니다. 독립변수로 구성된 행렬 $X$, 종속변수로 구성된 벡터 $y$는 우리가 이미 가지고 있는 학습데이터이고 벡터 y-hat은 모델이 예측한 값입니다. 회귀계수 벡터 $β$가 모델 구축 결과물입니다.

[\hat { y } =X \beta]

최소자승법은 실제값과 예측값의 MSE를 최소화하도록 합니다. 아래와 같이 쓸 수 있습니다.

[\begin{align} { \hat { \beta }^{ LS } } &=\min _{ \beta }{ { (y-\hat { y } ) }^{ T }(y-\hat { y } ) } \ &=\min _{ \beta }{ { (y-X\beta ) }^{ T }(y-X\beta ) } \end{align}]

최소자승법의 해인 회귀계수 벡터 $β$는 위 식을 $β$로 미분한 식을 0으로 놓고 풀면 다음과 같이 명시적으로 구할 수 있습니다.

[{ \hat { \beta }^{ LS } } ={ ({ X }^{ T }X) }^{ -1 }{ X }^{ T }y]

이렇게 구한 $β$는 bias가 없는 추정량 가운데 variance가 가장 작다고 합니다. 이름하여 Best Linear Unbiased Estimator(BLUE)입니다. 앞으로 설명해드릴 정규화 기법들은 bias를 소폭 허용(희생)하면서 variance를 줄이는 방법론이라고 할 수 있겠습니다.

릿지회귀

릿지 회귀(Ridge Regression)란 평균제곱오차를 최소화하면서 회귀계수 벡터 $β$의 $L_2$ norm을 제한하는 기법입니다. 선형회귀 모델의 목적식(MSE 최소화)과 회귀계수들에 대한 제약식을 함께 쓰면 아래와 같습니다. 여기에서 $λ$는 제약을 얼마나 강하게 걸지 결정해주는 값으로 사용자가 지정하는 하이퍼파라메터입니다.

[{ { \hat{ \beta }^{ Ridge } } } =\arg\min _{ \beta }{ \left{ { (y-X\beta ) }^{ T }(y-X\beta )+\lambda { \beta }^{ T }\beta \right} }]

릿지회귀의 해인 회귀계수 벡터 $β$는 위 식을 $β$로 미분한 식을 0으로 놓고 풀면 다음과 같이 명시적으로 구할 수 있습니다.

[{ { \hat{ \beta }^{ Ridge } } } ={ ({ X }^{ T }X+\lambda I) }^{ -1 }{ X }^{ T }y]

평균제곱오차뿐 아니라 $β$의 $L_2$ norm 또한 최소화하는 것이 릿지 회귀의 목적입니다. 우선 아래 예시 표를 볼까요?

MSE 기준으로는 벡터 $β$의 첫번째 요소 $β_1$과 두번째 요소 $β_2$가 각각 4, 5여야 최소입니다. 일반 선형회귀 모델이었다면 (4,5)가 회귀계수로 결정됐을 겁니다.

하지만 여기에 $β_1^2+β_2^2$이 30 이하여야 한다는 제약을 가해 봅시다. 그러면 표 상단 세 가지 경우의 수는 고려에서 제외됩니다. 제약을 만족하는 나머지 세 개 가운데 MSE가 최소인 (2,4)를 회귀계수로 결정하는 것이 릿지 회귀의 방식입니다.

릿지회귀의 기하학적 이해

우리가 찾아야 하는 최적 회귀계수 벡터 $β$를 [$β_1, β_2$]라고 두겠습니다. 평균제곱오차를 식으로 쓰면 다음과 같습니다. (아래 식의 모든 요소는 스칼라값입니다)

[\begin{align} MSE({ \beta }_{ 1 },{ \beta }_{ 2 })=&\sum _{ i=1 }^{ n }{ { ({ y }_{ i }-{ \beta }_{ 1 }{ x }_{ i1 }-{ \beta }_{ 2 }{ x }_{ i2 }) }^{ 2 } } \ =&\left( \sum _{ i=1 }^{ n }{ { x }_{ i1 }^{ 2 } } \right) { \beta }_{ 1 }^{ 2 }+\left( \sum _{ i=1 }^{ n }{ { x }_{ i2 }^{ 2 } } \right) { \beta }_{ 2 }^{ 2 }+2\left( \sum _{ i=1 }^{ n }{ { x }_{ i1 }{ x }_{ i2 } } \right) { \beta }_{ 1 }{ \beta }_{ 2 }\&-2\left( \sum _{ i=1 }^{ n }{ { y }_{ i }{ x }_{ i1 } } \right) { \beta }_{ 1 }-2\left( \sum _{ i=1 }^{ n }{ { y }_{ i }{ x }_{ i2 } } \right) { \beta }_{ 2 }+\sum _{ i=1 }^{ n }{ { y }_{ i }^{ 2 } } \end{align}]

위 식을 자세히 보시면 MSE는 $Aβ_1^2+Bβ_1β_2+Cβ_2^2+Dβ_1+Eβ_2+F$ 형태의 원추곡선(conic equation)이 됩니다. 타원, 쌍곡선, 원, 포물선은 원추곡선의 특수한 경우에 해당하는데요. 판별식 $B^2-4AC$이 0보다 작으면 타원 형태가 된다고 합니다. 위 식에서 판별식을 계산해 보면 코시-슈바르츠 부등식 조건에 의해 0 이하가 됩니다.

따라서 MSE가 같은 [$β_1, β_2$]의 자취를 그려보면 타원 모양이 된다는 겁니다. 바로 아래 그림처럼요.

좌측상단 그림에서 타원 모양의 녹색 실선은 MSE가 동일한 [$β_1, β_2$]의 자취입니다. $β^{LS}$라고 표시된 검정색 점은 일반 선형회귀 모델의 결과로, MSE가 최소가 되는 지점입니다. 여기에서 멀리 떨어져 있는 타원일 수록 MSE가 점점 커진다고 이해하면 좋을 것 같습니다.

좌측상단 그림에서 파란색 원은 $β$의 $L_2$ norm이 동일한 [$β_1, β_2$]의 자취입니다. 원의 반지름이 작아질 수록 $L_2$ norm이 감소하고, 그만큼 제약이 커진다고 이해하면 좋을 것 같습니다. 다시 말해 하이퍼파라메터 $λ$가 클수록 $β$의 $L_2$ norm이 줄어듭니다.

우리가 특정 $λ$을 지정해 $β_1^2+β_2^2$이 $t_3$ 이하가 되도록 제약을 가했다고 가정해 봅시다. 그러면 릿지 회귀 기법은 이러한 제약을 만족하면서도 MSE가 최소인 지점에 해당하는 [$β_1, β_2$]를 찾게 됩니다. 위 예시 기준으로는 $β^{LS}$라고 표시된 검정색 점과 가장 가까운 점이 릿지 회귀의 결과가 될 겁니다.

하이퍼파라메터 $λ$를 0으로 두면 릿지 회귀의 제약식($λβ^Tβ$)이 사라지기 때문에 일반 선형회귀 모델의 결과와 동일한 회귀계수들을 얻을 수 있습니다. 하지만 $λ$가 커질수록(=$t$가 작아질수록) 회귀계수들에 가해지는 제약이 커져서 계수들의 값이 점점 줄어드는 모습을 우측상단 그래프에서 확인할 수 있습니다.

마지막으로 릿지회귀에서의 ridge는 산등성이라는 뜻을 가졌는데요. 위 그림에서처럼 MSE와 제약식이 가지는 자취가 산등성이 모양을 지녀서 이런 이름이 붙은 것 아닌가 생각합니다.

라쏘회귀

라쏘회귀(Least Absolute Shrinkage and Selection Operator)의 목적식과 제약식을 한번에 쓰면 다음과 같습니다. 릿지회귀와 동일하지만 $L_1$ norm을 제약한다는 점이 다릅니다.

[{ { \hat { \beta } ^{ Lasso } } }=\min { \beta }{ \left{ { (y-X\beta ) }^{ T }(y-X\beta )+\lambda { \left| \beta \right| }{ 1 } \right} }]

요소 개수가 $p$개인 회귀계수 벡터 $β$의 $L_1$ norm은 각 요소에 절대값을 취한 뒤 모두 더해 구합니다. 아래와 같습니다.

$L_1$ norm은 미분이 불가능하기 때문에 라쏘회귀의 경우 해를 단박에 구할 수 없습니다. 이 때문에 numerial 기법들이 다양하게 제시됐습니다.

라쏘회귀의 기하학적 이해

우리가 찾아야 하는 최적 회귀계수 벡터 $β$를 [$β_1, β_2$]라고 두고, 이를 그림으로 나타내면 다음과 같습니다.

MSE가 동일한 [$β_1, β_2$]의 자취는 릿지회귀 때와 마찬가지로 타원입니다. 제약식은 $L_1$ norm(절대값)을 썼기 때문에 $L_2$ norm이 동일한 [$β_1, β_2$]의 자취는 마름모 꼴이 됩니다.

파란색 마름모 꼴의 제약 범위 내에서 MSE가 최소인 점은 $β_2$축 위의 검정색 점입니다. 이 점은 바로 $β_1=0$인 지점인데요. $β_1$이 0이라는 이야기는 그에 대응하는 독립변수 $x_1$이 예측에 중요하지 않다는 말과 같습니다.

이처럼 라쏘회귀는 예측에 중요하지 않은 변수의 회귀계수를 감소시킴으로써 변수선택(Feature Selection)하는 효과를 낸다고 합니다.

엘라스틱넷

엘라스틱넷(Elastic Net)은 제약식에 $L_1, L_2$ norm 모두 쓰는 기법입니다. 목적식과 제약식을 한번에 쓰면 다음과 같습니다.

[{ { \hat { \beta } ^{ enet } } }=\min { \beta }{ \left{ { (y-X\beta ) }^{ T }(y-X\beta )+{ \lambda }{ 1 }{ { \left| \beta \right| }{ 1 }+\lambda }{ 2 }{ \beta }^{ T }\beta \right} }]

릿지회귀 vs 라쏘회귀 vs 엘라스틱넷

세 가지 방법을 비교한 표는 다음과 같습니다.

세 기법의 제약식의 자취를 그림으로 나타내면 아래와 같습니다. (녹색 점선=릿지회귀, 검정색 점선=라쏘회귀, 파란색 도형=엘라스틱넷)

기타 정규화 기법들

인접한 변수들을 동시에 선택하는 Fused Lasso, 사용자가 정의한 그룹 단위로 변수를 선택하는 Group Lasso, 사용자가 정의한 그래프의 연결 관계에 따라 변수를 선택하는 Graph-Constrained Regularization 등이 있습니다.

딥러닝과의 연계

이미지가 주어졌을 때 해당 이미지가 고양이인지 개인지 배인지를 맞추는 문제를 푼다고 칩시다. 다음과 같이 다범주 선형회귀 모델을 만들 수 있습니다.

여기서 하나 상상해 봅시다. 만약 입력데이터 $x$가 [1, 1, 1, 1]이고 cat score를 만드는 데 쓰이는 가중치 벡터($W$의 첫 행벡터) $w_1$이 [1, 0, 0, 0]이라 칩시다. dog score를 만드는 가중치 벡터 $w_2$는 [0.25, 0.25, 0.25, 0.25]라 칩시다. 이렇게 되면 $w_1x=w_2x=1$이 되어 같은 결과를 냅니다. 다만 차이가 있습니다. $w_1$은 데이터의 특정 영역만 보고 dog인지 판단한다면, $w_2$는 데이터를 전체적으로 보고 판단한다는 겁니다.

이번엔 ship score를 내는 $w_3$가 [2, 2, 2, 2]라고 칩시다. $w_3x=8$이 되어 최종적으로 이 그림이 ship으로 분류되게 됩니다. 그런데 이렇게 되면 ship이라는 클래스가 cat이나 dog보다 더 큰 영향력을 발휘하게 되어 결과적으로 미지의 데이터에 대한 일반화 성능이 떨어지게 됩니다(어떤 그림이 들어와도 ship이라고 분류). 손실 최소화와 동시에 정규화(regularization)를 하는 이유입니다. 위 예시에서 $w_1$의 L2 norm은 1, $w_2$는 0.25, $w_3$은 16입니다.