프롤로그: 알고리즘의 원리
"알고리즘은 명령문들로 쓰여지며, 이 명령들은 대개 하나씩 처리되고 수행된다. 때로는 이전 단계로 되돌아가 거기서부터 다시 명령을 수행하라고 요구하는 단계도 있을 수 있다. 이렇게 되돌아가면서 몇 그룹의 단계를 되풀이하는 방식은 많은 알고리즘에서 사용되는 강력한 기능이다." "알고리즘을 표시할 때 각 단계는 대개 명확성을 위해 한 줄씩 끊어서 적는다. 그리고 들여쓰기로 서로 관련이 있는 단계들을 구분한다." "대부분의 알고리즘에는 의사결정 단계가 포함돼 있는데, 이때 알고리즘을 수행하는 운영자는 두 가지 가능한 행동 경로 중 하나를 선택해야 한다. 어떤 행동을 수행할 것인지는 조건에 따라 달라진다. 여기서 조건이란 참true 또는 거짓false 중 하나를 나타내는 문구다. 가장 일반적인 의사결정 구조인 'if-then-else'에는 하나의 조건과 두 가지 가능한 행동이 결합되어 있다. 조건이 만약if 참이면 'then' 다음에 나오는 행동(들)이 수행되고, 조건이 거짓이면 'else' 다음에 나오는 단계(들)가 수행된다."(9-10)
1 고대 알고리즘
"'YBC 7289'라는 이름의 메소포타미아 점토판은 바빌로니아 수학이 얼마나 놀라운 수준이었는지를 보여준다. 기원전 1600년부터 1800년경에 이미 그들은 마주 보는 모서리를 2개의 대각선으로 연결한 정사각형을 묘사할 수 있었던 것이다. 정사각형의 변의 길이는 30단위로 표시되어 있고, 대각선의 길이는 2의 제곱근의 30배로 기록되어 있는데, 이 값들은 우리가 학교에서 배운 피타고라스 정리를 가리킨다. 피타고라스 정리에 따르면, 직삼각형에서 사변(가장 긴 변)의 제곱은 다른 두 변 길이의 제곱의 합과 같다. 그런데 이 점토판은 피타고라스가 태어나기 1,000년 전에 새겨졌다. 그래서 이 발견은 수학의 역사에 대한 근본적인 의문을 제기하는 발견이기도 하다." "또한, YBC 7289 점토판에는 2의 제곱근이 (10진법으로 환산했을 때) 1.41421296이라고 적혀 있다. 이는 매우 흥미로운데, 오늘날 우리는 2의 제곱근이 (소수점 아홉 번째 자리까지) 1.414213562라는 것을 알고 있기 때문이다."(30-1)
"바빌로니아 알고리즘에 명시적인 의사결정 단계(if-then-other)가 없는 것이 오히려 이상하게 느껴진다. 사실 바빌로니아인들은 'If-then' 규칙을 비수학적인 지식을 체계화하기 위해서 사용했다. 기원전 1754년에 제정된 것으로 알려진 함무라비 법전은 시민들이 지켜야 할 282개의 법을 기록한 책인데, 모든 법에 죄의 내용과 그에 따른 처벌이 언급되어 있다. 〈아들이 아버지를 때리면, 그의 손가락을 잘라야 한다 / 누군가가 다른 사람의 눈을 상하게 하면, 그 사람의 눈도 상하게 해야 한다.〉 'If-then' 구조는 의학 지식과 미신 행위를 설명하는 데에도 사용되었다. 기원전 650년경 니네베에 있던 아슈르바니팔 왕의 도서관에서는 다음과 같은 예언이 발견되었다. 〈도시가 언덕에 세워지면, 그 도시에 사는 사람들에게는 좋지 않은 일이 생길 것이다 / 자신도 모르게 도마뱀을 밟아 죽이면, 적에게 승리할 것이다.〉 비록 의사결정 단계는 없었지만, 메소포타미아인들은 알고리즘을 통해 다양한 문제를 해결했다."(33-4)
2 끝없이 팽창하는 원들
"원의 기본 특성은 중심에서 둘레까지의 거리가 일정하다는 것이다. 이 거리를 반지름이라고 한다. 그리고 지름, 즉 원의 너비는 반지름의 2배다. 원주는 원의 둘레 길이다. 원이 클수록 원주와 지름도 커진다. 원주와 지름의 관계는 측정을 통해 알 수 있다. 원의 지름을 잰 다음, 그 길이를 원주와 비교해보는 것이다. 그러면 원주의 길이가 지름의 3배가 조금 넘는다는 사실을 알게 될 것이다. 그리고 측정을 반복해보면, 원의 크기가 어떻든 그 비율이 일정하다는 것을 알 수 있다." "지름에 대한 원주의 정확한 비율로 π라는 문자를 처음 사용한 사람은 고대 그리스인이 아니라 웨일스인 수학자 윌리엄 존스로, 1707년에 쓰기 시작했다. π의 정확한 값을 구하는 것은 불가능하다. 독일의 수학자 요한 하인리히 람베르트(1728~1777)는 π가 무리수라는 것을 증명했는데, 이는 계산에 무한히 많은 숫자가 필요하다는 의미다. 아무리 계산해도 같은 패턴만 반복될 뿐 끝나지 않는다. 그래서 구한 최선의 값이 어림수 π다."(46-7)
"π의 근사치를 계산하기 위한 아르키메데스의 알고리즘은 다음 세 가지 통찰력을 기반으로 한다. 첫째, 정다각형은 원에 근접한 도형이다. 둘째, 다각형의 변은 직선이므로 그 둘레를 계산하기 쉽다. 셋째, 정다각형의 변이 많을수록 원에 가까워진다." "아르키메데스는 알고리즘을 통해 이 값을 개선했다. 알고리즘을 반복할 때마다 다각형의 면 수를 2배씩 늘린 것이다." "아르키메데스 알고리즘의 장점은 계속 다시 적용할 수 있다는 것이다. 이전 실행에서 나온 출력을 다음 반복 때 입력으로 공급할 수 있다. 이런 식으로 12각형은 변이 24개인 24각형으로, 다시 48각형으로, 96각형으로 바뀔 수 있다. 알고리즘이 반복될 때마다 내부 다각형과 외부 다각형은 각각 원에 근접하면서 더 정확한 π값을 도출한다. 아르키메데스는 96각형에서 계산을 종료하고 223/71과 22/7이라는 π값의 추정치를 구했는데, 전자는 네 자릿수까지 정확하다. 후자는 정확성은 떨어지지만, 단순해서 더 인기가 있다."(48-50)
3 컴퓨터의 꿈
"앨런 튜링은 케임브리지대학교에서 장학금을 받고 연구를 계속하면서 주목할 만한 과학 논문을 발표했는데, 이 논문에서 다음 세 가지 중요한 아이디어를 주장했다. 알고리즘을 공식적으로 정의하고, 범용 컴퓨터가 처리해야 하는 기능을 정의했으며, 이러한 정의를 바탕으로 어떤 함수는 게산할 수 없다는 사실을 증명한 것이다. 놀랍게도, 그는 디지털 컴퓨터라는 것이 만들어지기 전에 이런 생각을 했다. 또, 튜링은 오늘날 '튜링 머신'이라고 불리는 가상의 컴퓨터 아이디어를 제시했다. 이 컴퓨터는 무한 종이 테이프, 테이프 헤드, 메모리 그리고 기계 작동을 제어하는 일련의 명령으로 구성되어 있다." "튜링 머신에서는 모든 명령이 전제 조건과 세 가지 작업으로 구성되어 있으며, 전제 조건이 충족되면 작업이 수행된다. 전제 조건은 기계의 현재 상태(메모리값)와 현재 테이프 헤드 아래에 있는 기호에 따라 달라진다. 상태와 기호가 전제 조건에서 지정한 값과 일치하면 전제 조건과 관련된 작업이 수행된다."(76-7)
"튜링은 그가 상상한 기계가 어떤 알고리즘도 수행할 수 있을 만큼 유연하다고 보았다. 지금도 인정되고 있는 이 생각은 동전의 양면과 같아서, 알고리즘과 범용 컴퓨터를 다음과 같이 정의할 수 있게 되었다. 알고리즘은 튜링 머신이 기능을 수행하도록 프로그래밍할 수 있는 일련의 단계를 말한다. 범용 컴퓨터는 튜링 머신이 실행할 수 있는 프로그램과 동등한 프로그램을 실행할 수 있는 모든 기계를 말한다. 범용 컴퓨터의 기본 특징은 그것이 '튜링 완전Turiong complete'이라는 것이다. 이는 현대의 범용 컴퓨터가 튜링 머신의 방식을 흉내 낸 것에 불과하다는 의미를 내포한다. 물론 종이 테이프 기호는 다른 물리적 기호(전자 전압 수치 등)로 대체되었지만 말이다." "튜링 머신의 가장 기본적인 기능은 데이터를 검사하고, 다음에 어떤 작업을 수행할지를 결정하는 것이다. 컴퓨터를 단순한 자동 계산기 이상의 존재로 만드는 것이 바로 이 기능이다. 이 기능은 컴퓨터에 알고리즘을 수행할 수 있는 능력을 제공한다."(78-9)
4 일기예보
"스타니스와프 울람은 혼자서 하는 카드 게임인 캔필드 솔리테어를 즐겼다. 캔필드 솔리테어는 52장의 카드를 사용하는데, 카드는 1장씩 돌려지고 게임 규칙과 게임자의 결정에 따라 카드 더미들로 이동된다." "울람은 자신이 게임에서 이길 가능성이 얼마나 될지 궁금했다. 승패 여부는 카드가 나뉘는 순서에 달려 있었다. 카드의 순서에 따라 승패가 갈리는 셈이다. 그 가능성을 계산하는 한 가지 방법은 가능한 모든 카드 순서를 나열한 후 이길 확률을 백분율로 계산하는 것이었다." "울람은 이 문제를 보다 단순하게 풀 수 없을까 고민했다. 만약 게임을 10번만 했다면? 10번 중 이길 확률을 계산할 수 있다면, 진정한 승률을 알 수 있을 것이다. 물론 10게임 내내 행운이 올 가능성도 있다. 이것이 확률을 왜곡시킬 것이다. 그러나 100게임을 한다면? 100게임 연속 행운이 올 가능성은 적다. 울람은 어느 정도 이상의 게임 결과의 평균을 내면 실제 이길 확률에 대한 합리적인 추정치를 얻을 수 있다고 결론지었다."(103-4)
"1,000게임을 하는 데에는 꽤 오랜 시간이 걸릴 것이다. 울람은 컴퓨터로 그 정도로 많은 게임을 하도록 프로그래밍할 수 있음을 알고 있었다. 그렇다면 컴퓨터가 무작위로 카드를 돌리고, 자신이 실제로 하는 것처럼 게임을 하도록 프로그래밍할 수도 있을 것이다. 이를 반복해 게임 횟수가 충분해지면, 이길 확률은 가능한 모든 게임을 한 것만큼 신뢰할 수 있는 추정치가 될 것이다." "울람은 이 알고리즘을 단순히 카드 게임에서 이길 확률을 구하는 일 이상의 문제에 사용할 수 있을 것이라고 생각했다. 중성자 확산 문제에서 중성자 궤적과 차폐 원자 위치는 난수로 나타낼 수 있다. 각 궤적과 차폐 구성에 대한 침투 거리도 계산할 수 있다. 어느 정도 많은 수의 무작위 시험을 하고 그 평균을 내면, 실제 중성자 침투 거리의 추정치를 얻을 수 있을 것이다." "실험 결과는 겸손하고 절제된 표현을 빌리더라도 〈썩 괜찮았다.〉 로스앨러모스의 동료들은 이 새로운 알고리즘에 '몬테카를로 방법'이라는 이름을 붙였다."(105-7)
"1961년, 에드워드 로렌즈는 작은 컴퓨터로 날씨 시뮬레이션을 실행했다. 그런데 늘 일상적인 결과가 나오던 실험에서 그날 따라 이상한 일이 일어났다." "컴퓨터와 프로그램은 모두 문제가 없었다. 로렌즈는 이런 불일치가 시뮬레이션 초기에 입력한 숫자의 사소한 차이에서 비롯된 것이라고 생각했다. 첫 실행에서 로렌즈는 대기 상태를 여섯 자리 숫자로 입력했지만, 두 번째 실행에서는 세 자리 숫자만 입력했다. 여섯 자리 숫자와 가장 가까운 세 자리 근삿값의 차이는 매우 작았다. 그는 입력시 차이가 작으면 출력에서도 큰 차이가 나지 않을 것이라고 생각했지만, 사실은 그렇지 않았다. 그 작은 차이가 계산을 거듭하면서 크게 벌어졌고, 결국 출력 시점에서 큰 불일치로 나타난 것이다." "이 우연한 발견에서 새로운 과학이 출현했다. 로렌즈의 카오스 이론은 실세계의 많은 물리 체계가 초기 조건에 매우 민감하다는 사실을 밝혀냈다. 초기 조건에 작은 차이만 있어도, 결괏값이 크게 달라질 수 있다는 것이다."(111-2)
"기존의 기상예보 시뮬레이션은 현재 기상 상태를 측정하는 것으로 시작해 칸별, 시간 단계별로 날씨의 변화를 계산한다. 여기에서 에드워드 엡스타인의 통찰력이 발휘됐다. 울람의 몬테카를로 방법을 적용한 것이다. 엡스타인은 하나의 시뮬레이션이 아니라 여러 개의 시뮬레시션을 실행해야 한다고 주장했다. 그리고 각 시뮬레이션은 무작위로 교란된 초기 조건으로 시작해야 한다. 이러한 초기 조건은 관찰된 대기 상태에 작은 변화나 교란을 가함으로써 생성된다. 측정의 한계를 감안했을 때, 예측자들은 어느 칸의 현재 기상 상태가 어떠한지 정확히 알 수 없기 때문에, 여러 가지 시나리오를 시도할 수 있다. 시뮬레이션이 끝난 후에는 각 시뮬레이션 결과의 평균을 내서 단일화된 최종 예측을 얻는다. 이때 여러 가능성을 고려해야 하는데, 모든 것을 고려하면 중간값이 가장 가능성이 큰 시나리오다. 이를 몬테카를로 앙상블 방법이라고 부른다(이 알고리즘의 단점은 너무 많은 계산을 해야 한다는 것이었다)."(112-3)
5 인공지능의 등장
"크리스토퍼 스트레이치의 알고리즘은 숫자를 사용해 체커 게임판에 있는 말들의 위치를 기록한다. 그리고 자기 차례가 되면 말을 둘 수 있는 가능한 모든 수手를 검사한다(평균 10가지)." "알고리즘은 가능한 모든 다음 수에 대한 상대방의 잠재적 반응을 평가한다. 이런 예측 기능은 향후 3회차의 수까지 내다볼 수 있고, 예측 결과는 나뭇가지 모양(트리)으로 시각화할 수 있다. 게임판에 있는 모든 말의 위치는 트리의 교점(또는 분기점)에 해당한다. 그 위치에서 가능한 모든 수에서 다음 위치로 이어지는 분기점이 생성된다. 앞 수를 더 많이 내다볼수록, 트리의 층이 많아진다. 알고리즘은 예측의 맨 끝에 있는 각 교점의 상황별로 게임자들이 현재 가지고 있는 말의 수를 계산한다. 그 후 예측의 맨 끝 교점에서 가장 큰 수數(가장 유리한 手)로 이어지는 수를 트리의 뿌리(현재 위치)에서 선택하는 것이다." "스트레이치의 시도는 컴퓨터가 계산만 하는 기계라는 통념을 깨트렸고, 여기서 인공지능 개념이 싹트기 시작했다."(122-4)
"아서 새뮤얼의 알고리즘은 영리한 평가 알고리즘scoring algorithm을 사용했다. 그래서 스트레이치의 알고리즘보다 말이 이동할 자리를 판단하는 데 훨씬 더 치밀했다. 또한 다양한 기능이 탑재되어 있어 기능별로 포인트가 제공되었는데, 그 기능들은 게임판 위치의 강점이나 약점을 나타냈다. 두 게임자가 보유하고 있는 말 개수의 차이를 알 수 있는 기능도 있었고, 킹 말이 몇 개인지도 알 수 있었다. 또 각 말이 놓인 위치의 상대성(중요도)도 평가할 수 있고, 게임판의 중앙을 자유롭게 이동하거나 제어하는 등의 전략적 요소를 인식하는 중요한 기능도 있었다. 프로그램은 이런 모든 기능에 점수를 매겼으며, 특정 기능에는 가중치를 곱한 점수가 주어졌다. 결괏값은 모두 합산되어 특정 위치에 대한 전체 점수로 제시되었다. 가중치가 크다는 것은 하나의 기능이 총 점수에 강한 영향을 미친다는 뜻이었다. 그러나 낮은 가중치를 가진 여러 기능이 합쳐져 전체 점수와 최종 결정에 영향을 미칠 수도 있었다."(137)
"하지만 각 가중치에 대한 최상의 값을 찾기가 어려웠다. 그래서 새뮤얼은 최적의 가중치를 결정하기 위해 머신러닝 알고리즘을 설계했다. 알고리즘이 가중치를 추정한다. 그러면 컴퓨터가 자기 자신을 상대로 수많은 게임을 한다." "어느 한쪽이 이기면 승부에 긍정적으로 기여한 기능의 가중치 점수가 조금씩 커진다. 반대로 패배의 원인을 제공한 기능의 가중치 점수는 줄어든다. 이 과정을 통해 어느 한쪽이 승리하는 행동이 강화된다." "가중치를 수동으로 선택하지 않고 이 알고리즘을 사용할 때의 장점은 두 가지다. 컴퓨터는 게임을 할 때마다 그 게임이 가중치에 영향을 미친다는 사실을 잊지 않는다는 것과, 인간보다 훨씬 더 많은 게임을 스스로 할 수 있다는 것이다. 이런 장점들 덕분에 컴퓨터는 아주 많은 양의 정보를 학습 과정에 이용할 수 있다." "가중치 숫자 몇 개를 변경하는 것은 아주 쉬운 작업이어서 알고리즘이 혼자서 수행할 수 있다. 이런 창의적인 개념이 학습의 자동화를 가능하게 한 것이다."(138-9)
6 모래에서 바늘 찾기
"영업사원 문제는 1800년대의 문헌에서 처음 발견되었다. 예를 들어 베를린이 영업 사원의 거점 도시고, 그가 함부르크, 프랑크푸르트, 뮌헨을 방문해야 한다고 가정해보자. 가장 짧은 이동 거리를 찾는 제일 간단한 방법은 모든 이동 거리를 일일이 탐색하는 것이다. 이런 완전 또는 무차별 억지 탐색은 이동 가능한 모든 경로를 계산해 그중 가장 짧은 거리를 선택하는 방식이다." "그러나 이런 무차별적 탐색은 속도가 느릴 수밖에 없다. 만약 거쳐야 할 도시가 100개라면 어떨까? 완전히 연결된 100개의 도시를 여행하는 경로의 수는 99!인데, 대략 9×10,155다(9에 0이 155개나 이어지는 숫자다)." "탐색 속도를 크게 높일 수 있는 유일한 방법은 절충을 인정하는 것이다. 알고리즘이 가능한 최단 경로를 찾지 못할 수 있다는 사실을 인정해야 한다는 뜻이다." "물론, 절충과 근사 알고리즘을 항상 받아들여야 할 필요는 없다. 우리는 어떻게 해서든 최단 경로를 찾아야 하니 말이다."(147, 151-2)
"에츠허르 데이크스트라는 무차별 억지 탐색 알고리즘에서 벗어나, 1952년에 세계에서 가장 흔히 발생하는 조합 최적화 문제를 해결하는 빠른 알고리즘을 고안해냈다." "데이크스트라의 알고리즘은 보드게임을 하는 것과 비슷하다. 알고리즘은 지도를 가로질러 토큰을 이동시키면서 이동 경로와 출발지에서부터의 누적 거리를 각 도시에 주석으로 달아놓는다." "어느 도시에 붙은 주석이 이 계산값보다 작으면 그 주석은 변경하지 않고, 계산값이 주석보다 작으면 그 주석을 계산값으로 교체한다. 이때 새로 계산된 거리와 그 경로도 기록된다." "직접 연결된 모든 도시에 대해 이 단계가 완료되면, 토큰은 주석을 기준으로 아직 방문하지 않은 가장 가까운 거리의 도시로 이동한다. 토큰이 원하는 목적지에 도달할 때까지 이 과정을 계속 반복한다." "최단 경로 찾기는 누구에게나 필요하다. 언제나 새로운 목적지를 찾아 나서야 할 경우가 있으니 말이다."(160-3, 166)
"존 홀랜드는 인공 진화가 조합 최적화 문제를 해결하는 데 적용될 수 있겠다고 생각했다. 그의 아이디어는 집단 내 개체처럼 가능한 솔루션이 나타날 수 있다는 것이었다. 그래서 유전 현상에 착안해 모든 솔루션을 일련의 문자로 표현할 것을 제안했다. 예를 들어, 영업 사원 문제를 풀 때 모든 도시의 첫 알파벳을 따 여행을 BFHM으로 표시하는 식이다. 그는 이 순서가 살아 있는 유기체의 염색체와 유사하다고 생각했다. 홀랜드의 유전자 알고리즘은 이 같은 인공 염색체 풀에서 작동한다. 선택은 모든 인공 염색체를 평가하고 그중 최악의 염색체를 폐기함으로써 이루어진다. 유전은 문자 순서를 혼합하는 것으로 다음 세대의 염색체를 만드는 방식을 모방한다. 돌연변이는 몇몇 염색체의 문자를 무작위로 바꿈으로써 그것이 나타나는 방식을 복제한다. 그리고 전체 집단 내에서 쓸 만한 솔루션이 발견될 때까지, 다음 세대의 염색체를 생산하는 과정을 반복한다. 계속적인 선택을 통해 보다 나은 솔루션을 찾는 것이다."(176)
7 인터넷
"아르파넷은 패킷 교환packet-switching 방식을 채택한 최초의 네트워크 중 하나였다. 이 기술은 폴 배런과 도널드 데이비스가 발명했다." "패킷 교환은 〈어떻게 하면 컴퓨터 네트워크를 통해 메시지를 효율적으로 전송할 수 있는가?〉라는 문제를 해결했다. 전자 신호를 전달하는 케이블로 9대의 컴퓨터가 물리적으로 상호 연결되어 네트워크를 이루고 있다고 생각해보자. 인프라 비용을 줄이기 위해 모든 컴퓨터는 몇몇 다른 컴퓨터들과 연결되어 있다. 이렇게 직접 연결된 컴퓨터들은 실제로 거리가 얼마나 멀리 떨어져 있든 '이웃'이라고 부른다. 컴퓨터가 이웃에게 메시지를 보내는 일은 간단하다. 메시지는 일련의 전자 파동으로 부호화되어 케이블을 통해 받는 컴퓨터로 전송된다. 반면 네트워크 반대편에 있는 컴퓨터로 메시지를 보내는 일은 좀 복잡하다. 그 중간에 있는 컴퓨터가 메시지를 중계해야 하기 때문이다. 따라서 네트워크 전체에 통신 서비스를 제공하려면, 네트워크상의 컴퓨터들이 서로 협력해야 한다."(186-7)
"패킷 교환에서는 단일 메시지가 여러 개의 세그먼트로 분할되고, 각 세그먼트는 하나의 패킷에 배치된다. 패킷들은 네트워크를 통해 독립적으로 전송되고, 모든 패킷이 목적지에 수신되면 세그먼트들이 합쳐져 원본 메시지가 다시 조립된다. 네트워크는 계속 바운드하면서 발신지에서 목적지로 패킷을 전송한다. 즉, 바운드할 때마다 패킷이 두 컴퓨터 사이에서 한 차례 연결되면서 전송되는 것이다. 이때 패킷은 1번당 하나의 링크만을 차단하기 때문에, 다른 메시지의 패킷들도 한 링크에 차례대로 삽입될 수 있다. 회로 교환 방식처럼 종단 간 연결선 전체를 점유할 필요가 없는 것이다." "패킷 교환 데이터 네트워크는 도로망과 유사하다. 패킷들은 목적지를 향해 가는 자동차들과 같다. 자동차들은 전체 경로를 미리 점유하지 않고, 도로가 비어 있을 때 그냥 끼어들기만 하면 된다. 또, 이 자동차들은 목적지로 가는 다른 길들을 택할 수도 있다. 각각의 차는 네트워크를 통해 자신이 갈 수 있는 최선의 길을 갈 뿐이다."(188-9)
"패킷 교환은 분산 알고리즘의 한 사례다. 패킷 교환 시스템의 필수 구성 요소는 경로 표를 덧붙이기 위해 사용되는 알고리즘이다. 모든 컴퓨터는 경로 표뿐만 아니라 지연 표도 기록한다. 지연 표에는 네트워크의 모든 컴퓨터 ID와 컴퓨터별로 해당 시점부터 패킷을 전송하는 데 걸릴 예상 시간이 기록된다. 모든 컴퓨터는 모든 이웃에게 주기적으로 지연 표를 보내는데, 수신 컴퓨터는 이웃의 지연 표를 받으면 그 표에 자신의 다른 이웃에게 패킷을 전달하는 데 걸리는 시간을 더한다. 이런 식으로 업데이트된 표에는 모든 컴퓨터의 ID 목록과 이웃을 통해 패킷을 전달하는 데 걸리는 시간이 담기고, 컴퓨터는 이 시간을 경로 표에 적혀 있는 시간과 비교한다. 새 경로가 더 빠르면, 시간이 업데이트된다." "패킷 교환 네트워크의 이점 중 하나는 웬만해서는 고장 나지 않는다는 것이다. 단점은 패킷 전송 시간을 예측할 수 없다는 것이다. 결국 패킷 교환은 '최선의 노력'을 다하는 서비스라고 할 수 있다."(190-2)
"기존 암호화 알고리즘은 대칭 키를 사용하는데, 이것은 암호화와 암호 해독에 같은 키가 사용된다는 의미다. 대칭 암호화의 단점은 항상 키에 대한 비밀이 지켜져야 한다는 것이다. 사실, 이는 '키 배포 문제'가 발생하는 근본적인 이유이기도 하다. 공개 키 암호화는 암호화와 해독에 각기 다른 두 가지 비대칭 키를 사용한다. 이때, 두 키가 쌍을 이루려면 두 가지 요구사항을 충족해야 한다. 첫째, 두 키는 암호화와 해독이라는 서로의 쌍으로서 성공적으로 작동해야 한다. 즉, 한 키로 암호화를 하면, 다른 키로 해독을 하고 원래 메시지를 복원할 수 있어야 한다. 둘째, 암호화 키 쪽에서 해독 키를 알 수 없어야 한다. 암호화 키 쪽에서 해독 키를 알 수 없다면, 암호화 키를 공개해도 아무런 문제가 되지 않는다. 해독 키만 비밀로 유지하면 되니 말이다. 그러므로 누구나 공개 암호화 키를 사용해 개인 키 홀더로 비밀 메시지를 보낼 수 있다. 해독 키를 가진 수신자만 메시지를 해독하고 읽을 수 있기 때문이다."(212-3)
"암호화 키에서 암호 해독 키를 알아낼 수 없게 하려면 그 비대칭 키를 생성하는 방법을 아는 사람이 아무도 없어야 한다. 이를 위해서는 출력으로부터 입력을 쉽게 추론할 수 없는 연산인 일방 함수가 필요하다. 그래야만 그 출력이 공개 암호화 키의 기초가 될 수 있고, 입력은 개인 해독 키의 기초가 될 수 있다. 계산을 되돌릴 방법은 없다. 일방 함수가 구현된 RSA 알고리즘은 인터넷상에서의 암호화의 초석으로 불리고 있다." "오늘날 공개 키 암호는 월드 와이드 웹의 보안소켓계층SLL에 내장되어 있다. 웹사이트 주소 앞에 'https:'가 있으면 컴퓨터가 SLL을 사용하고 있고, RSA 알고리즘이 원격 서버와 통신하고 있는 것이다. 최근 집계에 따르면, 웹사이트 트래픽의 70퍼센트가 SLL을 사용하고 있는 것으로 나타났다. 그러나 최근 몇 년간은 최신 슈퍼컴퓨터에 의해 암호문이 뚫리는 것을 막기 위해 키의 길이를 더 늘려야만 했다. 오늘날 일반적으로 사용되는 키는 2,048비트(617자리) 이상이다."(214-5, 219)
8 구글 검색
"1995년 7월 16일 탄생한 amazon.com의 신입 사원이었던 그레그 린덴은 아마존이 더 많은 책을 팔 수 있도록 제품 추천 시스템이라는 아이디어를 생각했다." "린덴의 알고리즘은 간단한 직관을 기반으로 한다. 짝을 이루는 제품들이 대개 함께 구매되는 경향이 있다면, 한 제품을 이미 갖고 있는 고객이 나머지 하나도 구매할 가능성이 클 것이라는 생각 말이다. 그 물건은 원래 쌍으로 구매해야 하는 제품은 아니다. 중요한 것은 고객들이 대개 두 물건을 모두 구입한다는 것이다. 그 이유가 어떤 것이든 상관없다. 같은 저자나 같은 장르의 책일 수도 있고, 어쩌면 같은 주에서 주관하는 시험 문제집일 수도 있다. 린덴의 알고리즘은 개인이 아마존 웹사이트에서 구매한 모든 내역을 기록한다. 구매자가 결제를 할 때, 알고리즘은 고객은 고유 ID와 구매한 책 제목을 모두 기록에 남긴다. 그리고 나중에 그 고객이 다시 찾아오면 그 고객이 이전에 구입한 목록을 다시 불러내, 그 목록과 새로 나온 책들을 쌍으로 구성한다."(231-2)
"래리 페이지는 웹 검색 문제에 꽂혀 있었다. 당시의 웹사이트 디렉토리는 편리하지 않았다. 먼저 범주를 찾고, 주제, 하부 주제를 알파벳순에 따라 드릴다운하는 작업은 시간이 너무 많이 걸렸다. 그는 그보다는 직접 조회 방식queries이 더 적합하다고 생각했다. 찾고 있는 것을 직접 입력하면, 가장 관련성이 높은 링크가 나타나게 하는 것이다." "학술 연구 논문은 일반적으로 다른 출판물에서 참조 및 인용된 횟수에 따라 순위가 매겨진다. 페이지는 인터넷의 하이퍼링크가 이와 매우 비슷하다는 것을 깨달았다. 하이퍼링크는, 그것을 만드는 사람이 링크 페이지가 어떤 면에서 중요하거나 관련이 있다고 생각하고 있음을 나타낸다고 볼 수 있기 때문이다. 그러니 링크 페이지에 연결되는 링크 수를 세는 것이 해당 페이지의 중요도를 평가하는 좋은 방법이 될 수 있다. 이를 바탕으로, 래리 페이지는 웹 페이지의 중요도에 순위를 매기는 알고리즘을 개발했다. 그리고 그 알고리즘에 페이지랭크PageRank라는 이름을 붙였다."(237-8)
# 드릴다운drill down : 더 많은 정보를 찾기 위해 관련 텍스트나 아이콘 등을 클릭하여 마치 뚫고 들어가듯이 검색하는 것
"페이지랭크는 무작위로 링크를 선택하는 웹 사용자가 자신이 찾고자 하는 특정 페이지에 도착할 확률로 간주될 수 있다. 이는 어느 페이지에 대한 링크 수가 많아지면, 사용자가 그 페이지에 도착할 가능성이 더 커진다는 것을 의미한다. 링크 페이지에 대한 하이퍼링크가 많아진다는 것 또한 사용자가 해당 페이지에 도착할 가능성이 커진다는 것을 뜻한다. 이런 '깔때기 효과'는 그 체인에 있는 다른 링크들에도 적용된다." "페이지랭크 점수를 계산하는 알고리즘은 반복적이다. 맨 처음 페이지랭크 점수는 어느 특정 페이지에 직접 수신되는 링크 수를 수신 링크의 평균값으로 나눈 숫자다. 다음에는 수신 페이지의 페이지랭크 점수 가중치의 합에 댐핑 합을 더한 숫자로 재계산된다. 이렇게 해서 새로운 세트의 페이지랭크가 생성되고, 이 값을 사용해 페이지랭크 점수가 다시 계산되는 것이다. 이 과정이 반복되면서 페이지랭크는 점점 안정된 값에 근접하고, 페이지랭크 점수가 변하지 않으면 반복은 중단된다."(239-40)
9 페이스북과 친구들
"초기에는 페이스북에서 새로운 게시물을 찾는 유일한 방법이 사용자의 프로필 페이지에 가서 업데이트가 있는지 확인하는 것뿐이었다. 그러나 수많은 프로필 페이지를 확인하는 일은 시간 낭비였다. 게다가 특별히 볼 만한 새로운 게시물도 많지 않았다. 저커버그는 등록한 친구들이 최근 게시물을 올렸는지 요약해주는 페이지가 있다면, 사용자들에게 도움이 될 것이라고 생각했다. 이렇게 페이스북 뉴스피드News Feed 알고리즘이 탄생했다." "2006년 9월 5일, 페이스북은 뉴스피드를 본격적으로 반영했다. 사용자들의 반응은 만장일치였다. 사람들은 그것이 너무 스토커 같다고 생각했다. 페이스북에는 뉴스피드를 반대하는 그룹들이 속속 등장했다. 그러나 아이러니하게도, 학생들은 그들이 반대하는 바로 그 기능을 사용해 뉴스피드 반대 운동을 하고 있었다. 저커버그에게는 그것이 뉴스피드가 효과가 있다는 증거로 보였다. 사용자들은 그 어느 때보다도 더 많은 시간을 페이스북에서 보내고 있었다."(251-2)
"뉴스피드 알고리즘은 구글의 페이지랭크 알고리즘에서 착안한 것으로 보인다. 페이스북에서의 모든 행동은 '에지edge'라고 부른다." "선호도는 에지에 대한 사용자의 연결 수준을 나타내는 척도다. 즉, 사용자가 그 에지를 만든 사람과 얼마나 가까운지를 나타낸다. 페이스북상의 '친구'는 친구가 아닌 사람들보다 더 가깝게 여겨진다. 겹치는 친구가 많을수록 호감도도 커진다. 사용자들 간의 상호 작용 수도 선호도 점수에 영향을 준다. 예를 들어 두 사용자가 서로의 게시물에 자주 댓글을 다는 경우, 서로에 대한 선호도가 높아진다. 반대로 사용자들이 상호 작용을 멈춘다면, 시간이 지날수록 선호도는 낮아진다. 가중치는 에지의 유형에 따라 달라진다. 생성에 더 많은 노력을 필요로 하는 에지는 더 높은 가중치 값을 갖는다. 댓글은 단순한 '좋아요'보다 가중치가 더 높다. 다른 모든 것이 동일하다면, 에지는 시간이 지남에 따라 에지랭크 점수가 감소한다. 이 규칙에 따라 알고리즘은 최신 게시물을 우선시한다."(252-3)
"넷플릭스는 공개경쟁 방식으로 새로운 알고리즘을 얻는다는 색다른 시도를 했다. 넷플릭스의 추천 알고리즘인 시네매치보다 10퍼센트 더 정확하게 추천을 해줄 수 있는 시스템을 공모하며 100만 달러의 상금을 건 것이다. 넷플릭스는 경쟁에 불을 붙이기 위해 약 50만 명의 고객이 1만 8,000여 편의 영화에 대해 평점을 매긴 1억 개에 달하는 훈련용 데이터 세트를 제공했다. 모든 데이터는 영화 제목, 사용자(고객) 이름, 별점(별 1~5개), 평가 기록일 등으로 구성되어 있었다." "며칠 후, 넷플릭스는 280만 개의 한정qualifying 데이터 세트를 추가로 배포했다. 별점을 숨겼다는 점을 제외하면, 첫 번째 데이터 세트와 비슷했다." "공모의 목표는 한정 데이터 세트에서 삭제된 평점을 정확하게 예측할 수 있는 추천 시스템을 구축하는 것이었다. 넷플릭스는 공모 참가자들이 제출한 추정치와 실제 평점을 비교했다. 공모 참가자의 추정치는 예측 오차, 즉 공모 참가자의 예측치와 실제 평점의 평균 차이를 측정해 평가되었다."(255-6)
"대부분의 공모 시스템에서 예측의 세부 사항은 수치값에 의해 제어되었고, 이 수치값, 즉 매개변수들은 예측 결과가 개선되도록 조정되었다. 예를 들어, 가중치 매개변수는 각 요소의 상대적 중요도를 조정하기 위해 수정된다. 이 과정을 통해 요소들이 식별되면, 정확한 평점 예측은 최적의 매개변숫값을 찾을 수 있느냐에 따라 달라진다. 최적의 매개변숫값을 결정하기 위해 공모 참여자들은 머신러닝 기법을 사용했다. 먼저 검증을 위해 훈련용 데이터의 일부를 따로 떼어놓은 다음, 매개변숫값을 추측한다. 그다음, 검증 데이터 세트의 평점 예측값을 구하기 위해 예측 알고리즘을 실행하고, 이 추정치에 대한 예측 오차를 측정한다. 그리고 예측 오차를 줄이기 위해 매개변수를 살짝 조정한다. 이 예측, 평가, 매개변수 조정 단계를 수차례 반복하면서 매개변숫값과 예측 오차 사이의 관계를 모니터링한다. 이를 바탕으로 매개변수는 계속 조정되고, 오차가 더 줄어들지 않으면 훈련이 종료되어 매개변수값이 확정된다."(259-60)
10 미국의 유명 퀴즈 쇼
"왓슨은 2011년 2월, 〈제퍼디 쇼!〉에서 우승한 IBM의 인공지능 컴퓨터이다. 왓슨의 소프트웨어는 수백 개의 협력 알고리즘이 합쳐진 결과물이다. 우선, 구문 분석 알고리즘이 사회자가 제시하는 단서를 구성 문법 요소로 분석해, 단서에 있는 모든 단어가 어법의 어느 부분에 속하는지 판단한다. 이 작업은 사전의 모든 단어를 찾아봄으로써 이루어진다." "단어 간의 명확한 관계를 찾은 다음, 왓슨은 그 단어에 내포되어 있는 연관성을 찾아낸다. 백과사전에서 원래 용어의 의미를 찾고 유의어를 검색한다. 이 과정에서 단서의 의미에 대해 더 깊은 통찰력을 얻는다." "관계가 추출되면 왓슨은 단서의 요소들을 식별하는데, 이때 구문 분석 결과물에 적용된 if-then-else 규칙을 사용한다. 여기서 단서의 초점, 답안 유형, 질문 분류라는 세 가지 주요 요소가 식별된다. 단서의 초점은 게임 참가자들의 답을 유도하는 항목이다. 답안 유형은 단서의 초점이 가진 본질적 특성이고, 질문 분류는 단서가 속해 있는 카테고리다."(275-6)
"단서 분석이 완료되면 왓슨은 데이터베이스에서 답을 검색한다. 이때, 수없이 많은 검색을 시작하면서 자신의 메모리뱅크에 저장된 정형 및 비정형 데이터에 접속한다. 정형 데이터는 잘 정리된 표에 보관된 정보를 일컫는다. 이런 데이터는 흥밋거리 정보 조회에 매우 유용하다." "비정형 데이터는 어떤 형식에 의해 정리되어 있지 않은 정보를 지칭하는 용어다. 이 데이터에는 신문 기사나 책 같은 텍스트 문서 형태의 정보들이 담겨 있다. 그 양은 엄청나게 많지만, 컴퓨터가 해석하기에는 어렵다." "왓슨은 자신이 정확한 결과를 도출했기를 바라면서 이러한 일련의 검색을 시도한다. 마지막으로 왓슨은 검색 결과로 도출된 여러 정답 후보가 단서의 요건을 얼마나 잘 충족하는지 계산해 평가한다. 답과 단서의 모든 측면을 비교해서 점수를 매기고, 가장 높은 점수를 받은 답을 최상의 솔루션으로 선택한다. 그 점수를 일정한 임계값과 비교해 점수가 임계값을 넘으면, 질문(퀴즈의 정답)으로 바꿔 벨을 누른다."(277-8)
11 인간의 뇌를 흉내 내다
"패턴 인식 시스템의 개발 과정에 대해 생각해보자. 첫 번째 단계는 이미지를 컴퓨터가 처리할 수 있는 숫자 배열로 변환하는 것이다. 디지털카메라의 렌즈가 전자 센서 그리드에 빛을 비추면, 각 센서가 조도를 0~1 범위의 숫자로 변환한다. 회색 톤 이미지의 경우, 0에는 검은색, 1에는 흰색, 회색 음영에는 중간값이 부여된다. 모든 숫자는 이미지상의 점 또는 픽셀(그림 요소)에 해당된다. 숫자 배열은 이미지의 디지털 근사치다." "진짜 어려움은 실제 이미지의 가변성에서 발생한다. 각각의 상황을 모두 파악할 수 있는 알고리즘을 작성하는 것은 매우 어렵다. 또, 새로운 규칙은 이전의 모든 규칙과 상호 작용해야 한다. 그러나 규칙끼리 충돌하는 경우가 많아, 결국 알고리즘 개발은 중단되고 만다. 그러자, 컴퓨터과학자들은 수백만 개의 규칙을 만드는 대신 다른 접근 방법을 선택했다. 그들의 논점은 간단했다. 세계 최고의 패턴 인식 엔진이 인간의 뇌라면, 그냥 인간의 뇌를 복제하면 되지 않겠는가?"(282-3)
"세계 최초의 인공신경망ANN은 1954년 벨몬트 팔리와 웨슬리 클라크에 의해 구축되었다. 두 사람은 컴퓨터 프로그램으로 점화하는 뉴런의 시뮬레이션을 구성했다. 그들은 숫자를 사용해 뉴런의 상태를 표시하고 입력과 출력의 민감도를 추적했다. 뉴런 네트워크는 간단한 2진수의 이미지를 인식하도록 프로그래밍되었다." "ANN 설계의 난제 가운데, 첫 번째는 적합한 위상수학topology을 선택하는 것이다. 이것은 네트워크에 있는 뉴런들이 어떻게 배열되느냐의 문제다. 위상수학은 층의 수, 각 층의 뉴런 양, 뉴런의 상호 연결 등을 결정하는데, 어느 위상수학을 선택하느냐에 따라 네트워크가 처리할 수 있는 작업의 복잡성에 영향을 준다. 일반적으로 보다 복잡한 패턴 인식 작업을 위해서는 더 많은 뉴런과 층이 필요하다. 두 번째는 네트워크 매개변수 값을 결정하는 것이다. 매개변수는 네트워크의 동작을 제어하기 때문에, 네트워크가 입력을 올바르게 분류하려면 매개변숫값이 정확해야 한다."(288, 293-4)
# 위상수학topology : 공간 속 물체가 가진 점, 선, 면 등의 특성을 토대로 위치와 형상을 탐구하는 수학의 한 분야
"딥러닝 열풍은 음성 인식, 이미지 인식, 차세대 자연어 처리라는 세 가지 파동을 일으켰다. 2012년, 구글의 제프리 힌턴 팀은 정지 이미지에서 실제 사물을 인식하도록 설계된 심층신경망에 대해 보고했다. 그들이 적용한 사물은 고양이, 개, 사람, 자동차, 식물 등과 같은 일상 사물들이었다. 문제는 사물 인식이 단순히 숫자를 인식하는 것과는 크게 다르다는 점이었다. 숫자는 선으로만 구성되어 있지만 사물을 인식하기 위해서는 모양, 색상, 촉감, 윤곽을 전체적으로 분석해야 하기 때문이다. 알렉스 크리제프스키의 이름을 따서 알렉스넷AlexNet이라고 명명된 이 네트워크에는 65만 개의 뉴런과 6,000만 개의 매개변수가 포함되어 있다." "연구 팀은 훈련 중에 몇 개의 뉴런을 임의로 선택해 점화를 막는 기술도 도입했다. 이 기술을 '드롭 아웃'이라고 부르는데, 말 그대로 네트워크가 의사결정 부하를 더 많은 뉴런에 강제로 분산시키는 것이다. 이는 입력 변화에 대해 네트워크를 보다 견고하게 만드는 효과가 있다."(310-1)
12 인간을 넘어서는 지능
"2016년, 이세돌과 대국을 벌인 알파고는 총 3개의 신경망을 사용한다. 첫 번째 ANN은 가치 네트워크다. 이 네트워크는 트리 검색의 끝에 있는 위치에 점수를 매겨 특정 위치에서 이길 확률을 추정한다. 두 번째 ANN은 정책 네트워크다. 이 네트워크는 모든 위치에 대해 얼마나 유망한지에 따라 점수를 매겨 트리 검색을 안내하는 역할을 한다. 만약 어떤 위치가 앞으로의 승리로 이어질 가능성이 크면 높은 정책 점수가 주어진다." "세 번째 ANN은 SL(통제학습)-가치 네트워크다. 이 네트워크는 인간과 같은 방식으로 점수를 매기도록 훈련되었다. 앞 두 가지 네트워크가 실제로 이길 가능성을 제1목표로 여긴다면, SL-가치 네트워크는 컴퓨터가 인간이 결정할 가능성이 가장 큰 수를 예측할 수 있게 해준다." "알파고는 먼저 SL-가치 네트워크를 통제 학습 방식을 사용해 훈련하고, SL-가치 네트워크를 개선해 정책 네트워크를 만든 후에, 다시 정책 네트워크를 사용해 가치 네트워크의 기능을 개선했다."(324-5)
"이후 딥마인드는 알파고 제로라는 새로운 신경망 프로그램에 관한 논문을 『네이처』에 게재했다. 알파고 제로는 축소된 트리 검색과 하나의 신경망만을 사용했다. 이 단일 쌍두 네트워크가 이전 버전인 알파고의 정책 네트워크와 가치 네트워크를 대채한 것이다. 알파고 제로는 오직 강화 학습에만 기반을 둔 새롭고 효율적인 훈련 절차를 사용했다. 인간이 두는 수에 대한 데이터베이스도 필요 없었다. 알파고 제로가 바둑 두는 법을 처음부터 스스로 터득하는 데에는 불과 40일밖에 걸리지 않았다. 40일 동안 알파고 제로는 2,900만 회의 게임을 소화했다. 한 수를 두는 데 5초밖에 걸리지 않았다. 이세돌과 커제를 꺾은 이전 버전 알파고와 벌인 대결에서도 100 대 0으로 승리를 거두었다." "알파고 제로의 소프트웨어에 내장된 알고리즘은 다른 문제에도 적용할 수 있다. 이 기능을 통해 ANN은 새로운 작업을 신속하게 수행할 수 있을 뿐만 아니라, 이전에는 해결할 수 없었던 문제 또한 해결할 수 있게 되었다."(331-2)
13 다음 단계는?
"비트코인은 RSA 공개 키 암호화에 의존해 사용자의 익명성을 보장하고 트랜잭션 인증을 제공한다. RSA 알고리즘의 보안성은 큰 숫자의 소인수분해를 빠르게 수행할 수 있는 알고리즘이 없다는 가정에 달려 있다. 즉, 특정 큰 수를 생성하기 위해 어떤 소수 2개가 곱해졌는지 빠르게 판단할 방법이 없다는 것이다. 21의 소인수는 3과 7이지만, 21이 작은 숫자라 빠르게 답을 계산할 수 있을 뿐이다. 큰 소수의 소인수분해는 슈퍼컴퓨터로도 수십 년 이상이 걸릴 수 있다. 비트코인과 인터넷 보안의 전반적 구조는 이 한 가지 가정에 입각하고 있다. 만일 소인수분해를 빠르게 처리할 수 있는 알고리즘이 개발된다면, 비트코인과 인터넷상의 거의 모든 비밀 메시지는 갑자기 공격에 취약해질 것이다. 1994년에 바로 그런 알고리즘이 생길지 모른다는 우려의 조짐이 처음 나타났다. 다행인 점은, 그런 기적 같은 알고리즘이 작동하기 위해서는 새로운 유형의 컴퓨터가 필요하다는 것이었다. 바로 양자컴퓨터이다."(346)
"양자컴퓨터는 아원자 또는 양자 입자의 특성을 사용해 정보를 나타낸다. 하위 입자의 다양한 물리적 특성을 이용할 수 있는 것이다." "양자 세계에서는 입자들이 동시에 여러 가지 상태로 존재할 수 있다. 이는 중첩의 원리principle of superposition에 잘 요약되어 있다." "데이터 표시에 이런 특성을 활용하면 하나의 전자가 0과 1을 동시에 표시할 수 있다. 양자컴퓨터의 기본 정보 단위인 양자 비트, 즉 '큐비트'를 발생시키는 것이다. 큐비트가 추가되면 양자컴퓨터는 기하급수적으로 강력해진다. 하나의 큐비트는 0과 1이라는 두 값을 동시에 나타낼 수 있다. 큐비트 2개를 사용하면 00, 01, 10, 11의 값을 동시에 나타낼 수 있고, 10개의 큐비트 시스템은 0부터 1,023까지의 모든 10진수값을 동시에 캡처할 수 있다. 양자컴퓨터가 하나의 연산을 수행하면, 그 연산이 동시에 모든 상태에 적용된다." "바로 이런 효과 때문에 양자컴퓨터가 계산을 기하급수적으로 빨리할 수 있는 잠재력을 갖고 있다고 말하는 것이다."(348-9)
