Introduction Word2Vec에서 weight를 학습하기 위해서 마지막에 Softmax function을 사용한다. 이때 Skip-gram에서 사용하는 softmax function은 다음과 같이 정의된다 : $$ p(w_O | w_I) = {{ \exp{\left( {v'_{w_O}}^T v_{w_I} \right)} } \over { \sum^W_{w=1} \exp{\left( {v'_{w}}^T v_{w_I} \right)}} } $$ 이때 분모는 corpus 안에 있는 모든 단어들을 대상으로 inner product를 하는 것이다. 보통 $W$는 $10^5-10^7$ 사이의 값이므로 대단히 computationally expensive하다. time complexity는 $O(W)$이다...

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 아주 기초적인 MST 문제다. 별자리들의 좌표를 받아서 별들 사이의 거리를 저장해서 prim's algorithm으로 풀든지 kruskal's algorithm으로 풀던지 하면 된다. 나는 kruskal's algorithm으로 풀었다. N이 매우 작기 때문에 시간은 크게 고려하지 않아도 된다. time complexity를 따지자면, $O(N^2 \log{N} * \alpha)$ 정도일듯. 두 n..

인류의 지식축적과 그로 말미암은 기술발전은 인간을 풍요롭게 한 적이 없다. 신기술의 유일한 책무는 인류의 인구 수용능력을 향상시키는 것이다. 인류가 위기에 직면하면, 인구 성장은 지체되었고, 지식으로 이를 돌파하면 새로운 국면이 접어들 때까지 인구는 폭발적으로 성장하였다. 이때 개인의 관점에서 바라본 세계는 무한에 가까운 개체들이 끊임없이 발생하고 소멸하는 번잡스럽고 혼미한 관경이다.[1] 인간의 대량생산과 대량사망이 동시에 이루어지는 대혼란의 중심에서 개인의 목가는 애초부터 어불성설이다. 불연속적인 개체는 짧은 생애 기간 동안 아무것도 이룰 수 없고, 조금이나마 축적한 무엇이라도 죽음과 함께 영원히 소멸한다. 죽음은 절대적 손실을 의미한다.[2] 혼미의 급류에서 고고하게 무위하지 않을 수 있는 것은 연..

에로스는 전근대사회까지 타동사의 영역으로 남아있었다는 점에서 독특한 욕망이다. 각 개인은 다른 개인에 의해 욕망의 대상이 될 기대를 가졌었다. 그러나 이 양상은 근대사회로 접어들며 해체되었다. 마르크스Karl Marx가 지적했듯, 자본주의 사회는 모든 관계를 금전적으로 환원시켰다. 이에 더해, 사회관계망의 발달과 인구 수 증가는 각자의 상대방을 유일무이한 선택지가 아니라 무한대의 선택지 중 가장 경제적인 선택으로 전락시켰다. 상대로부터의 피선택(被選擇)도 모순적이게도 피동적으로 이루어지는 것이 아니라 연애시장 풀 내에서 본인을 상품화하여 전시하는 능동적인 판매로 달성된다. 상품의 광고를 위해 후기근대사회까지도 완고한 비밀로 남아있던 프라이버시의 영역까지 인터넷 상에 공공연하게 전시된다. 정보가 지나치게 ..

Decision Tree Training은 가장 널리 사용되는 machine learning 방법론 중 하나이다. 이 중 자주 사용되는 것은 ID3, ASSISTANT, C4.5가 있다. 여기서는 ID3의 간략한 소개와 ID3의 pruning 방법 중 하나인 Reduced Error Pruning에 대해서 다루어보고자 한다. Decision Tree의 간략한 소개 Decision Tree는 학습에 Tree 형태의 decision tree를 사용한다. 다음과 같은 모양이다. 전체 형태를 보면 맨 위의 root node, 중간의 branch node, 말단의 leaf node로 구성되어 있다. 말단 노드인 leaf node에 class label이 붙어 있는 것을 알 수 있고, branch node는 특성들..

IntroductionK-S test는 두 가지 경우에 사용된다. 첫 번째는 추출한 샘플들이 특정한 probability distribution을 따를 것인지를 확인하는 것이고(one-sample K-S test), 두 번째는 두 개의 sample 집합을 보고 같은 probability distribution에서 추출되었는지를 확인하는 것이다(two-sample K-S test). K-S test는 non-parametric test이다. 두 함수가 continuous한 경우나 discrete한 경우 모두 사용할 수 있다. continuous한 경우에는 CDF(cumulative distribution function)을 사용하고, discrete한 경우에는 EDF(Empirical distributio..

Guassian elimination와 upper triangular matrix non-singular $3 \times 3$ matrix $A$가 row exchange없이 upper-triangular matrix $U$로 변환 가능하다고 하자. 예를 들어 다음의 matrix $A$가 있다. $$ A = \begin{bmatrix} 2 & 1 &1 \\ 4 & 3 & 7 \\ -2 &1 & 3 \end {bmatrix} $$ 이 matrix에 대한 equation $Ax=b$가 다음과 같다. $$\begin{align} Ax &= b\\ \begin{bmatrix} 2 & 1 &1 \\ 4 & 3 & 7 \\ -2 &1 & 3 \end {bmatrix} \begin{bmatrix}u \\v\\w \..

Matrix Multiplication 두 matrix $A$, $B$를 곱하는 상황을 생각해 보자. 이때 matrix $A$는 $2 \times 2$ 인 square matrix이고, $B$는 $2 \times 3$인 rectangular matrix이라고 하자. 즉, 다음과 같다. $$ A = \begin{bmatrix} 2 & 3 \\ 4 & 0 \end{bmatrix} \text {, } B = \begin{bmatrix} 1 & 2 & 0 \\ 5 & 1 & 0 \end{bmatrix}$$ 이때 두 matrix의 multiplication은 다음과 같이 될 것이다. $$ AB = \begin{bmatrix} 2 & 3 \\ 4 & 0 \end{bmatrix} \begin{bmatrix} 1 & ..

RNN(Recurrent Neural Network) Sequential data 일반적으로 deep neural network에서는 input과 output이 하나의 vector인 one-to-one으로 이루어진다. 하지만 어떤 경우에는 sequential data가 input이나 output에 포함되는 경우가 있다. 예를 들어 stochastic process(time series)나 ordered data structures가 있다. speech recognition이 time series에 해당하는 주요 예시가 될 것이고, machine translation이 ordered data structure의 예가 될 것이다. 이런 경우에 one-to-many나 many-to-many, many-to-o..