재미있는 인공지능(AI) 이야기(#4)

rgbi3307의 이미지

앞의 연재(#3)에서는 AI의 기본원리에 대해서 철학적으로 접근했으나,
이번 연재(#4)에서는 수학적으로 접근합니다.

수학(Mathematics)

* 타당한 결론을 이끌어내기 위한 정형화된 규칙은 무엇인가?(논리)
* 무엇이 계산될 수 있는가?(계산)
* 불확실한 정보에 어떻게 의미를 부여하는가?(확률)

철학자들은 AI에 대해서 몇가지 근본적인 생각들을 도출해 냈으나,
이것에 정형화된 수학 공식들을 도입하여 좀더 과학적으로 접근해 보자.
AI에 근본적으로 적용되는 수학 영역은 논리, 계산, 확률이다.

논리에 대한 기본 원리는 고대 그리스 철학자들로 부터 시작되었으나, 이것을 수학적으로 발전시킨 사람은
George Boole(1815-1864) 이었다. 그는 1847년에 명제, Boolean, 논리등에 대해서 자세한 연구결과를 발표했다.

1879년에 Gottlob Frcgc(1848-1925)는 Boole의 논리를 좀더 확장시켜 객체와 관계들을 처음으로 포함시켰다.
이것은 오늘날의 수학적 논리에 사용된다.
Alfred Tarski(1902-1983)는 참조 이론을 소개 했는데,
이것은 실제 생활속의 객체들에 논리를 연관시키는 방법에 관한 것이었다.

이러한 논리를 계산적으로 적용하는 데에는 몇가지 제한 사항들이 있는데, 이것을 알아보자.
첫째로 중요한 알고리즘이라 할 수 있는 것으로 Euclid의 최대공약수(Greatest Common Divisor) 알고리즘이 있다.
다음으로 word 알고리즘이 있는데, 이것은 9세기 페르시아의 수학자 al-Khowarazmi가 발표한 것이다.
그는 또한 아라비아 숫자와 대수(algebra)를 유럽에 소개했다.
알고리즘은 대부분 논리적인 추론으로 표현되었고,
19세기 후반에는 이러한 노력들로 인해 논리적 추론이 수학적으로 공식화되게 된다.

1930년에 Kurt Godel(1906-1978)은 Frege와 Russell의 first-order 논리의 참을 증명하기 위한
효과적인 절차가 존재한다고 했다. 그러나, first-order 논리는 자연수를 특성화 시키는데 필요한
수학적 유도의 원리를 제대로 잡아내지 못했다.
1931년에, Godel은 추론에는 제약사항들이 존재한다고 했다.
그의 완성되지 못한 이론은 다음과 같은 사항을 보여준다.
Peano 산술(자연수 원리론) 만큼이나 강력한 정형화된 이론에서는
증명할 것이 없다라는 관점으로 증명 불능을 논하는 것이 옳은 방법이다.(난해함(^^))

이러한 근본적인 결과는 정수를 다루는 몇몇 함수들은 알고리즘으로 표현할 수 있다라는 것을 보여준다.
Alan Turing(1912-1954)은 이것에서 영감을 얻어,
이러한 함수들이 계산가능 하다라는 것을 보여주기 위한 시도를 했다.

이 개념에는 몇가지 문제점들이 있었다. 왜냐하면, 효과적인 절차 혹은 계산의 개념에
형식 잡힌 정의가 주어지지 않았기 때문이다.
그러나, Turing 논문에서 Turing machine(Turing, 1936)은 어떠한 계산적인 함수라도 계산해낼 능력이 있고,
충분한 정의가 제공된 것을 일반적으로 적용한다라고 했다.
또한, Turing은 Turing machine이 계산해낼 수 없는 함수들이 몇가지 있다라고 했다.
예를들면, 주어진 프로그램이 제시된 입력에 대해서 해답을 출력할지 아니면 영원히 수행하고 있을지는
machine이 알수가 없다라고 했다.

결정능력과 계산능력이 계산을 이해하는데 중요하지만, 이해하기 쉬운 개념이 더 강력한 영향력을 가진다.

아주 다루기 힘든 문제를 어떻게 인식할 수 있을까?
NP-완전성(NP-completeness) 이론을 개척한 Steven Cook(1971)과 Richard Karp(1972)가 그 방법을 제공했다.
Cook과 Karp는 표준적으로 조합하는 검색의 사례들이 많이 존재함을 밝히고 NP-complete 문제들의 사유를 보여주었다.
NP-complete 문제들로 줄일 수 있는 문제는 다루기 힘들 것이다.

컴퓨터의 속도가 빨라지고 있지만, 주어진 자원들을 주의깊게 활용해야 지능적인 시스템의 모습을 갖출 수 있다.
세상은 아주 큰 문제로 이루어져 있다.
AI 분야에서 일하다보면 NP-complete 문제들이 왜 어려운지 알게 될 것이다.

지금까지 논리와 계산에 대해서 언급했는데, 세번째로,
AI에 대해서 수학적으로 접근하는 것으로 확률이론이 있다.

이탈리아의 Gerolamo Cardano(1501-1576)는 확률에 대해서 최초로 형틀을 만든(규격화한) 사람이었다.
그는 확률을 도박적인 결과로 나타나는 것으로 기술했다.
1654년에 Blaise Pascal(1623-1662)는 Pierre Fermat(1601-1665)에게 보낸 편지에서,
완료되지 않은 도박 게임의 미래를 어떻게 예측하는지 보여 주었고, 도박꾼들에게 평균적인 보상을 제공했다.

확률은 정량적인 것을 다루는 과학에서 점점 가치 없는 것으로 되었지만,
불확실한 측정이나 완료되지 않은 이론을 다루는 데는 도움을 주고 있다.
James Bernoulli(1654-1705), Pierre Laplace(1749-1827) 등은 확률이론을 좀더 개선하여
새로운 통계적인 방법들을 소개했다.
Thomas Bayes(1702-1761)는 확률에 대해서 새로운 믿음을 가질만한 규칙을 제안했다.
Bayes의 규칙은 현대의 AI 시스템에서 불확정적인 사유를 다룰때 배경지식으로 사용된다.


PS. 이번에는 AI의 기본을 수학적으로 얘기했습니다.
난해한 부분일수록 되도록이면 쉽게 기술해야 하는데,
저의 부족함으로 인해 문장이 매끄럽지 않아 읽기 힘든 부분이 많을 듯 합니다.
특히, NP-complete 문제를 의역할때는 머리에서 쥐가 나더군요(^^).
많은 지적과 조언 바랍니다.
다음 연재는 AI를 경제학적으로 얘기합니다.
수학 보다는 조금 더 재미 있을듯... 많은 기대 바랍니다~

참고서적:
Artificial Intelligence: A Modern Approach (3rd Edition)
by Stuart Russell, Peter Norvig

의역:
Jung,JaeJoon(rgbi3307(at)nate.com) on the www.kernel.bz

게시일:
2011년 10월 17일

댓글

snowall의 이미지

잘 읽는 중입니다.

피할 수 있을때 즐겨라! http://melotopia.net/b

익명 사용자의 이미지

평소 관심을 가지고 있던 분야였는데
부족한 지식이 채워지는 것 같습니다.
앞으로도 꾸준한 연재 부탁드립니다.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.