알고리즘 책

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: 2021/07/17 00:10:37

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.