알고리즘

제네릭 프로그래밍

제네릭 프로그래밍이란 대부분의 일반적인 설정에서 효율 저하 없이 작동할 수 있도록 알고리즘과 자료구조를 설계하는 데 초점을 맞춘 프로그래밍에 대한 접근법이다. (알고리즘 산책, 2015)

크리스마스 강연

2008년, 나는 1826년 마이클 패러데이가 첫 연사로 나선 왕립 연구소 크리스마스 강연(Royal Institution Christmas Lectures)의 180번째 연사로 선발되는 행운을 누렸다. 2008년 당시 나의 강연은 컴퓨터과학이란 주제로 진행된 최초의 강연이었다. 강연을 준비하며 컴퓨터과학을 일반 대중에게 설명할 방법을 고심하느라 많은 시간을 쏟았지만, 활용할 자료가 거의 없고 이런 필요를 다루는 대중 서적 또한 거의 전무하다는 사실을 깨달았다. 따라서 금번 맥코믹의 새 책 출간은 내겐 더욱 환영할 만한 일이다. (미래를 바꾼 아홉 가지 알고리즘, 2011)

크리스 비숍이 추천사에서 언급한 2008년 강연 영상

P-NP

  • P: Polynomial Time 다항식 시간 동안 ‘답을 해결할 수can provide an answer 있는’ 문제. 해결 문제.
  • NP: Non-deterministic Polynomial Time 다항식 시간 동안 ‘주어진 답이 맞는지 확인할 수can be verified 있는’ 문제. 검산 문제.

NP는 하나의 경우에 대해서 옳은지 그른지 보는 것이고, P는 해답이 되는 경우를 찾을 때 까지 모든 경우에 대해 옳고 그름을 따지는 것. P-NP 문제의 가장 중요한 쟁점은 수학적 귀납법으로 경우의 수를 P의 영역으로 넣을 수 있는지의 여부를 묻는 것으로 볼 수 있다. 대표적인 예로, 정렬 문제의 경우 경우의 수가 \(n!\) 이지만, 이미 수학적 귀납법으로 \(O(n^2)\) 나아가 \(O(n\log{n})\)으로 수렴된 바 있다. ref

A polynomial is a linear combination of terms that look like Constant * x^k. On the opposite, exponential means something like k^x, where in both case k is a constant and x is a variable. ref

Big O

Big-O 표기법은 다음 수식으로 표현될 수 있다.

O(f(n)) = s + C * f(n) + t

s는 작업 준비 시간이고, C는 비례 상수, t는 작업 정리 시간이다. 어떤 알고리즘에는 s, C, t들이 굉장히 큰 값일 수 있는데, 그런 경우 s+tC*f(n)을 압도할 수 있다. (전문가를 위한 C++, 2011)

Viterbi algorithm

mini example를 구현했다. \delta_3 의 값이 A, B 모두 잘못되어 있으며, (5) 수식이 잘못 표기되어 있다.

알고리즘을 Python으로 구현했을때, brute force 방식으로 전부 계산했을때 맥북 기준 30초가 넘어간다. DP를 적용해 max_delta_tr를 구하여 \psi를 위한 max 값을 기억하며 풀 경우 7초가 걸렸다.

성능 개선을 위해 동일한 알고리즘을 C++로 구현해봤는데, 65초로 훨씬 늦다. CPU 사용률은 100%를 넘지 못하며 이는 Python도 마찬가지다. 동일한 100%인데 일반적인 기대와 달리 심각한 성능 차이가 난다.

동일한 알고리즘을 Java로 구현하면 3초대에 실행된다. time값은 6.5초 정도가 출력된다.

6.46s user 1.17s system 167% cpu 4.561 total

Java는 별도 처리를 하지 않았음에도 불구하고 CPU 사용률이 180%를 넘어간다. CPU 코어를 고르게 활용하는 것으로 보이며 일부 null 처리를 하여 계산 횟수도 C++에 비해 조금 적긴 하나 이 부분이 중요한 것 같진 않다.

Java가 가장 빠르고 Python, C++ 순이다. 일반적으로 가장 빠를 것으로 예상되는 C++가 비교가 무색할 정도로 성능이 낮다. 멀티 쓰레딩으로 개선이 될 것으로 보이나 아쉽게도 시도 해보진 못했다.

언어 시간 CPU 연산
Python 2 16s 100% 1,869,188
Python 3 7s 100% 1,869,188
C++ 65s 100% 2,314,485
Java 3s 180% 2,095,600

Viterbi는 단순 행렬 연산의 반복이다. 논문과 달리 stack underflow를 방지하기 위해 log로 합산했으며, 0 일때도 이후 계산을 잇기 위해 라플라스 스무딩 처리를 했다.

C++에서 std::mapstd::unordered_map으로 바꾸는 것만으로 한 문장에 7.38s가 걸리던 것을 2.55s로 줄일 수 있었다. 34% 수준으로 줄었으므로, 위 결과는 22s가 될 것으로 예상된다. 물론 그래도 느리기 때문에 좀 더 최적화는 필요하다.

String Manipulation

Aho Corasick

아호 코라식 알고리즘은 finite set of strings의 요소를 찾는 일종의 사전-매칭 알고리즘으로, 동시에 모든 문자열을 찾는다.

문자열은 중복 순열Permutations with repetition이므로 \({k^n}\) 가 가능하다. (k elements, length n) 모든 위치에 가능하므로 문장의 길이인 (256 - 패턴 길이 n) * 패턴의 갯수 1,000,000개를 분자로 하여 \({k^n}\) 분모로 나누면 매칭 확률을 구할 수 있다. C++구현에 버그가 있었고 직접 패치했다.

첫 실행시 트라이tries를 메모리에 읽어들이는 시간이 다소 걸리지만 이후 문장 부터는 비교가 필요 없을 정도로 빠른 성능을 보여준다. 대부분의 문장이 1~2ms 이내에 처리된다.

무작위성

가상의 동전 던지기를 수백만 번 했을 때의 결과처럼 편향이 없고 패턴이 나타나지 않는 난수를 컴퓨터나 기계장치로 만들어내는 것은 극히 어렵다. (뉴욕타임스 수학, 2013, 1988년 기사) 도널드 커누스의 책 『The Art of Computer Programming』 에서도 random에 대해 여러 챕터를 할애한다.

기타

DNA 프로파일링은 복잡함으로 인해 Approximation Algorithm 근사 알고리즘 사용 (넘버스, 2017)

Books

알고리즘이 당신에게 이것을 추천합니다 2016, 2018

  • 계산
    1985년에서 2005년까지 20년 동안 컴퓨터 프로세서는 4000배 더 빨라졌다. 이는 56시간이었던 어떤 알고리즘을 새 컴퓨터에서는 겨우 50초 만에 실행할 수 있다는 뜻이다. 그러나 2005년에는 그 과거의 알고리즘을 입수할 길이 없었다. 당시 사람들은 20년 전 보다 2만 배 빠른 새로운 알고리즘을 사용하고 있었고, 이것은 옛 하드웨어에서 실행해도 겨우 10초라는 뜻이다. 새 알고리즘을 새 하드웨어에서 실행했을때는 겨우 0.1초였다. 결론적으로 20년 만에 컴퓨터의 작동속도가 200만 배 더 빨라진 셈이었다. p.32
  • 검색
  • 네비게이션
    p.79 모두 방문하는 최단 경로 검색 소개, 총 2234 킬로미터 이다.
    스탠포드 연구소의 세 연구자가 개발한 알고리즘의 이름은 A*이다. 닐손은 직선 경로에 관한 아이디어를 떠올렸고, 래피얼은 알고리즘의 원리적인 단계들을 고안했으며, 하트는 그 알고리즘이 확실히 최단 경로를 찾아낸다는 것을 증명했다.
    음수에는 다익스트라 알고리즘 또는 A* 알고리즘을 적용할 수 없다. 다익스트라가 1956년에 겨우 20분 동안 궁리하여 고안한 알고리즘은 지금도 쓰인다. 당시에 그는 경로 계획 알고리즘이 미래에 얼마나 많은 분야에서 활용될지 상상조차 하지 못했을 것이 틀림없다.
  • 추천
  • 연결
    sixdegrees.com의 회원은 몇 백만명에 달했지만 다들 그 웹사이트를 어디에 써먹어야 할지 막막했다. 2000년에 폐쇄됐다. 그 후 수많은 SNS들이 나타나고 사라졌다. 클레이 셔키는 YASNS라는 약자까지 고안했다. Yet Another Social Networking Service. p.120
  • 예측
    상관성(correlation)을 근거로 예측하기. 10대 소녀에게 임산부 쿠폰을 보낸 사례를 소개한다. 나중에 이 소녀는 실제로 임신했음이 밝혀진다. p.137
    구글은 공개하지 않은 45개 피처로 독감 트렌드를 분석했다. 처음에는 매우 성공적으로 예측했다. 그러나 시간이 지나자 심각한 오류가 몇 번 발생했다. 2009년 돼지독감의 대유행을 전혀 예측하지 못했으며 2013년에는 나중에 실제로 확인된 독감환자 수 보다 두 배 많은 환자가 발생하리라고 예측했다.
    실패 이유:
    • 초기에는 성공적이었다. 보외법 extrapolation이 아직 유효했기 때문이다. 과거의 상관성에 기초해 미래를 예측했다. 그러나 해가 거듭될수록 조건들은 늘 동일하지 않았다.
    • ‘잡음이 섞인’ 데이터에서 정확한 결론들을 도출하려 했다. 일반인이 스스로 독감에 걸렸다고 생각하는 경우의 대다수에서 그는 실제로 독감에 걸리지 않았다.
      p.152
  • 투자
    나이트캐피털은 잘못된 거래액이 70억 달러에 달했고, 45분만에 문제를 발견했지만 이미 회사는 4억 4천만 달러를 잃은 뒤였다. … 오늘날 한 주식이 한 소유자의 손에 머무는 시간은 평균 5일에 불과하다. 50년 전에는 8년이었다. p.164
  • 암호화
    밥과 앨리스의 혼합 페인트로 사례를 소개한다. 『미래를 바꾼 아홉 가지 알고리즘』에서 설명했던 방식이다.
  • 압축
  • 사랑
    여성은 본인이 나이를 먹으면 이상적인 파트너의 나이도 높이는 반면 남성은 나이와 상관없이 20대 여성을 선호한다. 오케이큐피드의 창업자 크리스천 러더가 쓴 책 『데이터클리슴 Dataclysm』에 따르면 그렇다. p.222
  • 학습
    팀 오라일리는 알고리즘 규제 Algorithmic regulation를 이야기 한다. 정부의 일은 다음 네 단계로 요약된다.
    • 성과에 대한 깊은 이해
    • 성과가 달성되었는지 알아내기 위한 실시간 측정
    • 새 데이터에 적응하는 알고리즘
    • 알고리즘이 올바른지, 바라는 대로 작동하는지에 대한 정기적이며 심층적인 분석

왜냐면 알고리즘은 편견을 강화하기 때문이다. 예컨대 집과 직장 사이 거리가 더 짧은 직원이 직장에 더 충실하다는 것이 밝혀졌다면 그 규칙을 직원 채용 알고리즘에 내장할 수 있을 것이다. 그러나 회사가 부자 동네에 위치해 있다면 그 규칙은 그 동네에서 살 형편이 안 되는 사회적 집단 전체를 차별하는 효과를 낸다. p.254

예전 『대량살상 수학무기』에서 언급됐던 알고리즘 규제 방안과 유사해 보인다.

  1. 히포크라테스 선서와 같은 도덕적 선언이 필요하다.
  2. 알고리즘 모델은 완벽하지 않으므로 오남용해선 안된다.
  3. 공정성에 논란을 일으킬 수 있는 데이터는 폐기해야 한다.
  4. 정기적으로 감사해야 한다.
  5. 모델은 가능한 투명하고, 누구나 쉽게 접근할 수 있어야 한다.

(대량살상 수학무기, 2018)

  • 나가는 말
    구글의 코드는 20억행, 윈도우는 5000만 행이라고 언급 p.263

알고리즘, 인생을 계산하다 2016, 2018

링크만 남겨서는 잘 보지 않음. 별도로 풀어서 정리할 필요가 있음.

Last Modified: 2020/06/06 12:29:28


Docker  ·  Kubernetes  ·  Zsh  ·  Software Deployment  ·  GCP  ·  AI Platform  ·  PyData  ·  GCS  ·  BigQuery  ·  XGBoost  ·  Deno  ·  JetBrains  ·  수식  ·  2020 Book Reports  ·  Santander Product Recommendation  ·  GPU Data Science  ·  Python  ·  Markov Decision Process  ·  통계학  ·  통계학 책  ·  Front-End  ·  머신러닝  ·  Activation, Cost Functions  ·  알고리즘  ·  자료구조  ·  비지니스  ·  AWS  ·  NLP 링크  ·  알고리즘 링크  ·  머신러닝 링크  ·  사회심리학  ·  Information Retrieval  ·  통계학 응용  ·  OOP  ·  2019 Book Reports  ·  Android Development  ·  데이터 사이언스  ·  인공지능  ·  진화생물학  ·  이산수학  ·  수학  ·  미래학  ·  Project Management  ·  LifeHacks  ·  C++  ·  2017 Book Reports  ·  Decision Tree  ·  TensorRT  ·  NLP  ·  Hadoop, Spark  ·  데이터 마이닝  ·  CNN, RNN  ·  2018 Book Reports  ·  운영체제  ·  머신러닝 분류기  ·  거리  ·  Support Vector Machine  ·  OAuth 2.0  ·  Naive Bayes  ·  Jupyter Notebooks  ·  RSA  ·  컴파일러  ·  딥러닝  ·  Word Embedding  ·  컴퓨터시스템구조  ·  영어  ·  Go  ·  Scikit Learn  ·  NLP 실험  ·  MySQL  ·  Keras  ·  Java
is a collection of Papers I have written.
© 2000 - Sang-Kil Park Except where otherwise noted, content on this site is licensed under a CC BY 4.0.
This site design was brought from Distill.