Abstract Propose two model architrectures for computing continuous word vector (CBOW, Skip-Gram) Propose two modified NNLM model using binary tree Introduce new method to measure word similarity Show that newly introduced models can be trained on very large model (reduced time complexity) Previous Works 기존에 있었던 word vector 학습 모델은 크게 두 가지로 나눌 수 있었다. 1. SVD(Singular Value Decomposition) 기반 모델 LSD(..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 수 하나를 집어넣고 median값을 물어보는 query가 있을 때, 100000번의 query를 어떻게 0.1s(1e7번 내외의 iteration) 안에 처리할 것인가 하는 문제이다. query의 개수를 $N$이라고 하고$(N \leq 100000)$, 정수의 범위를 $M$이라고 하자. $(M \leq 20000)$ 처음에 떠올릴 수 있는 방법은 linked list로 수를 집어넣..

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가 지적했듯, 자본주의 사회는 모든 관계를 금전적으로 환원시켰다. 이에 더해, 사회관계망의 발달과 인구 수 증가는 각자의 상대방을 유일무이한 선택지가 아니라 무한대의 선택지 중 가장 경제적인 선택으로 전락시켰다. 상대로부터의 피선택(被選擇)도 모순적이게도 피동적으로 이루어지는 것이 아니라 연애시장 풀 내에서 본인을 상품화하여 전시하는 능동적인 판매로 달성된다. 상품의 광고를 위해 후기근대사회까지도 완고한 비밀로 남아있던 프라이버시의 영역까지 인터넷 상에 공공연하게 전시된다. 정보가 지나치게 ..