전체 글

Analogies 벡터는 특정 차원 내의 한 점을 가리키는 화살표로 이해할 수 있습니다. 따라서 두 벡터 간의 차를 통해 다른 벡터 간의 특징을 유추할 수 있습니다. 예를 들어 man-woman의 차이를 생각해보면 성별이 반대라는 특징을 얻을 수 있죠. 이런 차이는 king-queen에서도 똑같이 드러날 것입니다. Analogies using word vetors 그래서 만약 man-woman과 유사한 관계에 있는 king의 짝꿍을 찾는다고 한다면 위와 같은 sim(유사도) 공식을 이용할 수 있습니다. 유사도가 가장 높은(arg max) 원소를 찾는 방식을 이용하는 것이죠. 이는 2차원 공간으로 시각화했을 때를 생각해보면, 두 벡터 간의 차이를 나타내는 화살표(벡터)가 가장 유사한 것이 무엇인지 찾는 과..

Named entity recognition example One-hot encoding 대신 word embedding을 활용할 수 있는 예시인 NER 태스크입니다. 이때는 학습된 word embedding을 이용하여 심지어 처음 보거나 익숙하지 않은 단어, 혹은 문구까지도 처리할 수 있습니다. 예를 들어 우리가 학습시킨 단어 중에 durian, cultivator라는 단어가 없었다고 하더라도, 이들이 위치하는 자리의 특성을 파악하여 durian은 과일, cultivator는 직업 중 하나로 인지할 수 있다는 뜻입니다. Transfer learning and word embeddings 여기에는 Transfer learning(전이 학습)의 개념이 적용되는데 그 원리 자체는 엄청 간단합니다. 우선 대량..

Word representation 만약 지금까지 공부했던 것처럼 각 단어를 one-hot vector로 나타내게 되면 단어 간의 특징을 파악할 수 없게 됩니다. 예를 들어 apple과 orange의 경우 둘 다 과일이면서 굉장히 유사한 특성을 지니겠죠. 하지만 위 상황에서는 어떤 두 벡터를 dot product(내적)하더라도 그 결과가 0입니다. 즉 유사도가 0이라는 뜻이죠. 따라서 orange와 king, orange와 apple을 비교하더라도 의미가 없기 때문에, 각 단어(token)가 지니는 특징이 추출되기 어렵다는 문제점이 존재합니다. 그렇기 때문에 apple 뒤에도 juice가 오겠구나 예측하는 것이 불가능하죠. Featurized representation: word embedding 위에서..

comparator는 comparable과 비교되는 자바의 인터페이스로 제가 이해하기엔 좀 어렵네요. 당장 자바로 알고리즘을 풀이할 것도 아니라서 과감히 패스하겠습니다! Stability 때로는 정렬 기준(key)이 여러 개가 될 수도 있습니다. 예를 들어 이름을 기준으로 정렬한 다음, 2번째 열의 숫자를 기준으로 정렬하고 싶을 수도 있다는 것이죠. 하지만 두 번째 열을 기준으로 정렬하는 순간 이름 기준의 정렬이 깨지는 것을 원하지 않을 수도 있습니다. 즉, 두 번째 정렬을 수행하더라도 기존의 정렬이 유지되길 원하는 경우 어떻게 이를 구현할 수 있을까요? Stability: insertion sort 삽입 정렬은 정렬이 수행되는 매 스텝(i)에서 이전에 정렬된 것들은 건드리지 않습니다. 비교 대상이 더 ..

Complexity of sorting 정렬 알고리즘의 계산 복잡도를 정리하는 내용입니다. 상한선은 당연히 최대치/최악의 경우를 나타내고 있으므로 guarantee라는 표현이 쓰였습니다. 하한선은 이보다 더 좋을 수 없는 최선의 경우가 증명된 것을 뜻합니다. 최적 알고리즘은 X라는 문제에 대해 최선의 것으로 증명된 경우에 해당하며 상한선과 하한선 사이에 위치합니다. Decision tree (for 3 distinct a, b, and c) 의사 결정 나무를 통해 정렬에 대한 결정을 시각화할 수 있습니다. 여기서는 각 비교를 합쳐 맨 마지막에 세 개의 값을 비교한 결과물을 얻어낼 수 있음을 보여주고 있습니다. 트리의 높이는 비교를 가장 많이 해야 하는 최악의 경우를 뜻하게 됩니다. Compare-base..

Two classic sorting algorithms 지금까지 배웠던 정렬들과 달리, 앞으로 배울 두 정렬인 '병합 정렬'과 '퀵 정렬'은 엄청나게 효율적이고 지금까지도 널리 쓰이는 공신력 있는 알고리즘입니다. Mergesort 병합 정렬의 기본 아이디어는, 배열을 반으로 쪼개고 그 결과를 합치는 작업을 재귀적으로 반복하는 것입니다. Abstract in-place merge demo 캡쳐본이라 영상이 아니지만, 방법은 이렇습니다. 우선 맨 처음의 배열을 복사한 aux 배열을 생성합니다. 그리고 이를 반으로 쪼개어 왼쪽의 첫 번째, 오른쪽의 첫 번째 원소에 인덱스 i, j 를 부여합니다. 그리고 오리지날 배열의 첫 번째 인덱스는 k가 됩니다. i, j 를 비교하여 더 작은 것을 k 자리에 넣고 k는 1..