미래를 바꾼 아홉 가지 알고리즘

지은이 / 존 맥코믹 | 옮긴이 / 민병교

미래를 바꾼 아홉 가지 알고리즘
컴퓨터 세상을 만든 기발한 아이디어들
인쇄 / 2013년 5월 24일
발행 / 2013년 5월 31일
지은이 / 존 맥코믹 John MacCormick
옮긴이 / 민병교
펴낸곳 / 에이콘출판주식회사 ( 경기도 의왕시 내손동 757-3)

저렴하지만 훌륭한 신뢰성을 갖춘 복잡한 장시의 시대가 도래했다. 이에는 분명히 원인이 있다. - 바네바 부시,<우리가 생각하는 대로>, 1945

1장 시작하며:컴퓨터를 움직이는 위대한 아이디어들

사실 컴퓨터과학에서 가장 아름다운 아이디어들은 상당수가 매우 추상적이며, 소프트웨어나 하드웨어 분야 어느 쪽에도 속하지 않는다. [23p]

2장 검색엔진 인덱싱 : 세상에서 가장 큰 건초 더미에서 바늘 찾기

1990년대 중반 몇 년 동안 알타비스타는 검색엔진의 왕이었다. 당시 컴퓨터 과학을 전공하는 대학원생이던 내가 알타비스타 검색결과의 포괄성에 감동했던 기억이 생생하다. 최초로 검색엔진은 웹의 모든 페이지에 있는 모든 텍스트를 완전히 인덱싱했다. [35p]

오늘날 ‘인덱스’란 단어는 주로 책 끝에 있는 찾아보기 페이지를 뜻한다. [36p]

가장 단순한 형태의 인덱싱 기술이 복수 단어 쿼리에도 잘 작동하는 것을 보면 지금까지는 검색엔진을 개발하는 것이 꽤 간단해 보인다. 그러나 유감스럽게도 이 단순한 접근은 오늘날 검색엔진에 전혀 적합하지 않다. 이는 구문 쿼리(phrase query)처리 문제다. 구문 쿼리는 페이지 어딘가에 있는 어떤 단어를 막 찾는 것이 아닌 정확한 구문을 검색하는 쿼리이며, 대부분 검색엔진에서 인용 부호를 이용해 입력한다. 예컨대 “cat sat”이라는 쿼리는 cat sat이라는 쿼리와는 전혀 의미가 다르다. cat sat이라는 쿼리는 ‘cat’과 ‘sat’이란 두 단어를 위치와 순서에 상관없이 포함한 페이지를 찾는다. 반면 “cat sat”이란 구문은 ‘cat’바로 다음에 ‘sat’이 뒤따르는 경우를 포함하는 페이지를 찾는다. [38p]

이와 같은 구문 쿼리 문제의 해결책이 오늘날 검색엔진을 잘 작동하게 만든 첫 번째 기발한 발상이다. 이는 인덱스가 페이지 번호뿐 아니라 페이지 안의 위치도 저장해야 한다는 아이디어에서 출발한다. 여기서 언급하는 위치가 특별한 의미를 뜻하진 않는다. 페이지 내에서 단어의 위치를 지칭할 뿐이다. [39p]

랭킹이란 개념을 조금 더 주의 깊게 검토해 보자. 페이지의 ‘순위rank’는 실제로 무엇에 달려 있는가? 진짜 질문은 ‘이 페이지가 쿼리에 부합하는가?’가 아니라 ‘이 페이지가 쿼리에 적합한가?’이다. 컴퓨터과학자는 ‘적합성’이란 용어를 주어진 페이지가 특정 쿼리에 적합하거나 유용한 정도를 기술하는 데 쓴다. [43p]

그러나 컴퓨터는 사람이 아니며, 페이지의 내용을 이해할 수 없기 때문에 검색엔진이 두 검색결과의 순위를 정확히 매기기란 불가능해 보일 수도 있다.
그러나 이런 경우 순위를 바르게 매기는 간단한 방법이 있다. 쿼리 단어가 서로 가까이 있는 페이지가 그렇지 않은 페이지보다 더 적합할 가능성이 높다. [44p]

보통 단어와 같은 방식으로 메타워드를 인덱싱하는 이 간단한 트릭을 ‘메타워드 트릭’이라 부르겠다. 터무니없이 간단해 보일 수도 있지만 메타워드 트릭은 검색엔진이 정확한 결과와 고품질의 랭킹을 내는 데 결정적인 역할을 한다. 잠시 검색엔진이 IN이란 핵심어를 이용한 특수 유형의 쿼리를 지원한다고 가정해 보자. 그래서 boat IN TITLE같은 쿼리는 웹페이지의 제목에 ‘boat’란 단어가 있는 페이지에 해당하는 검색결과만 출력하고 giraffe IN BODY는 ‘giraffe’가 본문에 있는 페이지만 찾는다. [48p]

3장 페이지랭크 : 구글을 출범시킨 기술
페이지랭크를 이해하는 첫 단계는 이 책에서 하이퍼링크 트릭hyperlink trick이라고 부를 간단한 발상이다. -중략- 간단히 각 레시피에 연결된 페이지 수를 세어(하이퍼링크로) 각 페이지에 있는 인커밍 링크incoming link의 수(이 경우 어니에 하나, 버트에 세 개)에 따라 레시피 순위를 매기는 방식으로 접근했다. [56~58p]

전문가의 추천은 일반인의 추천보다 분명히 더 가치가 있다. -중략- 하이퍼링크 트릭과 권위 트릭을 결합하자. 모든 페이지는 1점의 권위 점수로 시작한다. 그러나 한 페이지에 인커밍 링크가 있다면 이를 지칭하는 모든 페이지의 권위를 추가해서 권위를 계산한다. [60~61p]

하이퍼링크는 컴퓨터과학자가 ‘사이클cycle’이라고 부르는 것을 형성할 가능성이 꽤 있다. 사이클은 하이퍼링크를 클릭하다가 출발점으로 되돌아오는 경우를 말한다. [61p]

다행히도 우리는 무작위 서퍼 트릭random sufer trick이라고 부르는 기법으로 닭과 달걀의 문제를 해결할 수 있다. 무작위 서퍼 트릭에 관한 첫 설명은 지금까지 논한 하이퍼링크 및 권위 트릭과 전혀 비슷한 점이 없음을 주의하길 바란다. -중략- 무작위 서퍼 모델과 웹페이지 랭킹에 쓰고 싶은 권위 트릭 사이엔 어떤 관계가 있을까? 무작위 서퍼 시뮬레이션에서 계산한 백분율은 정확히 페이지의 권위를 측정하는 데 필요한 수치다. 그러므로 웹페이지의 서퍼 권위 점수를 무작위 서퍼가 이 페이지를 방문하며 보낸 시간의 백분율로 정의하자. 눈에 띄는 점은 서퍼 권위 점수는 웹페이지의 중요성 순위를 매기는 앞선 두 트릭을 모두 포함한다는 사실이다. 이를 하나씩 검토하겠다.
우선 하이퍼링크 트릭이 있었다. 여기서 주요 개념은 많은 인커밍 링크가 있는 페이지가 더 높은 순위를 받아야 한다는 점이었다. 이는 무작위 서퍼 모델에서도 그렇다. 많은 인커밍 링크를 가진 페이지를 많이 방문할 가능성이 크기 때문이다. 그림 3-6(2)의 페이지 D는 좋은 예다. 이는 (시뮬레이션 페이지 중 가장 많은) 다섯 개의 인커밍 링크를 갖고 있고 결국 가장 높은 서퍼 권위 점수(15%)를 획득하게 됐다.
둘째로 권위 트릭이 있었다. 핵심 개념은 높은 권위를 가진 페이지로부터의 인커밍 링크는 낮은 권위를 가진 페이지로부터의 인커밍 링크보다 페이지의 순위를 높인다는 내용이었다. 이번에도 무작위 서퍼 모델은 이를 감안한다. 인기 있는 페이지로부터의 인커밍 링크는 인기없는 페이지로부터의 링크보다 더 따라갈 기회가 많기 때문이다. 그림 3-6(2)의 페이지 A와 C를 비교해 보라. 각 페이지는 정확히 하나의 인커밍 링크를 가진다. 그러나 페이지 A에 있는 질 좋은 인커밍 링크 덕분에 A가 훨씬 더 높은 서퍼 권위 점수(13% 대 2%)를 획득했다. -중략- 무작위 서퍼 트릭은 권위 트릭과는 달리 하이퍼링크에 사이클이 있는지 여부와 관계 없이 완벽히 잘 작동한다. [63~67p]

또 다른 복잡한 요인은 페이지랭크 계산의 효율성과 연관된다 이 책에서는 서퍼 권위 점수를 무작위 시뮬레이션을 돌려 계산했지만 전체 웹을 대상으로 이렇게 시뮬레이션을 구동하는 것은 너무 오래 걸려 실제로 사용할 수 없을 것이다. 그래서 검색엔진은 무작위 서퍼를 시뮬레이션해 페이지랭크 값을 계산하지 않는다. 대신 무작위 서퍼 시뮬레이션과 같은 값을 제시하면서도 훨씬 적은 계산 비용이 드는 수학 기법을 이용한다. [70p]

4장 공개 키 암호화 : 공개 엽서에 비밀을 적어 아무도 모르게 보내는 방법

‘128비트 암호화’ 같은 특정 비트 수를 명시한 암호화 유형을 들어 봤을 것이다. 여기서 비트 수는 공유 비밀의 실제 길이를 나타낸다. 공유 비밀을 대개 ‘키key’라 부른다. (열쇠로 집의 문을 여는 것처럼) 메시지를 풀거나 ‘복호화decrypt’할 때 키를 이용할 수 있기 때문이다. [79p]

오늘날 암호화 기법은 ‘블록 암호block cipher’라는 변형된 덧셈 트릭을 이용한다.
우선 긴 메시지를 통상 10~15자로 이뤄진 고정된 크기의 작은 ‘블록’으로 쪼갠다. 그 다음, 그냥 메시지 한 블록과 키를 더하는 대신 각 블록을 덧셈과 유사하지만 메시지와 키를 더 공격적으로 섞는 고정된 규칙에 따라 수 차례 변형한다. 예를 들어 ‘키의 앞 절반을 블록의 뒤 절반에 더하고 결과를 뒤집은 다음 키의 나머지 절반을 블록의 마지막 절반에 더하라’. 같은 규칙을 말할 수 있다. 물론 실제 규칙은 이보다 훨씬 복잡하다. [79~80p]

페인트 혼합 트릭은 네 단계로 구성된다.
1) 당신과 아놀드가 각각 ‘개인 색’을 고른다.
2) 당신과 아놀드 중 한 명은 우리가 ‘공개 색’이라고 부를 새로운 색을 공개적으로 발표한다.
3) 당신과 아놀드는 각각 개인 색 한 통과 공개 색 한 통을 섞어 혼합색을 만든다. 이는 당신의 ‘공개-개인 혼합색’을 생산한다.
4) 아놀드의 공개-개인 혼합색 통 하나를 골라 당신의 사적 공간으로 가져가서 여기에 당신의 개인 색 한 통을 더하라. 아놀드도 당신의 공개-개인 혼합색 하나를 그의 사적 공간으로 가져가 그의 개인 색 한 통을 이에 더한다. [83~85p]

수로 하는 페인트 혼합 체계의 유일한 결점은 아무도 나눗셈을 못한다는 ‘가상 수학’을 썼다는 점이다. 가상 수학 같은 방안을 현실로 만들려면 (페인트 혼합처럼) 쉽지만 (섞인 페인트의 분리처럼) 원상태로 되돌릴 수는 없는 실제 수학 계산이 필요하다. 컴퓨터가 실제로 이를 행할 때 혼합 계산은 이산 누승법dicrete exponentiation이라고 부르고 원상태로 돌리는 계산은 이산 로그discrete logarithm라 부른다. 그리고 컴퓨터가 이산 로그를 효율적으로 계산할 방법이 없기에 이산 누승법은 일방향 행위의 종류가 된다. 이산 누승법을 적절히 설명하려면 두 가지 간단한 수학적 개념이 필요하다. -중략-
중요한 첫 번째 수학 개념은 나머지 연산modular arithmetic이라고도 불리는 시계 연산clock arithmetic이다. 이는 사실 누구나 익숙한 개념이다. [92~93p]

거듭제곱과 시계 연산을 이요해 수를 섞는 페인트 혼합 트릭의 최종 버전은 실제로 컴퓨터가 인터넷에서 공유 비밀을 설정하는 방법 중 하나다. 여기서 기술할 방법을 1976년 이 알고리즘을 처음으로 발표한 휘필드 디피와 마틴 헬먼의 이름을 따 디피-헬먼 키 교환 프로토콜이라 부른다. (‘http:’ 대신 ‘https:’로 시작하는) [99p]

디피-헬먼 공개 수에서 가장 중요한 속성은 시계 크기가 소수(prime number)여야 한다는 점이다. 즉 이는 1과 자신 외에 어떤 약수도 갖지 않는다. 또 다른 매우 흥미로운 조건은 기저수가 시계 크기의 원시근(primitive root) 이어야 한다는 점이다. 이는 기저수의 제곱수가 결국 시계에서 가능한 모든 값을 따라 순환한다는 뜻이다. 시계 크기 11에서의 거듭제곱 표를 다시 보면 2와 6은 11의 원시근이지만 3은 아니라는 사실을 알 수 있다. 3의 제곱수는 3, 9, 5, 4, 1을 따라 순환하고 2, 6, 7, 8, 10은 지나친다. [100p]

5장 오류 정정 코드: 데이터 오류를 스스로 찾아 고치는 마법

데이터 전송 및 저장과 관련된 큰 난고나이 있다. 데이터는 정확해야 한다는 점이다. 많은 경우 사소한 실수 하나조차 데이터를 무용지물로 만들 수 있기 때문이다. 인간은 오류 없이 정보를 저장하고 전송하는 것이 얼마나 중요한지는 잘 알고 있다. 예를 들어 다른 사람의 전화번호를 적는다면 모든 숫자를 정확히 그리고 옳은 순서로 기록해야 한다. 숫자 중 하나만 실수를 하더라도 전화번호는 무용지물이 된다. 때에 따라 데이터에서의 오류는 그저 무용지물인 상황보다 더 나쁜 상황을 초래할 수 있다. 예를 들어 컴퓨터 프로그램을 저자한 파일에 있는 오류는 프로그램 충돌을 일으키거나 프로그램의 본래 목적에서 벗어난 일을 하게 될 수 있다. [105~106p]

이 기본 원리는 원본 메시지를 그냥 전송할 수는 없다는 것이다. 신뢰도를 높일 잉여 정보를 보내야 한다. 반복 트릭의 예에서 여러분이 보내는 잉여 정보는 여러 개의 원본 메시지 사본일 뿐이다. 그러나 신뢰도를 향상시키기 위해 보낼 수 있는 잉여 정보의 유형은 다양하다. 컴퓨터과학자는 이런 잉여 정보를 ‘리던던시redundancy’라고 부른다. 때론 리던던시를 원본 메시지에 추가한다. [111p]

아직 리던던시의 작동 원리를 정확히 살펴보지 않았지만 메시지를 더 길게 만드는 일과 관련이 있고 메시지의 각 부분은 일종의 잘 알려진 패턴을 따라야 한다는 점을 이미 봤다. 이런 식으로 어떤 하나의 변형도 (알려진 패턴에 부합하지 않으므로) 확인할 수 있고 (오류를 패턴에 부합하게 바꿈으로써) 정정할 수 있다. 컴퓨터 과학자는 이런 알려진 패턴을 ‘코드워드code word’라 부른다. [112p]

체크섬 트릭을 쉽게 이해하려면 모든 메시지가 숫자로만 구성됐다고 생각하면 된다. 컴퓨터는 모든 정보를 숫자의 형태로 저장하고, 인간에게 정보를 보여줄 때만 이를 텍스트나 이미지로 해석하기 때문에 이는 매우 현실적인 가정이다. 그러나 많은 경우 메시지를 나타내기 위해 어떤 형태의 심벌을 선택하더라도 여기서 설명하는 기법에 영향을 주지는 않는다. 어떤 경우에는 숫자 심벌(숫자 0~9)을 사용하는 것이 더 편리하지만 때론 알파벳 심벌(문자 a~z)의 사용이 더 편리할 수도 있다. 하지만 둘 중 어떤 심벌 집합을 사용해도 무방하도록 두 집합의 심벌간 해석 규칙을 설정할 수 있다. -중략-
숫자 메시지의 단순 체크섬 게산은 정말 쉽다. 수신자는 메시지의 숫자를 취해 모두 더한 다음 결과에서 마지막 자릿수만 남기고 모두 버리면 된다. 이제 남는 숫자가 단순 체크섬이다. [116p]

하지만 이런, 단순 체크섬 시스템은 정말 너무 훌륭해서 진짜일리 없음이 밝혀졌다. 문제는 이렇다. 앞에서 설명한 단순 체크섬은 메시지에서 하나의 오류만을 검출할 수 잇다. 두 개 이상의 오류가 있을 경우 단순 체크섬은 이를 검출할 수도 있지만 검출하지 못할 수도 있다. -중략- 원본 메시지(45756)는 전과 같으므로 체크섬도 8로 같다. 다음 행에 있는 메시지는 오류를 하나 갖고 있다(첫 숫자가 4가 아닌 1이다). 그래서 체크섬은 5다. 사실 숫자가 하나만 바뀌어도 8이 아닌 체크섬이 생성된다고 확신해서, 메시지에 있는 모든 실수의 검출을 보장한다고 생각할 수 있다. 이는 늘 참이라는 사실을 증명하기란 어렵지 않다. 하나의 오류만 있는 경우 단순 체크섬은 이를 100% 검출한다.
표의 다음 행에 두 개의 오류를 가진 메시지가 있다. 첫 두 숫자가 바뀌었다. 이 경우 체크섬은 4다. 4는 원래 체크섬인 8과 다르므로 이 메시지를 받는 사람은 오류가 발생했다는 사실을 실제로 검출하게 된다. 그러나 문제는 표의 마지막 행에서 나타난다. 첫 두 숫자에서 (두 개의) 오류를 가진 메시지다. 그러나 값이 다르고 두 개의 오류를 가진 이 메시지에 해당하는 체크섬은 8이다. 이는 원래 체크섬과 동일하다. 그래서 이 메시지를 받는 사람은 메시지에 오류가 있다는 사실을 검출하지 못한다.
다행히도 우리의 체크섬 트릭에 몇 가지 수정을 추가해 이 문제를 다룰 수 있다. 첫 단계는 새로운 유형의 체크섬을 정의하는 것이다. 이를 계산하는 과정이 계단을 오르는 것이라 생각하면 도움이 되므로 이를 ‘계단staircase’ 체크섬이라 하자. -중략- 이와 매우 유사한 아이디어를 더 긴 메시지에도 적용할 수 있다. 숫자의 덧셈, 숫자를 다양한 형태의 ‘계단’과 곱하기, 고정된 패턴에 따라 일부 숫자 바꾸기 같은 일련의 단순한 계산으로 체크섬을 정의할 수 잇다. 복잡하게 들릴지 몰라도 컴퓨터는 이런 체크섬을 극도로 빠르게 계산하고, 이는 메시지에 있는 오류를 검출하는 데 매우 유용하고 실용적이다. [115~121p]

- 핀포인트 트릭에서 첫 단계는 메시지의 16자리 숫자를 왼쪽에서 오른쪽, 위에서 아래로 읽는 상자 안에 재정렬해 넣는 일이다. -중략- 핵심은 이렇다. 두 값의 차이가 나는 위치가 통신 오류가 발생한 지점을 정확히 말해 준다! 오류는 (다른 모든 행은 정확한 체크섬을 가지므로) 셋째 행에 있어야만 하고 (다른 모든 열이 정확한 체크섬을 가지므로) 둘째 열에 있어야만 한다. 그리고, 오류의 위치는 정확히 하나로 좁혀진다. [125~127p]

컴퓨터과학에서는 핀포인트 트릭을 ‘이차원 패리티two-dimensional parity’라 부른다. 패리티란 컴퓨터가 통상 쓰는 이진수로 작동하는 단순 체크섬을 뜻한다. 그리고 메시지를 이차원 격자grid(행과 열)에 배열하기에 이차원 패리티라고 부른다. 이차원 패리티를 일부 실제 컴퓨터에 이용했지만 이는 그 어떤 리던던시 트릭보다 비효율적이다. 하지만 시각화가 매우 쉽고, 오늘날 컴퓨터 시스템에서 흔히 쓰는 코드 이면의 복잡한 수학을 요하지 않고도 오류를 찾고 정정하는 방법의 묘미를 전달하기에 적합하기 때문에 여기서 설명했다. [128p]

일반적으로 체크섬은 오류 정정보다 오류 검출에 널리 사용된다. 아마도 가장 보편적인 예는 이더넷Ethernet일 듯하다. 이더넷은 오늘날 지구에 있는 거의 모든 컴퓨터가 쓰는 네트워킹 프로토콜로서, CRC-32란 체크섬을 이용해 오류를 검출한다. 가장 유명한 인터넷 프로토콜인 TCP(Transmission Control Protocol:전송 제어 프로토콜)도 보내는 데이터의 각 청크chunk또는 패킷packet에 체크섬을 이용한다. 체크섬이 부정확한 패킷은 그냥 폐기된다. TCP는 필요한 경우 이를 나중에 자동으로 재전송하도록 설계됐기 때문이다. [130p]

6장 패턴 인식과 인공지능 : 사람처럼 학습하고 생각하는 컴퓨터
패턴 인식의 기본 과제는 (여러 사람이 각각 다른 조명 아래서 찍은 얼굴 사진이나, 여러 사람이 쓴 손글시 샘플처럼) 극도로 가변적인 데이터를 취해 유용한 일을 하는 데 있다. [135p]

분명히 컴퓨터는 손으로 쓴 숫자의 모양을 식별하는 지식을 탑재하지 않았다. 사실 인간도 이런 지식을 타고 나지는 않았다. 인간은 명시적 교육(explicit teaching)과 스스로 예를 찾아 보면서 이해하는 자가 교육 과정을 거쳐 숫자 등의 다양한 손글씨를 인식하는 법을 배운다. [137p]

안타깝게도 컴퓨터 손글씨 같은 흥미로운 분류 과제를 풀도록 명시적으로 교육할 수는 없다. 그래서 컴퓨터과학자는 컴퓨터가 샘플의 분류법을 자동으로 ‘학습’하게 하는 또 다른 전략을 지향한다. 기본전략은 컴퓨터에게 엄청난 양의 분류된 데이터(labeled data)를 주는 것이다. 즉 이미 분류된 샘플을 제공한다. [138p]

이는 컴퓨터과학자들이 인접이웃 분류자(nearest-neighbor classifier)라고 부르는 접근 방식이다. 가장 단순한 형태의 인접이웃 트릭은 문자 그대로의 작업을 한다. 분류되지 않은 데이터 샘플을 받으면 우선 훈련 데이터에서 이 샘플에 가장 근접한 이웃을 찾아 이 최근접 이웃의 클래스를 예측값으로 이용한다. [141p]

두 사람의 손으로 쓴 숫자 간 ‘거리’ 계산하기. 각 행에서 두 번째 그림을 첫 번째 그림에서 빼면 오른쪽에 있는 두 이미지의 차이를 강조한 새로운 이미지가 나온다. 이 차이 그림의 백분율을 원본 이미지간 ‘거리’로 간주할 수 있다. [143p]

인접이웃 분류자는 어떤 명시적 학습 단계도 필요하지 않다. [145p]

스무고개 게임은 대개 아이들이 하지만 어른이 해도 놀라운 보람을 준다. 몇 분 지나면 ‘좋은 질문’과 ‘나쁜 질문’이 있다는 사실을 인식하게 된다. 좋은 질문은 많은 양의 ‘정보’ 제공을 보장하지만 나쁜 질문은 그렇지 않다. [145p]

완전한 의사결정나무는 다양한 속성에 의존하지만 여기서 다룰 부분은 페이지에 있는 단어의 인기도에 집중한다. 웹 스패머들은 인기 있는 단어를 많이 집어 넣어 랭킹을 높이고 싶어 한다. 따라서 인기 있는 단어가 적게 포함됐다는 사실은 스팸일 가능성이 낮다는 뜻이다. 이는 이 의사결정나무에서 첫 번째 결정을 의미하며 다른 결정도 이와 비슷한 논리를 따른다. 이 의사결정 나무는 약 90%의 정확도를 달성한다. 이는 완벽에선 거리가 있는 수치지만 웹 스패머와 맞서 싸울 소중한 무기라는 점은 분명하다. [148p]

기본 모델에서 각 뉴런에 역치threshold라 불리는 수를 할당한다. 모델이 작동할 때 각 뉴런은 받는 입력을 더한다. 입력의 합이 역치에 이르면 뉴런은 신호를 쏘고 그렇지 않으면 쉬는 상태를 유지한다. [152p]

가중 신호 더하기
강화 1) 신호는 0 부터 1 사이 값을 취할 수 있다.
강화 2) 총 입력은 가중 합계로 게산한다.
강화 3) 역치의 효과는 약화된다. [156~157p]

이제 인공 신경말 조율의 의미를 정의할 준비가 됐다. 첫째, 모든 연결은 그 비중을 양(흥분성) 또는 음(억제성)이 될 수 있는 값으로 설정해야한다(수천 개의 연결이 있을 수 있음을 기억하라). 둘째, 모든 뉴런에서 역치가 적합한 값으로 설정되게 해야 한다. 밝기 조절이 가능한 전등 스위치처럼 비중과 역치를 신경망의 작은 다이얼로 생각하면 좋다. 물론 이 다이얼을 손수 설정하려면 엄두를 내지 못할 정도로 시간이 많이 걸린다. 대신 학습 단계에서 컴퓨터를 이용해 다이얼을 설정할 수 있다. 처음에 다이얼은 무작위 값으로 설정된다(과도하게 임의적으로 보일 수도 있지만, 전문가들이 실제 애플리케이션에서 이렇게 한다). 그 다음에 컴퓨터에게 첫 훈련 샘플을 제시한다. 우리 예에서 이는 선글라스를 쓰거나 쓰지 않은 사람의 사진이다. 이 샘플은 신경망을 지나 0과 1사이에서 하나의 출력갑슬 산출한다. 그러나 이 샘플은 훈련 샘플이므로 우리는 신경망이 이상적으로 산출해야 할 ‘목표’값을 알고 있다. 핵심 트릭은 출력값이 이상적인 목표값에 더 근접하도록 신경망을 조금 변경하는데 있다. 예를 들어 첫 훈련 샘플 사진에 선글라스가 있다고 가정하자. 그럼 목표값은 1이다. 그러므로 전체 신경망에 있는 모든 다이얼은 출력값이 1이라는 목표를 향해 움직이는 방향으로 조금씩 조정된다. 첫 훈련 샘플 사진에 선글라스가 없다면 모든 다이얼은 반대 방향으로 조금씩 움직여 출력값이 0을 향해 움직인다. 여러분은 이 과정이 어떻게 이어질지 금세 알 수 있으리라 생각한다. 신경망은 차례대로 각 훈련 샘플을 받고, 신경망의 성능이 개선되도록 모든 다이얼이 조정된다. 모든 훈련 샘플을 여러 번 연습한 후 신경망은 성능 수준이 노아지고 학습 단계는 현재 다이얼 설정 상태에서 종료된다. [159p]

신경망 학습 단계는 신경망이 훈련 샘플에 대해 제대로 수행할 때까지 모든 비중과 역치를 반복 조정하는 일을 비롯해 상당한 작업량이 필요하다. 그러나 이 모든 것은 컴퓨터로 할 수 있으며, 새로운 샘플을 단순하고 효율적 방법으로 분류하는 데 이용할 수 있는 신경망이 결과로 산출된다. [160p]

7장 데이터 압축 : 책 한권을 종이 한 장에 담기

JPEG 생략 기법의 세부 내용은 지나치게 전문적이라 여기서 완전히 설명할 수 없지만 이 기법의 기본 발상은 상당히 간단하다. JPEG는 우선 전체 이미지를 8x8픽셀 크기의 작은 정사각형으로 나눈다. 각 정사각형을 개별적으로 압축한다. 압축하지 않으면 각 사각형을 8x8=64개의 수가 대표한다는 점을 주목하라. 우연히 정사각형 안에 있는 색이 모두 같다면 단 하나의 수가 이 사각형 전체를 대표할 수 있고 컴퓨터는 63개의 수를 ‘생략할’ 수 있다. (예컨대 거의 같은 회색 음영인 하늘 지역처럼) 정사각형이 약간의 차이만 있고 거의 동일한 색이라면 컴퓨터는 하나의 숫자로 대체할 수 있고, 압축을 해제했을 때 매우 작은 오류만이 드러나는 괜찮은 압축 결과를 낳는다. -중략- 정사각형이 한 색에서 다른 색으로 점차 변한다면 64개의 수를 두 수로 압축할 수 있다. 하나는 어두운 회색을 대표하는 값이고 다른 하나는 밝은 회색을 대표하는 값이다. JPEG 알고리즘이 정확히 이렇게 작동하진 않지만 유사한 아이디어를 기반으로 한다. 8x8 정사각형이 단색이나 그라디언트처럼 이미 알려진 패턴의 조합에 충분히 가깝다면 정보 대부분을 버릴 수 있고 각 패턴의 수준이나 양만 저장하면 된다. [186~187p]

8장 데이터베이스: 일관성을 향한 여정

컴퓨터과학자들은 이런 유형의 구조를 테이블이라고 부른다. 테이블의 각 행은 하나의 대상에 관한 정보를 담고 있다. 테이블의 각 열은 사람의 나이나 이름 같은 특정 유형의 정보를 담고 있다. [195p]

트랜잭션transaction은 데이터베이스 세계에서 가장 중요한 개념일 것이다. 그러나 트랜잭션의 정의와 필요성을 이해하려면 컴퓨터에 관한 두 가지 사실을 받아들여야 한다. 첫 번째는 누구에게나 익숙한 사실이다. 이는 프로그램이 충돌한다는 점이다. 그리고 프로그램은 충돌하면, 기존에 하던 모든 일을 잊는다. 컴퓨터 파일 시스템에 직접 저장한 정보만 보존된다. 두 번째 사실은 잘 알려져 있지 않지만 매우 중요하다. 이는 하드 드라이브와 플래시 메모리 스틱 같은 컴퓨터 저장 장치는 적은 양의 데이터만을 동시에 쓸 수 있다는 점이다. 이는 약 500자 정도에 해당한다. 컴퓨터 사용자는 한 번에 저장하는 데이터의 양에 이렇게 작은 크기의 제한이 있다는 사실을 눈치채지 못한다. 이는 오늘날 드라이브가 이런 500자 쓰기를 1초에 수백, 수천 번을 실행할 수 있기 때문이다. 그러나 디스크의 내용은 한 번에 수백 글자만 바뀐다는 사실에는 변함이 없다.
도대체 이 두 사실이 데이터베이스와 무슨 관계가 있을까? 이는 매우 중요한 결과를 의미한다. 일반적으로 컴퓨터는 한 번에 데이터베이스의 한 행만을 업데이트할 수 있다. 불행히도 앞에서 제시한 매우 작고 단순한 예는 이를 보여주지 못한다. 앞 테이블 전체의 내용이 200자가 채 안 되기 때문에 컴퓨터가 한 번에 두 행을 업데이트하는 일이 가능하다. 그러나 일반적인 크기의 데이터베이스에서 두 행을 바꾸려면 각각 두 번의 디스크 연산이 필요하다.
이 배경지시기을 토대로 문제의 핵심에 이를 수 있다. 겉보기에 간단해 보이는 많은 데이터베이스 변화는 두 행 이상의 변화를 요한다. 그리고 방금 설명했듯 두 행의 변화를 한 번의 디스크 작업으로 달성할 순 없다. 그래서 데이터베이스 업데이트는 두 번 이상의 연속적인 디스크 작업을 초래한다. 그러나 컴퓨터는 언제든 충돌할 수 있다. 두 번의 디스크 작업 사이에 컴퓨터가 충돌하면 어떻게 될까? 컴퓨터를 재부팅할 수 있지만 컴퓨터는 수행하려 했던 모든 작업을 잊어버린다. 따라서 필수적인 변화가 일부 이뤄지지 않았을 수 있다. 다시 말해 데이터베이스는 일관성 없는 상태로 남을 수도 있다. [196~197p]

불일치에 관한 첫 번째 예에선 자명하게 불일치한 데이터베이스가 도출됐다. 즉 A는 B와 친구지만 B는 A와 친구가 아닌 상황이 발생했다. (데이터베이스가 수백만개의 [혹은 수십 억 개의] 기록을 담고 있다면 검출 과정이 매우 오래 걸릴 수 있지만) 이런 유형의 불일치는 데이터베이스를 검토하기만 하면 쉽게 검출할 수 있다. 불일치에 관한 두 번째 예에서의 데이터베이스는 특정 시점의 스냅샷이라고 간주하면 충분히 개연성이 있는 상황이다. 계좌 잔액이나 계좌 잔액 간 관계를 말해주는 규칙은 없다. 그럼에도 우리는 시간을 두고 데이터베이스의 상태를 검토하면 일관되지 않은 행동을 관찰할 수 있다. 이와 관련한 세 가지 사실이 발견된다. (1) 제이디는 이체 실행 전 $1,100를 갖고 있었다. (2) 충돌 후 제이디에겐 $900만 남았다. (3) 제이디가 중도에 돈을 인출한 적은 없다. 이 세 가지 사실을 한데 놓으면 일관성 없음이 분명하지만, 이 불일치는 특정 시점에 데이터베이스를 검토한다고 해서 발견될 리 없다.
이 두 유형의 불일치를 모두 피하고자 데이터베이스 연구자들은 ‘트랜잭션’이라는 개념을 제시했다. 이는 데이터베이스가 일관적인 경우 모두 일어나야 하는 데이터베이스 변화의 집합이다. [200~201p]

특수한 종류의 할 일 목록을 이용해 데이터베이스 트랜잭션을 할 수 있다. 그래서 이 책에서 이를 ‘할 일 목록’ 트릭이라고 부른다. 컴퓨터과학자들도 유사한 개념으로 ‘미리 쓰기 로그write-ahead logging’란 용어를 쓴다. 기본 개념은 데이터베이스가 수행하려는 동작의 로그를 유지하는 것이다. 로그는 하드 드라이브 같은 영구적 저장 장치에 저장된다. 그래서 로그에 있는 정보는 충돌과 재시작 후에도 살아남게 된다. [202~203p]

이제 로그에 정보가 남아 있으므로, 컴퓨터는 충돌이 일어났을 때 트랜잭션 도중이었음을 알 수 있다. 그러나 로그에는 네 가지 계획한 동작이 있다. 데이터베이스에서 어떤 동작이 수행됐고 어떤 동작이 수행되지 않았는지 어떻게 구별할 수 있을까? 이 질문에 대한 답은 간단하다. 전혀 구별할 필요가 없다! 왜냐하면 데이터베이스 로그에 있는 모든 엔트리는 몇 번 수행되든 상관없이 같은 결과를 내도록 고안됐기 때문이다. [204p]

데이터베이스 사용자의 관점에서 모든 트랜잭션은 원자성atomicity을 띤다. ‘원자적’이라는 단어는 ‘쪼갤 수 없는’이란 뜻의 그리스어에서 유래했다. 수십 년 전 물리학자들에 의해 원자도 분리할 수 있음이 밝혀졌지만, 컴퓨터과학자들이 ‘원자적’이라고 말할 때 이는 쪼갤 수 없다는 원래 뜻을 지칭한다. 따라서 원자적 트랜잭션은 더 작은 작업으로 쪼갤 수 없다. 즉 트랜잭션 전체가 성공적으로 완료되거나 데이터베이스는 트랜잭션이 시작조차 되지 않은 원래 상태로 남아 있어야 한다. [205p]

데이터베이스는 할 일 목록 트릭 덕분에 충돌 시점에 진행 중이던 트랜잭션을 완료하거나 복귀시켜 특정 유형의 충돌을 회복시킬 수 있다. 그러나 이는 충돌 전 저장된 모든 데이터가 여전히 그대로 남아 있을 경우를 전제로 한다. 컴퓨터의 하드 드라이브가 다시 쓸 수 없게 망가져서 데이터의 일부 또는 전체가 소실됐다면 어떠헥 해야 할까? 이는 컴퓨터가 영구적 데이터 손실로부터 피해를 입을 수 있는 다양한 방식 중 하나일 뿐이다. 여타 원인으로 (데이터베이스 프로그램 자체 또는 운영체제의) 소프트웨어 버그와 하드웨어 고장이 있다. 이런 문제 때문에 컴퓨터는 사용자가 하드 드라이브에 안전하게 저장했다고 생각한 데이터를 덮어 써서overwirte 원래 데이터를 파괴하고 쓰레기 데이터로 교체한다. 여기서 할 일 목록 트릭은 도움이 안 된다. [206~207p]

백업은 특정 시점 데이터의 스냅샷이다. 수동 백업을 하는 경우 백업 프로그램을 실행할 때 스냅샷을 찍는 반면, 자동 백업은 매일 오전 2시처럼 주 또는 하루 단위로 특정시점에 시스템의 스냅샷을 찍는다. 다시 말해 백업은 파일이나 데이터베이스 등 여분의 사본이 필요한 모든 정보의 완벽한 사본이다.
그러나 백업은 반드시 최신 상태를 유지하진 않는다. 백업 이후 변화가 발생하면 이 변화는 다른 장소에 저장되지 않는다. 이와 달리 중복 데이터베이스는 데이터베이스의 모든 사본을 늘 동기화하다. 데이터베이스의 어떤 엔트리에라도 아주 작은 변화가 있을 때마다 모든 복제본은 즉시 같은 변화를 반영해야 한다. [208p]

그러나 데이터베이스의 일부는 트랜잭션 중에 그대로 유지돼야한다. 예를 들어 트랜잭션 A가 로시나가 징이의 친구가 됐다고 기록하는 엔트리를 업데이트하는 동시에 실행 중인 트랜잭션 B가 데이터베이스에서 징이를 삭제한다면 끔찍한 결과가 초래된다. 그러므로 트랜잭션 A는 징이의 정보를 담고 있는 데이터베이스의 부분을 ‘잠근다’. 이는 데이터가 그대로 고정돼 있고 어떤 다른 트랜잭션도 이를 바꿀 수 없다는 뜻이다. 대부분 데이터베이스에서 트랜잭션은 개별 행이나 열 또는 테이블 전체를 잠근다. [209p]

컴퓨터과학자들은 교착상태를 매우 상세히 연구했고 많은 데이터베이스는 교착상태 검출 절차를 주기적으로 실행한다. 교착상태가 발견되면 교착상태에 있는 트랜잭션 중 하나가 취소돼 나머지 트랜잭션을 진행할 수 있다 –중략- 핵심은 트랜잭션은 예상치 못한 이유로 완료되지 않을 때가 많다는 사실이다. [211p]

영화 관람 약속을 잡는 전략에 두 단계가 있음을 주목하라. 우선 날짜와 시간을 제안하지만 이는 100% 확실하지 않다. 당신은 모두로부터 해당 날짜와 시간이 가능하다는 회신을 받으면, 이 날짜와 시간은 이제 100%확실하다는 점을 알게 되지만 다른 친구는 아직 모른다. 그러므로 약속을 확정하는 전화를 친구들에게 다시 하는 두 번째 단계가 있다. 또는 한 명 이상의 친구가 이 약속 시간을 맞출 수 없다면 두 번째 단계는 기존 약속을 취소하는 통화가 된다. 컴퓨터과학자들은 이를 2단계 커밋 프로토콜이라고 칭한다. 이 책에서는 이를 ‘준비 후 커밋 트릭’이라 부르겠다. 첫 단계는 ‘준비’단계다. 두 번째 단계는 최초 제안을 모두 수용했는지 여부에 따라 ‘결정’ 또는 ‘중단’ 단계가 된다. [213p]

이제 우리는 마음대로 할 수 있는 데이터베이스 트릭 두 개를 알게 됐다. 이는 할 일 목록과 준비 후 커밋 트릭이다. 이는 우리에게 무엇을 해줄까? 이 두 트릭을 결합하면 은행이(그리고 여타 온라인 개체가) 원자적 트랜잭션으로 중복 데이터베이스를 실행할 수 있으며, 동시에 접속한 수천 명의 고객을 불일치나 데이터 손실 가능성이 전혀 없는 상태에서 응대할 수 있다. 그러나 아직 데이터베이스의 핵심을 보지는 않았다. 이는 데이터 구조화 방식과 쿼리에 답하는 방식이다. [217p]

그러나 오늘날 데이터베이스 테크놀로지의 진짜 힘은 복수의 테이블을 가진 데이터베이스에서 촉발됐다. 기본 아이디어는 각 테이블이 서로 다른 정보의 집합을 저장하지만 다양한 테이블에 있는 대다수 개체는 어떤 식으로든 서로 연결된다는 것이다. [217p]

이 복수 테이블 접근의 이점 하나를 즉시 알 수 있다. 즉 저장해야 하는 정보의 양이 줄어든다. [218p]

테이블에 있는 상세 정보를 ‘찾아보는’ 데 이용하는 열을 데이터베이스 용어로 키key라고 한다. 예를 들어 루이지가 듣는 역사 수업의 강의실 번호를 찾는 방법을 생각해 보자. 단일 테이블 접근(그림 8-4의 위쪽)을 이용하면 루이지의 역사 수업을 찾을 때까지 행을 검색하고 851호란 답을 얻는다. 그러나 복수 테이블 접근에선 우선 첫 테이블에서 루이지의 역사 강의 번호를 찾는다. 이는 ‘HIST’이다. 이제 ‘HIST’을 다른 테이블에서 키로 이용한다. HIST‘의 정보를 포함한 행을 찾아 이 행에서 강의실 번호(851)을 찾을 수 있다. [221p]

데이터베이스의 모든 정보는 고정된 테이블에 저장되지만 데이터베이스는 필요할 때마다 완전히 새로운 테이블을 일시적으로 생성할 수 있다. 이렇게 일시적으로 추가하는 테이블은 어디에도 실제로 저장되지 않는다는 점을 강조하기 위해 이를 ‘가상 테이블’이라고 부르겠다. 데이터베이스는 데이터베이스에 대한 쿼리에 답할 필요가 있을 때마다 이를 만들고 즉시 삭제한다. [222p]

이제 데이터베이스는 셀렉트select라는 또 하나의 중요한 연산을 이용한다. 셀렉트 연산은 특정 기준을 기반으로 테이블에서 일부 열을 선택하고 나머지 행을 버려 새로운 가상 테이블을 만든다. [224p]

9장 디지털 서명 : 진짜 누가 이 소프트웨어를 작성했을까?
10장 계산 가능성과 결정 불가능성: 컴퓨터로 모든 문제를 해결할 수 있을까?
첫째, 어떤 파일이나 입력을 이용해서 어떤 프로그램이라도 실행할 수 있다는 개념이 있다. 그러나 입력 파일이 이를 실행한 프로그램의 목적에 맞는 파일이 아닌 경우, 결과 출력은 주로 쓰레기다. 둘째, 컴퓨터 프로그램도 컴퓨터 디스크에 파일로 저장되므로, 아무 프로그램이나 입력으로 이용해 어떤 프로그램이라도 실행할 수 있다는 사실을 알았다. 셋째, 한 컴퓨터 프로그램은 자기 자신을 입력으로 이용해 실행할 수 있다. [275p]

프로그램 이름
프로그램 동작
CanCrash.exe
-입력이 충돌할 수 있으면 예를 출력한다.
-입력이 절대 충돌하지 않으면 아니요를 출력한다.
CanCrashWeird.exe
입력이 충돌할 수 있으면 충돌한다.
입력이 절대 충돌하지 않으면 아니요를 출력한다.
CrashOnSelf.exe
입력이 자신을 대상을 실행될 때 충돌하면 충돌한다.
입력이 자신을 대상으로 실행될 때 충돌하지 않으면 아니요를 출력한다.
AntiCrashOnSelf.exe
입력이 자신을 대상을 실행될 때 충돌하면 예를 출력한다.
입력이 자신을 대상으로 실행될 때 충돌하지 않으면 충돌한다.
존재할 수 없는 일련의 검출 프로그램 네 가지, 마지막 프로그램인 AntiCrashOnSelf.exe는 명백히 존재할 수 없다. 자신을 대상으로 실행될 때 모순을 산출하기 때문이다. 그러나 각 프로그램은 화살표 위에 있는 프로그램에 작은 변화를 줘서 쉽게 만들 수 있다. 그러므로 네 프로그램 중 어느 하나도 존재할 수 없다.
[291p]

AntiCrashOnSelf.exe가 자신을 입력으로 이용하면 어떻게 될까? 정의에 따라 이 프로그램이 충돌하면 ‘예’를 출력해야 한다(이 프로그램이 이미 충돌했다면 ‘예’를 출력하며 성공적으로 종료될 수 없으므로 이는 모순이다). 또 정의에 따라 AntiCrashOnSelf.exe는 충돌하지 않으면 충돌해야 한다. 이 역시 자가당착이다. AntiCrashOnSelf.exe의 가능한 두 동작을 모두 제거했고 이는 이런 프로그램이 존재할 수 없음을 뜻한다.
이 프로그램이 존재한다면 이 그림의 순서를 따라 변형해 AntiCrashOnSelf.exe를 만들 수 있다. 하지만 우리는 AntiCrashOnSelf.exe가 존재할 수 없음을 이미 알고 있다. 이는 모순이므로 CanCrash.exe가 존재한다는 가정은 거짓임에 틀림없다. [292~293p]

11장 마치면서 : 미래의 알고리즘과 진화하는 컴퓨터

여기서 간단한 비유를 하나 들겠다. 주 연구 관심이 일본 문학인 교수를 만난다고 하자. 이 교수가 일본어를 말하고 일고 쓸 수 있을 가능성은 매우 크다. 그러나 이 교수가 연구를 하면서 주로 무엇에 관해 생각을 하며 시간을 보내는지 여러분에게 묻는다면 ‘일본어’라고 답하진 않을 것이다. 일본어는 일본 문학을 구성하는 주제와 문화, 역사를 연구하는 데 필수적인 지식이다. 반면 완벽한 일본어를 구사하는 사람일지라도 일본 문학에 완전히 무지할 수도 있다. 컴퓨터 프로그래밍 언어와 컴퓨터과학의 관계는 이와 꽤 유사하다. [306p]