Dynamic Programming
무엇을 바꿨나.
이 목록의 논문 중 인용한 것: 없음
이 목록의 논문 중 이 논문을 인용한 것: Minsky 1961, Schmidhuber 2014, Sutton 1988, Sutton & Barto 1998
2장 기호와 퍼셉트론 1956–74
기호 AI와 첫 신경망 (1956–1974)
탐색과 논리로 지능을 쓸 수 있는가, 퍼셉트론은 어디까지 배우는가.
핵심
- 1958년의 퍼셉트론과 1960년의 LISP가 같은 장에 있다. 확률론으로 쓴 학습 기계와 재귀 함수로 쓴 기호 처리 — 뒤의 두 전통이 두 해 사이에 각각 원문을 얻었다.
- Samuel(1959)의 체커 프로그램은 「작성자보다 잘 두게 학습했다」는 문장을 남겼고, Widrow–Hoff의 적응 소자(1960)는 예시로 훈련하는 설계를 적었다. 둘 다 3장의 강화학습 논문들이 인용한다.
- Minsky–Papert의 『Perceptrons』(1969)와 Werbos의 학위논문(1974)은 이 판에서 원문을 확보하지 못했다. 카드에 인용문이 없는 까닭이며, 이 장이 통념상 「첫 겨울」로 끝나는 시기라는 점은 겨울 면에서 수치로 따진다.
1957년 Bellman의 『Dynamic Programming』(Princeton)이 이 장을 연다. 책은 이 판에서 읽지 못해 카드가 비어 있지만, 3장 Sutton(1988)과 4장 Sutton–Barto의 교과서(1998)가 참고문헌에서 이 책을 인용한다. 강화학습 계보의 뿌리로서 점을 찍었다.
Rosenblatt의 「The perceptron」은 1958년 11월 『Psychological Review』에 실렸다. 1장의 McCulloch–Pitts가 기호 논리로 썼던 것을 Rosenblatt는 확률론으로 다시 썼다. 「퍼셉트론이라 부르는 가상의 신경계 또는 기계」를 두고, 무작위로 연결된 단위들의 체계가 특정 자극에 특정 반응을 연합하도록 학습할 수 있다고 결론지었다. 참고문헌에 Hebb 1949와 McCulloch–Pitts 1943이 함께 있다 — 1장에서 따로 흐르던 두 전통이 여기서 만난다.
이듬해 Samuel의 「Some Studies in Machine Learning Using the Game of Checkers」(1959년 7월, 『IBM Journal』)는 암기 학습과 평가 다항식의 계수를 조정하는 일반화 절차 두 가지를 체커에 적용했다. 논문의 문장은 이렇다. 「컴퓨터가 프로그램을 쓴 사람보다 체커를 더 잘 두도록 학습하게 프로그램할 수 있다는 사실을 확인할 만큼의 연구는 이루어졌다.」 Samuel은 Shannon의 체스 논문과 Rosenblatt를 인용했고, 3장의 Sutton(1988)과 Watkins(1989)가 Samuel을 인용한다. 이 네 편이 강화학습 계보의 가장 오래된 실선이다.
1960년에 두 점이 찍힌다. 4월 『Communications of the ACM』의 McCarthy 「Recursive functions of symbolic expressions」는 IBM 704용 프로그래밍 체계 LISP를 기호식에 대한 재귀 함수와 조건식으로 기술했다. 이 논문의 인용문은 저자가 재조판한 사본에서 가져왔고, ACM 게재본은 이 판에서 열지 못했다. 6월 30일 기술 보고서로 나온 Widrow–Hoff의 「Adaptive switching circuits」는 평균 오류를 최소화하도록 이득을 조정하는 적응 뉴런 소자를 제안하고, 설계자가 「입력과 바라는 출력의 예를 보여 주어 체계를 훈련한다」고 적었다. 3장의 Sutton 1988과 Barto 1983이 이 보고서를 인용한다.
Minsky의 「Steps toward Artificial Intelligence」(1961, 『Proceedings of the IRE』)는 탐색·패턴 인식·학습·계획·귀납을 한 편에서 개관한 글로, 3장 Barto 1983이 인용한다. 1961년 1월호에 실렸다.
Minsky–Papert의 『Perceptrons』(1969, MIT Press)는 이 장에서 가장 많이 인용되는 책이다 — Rumelhart 1986, Hopfield 1982, Ackley 1985, Cybenko 1989, Minsky 1974가 모두 인용한다. 단층 퍼셉트론이 어떤 함수를 표현하지 못하는지를 기하학으로 보인 책으로 알려져 있으나, 이 판은 1969년 원판을 열지 못해 카드에 인용문을 싣지 않았다. 1988년 증보판이 아카이브에 있으나 원판 본문과 쪽이 다를 수 있어 쓰지 않았다.
장의 끝에 언어와 역전파가 있다. Winograd의 「Understanding natural language」는 1971년 1월 MIT AI 기술 보고서 235호로 먼저 나오고 1972년 『Cognitive Psychology』에 실렸다. 단순한 로봇 세계에 관한 영어 대화를 절차로 표현한 지식으로 처리하는 체계(SHRDLU)다. Werbos의 하버드 학위논문 「Beyond Regression」(1974)은 다층망의 가중치를 체인 룰로 조정하는 방법을 사회과학 예측 문제에 적용한 것으로 알려져 있다. 공개 사본이 없어 카드가 비어 있고, 전문은 1994년 Wiley 단행본에 수록되어 있다. 역전파의 우선권은 3장의 상자에서 다룬다.
기호 AI의 원문들
McCarthy의 「Programs with Common Sense」는 1958년 11월 테딩턴 국립물리연구소 심포지엄에서 발표되고 1959년 회의록에 실렸다. 지식과 휴리스틱을 술어 계산의 문장으로 적어 두고 거기서 즉각적 결론을 끌어내는 「조언 수용자」를 제안하면서, 「들은 것과 이미 아는 것에서 충분히 넓은 부류의 즉각적 귀결을 자동으로 연역하면」 상식이 있는 프로그램이라고 정의했다. 1960년의 LISP 논문과 1969년의 McCarthy–Hayes가 이 글을 인용한다. 같은 겨울 Newell–Shaw–Simon의 「Report on a general problem-solving program」(RAND P-1584, 1958년 12월 30일 작성·1959년 2월 9일 개정)은 문제의 내용과 일반 해결 기법을 분리하고 수단-목표 분석과 계획을 재귀적 목표로 적용하는 GPS를 기술했다. 참고문헌에 1956년의 논리 이론가가 있다. Robinson의 분해 원리(1965년 1월, 『JACM』)는 대입과 진리함수적 분석을 한 단계로 합친 단일 추론 규칙으로 1차 논리의 완전한 정리 증명 체계를 주었고, Winograd 1972가 인용한다. Zadeh의 「Fuzzy sets」(1965년 6월, 『Information and Control』)는 소속 등급이 0과 1 사이 연속값인 집합을 정의했다 — 이 판은 초록만 읽어 카드가 「부분」이다. Weizenbaum의 ELIZA(1966년 1월, 『CACM』)는 키워드가 촉발하는 분해·재조립 규칙으로 영어 대화를 흉내 낸 프로그램으로, 규칙을 편집 가능한 「스크립트」로 분리했다. 3장의 Searle과 7장의 Generative Agents가 이 논문을 인용한다.
Hart–Nilsson–Raphael의 A*(1968년 7월, 『IEEE Trans. SSC』)는 남은 경로 비용의 추정값으로 그래프 탐색을 이끄는 형식 틀을 세우고, 추정값이 실제를 넘지 않으면(허용 가능) A*가 같은 정보를 쓰는 어떤 허용 가능 알고리듬보다 많은 마디를 펼치지 않음(동점 제외)을 증명했다. 참고문헌에 Samuel 1959가 있고, 3장 Pearl 1988과 7장 Tree of Thoughts가 이 논문을 인용한다. McCarthy–Hayes의 「Some Philosophical Problems from the Standpoint of Artificial Intelligence」(1969, 『Machine Intelligence 4』)는 상황·유동자·행동을 1차 논리로 형식화하고 「프레임 문제」라는 이름을 붙였다. 참고문헌에서 McCarthy 1959, Minsky 1961, Shannon 1950, Turing 1950을 인용한다 — 이 장에서 1장과 가장 많이 이어지는 논문이다. Fikes–Nilsson의 STRIPS는 1970년 10월 SRI 기술 노트 43으로 먼저 나오고 1971년 『Artificial Intelligence』에 실렸다. 세계 모델을 술어 계산 식의 모음으로 두고 수단-목표 분석으로 연산자 열을 찾는 이 문제 해결기는 McCarthy–Hayes를 인용하며, 7장의 SayCan·Inner Monologue가 계획의 원문으로 돌아가 인용한다.
장의 끝에 Lighthill 보고서가 있다. 영국 과학연구위원회의 의뢰로 쓰인 「Artificial Intelligence: A General Survey」는 1972년 7월에 작성되어 1973년에 반론들과 함께 간행되었다. AI 연구를 고급 자동화(A)·중추신경계 연구(C)·그 다리인 로봇 제작(B)으로 나누고, 「이 분야의 어느 부분에서도 지금까지의 발견은 그때 약속되었던 큰 영향을 내지 못했다」고 썼다. 조합 폭발을 실패의 주된 까닭으로 들었고, 본문에서 Winograd 1972를 거명한다. 이 보고서가 영국의 AI 지원을 줄였다는 서술은 널리 받아들여지지만, 겨울 면이 적듯이 금액의 연도별 추이는 자료에 없다.
이 장에서 확인한 것과 못 한 것
18편 가운데 원 인쇄본을 읽은 것은 Rosenblatt, Samuel, Widrow–Hoff(WESCON 회의록), Robinson, Weizenbaum, A* 등이고, GPS는 RAND 보고서 스캔으로, McCarthy 1959·1969는 저자 재조판본으로, Zadeh는 초록만, STRIPS는 기술 노트와 저널 면으로 읽었다. McCarthy는 저자 재조판본, Winograd는 기술 보고서판으로 읽었다. Bellman, Minsky–Papert, Werbos는 읽지 못했다. 이 시기의 후보 가운데 Newell–Shaw–Simon의 논리 이론가(1956), 다트머스 제안서(1955), Selfridge의 Pandemonium(1959), Ivakhnenko(1965)와 Amari(1967)의 다층망 학습, Quillian의 의미 기억(1968)은 교과서 2종 기준을 넘지 못했다.
계보
논문 목록 (18)
Programs with Common Sense
The advice taker is a proposed program for solving problems by manipulating sentences in formal languages.p. 1 (author's web PDF)
조언 수용자는 형식 언어의 문장을 조작해 문제를 푸는 프로그램으로 제안된 것이다.
무엇을 바꿨나. 지식과 휴리스틱을 형식 언어(술어 계산의 일부)의 문장으로 표현하고 그로부터 즉각적 결론을 끌어내어, 문장을 말해 주는 것만으로 행동을 개선할 수 있는 프로그램 「조언 수용자」를 제안했다. 들은 것과 이미 아는 것에서 충분히 넓은 부류의 즉각적 귀결을 자동으로 연역하면 그 프로그램에 상식이 있다고 정의했다.
이 목록의 논문 중 인용한 것: 없음
이 목록의 논문 중 이 논문을 인용한 것: McCarthy 1960, McCarthy & Hayes 1969, Minsky 1961
The perceptron: A probabilistic model for information storage and organization in the brain
The theory has been developed for a hypothetical nervous system, or machine, called a perceptron.p. 387
이 이론은 퍼셉트론이라 부르는 가상의 신경계 또는 기계를 두고 전개되었다.
무엇을 바꿨나. 기호 논리가 아니라 확률론으로 정보가 어떻게 저장되고 인식에 어떻게 작용하는지를 퍼셉트론이라는 가상의 신경계로 설명한다. 무작위로 연결된 단위들의 체계가 특정 자극에 특정 반응을 연합하도록 학습할 수 있다고 결론짓는다.
이 목록의 논문 중 인용한 것: Hebb 1949, McCulloch & Pitts 1943
이 목록의 논문 중 이 논문을 인용한 것: Samuel 1959, Schmidhuber 2014
Report on a general problem-solving program
GPS, the program described in this paper, contributes to the theory of problem solving by embodying two very general systems of heuristics — means-ends analysis and planning — within an organization that allows them to be applied to varying subject matters.p. 2
이 논문이 기술하는 프로그램 GPS는 매우 일반적인 두 휴리스틱 체계 — 수단-목표 분석과 계획 — 를 여러 주제에 적용할 수 있는 조직 안에 담아 문제 해결 이론에 기여한다.
무엇을 바꿨나. 문제의 내용(대상과 연산자의 과제 환경)을 일반적 문제 해결 기법과 분리하고, 수단-목표 분석과 계획이라는 두 일반 휴리스틱을 재귀적 목표로 적용하는 프로그램 GPS-I을 기술한다. 기호 논리와 삼각 항등식의 예를 든다.
이 목록의 논문 중 인용한 것: 없음
이 목록의 논문 중 이 논문을 인용한 것: McCarthy & Hayes 1969, Minsky 1961, Yao et al. 2023
Some Studies in Machine Learning Using the Game of Checkers
Enough work has been done to verify the fact that a computer can be programmed so that it will learn to play a better game of checkers than can be played by the person who wrote the program.p. 211
컴퓨터가 프로그램을 쓴 사람보다 체커를 더 잘 두도록 학습하게 프로그램할 수 있다는 사실을 확인할 만큼의 연구는 이루어졌다.
무엇을 바꿨나. 체커를 재료로 두 가지 기계학습 절차, 곧 암기 학습과 평가 다항식의 항을 조정하는 일반화 절차를 조사한다. 규칙과 방향 감각과 불완전한 매개변수 목록만 받은 프로그램이 8~10시간의 대국 뒤 저자보다 잘 두게 되었다고 보고한다.
이 목록의 논문 중 인용한 것: Rosenblatt 1958, Shannon 1949
이 목록의 논문 중 이 논문을 인용한 것: Barto et al. 1983, Hart et al. 1968, Hochreiter 1991, Minsky 1961, Schmidhuber 2014, Sutton 1988, Sutton & Barto 1998, Tesauro 1995, Watkins 1989, Widrow & Hoff 1960
Recursive functions of symbolic expressions and their computation by machine, Part I
A programming system called LISP (for LISt Processor) has been developed for the IBM 704 computer by the Artificial Intelligence group at M.I.T.p. 1 (author's version)
M.I.T. 인공지능 그룹은 IBM 704 컴퓨터를 위한 LISP(LISt Processor)라는 프로그래밍 체계를 개발했다.
무엇을 바꿨나. IBM 704용 프로그래밍 체계 LISP를 기호식(S-식)에 대한 재귀 함수와 조건식의 형식 체계로 기술한다. 보편 S-함수 apply와 S-식의 리스트 구조 메모리 표현을 제시한다.
이 목록의 논문 중 인용한 것: McCarthy 1958
이 목록의 논문 중 이 논문을 인용한 것: Minsky 1961, Newell & Simon 1975
Adaptive switching circuits
An approach to such problems is taken in this paper which does not require an explicit use of the truth table.p. 96
이 논문은 진리표를 명시적으로 쓰지 않는 접근으로 그런 문제에 다가간다.
무엇을 바꿨나. 평균 오류 수를 최소화하도록 설계한 적응 스위칭 회로를 제안한다. 적응 뉴런 소자의 이득은 훈련 절차에서 성능 피드백으로 정해지며, 설계자는 입력과 바라는 출력의 예를 보여 주어 체계를 훈련한다.
이 목록의 논문 중 인용한 것: Samuel 1959, Shannon 1949
이 목록의 논문 중 이 논문을 인용한 것: Barto et al. 1983, Sutton 1988, Sutton & Barto 1998
Steps toward Artificial Intelligence
Summary—The problems of heuristic programming—of making computers solve really difficult problems—are divided into five main areas: Search, Pattern-Recognition, Learning, Planning, and Induction.p. 8
요약 — 휴리스틱 프로그래밍의 문제, 곧 컴퓨터가 정말 어려운 문제를 풀게 하는 문제는 탐색·패턴 인식·학습·계획·귀납의 다섯 영역으로 나뉜다.
무엇을 바꿨나. 휴리스틱 프로그래밍의 문제를 탐색·패턴 인식·학습·계획·귀납 다섯 영역으로 조직하고, 당시의 문제 해결 프로그램과 문헌을 그 틀로 개관한다. 패턴 인식·학습·계획이 문제 해결 기계가 해야 할 탐색을 줄인다고 논한다.
이 목록의 논문 중 인용한 것: Bellman 1957, Hebb 1949, McCarthy 1958, McCarthy 1960, Newell et al. 1959, Samuel 1959, Turing 1950, Wiener 1948
이 목록의 논문 중 이 논문을 인용한 것: Barto et al. 1983, McCarthy & Hayes 1969, Schmidhuber 2014, Sutton & Barto 1998
A Machine-Oriented Logic Based on the Resolution Principle
Presented in this paper is a formulation of first-order logic which is specifically designed for use as the basic theoretical instrument of a computer theorem-proving program.p. 23
이 논문에서 제시하는 것은 컴퓨터 정리 증명 프로그램의 기본 이론 도구로 쓰도록 특별히 설계한 1차 논리의 정식화다.
무엇을 바꿨나. 대입과 진리함수적 분석을 한 단계로 합친 단일 추론 원리인 분해 원리로 1차 논리 체계를 제시하고 그 완전성을 증명했다. 분해를 쓰는 효율적 증명 절차를 설계하기 위한 탐색 원리를 논했다.
이 목록의 논문 중 인용한 것: 없음
이 목록의 논문 중 이 논문을 인용한 것: Winograd 1971
Fuzzy sets
A fuzzy set is a class of objects with a continuum of grades of membership.page unknown (abstract as shown on the publisher page)
퍼지 집합은 소속 등급의 연속체를 가진 대상들의 부류다.
무엇을 바꿨나. 퍼지 집합을 0과 1 사이의 값을 갖는 소속 함수로 특징지어지는, 소속 등급의 연속체를 가진 대상들의 부류로 정의했다. 포함·합·교·여·관계·볼록성을 이런 집합으로 확장하고, 서로소를 요구하지 않는 볼록 퍼지 집합의 분리 정리를 증명했다.
이 목록의 논문 중 인용한 것: 없음
이 목록의 논문 중 이 논문을 인용한 것: 없음
ELIZA—a computer program for the study of natural language communication between man and machine
ELIZA is a program which makes natural language conversation with a computer possible.p. 36
ELIZA는 컴퓨터와의 자연어 대화를 가능하게 하는 프로그램이다.
무엇을 바꿨나. MIT MAC 시분할 체계에서 입력 문장을 키워드가 촉발하는 분해 규칙으로 분석하고 재조립 규칙으로 응답을 만들며, 규칙은 편집 가능한 「스크립트」로 주는 프로그램 ELIZA를 기술했다. 키워드 식별, 최소 문맥, 변환, 키워드 없는 응답, 이 접근의 심리학적 문제를 논했다.
이 목록의 논문 중 인용한 것: 없음
이 목록의 논문 중 이 논문을 인용한 것: Park et al. 2023, Searle 1980, Winograd 1971
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
This paper describes how heuristic information from the problem domain can be incorporated into a formal mathematical theory of graph searching and demonstrates an optimality property of a class of search strategies.p. 100
이 논문은 문제 영역의 휴리스틱 정보를 그래프 탐색의 형식적 수학 이론에 어떻게 넣을 수 있는지 기술하고, 한 부류의 탐색 전략이 갖는 최적성 성질을 증명한다.
무엇을 바꿨나. 문제 영역에서 끌어낸 남은 경로 비용의 추정값이 그래프 탐색을 이끄는 형식 틀을 주고, 알고리듬 A*와 그것이 허용 가능한 조건을 정의했다. A*가 문제 영역의 정보를 그 이상 쓰지 않는 어떤 허용 가능 알고리듬보다 많은 마디를 펼치지 않음(동점 제외)을 보였다.
이 목록의 논문 중 인용한 것: Samuel 1959
이 목록의 논문 중 이 논문을 인용한 것: Pearl 1988, Yao et al. 2023
Some Philosophical Problems from the Standpoint of Artificial Intelligence
A computer program capable of acting intelligently in the world must have a general representation of the world in terms of which its inputs are interpreted.p. 1 (author's web PDF)
세계에서 지능적으로 행동할 수 있는 컴퓨터 프로그램은 자신의 입력을 해석할 바탕이 되는 세계의 일반적 표현을 가져야 한다.
무엇을 바꿨나. 지능적 프로그램을 만들려면 인식론적으로 적절한 세계 표현이 필요하다고 논하고, 「할 수 있다」·「원인이다」·「안다」를 상호작용하는 자동자 모델로 설명했다. 상황·유동자·행동·전략·지식을 1차 논리로 형식화해 어떤 전략이 목표를 이룸을 증명할 수 있게 하고, 프레임 문제를 비롯한 이 형식화의 어려움을 논했다.
이 목록의 논문 중 인용한 것: McCarthy 1958, Minsky 1961, Newell et al. 1959, Shannon 1949, Turing 1950
이 목록의 논문 중 이 논문을 인용한 것: Amodei et al. 2016, Fikes & Nilsson 1970, Pearl 1988
Perceptrons: An Introduction to Computational Geometry
무엇을 바꿨나.
이 목록의 논문 중 인용한 것: 없음
이 목록의 논문 중 이 논문을 인용한 것: Ackley et al. 1985, Cybenko 1989, Hochreiter 1991, Hopfield 1982, Hornik et al. 1988, Minsky 1974, Rumelhart et al. 1986, Schmidhuber 2014
STRIPS: A new approach to the application of theorem proving to problem solving
This paper describes a new problem-solving program called STRIPS (STanford Research Institute Problem Solver).p. 189
이 논문은 STRIPS(STanford Research Institute Problem Solver)라는 새 문제 해결 프로그램을 기술한다.
무엇을 바꿨나. 각각이 1차 술어 계산 식들의 모음인 세계 모델들의 공간에서, 목표 식이 증명되는 모델에 이르는 연산자 열을 찾는 문제 해결기 STRIPS를 기술했다. 특정 모델에 관한 물음에는 분해 정리 증명기로 답하고, 탐색은 수단-목표 분석으로 이끈다.
이 목록의 논문 중 인용한 것: McCarthy & Hayes 1969
이 목록의 논문 중 이 논문을 인용한 것: Ahn et al. 2022, Huang et al. 2022
Understanding natural language
This paper describes a system for the computer understanding of English.p. 3 (TR-235, Abstract)
이 논문은 컴퓨터가 영어를 이해하는 체계를 기술한다.
무엇을 바꿨나. 단순한 로봇 세계에 관한 영어 대화에서 의미 정보와 맥락을 써서 질문에 답하고 명령을 수행하고 정보를 받아들이는 체계를 기술한다. 지식을 절차로 표현하며, 문법·의미·연역 논리에 각각 절차 언어를 둔다.
이 목록의 논문 중 인용한 것: Robinson 1965, Weizenbaum 1966
이 목록의 논문 중 이 논문을 인용한 것: Ahn et al. 2022, Lighthill 1973
Artificial Intelligence: A General Survey
In no part of the field have the discoveries made so far produced the major impact that was then promised.page unknown (section 3 'Past disappointments')
이 분야의 어느 부분에서도 지금까지의 발견은 그때 약속되었던 큰 영향을 내지 못했다.
무엇을 바꿨나. 과학연구위원회를 위해 AI 연구를 고급 자동화(A)·컴퓨터 기반 중추신경계 연구(C)·그 다리인 로봇 제작(B)으로 나누어 검토하고, 지난 진전에 실망을 표하며 실패의 큰 부분을 조합 폭발에 돌렸다. A와 C는 계속되고 다리 범주 B는 목표에 이르지 못해 분야가 갈라질 것으로 내다봤다.
이 목록의 논문 중 인용한 것: Winograd 1971
이 목록의 논문 중 이 논문을 인용한 것: 없음
Beyond Regression: New Tools for Prediction and Analysis in the Behavioral Sciences
무엇을 바꿨나.
이 목록의 논문 중 인용한 것: 없음
이 목록의 논문 중 이 논문을 인용한 것: Ciresan et al. 2010, Ciresan et al. 2012, LeCun et al. 2015, Schmidhuber 2014, Williams 1992