Leslie Gabriel Valiant(1949년 3월 28일 출생)은 영국계 미국인 컴퓨터 과학자이자 계산 이론가로, 현재 하버드 대학교의 T. Jefferson Coolidge 컴퓨터 과학 및 응용 수학 교수이다. 그는 Probably Approximately Correct(PAC) 학습 모델을 도입하여 계산 학습 이론 분야를 창시하고 머신 러닝의 이론적 기초를 마련한 것으로 가장 잘 알려져 있다. 또한 복잡도 이론에서 #P-완전성 개념과 병렬 컴퓨팅을 위한 Bulk Synchronous Parallel(BSP) 모델을 도입했다. 미국 컴퓨터 협회는 그에게 2010년 A.M. 튜링상을 수여하며, 과학의 깊은 미해결 문제를 다루는 "깊이와 폭의 놀라운 결합"으로 이론 컴퓨터 과학의 "영웅적 인물"이라고 평가했다.
Valiant는 화학 공학자 아버지와 번역가 어머니 사이에서 태어났다. 그는 케임브리지 킹스 칼리지, 임페리얼 칼리지 런던, 워릭 대학교에서 고등 교육을 받았으며, 1974년 워릭 대학교에서 컴퓨터 과학 박사 학위를 취득했다. 1982년 하버드 대학교에 합류하기 전에는 에든버러 대학교, 리즈 대학교, 카네기 멜론 대학교에서 학술 직책을 역임했다.
복잡도 이론과 #P-완전성
1977년, Valiant는 행렬의 퍼머넌트 계산이나 그래프의 매칭 개수 세기와 같은 계수 및 열거 문제를 분류하기 위해 복잡도 클래스 #P(샤프-P)를 도입했다. 그의 연구는 #P-완전성을 복잡도 이론의 기본 개념으로 확립했으며, 많은 신뢰성 및 열거 문제가 검증이 쉬운 결정 문제임에도 불구하고 계산적으로 다루기 어려운 이유를 설명했다. 이 기여는 이론가들이 단순한 결정 작업을 넘어선 문제의 난이도를 이해하는 방식을 재구성했다.
PAC 학습과 계산 학습 이론
1984년, Valiant는 계산적 실현 가능성과 비자명한 논리 규칙 클래스에 대한 적용 가능성을 결합한 귀납 학습 프레임워크를 정의했다. 이후 Probably Approximately Correct(PAC) 학습이라고 불린 이 프레임워크는 학습자가 제한된 수의 샘플에서 일반화하면서 작은 오류 확률을 허용하는 방식을 공식화했다. PAC 학습은 샘플 복잡성과 계산적 실현 가능성에 대한 질문을 다루며 머신 러닝의 이론적 기초를 제공했다. 그의 2013년 저서 Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World는 이러한 아이디어를 확장하여 학습 알고리즘이 컴퓨팅뿐만 아니라 진화와 인지의 기반이 된다고 주장했다. 이 책에서 그는 다윈의 도식이 전반적으로 옳음에도 불구하고 진화 생물학이 진화의 속도와 변화하는 환경에서 복잡한 메커니즘을 발전시키는 능력에 대한 적절한 설명을 제공하지 못한다고 주장했다.
교육과 초기 경력
Valiant는 케임브리지 킹스 칼리지와 임페리얼 칼리지 런던에서 공부한 후 1974년 워릭 대학교에서 컴퓨터 과학 박사 학위를 마쳤다. 오토마타 이론에서의 그의 초기 연구는 문맥 자유 파싱을 위한 알고리즘을 생산했으며, 이는 현재까지 알려진 점근적으로 가장 빠른 방법으로 남아 있다. 그는 또한 계산 분석에 그래프 속성을 사용하는 선구자 역할을 하여 구조적 그래프 이론을 알고리즘 효율성과 연결했다.
계산에 대한 기여
Valiant의 연구는 이론 컴퓨터 과학의 여러 영역에 걸쳐 있다. 그는 열거 및 신뢰성 문제가 다루기 어려운 이유를 설명하기 위해 #P-완전성 개념을 도입했으며, 첫 번째 적용 사례는 행렬 퍼머넌트 함수였다. 1984년에는 예제로부터 학습에 대한 엄격한 정의를 제공하고 인공 지능의 기초가 된 PAC 학습 모델을 제안했다. 그는 또한 양자 계산에서 영감을 받은 홀로그래픽 알고리즘을 개발했으며, 현재까지 점근적으로 가장 빠른 것으로 알려진 문맥 자유 파싱 알고리즘으로 오토마타 이론에 초기 기여를 했다. 1990년대에 Valiant는 폰 노이만 모델과 유사하지만 병렬 아키텍처를 위한 Bulk Synchronous Parallel(BSP) 모델을 공식화했으며, 이는 구글의 Pregel과 Beam, 그리고 Hadoop과 Spark와 같은 오픈 소스 프로젝트에 영향을 미쳤다.
교육과 학문적 경력
Valiant는 케임브리지 킹스 칼리지에서 공부한 후 임페리얼 칼리지 런던에서 공부했으며, 1974년 워릭 대학교에서 컴퓨터 과학 박사 학위를 받았다. 그는 에든버러 대학교와 카네기 멜론 대학교에서 가르친 후 1982년 하버드 대학교에 합류하여 그 이후로 그곳에 머물렀다. 하버드에서 그는 이론 컴퓨터 과학과 계산 신경과학 분야에서 일하며 기억과 학습 과정을 이해하는 데 중점을 두었다.
PAC 학습과 머신 러닝
Valiant가 1984년에 도입한 PAC 모델은 학습자가 유한한 예제 집합에서 일반화할 수 있는 조건을 공식화했다. 이 프레임워크는 계산적 실현 가능성과 논리 규칙 학습을 조화시켰으며 - 이는 계산 학습 이론의 초석이 되고 실용적인 인공 지능 시스템 개발에 영향을 미쳤다. 그의 2013년 저서 Probably Approximately Correct는 이러한 아이디어를 생물학과 진화로 확장하여, 현재의 진화 이론이 진화적 진보의 속도를 적절히 설명하지 못하며 학습 이론이 유용한 비유를 제공한다고 주장했다.
병렬 및 분산 컴퓨팅
1990년에 도입된 Valiant의 Bulk Synchronous Parallel 모델은 장벽 동기화를 사용한 슈퍼스텝으로 실행을 구성하여 병렬 계산을 위한 하드웨어와 소프트웨어 사이의 다리를 제공한다. 이 모델은 구글의 Pregel과 오픈 소스 프로젝트인 Apache Giraph, Apache Hama, Apache Beam, Dask와 같은 분산 처리 시스템에 영향을 미쳤다. 그의 Xerox PARC에서의 초기 작업과 관련된 맥락 및 이후 학술 연구는 현대 데이터 센터에서 사용되는 확장 가능한 그래프 분석 엔진의 기초를 마련했다.
수상 및 영예
Valiant는 1986년 네반린나 상, 1997년 커누스 상, 2008년 EATCS 상, 2010년 A.M. 튜링 상을 받았다. 그는 1997년 왕립학회 회원(FRS)으로 선출되었고 미국 국립 과학 아카데미 회원이 되었다. 그의 튜링 상 인용문은 PAC 학습 이론, 열거 및 대수 계산의 복잡성, 병렬 및 분산 컴퓨팅 이론에 대한 그의 변혁적 기여를 인정했다.
개인 생활
Valiant는 결혼했으며 두 아들 Gregory Valiant와 Paul Valiant를 두고 있으며, 둘 다 컴퓨터 과학자이다. Gregory는 스탠포드 대학교에서 알고리즘과 통계를 연구하고, Paul은 계산 복잡성과 암호학을 연구한다. Valiant의 가족은 이론 컴퓨터 과학에 대한 그의 헌신을 공유하며, 두 아들 모두 각자의 연구를 통해 이 분야에 기여하고 있다.