1. 소식
  2. arrow_forward_ios

새 소식

태그
검색
과거 미분류

[문병로의 알고리즘 여행] 생물정보학의 초석을 놓은 낸시 웩슬러

출처: 중앙일보 2020년 10월 25일자 [문병로의 알고리즘 여행] 어떤 학문 분야에서 엉뚱한 분야의 사람이 결정적인 영감을 주고 발전을 이끄는 경우가 있다. 1968년 23살의 낸시 웩슬러는 어머니가 헌팅턴병이란 사실을 알게 되었다. 신체가 춤추듯 움찔거리고 끝에는 정신도 나가버리는 유전병이다. 부모 중 한 명이 환자이면 자식의 발병 확률은 50%다. 낸시와 엘리스 자매는 평생 자식을 갖지 않기로 결정했고, 낸시는 이 병의 연구에 평생을 바치기로 한다. 낸시는 72년 미시간대학에서 심리학 전공으로 박사 학위를 받고 교수가 된다. 인간의 DNA는 A·C·T·G라 이름 붙은 4개의 기호가 30억개 정도 연결되어 있다. 이 30억개는 23쌍의 염색체로 나누어져 있다. 낸시의 여정은 이 30억 길이의 띠에서 하나의 유전자를 찾는 것이었다. 백사장에서 쌀알 찾기 같은 일이다. 처음에는 헌팅턴병이 느리게 자라는 바이러스 탓인지 의심하던 수준이었다. 낸시는 환자의 뇌에서 시료를 추출해 침팬지의 뇌에 주사해 보기도 했다. 결국은 바이러스가 원인은 아니고 유전자를 찾는 것으로 방향이 잡혔다. 심리학자인 아버지 밀턴 웩슬러와 낸시는 유전병 재단을 만들어 과학자들과 함께 워크숍을 거듭했다. 뜬금없는 아이디어가 속출했다. 낸시가 참석자들을 독려했다. “지금 단계에서 누가 유용한 아이디어와 실수를 구분할 수 있겠어요?” 주변을 들뜨게 하는 비범함을 가진 사람들이 있다. DNA는 너무나 방대하기 때문에 탐색하기가 막연하다. DNA 내부에 마커를 설정해야 한다는 아이디어가 나왔다. 마커는 도로의 이정표 같은 것이다. 암수가 교접하면 두 DNA가 절단되어 섞인다. 마커와 어떤 유전자 사이가 절단되면 같이 자식으로 전해지지 않는다. 절단 점이 임의로 정해지므로 가까이 있을수록 같이 전해질 확률이 높다. 여러 마커를 만들어두고 헌팅턴병 환자의 DNA에서 유독 높은 비율로 존재하는 마커가 있으면 그 마커 근처에 헌팅턴 유전자가 있을 거라는 논리였다. 실패가 거듭되었다. 1983년 드디어 환자들에게서 공통적으로 관찰되는 마커를 발견했다. 4번 염색체에 있었다. 이제 범위가 좁혀졌다. 낸시의 여정 15년 차쯤이다. 그렇다 해도 범위가 30억 크기에서 1억 정도로 좁혀진 것이니 갈 길은 멀었다. 6개의 국제 연구팀이 만들어졌다. 10년간 실패를 거듭한 끝에 드디어 93년에 헌팅턴병을 일으키는 DNA 서열을 발견한다. 낸시의 여정 25년 만의 일이다. 그동안 낸시는 끊임없이 환자들을 만나서 역학조사를 하고 1200본이 넘는 혈액 샘플을 채취해서 과학자들에게 제공했다. 과학적 성공은 대부분 실패의 기록이다. 가물에 콩 나듯 발견되는 몇몇 결과들이 성공을 만든다. 25년이란 시간을 좌절하지 않고 한 방향으로 나갈 수 있는 힘은 쉽게 가질 수 있는 것이 아니다. 이 과정에서 마커 관찰, 유전자를 이어 붙이는 방법을 비롯해서 많은 아이디어들이 도출되었다. 후에 휴먼 지놈 프로젝트가 인간 DNA 전체의 염기서열을 규명하게 되는데 여기에 결정적인 바탕을 제공한 한 사람을 들라면 낸시 웩슬러다. DNA 염기서열은 기계가 연속해서 읽을 수 있는 길이가 극히 제한된다. 그래서 서로 중복이 있는 조그만 조각들로 잘라 전체 서열을 추정해야 한다. 변이로 인한 에러까지 감안해야 한다. 이 과정에서 컴퓨터 알고리즘 연구자들이 결정적인 기여를 했다. 이로 인해 DNA 서열분석이라는 분야가 만들어졌고, 확장을 거듭해 생물정보학이라는 거대한 분야가 만들어졌다. 빅데이터의 대표적 응용 예다. 헌팅턴병은 4번 염색체 끝부분에 CAG라는 기호서열이 40번 이상 반복되면 확실히 발병한다. 30번 이하이면 발병하지 않는다. 41번이면 대략 51세에, 42번이면 37세에, 50회면 27세 무렵에 지능을 잃는다. 지금은 이 유전자를 가졌는지 간단히 테스트할 수 있고, 배아 단계에서 결함 부분을 잘라내고 인공수정을 할 수 있는 수준까지 왔다. 50%의 발병 확률을 가진 낸시는 자신의 노력으로 가능하게 된 유전자 검사를 하지 않기로 한다. 필자는 가끔 그녀의 근황을 살펴보곤 했다. 오랜만에 그녀의 인터뷰 영상을 보았다. 2016년 71세인 그녀의 어깨와 팔이 춤추고 있었다. 슬프게도, 여전히 밝은 얼굴로. 75세의 그녀는 더 악화하였을 것이다. 신경심리학 전공으로 생명과학과 컴퓨터 알고리즘의 한 분야에 거대한 추동력을 제공한 거인에게 감사와 연민의 마음을 전한다. 서울대학교 컴퓨터공학부 문병로 교수 ...
포스트 대표 이미지
포스트 대표 이미지
포스트 대표 이미지

이준영 박사과정생, LLVM 개발자 미팅 기조강연

소프웨어원리 연구실 이준영 박사과정 학생, 세계 선도 컴파일러 개발 시스템 (LLVM) 개발자 회의에서 기조 강연 컴퓨터공학부 허충길 교수 연구실에서 박사과정 중인 이준영 학생이 올해 열리는 LLVM 개발자 미팅(2020 LLVM Developer's Meeting)에서 키노트 발표자로 선정되었다. Undef and Poison: Present and Future라는 주제로 2020년 10월 6일 미국 서부 시간 (PDT) 오전 8시(한국 시간 10월 6일 밤 자정)에 온라인으로 발표할 예정이다. 박사과정 학생이 LLVM 개발자 미팅에서 키노트 발표를 하는 것은 처음 있는 일로, 그동안 이준영 학생이 주도해온 연구가 산업계에서 큰 주목을 받아 이루어진 결과이다. 박사과정 중 이준영 학생은 LLVM 컴파일러 중간 언어에 존재하는 Undef와 Poison Value라는 개념과 관련된 문제점 및 해결책을 연구해 왔으며, 이 결과로 freeze라는 명령어를 제안하여 작년 11월 공식적으로 LLVM에 추가되었다. 이 후 freeze를 사용해 여러 LLVM 컴파일러 오류들을 고쳤으며, 컴파일러 개발자들이 freeze 명령어를 쉽게 사용할 수 있도록 다양한 패치들을 LLVM 프로젝트에 추가하였다. 키노트 발표에서는 Undef 및 Poison 관련하여 지금까지 있어왔던 문제, 이를 해결하기 위해 있어왔던 노력, 그리고 앞으로 남은 문제 및 이를 해결하기 위한 방향에 대해 이야기할 예정이다. 참고로 LLVM은 현재 Apple, Google, Facebook 등 세계 유수 회사 및 여러 오픈소스 프로젝트에서 사용되고 있는 컴파일러 인프라(Compiler Infrastructure)이며, 대표적인 프로젝트로는 C/C++ 컴파일러 Clang, Apple의 Swift 언어, Google의 Tensorflow 프로젝트, 그리고 프로그래밍 언어 Rust가 있다. LLVM 개발자 미팅(LLVM Developer’s Meeting)은 LLVM 관련 가장 큰 모임으로써 매년 2회 (유럽 1회, 산호세 1회) 개최되며, 매번 수백명의 산업계 개발자들이 참여하는 중요한 모임이다. 이번 모임은 10월 6일부터 3일간 온라인으로 열리며, 1회의 키노트 발표 외 60회의 다양한 구두 발표 및 11개의 포스터 발표로 구성되어 있고, 총 1500여명이 참여한다. 2020 LLVM 개발자 미팅 웹페이지: https://llvm.org/devmtg/2020-09 Freeze 관련 연구 웹페이지: https://sf.snu.ac.kr/freeze...
포스트 대표 이미지
포스트 대표 이미지

이영기교수 연구진, 증강현실 개선기술로 세계적으로 주목받는 중

서울대학교 이영기 교수 연구진, 증강현실 개선기술로 세계적으로 주목받는 중 원거리 사람 인식 기술, 복잡한 도심에서 범인 찾기등 실시간, 고정밀 AR 서비스 가능해져 소형 AR 기기를 위한 딥러닝 실행 기술, AR 컨텐츠 다양화 및 사용자 경험 증진에 큰 기여 3D 비디오 실시간 스트리밍 기술, 텔레프레전스, 원격의료 서비스를 위한 현장감 극대화 이영기 교수 연구진이 증강현실(Augmented Reality, AR)을 위한 모바일 딥러닝 시스템 및 3D 비디오 스트리밍 시스템 원천기술을 개발하였다. 특히, 복잡한 도심 공간에서의 고속, 고정밀 얼굴 인식을 위한 EagleEye 시스템은 기존 모바일 시스템들의 인식 정확도 및 지연 시간을 크게 개선하여 범인 추적, 실종 아동 찾기 등 다양한 AR 응용에 활용될 것으로 예상된다. 또한, AR 응용을 위한 모바일 GPU 스케줄링 플랫폼 Heimdall은 미래형 AR 응용의 핵심 요구사항인 다중 딥 뉴럴 네트워크(Deep Neural Network, DNN) 및 렌더링 연산의 동시 수행을 효율적으로 지원하지 못하는 기존 모바일 딥러닝 프레임워크들의 한계를 극복하여 AR 응용 개발 및 확산에 크게 기여할 것으로 기대된다. 고해상도 3D 볼류메트릭(volumetric) 비디오 스트리밍을 위한 모바일 시스템 GROOT 역시 미래형 AR 응용에 필수적인 차세대 3차원 미디어의 실시간 스트리밍을 지원하여 텔레프레전스(telepresence), 원격의료 등 새로운 사용자 경험 제공에 핵심기술이 될 것으로 전망된다. EagleEye [1]: 이영기 교수 연구진(제 1저자: 이주헌 박사과정)은 모바일/웨어러블 기기를 활용한 선도적 얼굴 인식 AR 응용 시스템 EagleEye를 개발하였다. 핵심 기술로, 복잡한 도심 공간 속에서의 얼굴 인식 정확도를 높이기 위해 먼 거리에서 촬영된 저해상도 얼굴의 화질을 개선하는 딥러닝 알고리즘을 개발하였다. 또한, 고화질 비디오 입력 데이터에 다중 DNN 연산을 반복적으로 수행해야 하는 얼굴 인식 알고리즘(그림 1)의 성능 문제가 심각함을 보이고, 입력 비디오의 장면 구성에 따라 다양한 DNN을 적응적으로 선택하여 모바일 및 클라우드에서 병렬처리하는 파이프라인을 개발하였다(그림 2). 이를 통해, 기존 순차적 연산 수행 대비 약 9배 지연 시간 성능 향상을 달성하였다. https://cse.snu.ac.kr/sites/default/files/node--notice/20200907_%EC%9D%B4%EC%98%81%EA%B8%B01.png Heimdall [2]: 이영기 교수 연구진(제 1저자: 이주헌 박사과정) 미래형 AR 응용 워크로드를 지원하기 위한 선도적 모바일 GPU 스케줄링 플랫폼 Heimdall을 개발하였다. 기존의 모바일 딥러닝 프레임워크는 단일 DNN을 독립적으로 실행하도록 설계되어, 모바일 GPU에서 다중 DNN과 렌더링 연산을 동시 수행 시 자원경쟁으로 인한 심각한 성능 저하가 발생한다(그림 3). 이러한 한계를 극복하기 위해, 연산 수행시간이 긴 DNN을 작은 스케줄링 단위로 나누고, 동시 수행되는 GPU 작업을 우선순위를 기반으로 유연하게 스케줄링하기 위한 Pseudo-Preemption 메커니즘을 제시하였으며, 이에 기반한 GPU 스케줄러를 개발하였다(그림 4). Heimdall은 기존 모바일 딥러닝 프레임워크 대비 렌더링 프레임 레이트 약 3배 향상, DNN 추론 연산 수행시간 최대 15배 감소 성능을 달성하였다. https://cse.snu.ac.kr/sites/default/files/node--notice/20200907_%EC%9D%B4%EC%98%81%EA%B8%B02.png GROOT [3]: 이영기 교수 연구진(제 1저자: 이경진 연구원)은 모바일 기기에서 고해상도 3D 볼류메트릭 비디오의 실시간 스트리밍을 지원하는 최초의 시스템 GROOT 개발하였다. 3D 볼류메트릭 비디오(그림 5)은 미래형 AR 응용에서 높은 사용자 몰입도를 제공하기 위한 핵심 미디어 기술이다. 하지만, 3D 볼류메트릭 비디오는 기존 2D, 360° 비디오보다 데이터 용량이 매우 크며, 2D 비디오의 그리드 구조와 달리 3D 데이터 구조는 불규칙적이고 희소성이 높아 병렬처리가 어려워 기존 프레임워크로 실시간 디코딩이 불가능하다. 이러한 한계를 극복하기 위해 볼류메트릭 비디오를 병렬적으로 디코딩할 수 있는 데이터 구조를 개발하고, 실시간 프레임 레이트를 달성하는 스트리밍 파이프라인을 설계하여(그림 6) 기존 프레임워크 대비 약 9배 프레임 레이트 향상을 달성하였다. https://cse.snu.ac.kr/sites/default/files/node--notice/20200907_%EC%9D%B4%EC%98%81%EA%B8%B03.png 이영기 교수 연구진은 모바일 컴퓨팅 분야 플래그십 컨퍼런스인 ACM MobiCom 2020에 3편의 논문을 게재 예정이다. 이는 세계적으로 사례가 적은 우수한 성과이다. MobiCom 2020 홈페이지: https://sigmobile.org/mobicom/2020/ References [1] Juheon Yi, Sunghyun Choi, and Youngki Lee, “EagleEye: Wearable Camera-based Person Identification in Crowded Urban Spaces,” ACM International Conference on Mobile Computing and Networking (MobiCom), 2020. [2] Juheon Yi and Youngki Lee, “Heimdall: Mobile GPU Coordination Platform for Augmented Reality Applications,” ACM International Conference on Mobile Computing and Networking (MobiCom), 2020. [3] Kyungjin Lee, Juheon Yi, Youngki Lee, Sunghyun Choi, and Young Min Kim, “GROOT: A Real-time Streaming System for High-Fidelity Volumetric Videos,” ACM International Conference on Mobile Computing and Networking (MobiCom), 2020....
포스트 대표 이미지

제 1회 율촌 AI 스타에 컴퓨터공학부 대학원생 3명 선정

서울대학교 AI 핵심기술 분야 최고 인재를 가리는 ‘율촌 AI 스타’에 컴퓨터공학부 대학원생 3명 선정 AI 핵심기술 분야에서 최고의 인재를 가려 AI Star 상금 800만원 수여 총 34명 지원, 5명 중 3명이 컴퓨터공학부 학생 AI 핵심기술 분야의 최고 인재를 선발하는 ‘율촌 AI 스타’ 공개 선발에서 컴퓨터공학부의 유재민, 정연우, 정은지 학생이 제1회 AI 스타로 선정되었다. ‘율촌 AI 스타’는 농심그룹 율촌재단이 AI 인재를 육성해 국가발전에 이바지한다는 목표로 올해부터 출연하는 ‘율촌 AI 장학금’의 일환으로, AI핵심기술분야에서 가장 우수한 연구를 보인 대학원생들을 매년 5명씩 선발해 800만원의 상금을 지급하는 장학금이다. 서울대 AI연구원을 통해 대상자를 공개 모집한 결과 ICML, NeurIPS 등 AI 분야 최고의 학회에 재학 중에만 여러 편의 논문을 발표한 학생들이 34명 지원하였다. 심사를 맡은 교수들은 “우리 학교에 이렇게 우수한 Core AI 학생들이 많다는 것을 새삼스럽게 실감했다” 며, “연차에 따른 실적과 연구 발전 속도, 향후 연구 계획을 모두 계산하여 선발했다” 고 설명했다. https://cse.snu.ac.kr/sites/default/files/node--notice/20200909_%EC%9C%A8%EC%B4%8C_size770.png 유재민 학생(석박통합과정 9학기, 지도교수 강유)은 데이터 마이닝 분야 중 그래프 데이터에 머신 러닝 기법을 적용하는 연구로 ICDM, IJCAI, NeurIPS, WSDM 등에 1저자로 논문을 발표하였다. 그는 최근에 데이터가 없는 상태에서의 제로샷 학습에 대해 연구하고 있다고 설명하고, “빠른 속도로 발전하고 있는 머신 러닝 기술을 다양한 형태의 실세계 데이터에 적용하고, 제약 상황에서 모델의 효율성을 키우는 한편, 해석 가능한 결과를 도출함으로써 기술의 수직적 발전보다는 적용 분야와 응용 능력을 키우는 수평적 방향의 발전을 목표로 연구하고 있다”고 밝혔다. 지도교수인 강유 교수는 유재민 학생은 “전 세계 우수대학 학생과 비교해도 비교우위가 있는 학생”이라며 설명했다. 정연우 학생(석박통합과정 6학기, 지도교수 송현오)은 데이터의 효율적인 검색을 위한 이진 코드 생성 알고리즘과 비지도학습에서 데이터의 설명 가능한 이산 정보와 연속 정보를 분리 시키는 알고리즘으로 2018년 ICML, 2019년 ICML, CVPR에 논문을 기재하였다. 그는 최근에 커다란 네트워크에서 자원이 부족한 상황에서 사용할 수 있도록 작고 빠른 네트워크를 추출하는 연구를 하고 있으며, "현재의 사람의 정보를 저장해 미래에서 과거의 자신과 소통할 수 있게 만드는 연구를 하고 싶다" 라고 포부를 밝혔다. 송현오 교수는 연구를 수행하는 정연우 학생의 주도적인 태도와 창의적인 연구자세를 높이 샀다. 정은지 학생(박사 8학기, 지도교수 전병곤)은 딥러닝 시스템의 성능과 사용성을 높이는 연구로 NSDI, EuroSys 등 시스템 분야 최우수 학회에 발표하였다. 컴퓨팅 자원을 효율적으로 관리하고 사용하는 인공지능의 필수적인 시스템을 개발하는 그녀의 연구는 국제적인 주목을 받아 Google Brain, UC 버클리 등에서 먼저 협업을 제안해 프로젝트를 함께 수행하였다. 그녀는 “인공지능 연구자가 작성한 모델 전체를 분석하고, 주어진 CPU와 GPU에서 모델을 어떻게 더 효율적으로 수행할 것인지 컴파일러, 런타임 시스템 측면에서 연구를 진행할 계획”이라고 밝혔다. 율촌재단에서는 9월 중에 온라인 시상식을 실시하고 율촌 AI 스타에게 각 800만원의 상금을 수여할 예정이다. 율촌 AI 스타는 매년 8월 공고를 통해 5명씩 선발할 예정이다....
포스트 대표 이미지

2020년 8월 우수학위논문상 수상자 안내

서울대학교 컴퓨터공학부에서는 매 학기 졸업생을 대상으로 우수학위논문상을 수여합니다. 석박사 과정 졸업논문의 경우 논문 심사 위원들이, 학부 졸업 논문의 경우 지도교수가 뛰어난 논문을 선별하여 우수학위논문상 후보로 추천하고, 논문상 심사위원회에서 엄격한 심사를 거쳐 수상자를 선정하고 있습니다. 2020년 가을학기에는 박사 논문상 수상자 1명, 석사 논문상 수상자 1명, 학사 논문상 수상자 1명을 최종 선발하였습니다. o 박사 논문상 수상자: 김명석 (지도교수: 김지홍) 제목: Cross-layer Optimization Techniques for Secure Real-time 3D NAND Flash-Based Storage Systems 김명석 학생은 플래시메모리 저장 장치의 수명과 성능을 개선하기 위한 다양한 최적화 기법을 연구하였다. 이를 바탕으로 최신 컴퓨팅 환경에서 요구되는 실시간성과 보안성을 고려한 SSD 최적화 기법을 개발 하였다. 관련 연구 결과는 컴퓨터시스템분야의 최우수 학술대회인 MICRO와 ASPLOS를 포함하여 다수의 학술 대회 및 저널에 발표되었다. o 석사 논문상 수상자: 김형석 (지도교수: 송현오) 제목: Exploration in Reinforcement Learning with Mutual Information-based Embeddings 김형석 학생은 석사 학위 과정 중 심층 강화학습(Deep Reinforcement Learning)의 탐색 대한 연구를 수행했습니다. 에이전트의 상태와 행동 사이의 상호정보량을 최대화하여 보상이 희소한 환경에서 탐색을 원활히 수행할 수 있는 알고리즘을 연구하였습니다. 이를 바탕으로 인공지능 분야 최우수 학술대회인 ICML에 논문을 발표하였습니다. o 학사 논문상 수상자: 원재연 (지도교수: 이재욱) 제목: IIU : Specialized Architecture for Inverted Index Search 원재연 학생은 웹서치 엔진에서 주로 사용되는 역색인 구조를 이용한 검색을 획기적으로 가속시키는 아키텍쳐를 제안하였습니다. 하드웨어 친화적인 역색인구조 압축/검색하는 알고리즘을 고안하였고 이 결과를 컴퓨터 시스템 분야 최우수 학회인 ASPLOS 논문에 공저자로 참여하였습니다....
포스트 대표 이미지

송현오 교수 연구진, 최고 성능의 mixup 알고리즘 고안

서울대학교 송현오 교수 연구진, 인공신경망의 활용 가능성을 크게 높이는 새로운 알고리즘으로 세계 선도 송현오 교수 연구진(김장현 석박통합과정, 추원호 학사과정)은 데이터의 돌출성(saliency) 정보를 활용하여 기존 데이터 증대 기법인 mixup의 성능을 크게 향상하는 알고리즘을 개발하였다고 밝혔다. 해당 기법은 인공신경망의 일반화 성능과 데이터 왜곡 또는 적대적 공격에 대한 강건성을 향상시켜 인공신경망의 실제 응용 분야에서의 활용 가능성을 크게 높여줄 것으로 기대된다. 기존의 mixup 기법은 이미지의 대상 물체, 음성 데이터의 의미있는 음절 등 주어진 과제에 대한 답을 도출하는데 필요한 핵심적인 정보를 반영하지 않아 잘못된 데이터와 레이블을 만들어내는 경우가 존재한다. 잘못된 데이터를 생성하여 인공신경망 학습에 활용할 경우 인공신경망의 일반화 성능이 감소하게 된다. 이러한 문제를 해결하기 위해 송현오 교수 연구진은 데이터 돌출성과 국소적 연속성(smoothness)을 고려하였고 돌출성 정보를 극대화하기 위해 수송(transport) 과정을 모델링한 새로운 mixup 목적함수를 제안하였다 [식 1]. 연구팀은 해당 목적함수를 최적화하기 위해 GPU 최적화된 2단계 교차 알고리즘을 개발하였다. 본 논문에서 제안한 Puzzle Mix는 이미지 분류 벤치마크 데이터셋인 CIFAR, Tiny-ImageNet, ImageNet에서 기존 mixup 방법들보다 뛰어난 일반화 성능을 보였으며, 적대적 공격과 데이터 왜곡에 대해서도 향상된 강건성을 보였다 [그림 1]. 송현오 교수 연구진은 해당 기술을 다룬 논문을 머신러닝 최고 학회인 ICML 2020에 게재하였다고 밝혔다. https://cse.snu.ac.kr/sites/default/files/node--notice/20200729_%EC%86%A1%ED%98%84%EC%98%A41.png https://cse.snu.ac.kr/sites/default/files/node--notice/20200729_%EC%86%A1%ED%98%84%EC%98%A42.png 논문: Jang-Hyun Kim, Wonho Choo, Hyun Oh Song, Puzzle Mix: Exploiting Saliency and Local Statistics for Optimal Mixup, ICML 2020 링크: https://proceedings.icml.cc/static/paper_files/icml/2020/6618-Paper.pdf 코드: https://github.com/snu-mllab/PuzzleMix 발표 영상: https://icml.cc/virtual/2020/poster/6827 [문의] 송현오 교수 / 서울대학교 컴퓨터공학부 / hyunoh@snu.ac.kr 김장현 석박통합과정 / 서울대학교 컴퓨터공학부 / blue378@snu.ac.kr 추원호 학사과정 / 서울대학교 통계학부 / cwh104504@snu.ac.kr...
포스트 대표 이미지

[문병로의 알고리즘 여행] 불가능하다는 사실이 유용할 때도 있다

출처: 중앙일보 2020년 7월 3일자 [문병로의 알고리즘 여행] 대부분의 연구는 무얼 어떻게 잘해볼 것인가에 관한 것이다. 이런 가운데 몇몇 천재들은 자신들 분야의 근본적인 한계를 규명한다. 쿠르트 괴델은 1931년 어떠한 정상적인 논리 체계 내에서도 근본적으로 풀 수 없는 문제가 존재한다는 것을 증명했다. 20세기 수학의 기념비적 업적이 된 불완전성 정리다. 정신질환을 앓던 괴델은 자신이 오래 못 살 것으로 생각하고 프린스턴 고등연구소의 선배 교수인 세기의 천재 폰 노이만에게 자신의 유고 정리를 부탁했다. 그러기로 약속한 노이만은 먼저 죽고 괴델은 노이만보다 21년이나 더 살다가 죽는다. 괴델의 논제는 문제를 풀 수 있느냐 없느냐다. 즉 계산의 가능성에 관한 것이다. 알고리즘 분야에서도 가능성에 관한 논의를 포함하지만 대개 풀 수 있는 문제들을 얼마나 빠른 시간에 풀 수 있느냐에 관심이 더 많다. 풀 수 있지만 너무 오래 걸리면 실용적 의미가 없다. 수행 ‘시간’은 알고리즘 연구의 중심축 중의 하나다. 1971년 스티븐 쿡과 레너드 레빈은 GSAT이란 문제를 빨리 풀 수 있으면 어마어마하게 많은 알고리즘 문제를 빨리 풀 수 있다는 것을 증명했다. 이어서 리처드 캅은 21개의 문제를 제시하며 이들 중 어느 하나라도 빨리 풀 수 있으면 GSAT 문제가 빨리 풀린다는 사실을 증명했다. 이러면 논리적 체인에 의해 앞의 ‘어마어마하게 많은’ 문제가 빨리 풀린다. 이런 식으로 한 문제를 빨리 풀 수 있으면 다른 문제가 빨리 풀리는 연결 관계를 가진 문제 군이 급속히 커졌는데, 이로부터 ‘NP-완비’라는 거대한 연구 분야가 만들어졌다. 쿡은 자신의 연구 결과가 그저 흥미로운 것 정도로 생각했고 후에 거대한 연구 분야를 만들 것이라고 전혀 짐작하지 못했다고 한다. NP-완비는 현실적인 시간 내에 잘 안 풀리는 문제들에 대한 이야기다. 고객 방문 스케줄링 문제나 반도체 디자인에서 게이트들을 배치하고 연결하는 문제 등이 가까운 예다. 실로 다양한 문제들이 NP-완비 문제 군에 속한다. 알려진 것만 적어도 수만 개는 될 것이고 이론적으로 무한히 만들 수 있다. 이 그룹의 문제들은 현재까지의 기술로는 빨리(현실적인 시간 내에) 푸는 방법이 알려져 있지 않다. 이들 중 단 하나만 현실적인 시간에 해결되면 순식간에 이 군의 모든 문제들이 현실적인 시간에 해결되어 버린다. 현실적인 시간을 의미하는 전문적 정의가 있지만 여기서는 생략한다. 장난감 사이즈를 넘어서는 문제에 대해 어떤 컴퓨터든 돌려서 죽기 전에 결과를 볼 수 있다면 현실적인 시간에 속한다는 정도로만 받아들이자. 알고리즘 과목에서 배우는 대부분의 주제가 어떻게 잘할 것인가에 관한 이야기인데 반해 NP-완비는 뭐가 잘 안되는가에 관한 이야기다. 클레이 수학연구소에서 21세기에 접어들면서 세기의 7대 난제를 정하고 각각에 대해 100만 달러씩 상금을 걸었다. 그중 하나가 “P=NP인가?”라는 질문이다. NP-완비 문제 중 하나만 현실적인 시간에 풀면 이 질문에 대한 답을 얻을 수 있어 상금을 받는다. 아마도 그런 일은 없을 것이고 현실적인 시간에 풀 수 없다는 것을 증명하는 것으로 결론이 날 것이다. 7대 난제 중 하나인 푸앵카레 추측은 2002년 러시아 수학자 그리고리 페렐만이 증명했다. 페렐만은 100만 달러를 거부하고 허드렛일을 하는 어머니와 궁핍한 생활을 하고 있다. 어떤 문제가 잘 안 풀리면 자신의 지적 역량이 부족해서 그런지, 문제 자체가 어려워서 그런지 모르는 불안한 상태가 된다. 그 문제가 NP-완비에 속한다는 것이 판명되면 이런 걱정을 접어둘 수 있다. 지난 수십 년간 많은 천재들이 시도했지만 단 한 명도 해내지 못한 일이기 때문에 거의 불가능할 것이라고 잠정 결론지을 수 있다. 그러면 주어진 시간 내에 최적 품질은 보장할 수 없지만 꽤 괜찮은 답을 찾는 것을 목표로 하면 된다. 필자의 연구실에서 박사학위를 취득한 최성순 박사는 영어 대화도 잘 안 되는 상태로 실리콘 밸리의 반도체 자동 디자인 툴을 만드는 회사에 취업했다. 처음엔 좀 고생하더니 몇 년 후 게이트의 배치와 연결 품질에 관한 NP-완비 문제의 답을 획기적으로 개선하여 회사를 도약시켰다. 이 그룹의 문제들은 이미 어떤 좋은 알고리즘이 알려졌어도 최적을 보장하지는 못하므로 항상 개선될 여지가 남아 있는 장점이 있다. 서울대학교 컴퓨터공학부 문병로 교수...
포스트 대표 이미지