coursera

Quicksort 퀵정렬의 기본 개념은 다음과 같습니다. 우선 배열을 무작위로 섞고, 좌우 구간으로 나눕니다. 하나(i)는 왼쪽에서 오른쪽으로 이동하고, 나머지(j)는 오른쪽에서 왼쪽으로 이동합니다. i는 기준(partitioning element)보다 큰 값이 나오면, j는 기준보다 작은 값이 나오면 이동을 멈춥니다. 두 값을 교환합니다. 위 과정을 반복합니다. 퀵정렬은 합병 정렬이 그 자체로 수행되기 전에 분할하는 것과 달리, 퀵정렬은 분할마다 정렬이 수행된다는 차이점이 있습니다. Quicksort partitioning demo Quicksort: Java code for partitioning, Java implementation def partition(a, lo, hi): i, j = lo, ..

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..