나의 큰 O는 log x야

상속은 객체지향 프로그래밍의 꽃이라고 할 수 있습니다. 상속을 통해 공통되는 코드를 통합하고, 다형성을 확보하는 등 다양한 작업이 가능하지요. C++에서는 일반적으로 클래스와 가상 함수, 상속이라는 문법적 장치를 통해 이러한 개념들이 구현됩니다. 어떤 Data에 대한 처리를 수행하는 클래스 ModelA이 있다고 생각해봅시다. struct Data { int foo, bar; }; class ModelA { std::vector myData; public: virtual void loadData() { // myData에 값들을 채워넣는다~~ } virtual void work() { // myData를 가지고 어떠한 처리를 한다~~ } void loadAndWork() { loadData(); work(..

프로그래밍/테크닉 2019. 3. 7. 20:41

sigmoid 함수는 연속이고 미분가능하면서 비선형이라는 특징 덕분에 여러 기계 학습 및 신경망에 두루 쓰이는 함수이죠. 최근에 word2vec을 확장한 모형을 공부하면서 목적함수에 log sigmoid를 잔뜩 사용하는 코드를 구현한 적이 있었는데, log sigmoid 계산 비용이 꽤나 컸기에 전반적인 속도 향상에 어려움이 있었습니다. 그래서 Look Up Table을 이용해 최적화를 실시했었는데 그 결과를 포스팅으로 공유하고자 합니다. 먼저 log sigmoid 함수는 다음과 같이 정의됩니다. 이름처럼 sigmoid 함수에 log를 취한 형태이구요, 그 그래프 모양은 다음과 같습니다. 전 범위에서 음수 값을 가지며, x > 0일는 그 값이 0에 극도로 가까워집니다. 이 함수를 계산하기 위해서는 exp..

프로그래밍 2019. 1. 2. 01:26

최근 Kiwi 형태소 분석기 0.6 버전 업데이트를 실시했습니다. 사실 엄청 바뀐건 없고, 이전 버전에서 사용하던 최적화를 좀더 한 단계 끌어올리는 작업을 수행했습니다. 0.4버전에서 도입한 그래프 기반 경로 탐색 알고리즘의 경우, 이상하게도 끝쪽에서 앞쪽으로 분석을 진행했습니다. 당시에 왜 이렇게 설계했는지 모르겠는데, 개발하고 보니, 역방향으로 추적을 진행하더라구요. 사실 경로 탐색을 진행하는게 순방향인지 역방향인지 자체는 성능에 영향을 미치지 않습니다만, n-gram 언어모델을 캐싱하는데에는 순방향이 훨씬 유리합니다. 0.5버전에서 Kneser-Ney smoothing을 적용한 n-gram 언어 모델을 바탕으로 형태소가 출현할 확률을 계산하도록 알고리즘을 교체하였는데요, 이게 약 2만 여개의 형태소..

프로그래밍/NLP 2018. 12. 9. 23:23

프로그래밍을 하다보면 클래스나 구조체의 내용물을 그대로 파일에 저장하거나, 파일로부터 읽어와야 할 경우가 생깁니다. 구조가 있는 객체의 내용물을 바이트 배열로 저장하는 것을 직렬화(Serialization)이라고 하고, 반대로 바이트 배열로부터 내용물을 읽어와 객체에 채우는 것을 역직렬화(Deserialization)라고 합니다.Java나 C#과 같은 여러 언어에서는 직렬화 기능을 언어차원의 라이브러리로 지원해주는 경우가 많습니다. 따라서 클래스나 구조체의 내용물을 저장하는데에 어려움을 겪지 않죠. 하지만... 당연하게도 C++에서는 언어 자체적으로 그런 기능을 지원하진 않습니다. 직렬화가 하고싶으시다면 직접 짜시면 됩니다. (어떻게 보면 그게 C++의 매력이라고 할수도 있겠죠...?) 사실 이런 꼭 필..

프로그래밍/테크닉 2018. 10. 5. 18:10

2013년 등장한 Word2Vec은 강력한 단어 임베딩 기법입니다. 의미적으로 유사한 단어를 벡터 공간 상에 가까운 위치에 배치시키도록 학습하는 신경망을 이용해서 성공적으로 단어를 임베딩시켰습니다. 유사한 단어가 유사한 위치에 배치된다는 특징 덕분에 여러 자연언어처리 기법에서 이미 널리 쓰이고 있는데요, 사실 이 기법에는 한가지 약점이 있습니다. 오직 단어의 형태로만 단어를 구분하기 때문에 형태가 같아도 의미가 전혀 다른 단어를 구분해내지 못한다는 것입니다. 예를 들어 한국어 단어 '밤'을 생각해봅시다. 해 진 이후의 시간대를 뜻하는 '밤'과 견과류의 일종인 '밤'이 같은 형태로 적히기 때문에 Word2Vec은 학습과정에서 두 단어를 동일한 단어로 간주하고 처리합니다. 실제로 두 단어는 다른 단어인데 말..

프로그래밍/NLP 2018. 9. 23. 03:38

르장드르 다항식은 [-1, 1] 구간에서 직교(orthogonality)하는 다항식들의 집합을 가리킵니다. 다항식들간에 서로 직교하면서, 간단하게 곱셈과 덧셈만으로 계산이 가능하다는 특징 덕분에 물리학이나 공학 등의 분야에서 특정 상태를 근사하여 풀 때 직교 기저로 자주 사용합니다. 저 역시도 최근 연구에서 임의의 모양을 띈 다차원 공간의 함수를 근사하기 위해서 이 다항식을 사용했는데요, 이를 위해서 르장드르 다항식을 구현하여 L-BFGS 함수식에 넣어 그 값을 계산해야 할 일이 있었습니다.이 다항식은 재귀적 방법이나 조합식을 이용하여 쉽게 계산될 수 있지만, 이를 매번 함수 값을 구할때마다 반복할 수 없으므로 컴파일 타임에 처리하고자 템플릿 메타 프로그래밍(template meta programming..

프로그래밍/테크닉 2018. 7. 8. 18:26

지난 몇년간 CPU의 성능은 반도체 공정의 향상과 그로 인한 클럭 상승에 따라서 줄곧 높아져왔습니다. 무어의 법칙이 잘 작동하던 2000년대 초반까지는 프로그램 코드를 고치지 않아도 CPU의 클럭 상승으로 자동으로 프로그램의 성능도 높아져올 수 있었습니다. 그러나! 공정 미세화가 차츰 둔해지고, 집적화로 인한 발열을 감당할 수 없게 되자 CPU업계는 CPU의 발전 방향을 약간 틀었는데요, 1) 단일 코어의 성능을 향상시키기보다, 코어의 수를 늘리는 쪽으로, 2) 명령어 수준의 병렬성을 높여 최대한 효율적으로 연산을 처리하는 쪽으로 말이죠.1번은 멀티 스레딩 프로그래밍을 촉발시켰습니다. 기존의 알고리즘들을 병렬화하는 방향으로 코드를 수정함으로써 프로그램의 성능을 높일수 있게된 것입니다. 깁스 샘플링 알고리..

프로그래밍 2018. 5. 6. 19:52

속도가 만족할 만큼 나오지 않아서 아쉽길래 한동안 접어두고 있었는데, 갑자기 좋은 아이디어가 떠올라서 업데이트를 해보았습니다. 약간의 알고리즘 수정으로 최소 +50%~200%의 속도 향상을 달성할 수 있었는데, 기록하지 않고 넘어가기에 너무 아까워서 포스팅을 써보았습니다. 0.3버전까지 방법이전 포스팅에서도 간단히 적었듯이 형태소 분석기의 핵심은 마르코프 연쇄입니다. 각각의 형태소가 등장할 확률 및 한 형태소 다음에 다른 형태소가 등장할 확률을 계산해서, 그 확률이 가장 높은 형태소열을 찾는것이 형태소 분석기의 업무라고 할 수 있습니다. 원활한 이해를 위해 다음 예시를 들어보죠. 먹었다 위 단어를 분석한다고 해봅시다. 어떤 형태소가 들어갈 수 있는지 일단 나열해보자면, 다음과 같을 겁니다. 먹었다 먹/V..

프로그래밍/NLP 2017. 9. 11. 02:59