행렬 곱 알고리즘의 복잡도

가급적 한쪽 분야로 치우치지 않고 싶은데, 자꾸 복잡도 이론과 관련해서 포스팅하게 되네 이거-_-

간만에 Luca Trevisan 선생의 블로그 in theory[1]를 보니 뭔가 수상한(?) 논문[2]을 소개하고 있다.

matrix multiplication의 알고리즘 속도가 \Theta(n^2 )라고 주장하는 내용인 듯 한데, Ran Raz의 증명[3]에 의하면 matrix multiplication의 속도는 \Theta(n^2 \log n)이하로 내려갈 수 없다고 한다. 헐 이게 어떻게 된 일이야?

어쨌든 Luca 선생은 Scott Aaronson 선생의 “수학적 사기꾼을 구별하는 열가지 증거”[4]에서 4번에 걸린다는 이야기를 한다. 일전에 graph isomorphism 사건[5]도 있었지만, 저자가 논문을 철회했다면 뭐 좀 실수할 수도 있는 거지-_- 사기꾼 이야기하는 건 좀 아닌 것 같습니다. 허허허

 


[1] Matrix Multiplication Not Yet Doable In Quadratic Time in in theory
[2] Yijie Han, “A \theta(n^2 ) Time Matrix Multiplication Algorithm”, arXiv:1612.04208 [cs.DS]
[3] Ran Raz, (2002) “On the complexity of matrix product”, In Proceedings of the thirty-fourth annual ACM symposium on Theory of computing. ACM Press, doi:10.1137/S0097539702402147
[4] 내 백과사전 수학적 사기꾼을 구별하는 열가지 증거 2011년 12월 16일
[5] 내 백과사전 graph isomorphism 판정 알고리즘의 철회 2017년 1월 6일

이코노미스트지의 기계 번역/음성 인식 기사

이코노미스트지에서 1년에 네 번 발행하는 Technology Quarterly에는 다양한 기술 분야의 현황을 두루 소개하는 글로 채워지는데, 이번 주는 완전 작정하고 모든 기사가 기계 번역과 음성 인식 분야에 몰빵[1]을 하고 있다-_- 얼마전에 아마존 에코가 대박 많이 팔렸다[2]는 기사를 봤는데, 이쪽 분야가 확실히 요즘 화제가 되긴 되는 모양이다. ㅋㅋ

기계번역/음성인식 분야에 관한 역사와 최신 현황을 두루 아우르고 있는 듯 한데, 너무 길어서-_- 본인은 앞쪽 절반 정도만 읽었다. 흑 그놈의 영어 울렁증 ㅋ

초반에 ALPAC에 관한 이야기가 나오는데, 본인은 이런 역사가 있는 줄 처음 알았다. ㅎㅎ 당시에 기계번역에 대한 장밋빛 전망이 우세했던 모양인데, 1964년에 미 정부에서 7명의 학자 자문단 ALPAC을 구성하여 기계번역의 미래에 관해 물어보니, 기계번역이 완성되려면 택도 없다는 요지의 보고서-_-를 내는 바람에, 기계번역 분야의 지원금이 몽땅 끊기고 이 분야는 거진 20년간 암흑기에 들어갔다고 한다. ㅋㅋ 하긴 근래들어 엄청 좋아졌다는 구글 번역기도 대충 의미 파악용으로만 쓸 수 있지, 실제 활용가능한 문장으로는 좀 무리가 많은데, 60년대는 오죽하겠나 싶다.

기계 번역으로 과거에는 rule-based translation이 주력이었던 모양인데, 검색해보니 그런 관점에서의 재미있는 글[3]도 발견할 수 있었다. 과학동아의 1987년(!) 글인데, 과학동아 대단하다 ㅋㅋㅋ 1987년도 글을 웹으로 볼 수 있게 서비스 하다니 ㅋㅋ rule-based translation이 번역 알고리즘의 주력이던 시절의 관점을 간접적으로나마 엿볼 수 있어, 기술의 시대감이 느껴진다.

글[1] 중간에 Mark Liberman 교수가 언급되는데, 본 블로그에서도 종종 소개하는 유명한 언어학 블로그 Language Log[4]의 필진 중 한 명이다. 뭐 언어학 공부하는 사람은 이 블로그 이미 다 알고 있더만. ㅋ

일전에 확률 문법에 대한 이야기[5]에서도 잠시 나오고, 구글의 SyntaxNet 소개[6]에서도 나오지만, 언어의 모호성과 중의성 때문에, 또 문법의 예외적 측면이 너무 광범위해서 rule-based는 한계가 많다. statistics-based는 (비록 촘스키 선생은 대단히 회의적이라지만 ㅋ) 그런 측면에서 돌파구가 될 수 있다. 근래에는 이 두 가지에다가 neural network를 짬뽕한 Neural machine translation이 시도되는 모양.

중간에 phrase-based 번역과 neural-network 번역, 인간 번역을 비교한 그래프도 있다. 모든 번역에서 neural-network 번역은 phrase-based보다 우수하지만 인간이 직접 번역한 것 보다는 못한 점수를 얻는다. 꽤나 고무적인 결과지만, 본인이 보기에는 아직 갈 길이 멀다. 언제나 그렇듯이 60%에서 90%로 향상하기는 쉽지만, 90%에서 99%로 향상하는 것은 어렵기 때문이다.

일전에 음성인식 스마트거울 만드는 이야기[7]도 했지만, annyang[8]을 써 보니 음성인식 쪽은 진짜 성능이 비약적으로 발전한 것 같다. 뭐 좀 시끄러우면 인식 실패할 때가 많긴 하지만-_- 비교적 조용한데 설치하면 거의 백발백중이다. 음성합성도 마찬가진데, 일전에 소개[7]한 responsive voice[9]를 이용하면 정말 사람이 말하는 것 같이 사운드를 만든다. annyang이든 responsive voice든 구글의 데이터를 베이스로 쓰니 결국 구글의 기술인데, 구글이 무슨 요술을 부린건지 한국어를 이렇게 잘 맞춘다. 마술과 구별이 안 될거라는 클라크 선생의 말이 역시 맞구만-_-

 


[1] http://www.economist.com/technology-quarterly/2017-01-07
[2] geekwire Amazon Echo sales up 9X compared to last year, company says in holiday roundup December 27, 2016 at 8:28 am
[3] 과학동아 컴퓨터 자동번역 시스템 언어장벽이 무너진다 1987년 02월호
[4] http://languagelog.ldc.upenn.edu/nll/
[5] 내 백과사전 확률 문법의 간략한 소개 2016년 10월 7일
[6] 내 백과사전 구글의 자연어 처리 오픈소스 SyntaxNet 2016년 5월 14일
[7] 내 백과사전 음성인식 스마트 거울 만들기 2016년 11월 2일
[8] https://www.talater.com/annyang/
[9] http://responsivevoice.org/

국내 로봇 저널리즘 현황

본인이 알기로, 봇이 작성하여 정식 기사로 송출한 국내 최초의 기사는 파이낸셜 뉴스의 증시 보도[1]로 알고 있다. 파이낸셜 뉴스의 봇 IamFNBOT은 서울대 이준환 교수의 연구로 진행되는 것 같은데[2,3], 스포츠나 증시와 같이 알려진 수치를 보고 이것을 기반으로 문장을 만드는 어떤 방법론을 사용하는 것 같다. 숫자를 보고 경기가 어떤 맥락에서 긴장상태인지, 증시가 어떤 상황 때문에 급등락하는지 그 분위기를 추출하는 방법을 연구하는 것 같다. 뉴스1의 기사[3]가 조금 오래됐긴 하지만 설명을 잘 하고 있어 나름 볼만하다. 요새 나오는 파이낸셜 뉴스의 봇기사는 전부 제목에 ‘fnRASSI’라고 헤더가 붙어 나오는 것 같다.

매일경제에서는 M-Robo를 개발하고 있다[4]고 한다. 보니까 사내 벤쳐 형식으로 지원[5]하고 있는 듯. 봇으로 기사를 작성하면, 대장주/우량주에 비해 상대적으로 소외되어 기자의 손이 모두 미치지 않는 여러 소형주들의 기사 작성에 유리한 측면이 있다고[6] 한다. 그냥 매경에서 개발하는 거랑 사내 벤쳐는 뭐가 다른지는 뭐 본인도 잘 모르니 넘어갑시다-_- 아직 실제 서비스되고 있지는 않은 것 같다.

씽크풀과 전자신문(이티뉴스)에서 공동으로 개발한 로봇 ET도 있다. 전자신문 사이트에 봇이 작성한 기사만 따로 모아 볼 수 있도록 해 두었는데[7], 읽어보면 나름 괜찮다. 파이낸셜 뉴스의 첫 기사[1]는 데이터의 나열 뿐이지만, 이쪽은 데이터의 나열뿐만 아니라 나름 분석스러운 문장을 사용하고 있어 은근 사람스럽다-_- 여태까지 본 로봇 기사 중에서 제일 성능이 좋은 것 같다.

아예 로봇만 기사를 작성하는 언론사[8]도 생겼는데, 이름이 로봇저널이라고 한다. 2016년 3월 창간했다고 위키에 나와 있는데, 왠지 위키의 내용이 저널 창립자가 작성한게 아닐까 싶은 느낌적 느낌이 든다-_- 또, 소스코드가 GitHub에 공개[9]되어 있다고 한다. 홈페이지[8]의 기사를 대충 보니 아직까지는 단순히 데이터를 나열한 정도의 레벨인 것 같다. 로봇저널의 발행인이 미디어스에 자신의 견해를 피력하는 기사[10]가 있다.

당연한 이야기지만, 근시일안에 로봇 기자가 기자 전체를 완전히 대체하는 것은 불가능하다. 로봇 기자가 발로 뛰어 취재하는 일은 없기 때문이다. 다만 데이터를 디지털로 수집하여 기사를 송고하는 일을 하는 종류의 기자는 거의 사라질 것 같다. 웹서핑해서 글을 쓰는 정도라면 본인도 하고 있는 거 아닌가. ㅋㅋㅋ 기자가 스스로의 가치를 높이려면 로봇이 절대 할 수 없는 현장취재, 인터뷰, 사실확인 등의 품이 많이 들어가는 작업에 집중해야 할 것이다.

 


[1] 파이낸셜 뉴스 코스피 4.92포인트 하락, 1840.53포인트 거래 마감 2016.01.21 15:27
[2] 블로터 ‘파이낸셜뉴스’, 로봇 기자를 채용하다 2016.01.26
[3] 뉴스1 로봇이 야구기사를 쓴다…그런데 아주 잘 쓴다 2015-05-25 09:54
[4] 매일경제 [커버스토리] 증권기사 쓰는 로봇기자 `매경 M-Robo` 인터뷰 2016.04.21 09:12:14
[5] 매일경제 [커버스토리] 매경 M-Robo, 한국 미디어업계 첫 사내벤처 2016.04.21 09:12:08
[6] 한국기자협회 매경 사내벤처 ‘엠로보’ 출범 2016.03.30 09:28:11
[7] http://www.etnews.com/news/atnews.html
[8] http://www.rbjn.kr
[9] https://github.com/Robot-Journal/rbjn
[10] 미디어스 “로봇저널리즘의 등장” … 기자들의 역할은? 2016.08.02 07:41

성인 VR 엑스포 2017

ねとらぼ기사[1]를 보니 오사카에서 이번 달 19, 20일에 성인용 가상현실 엑스포[2]가 열린다고 한다. 이것들이 이제 아주 엑스포를 여는구나-_- 역시 성진국ㅋㅋㅋㅋ의 기술활용은 남다르다.

일전에 아키하바라에서 성인 VR 축제를 기획했으나, 사람들이 너무 많이 몰리는 바람에 취소-_-되었다는 기사[3]가 생각나는데, 이번에는 제대로 각을 잡고 할 것 같다.

설 연휴에 일본에 놀러갈 예정인데, 행사기간이 설 연휴와 겹치지 않아서 상당히 아쉽구만. ㅎㅎ 기사[1]에 우유 짜내는 장비 한 번 사용해 보고 싶은데… ㅋ 여유가 있는 사람은 재미로 한 번 참가해보는 것도 나쁘지 않을 듯.

일전에 중국에서는 VR기술을 독특하게 활용[4]한다는 이야기를 했는데, 이런걸 보면 어쨌건간에 VR 기술이 사장되지 않고 번창할 것은 확실할 듯 하다. ㅎㅎㅎ

 


2017.1.14
venturebeat Will Japanese VR sex simulation with dolls fly in the U.S.? JANUARY 11, 2017 7:15 AM
헐… 라스베가스에서도 성인 VR 엑스포가 열리는 듯-_-

 


[1] ねとらぼ アダルトVRエキスポ、大阪で開催 乳しぼり(される側)や実写セクシービデオ体験など突き抜けた出展続々 2017年01月06日 21時36分
[2] http://osaka.adult-vr.jp/
[3] UploadVR Japan’s Adult VR Festival Proves (Venue) Size Matters, Canceled Due to Overcrowding JULY 5TH, 2016
[4] 내 백과사전 중국의 가상현실(VR) 시장 상황 2016년 10월 17일

대구시-테슬라 협력

지나가다 우연히 영남일보 1면을 슬쩍 보게 되었는데, 눈이 똥그래질 기사가 1면에 있었다. 대구시-테슬라가 협력을 체결했다[1]는 내용이다.

헐… 다른 기사[2]를 찾아보니 작년 9월에 비공개로 대구에서 오토파일럿 등의 주행테스트도 한 모양이다. 전국구 신문들은 전부 기사가 짧고 내용이 별로 없는데, 대구 지방지들의 내용[1,2,3]이 오히려 자세해서 읽을만하다.

우리 동네에 먼저 테슬라가 들어올지도 모른다고 생각하니 쓸데없이 흥분되네 ㅋㅋㅋㅋ 물론 본인이 김칫국부터 마시는 것일 수도 있지만…-_- 일전에 전기차 사고싶다는 이야기[4]를 했는데, 본인은 평생 차를 살 일이 없을 것이라고 생각했지만, 어쩌면 첫 차가 테슬라가 될 수도 있겠다. ㅋ 뭐 물론 얼리어댑터는 어디든 있어서, 국내에 테슬라를 실사용하는 사람[5]이 이미 있긴 하지만….

얼마전에 자본금 늘렸다는 기사[6]를 봤을 때, 이 쉐이들 세금 안 내려고 머리쓰는 건가 싶어서 좀 마음에 안 들긴 했다. 뭐 이런 부분은 마이크로소프트[7,8,9]와 구글[10] 등등도 다 마음에 안 들지만..

 


[1] 영남일보 대구시-테슬라 손 잡았다 2017-01-07
[2] 대구일보 세계적 전기차기업 테슬라 대구서 주행테스트 “만족” 2016.09.05
[3] 매일신문 미래자동차 산업 육성 대구시-테슬라 손잡았다 2017-01-06 19:59:38
[4] 내 백과사전 전기차 사고 싶다 2013년 9월 2일
[5] 슬로우뉴스 전기자동차 테슬라, 최초 서울-부산 왕복 후기 2015-10-05
[6] 조선비즈 [단독] 테슬라 한국법인 자본금 늘린 까닭은…”1호 매장은 로드숍” 2016.07.12 06:01
[7] 비지니스포스트 국세청과 마이크로소프트, 6천억대 법인세 소송 벌이나 2016.09.22 16:14:45
[8] MBC 마이크로소프트 “특허사용료 법인세 6천억 원 돌려달라” 2016-08-30 06:42
[9] 경향비즈 글로벌IT기업 ‘코리아 유한회사’의 미스터리 2016.01.02 14:44:43
[10] 내 백과사전 에릭 슈미트, “조세회피가 자랑스럽다” 2012년 12월 16일

graph isomorphism 판정 알고리즘의 철회

일전에 graph isomorphism 판정을 quasipolynomial로 하는 알고리즘을 발견했다는 이야기[1]를 했는데, 그 내용에 오류가 있어서 논문[2]이 철회된 것 같다. 타오 선생도 언급[3]하고 있고, Quanta magazine 기사[4]로도 나왔다. 팀 블로그인 Windows on Theory[5]와 Gödel’s Lost Letter and P=NP[6]에서도 이 내용을 언급하고 있다.

그러나 quasipolynomial은 아니지만 여전히 sub-exponential이고 기존에 알려진 어떤 알고리즘보다 빠른 것이라고 한다. 음… 혹시나 알고리즘이 점점 개선되어 결국 P=NP가 되지 않을까 가슴 두근하던 나의 망상을 확 깨주시는군-_-

논문[2]의 중요한 오류 부분을 Harald Helfgott 선생이 지적한 모양인데, 이 사람 약한 골드바흐 추측을 끝장낸[7] 바로 그 페루 출신 수학자가 아닌가. 이쪽 분야로도 소양이 있는 줄은 몰랐네 ㅋ

Helfgott 선생의 블로그[8]를 보니 2014년 ICM 때문에 한국에 다녀간 모양인데, 한글의 창제 원리에 대해 꽤 흥미로워 하는 듯? 근데 ‘아침글’이라는 표현은 처음 듣는데, 내가 뭔가 잘못알고 있는 건지…-_- 국어 선생님에게 물어봐야겠다. ㅋ

여하간 Helfgott 선생은 한국의 로컬푸드와 주류는 가격이 싼데, 커피는 비싼 점이 미스테리라고 생각하는 것 같다. ㅎㅎㅎ

 


2017.1.15
Quanta magazineGraph Isomorphism Vanquished — Again January 14, 2017
Babai 선생이 증명을 다시 고쳐서 quasipolynomial이 된 듯 하다. ㅋ

 


[1] 내 백과사전 새로운 graph isomorphism 판정 알고리즘 2015년 11월 14일
[2] László Babai, “Graph Isomorphism in Quasipolynomial Time”, arXiv:1512.03547 [cs.DS]
[3] https://plus.google.com/+TerenceTao27/posts/2nSqird8NHt?sfc=true
[4] Quanta magazine Complexity Theory Problem Strikes Back January 5, 2017
[5] On exp(exp(sqrt(log n))) algorithms. in Windows on Theory
[6] Babai’s Result: Still a Breakthrough in Gödel’s Lost Letter and P=NP
[7] 내 백과사전 홀수 골드바흐 추측이 완전히 풀렸나? 2013년 5월 14일
[8] Hangul and stinky tofu in The value of the variable

어느 산수덕후 아버지의 연하장

일본은 연하장 문화가 꽤 발달해 있다고 하던데, ねとらぼ의 기사[1]에 어떤 사람이 자신의 아버지가 보낸 연하장을 소개[2]하고 있다. ㅋ
c1ifagzveaaqgg9
대충 발번역하면 다음과 같다. (확실하지는 않은데, 일본인들은 편지에서는 친한사이라도 경어를 쓰는 것 같다.)

새해 복 많이 받으세요.
2017(년)+(헤이세이)29 = 21+22+23+24+25+26+27+28+29+210

2017은 세 소수의 3승의 합입니다(73+73+113 = 2017). 세 소수의 3승의 합이 되는 수 중에 2017은 작은 쪽으로부터 세어 30번째로서, 참고로 29번째는 1799( = 53+73+113), 31번째는 2213( = 23+23+133)입니다. 따라서 19세기부터 22세기까지 400년간 세 소수의 3승의 합이 되는 해는 올해 뿐입니다.

와 아버지 대단하군-_- 근데 저 주장이 사실인지 별로 확인해보고 싶지는 않다-_- 술먹고 포스팅하면 만사 귀찮다-_-

참고로 454보다 큰 모든 자연수는 7개의 양수 세제곱수의 합으로 표현가능하다.[3] 음수를 포함한 세 개의 세제곱수로 나타내는 문제[4]도 일전에 소개한 바 있다.

은근히 아무짝에도 쓸데 없는 문제들인데-_-, 이게 만약 실용적으로 쓸모있는 문제가 된다면, smbc만화[5]처럼 패닉을 일으키는 사람도 있지 않을까? ㅋㅋㅋ

 


[1] ねとらぼ 「2017は3つの素数の3乗の和、400年間で今年だけ!」 父から送られてきた年賀状に数学クラスタが沸く 2017年01月05日 14時25分
[2] https://twitter.com/kwd24195/status/815748586663124992/photo/1
[3] 내 백과사전 454보다 큰 모든 자연수는 일곱개 이하의 세제곱수의 합으로 표현가능하다 2016년 1월 20일
[4] 내 백과사전 세 개의 세제곱수 2012년 6월 22일
[5] http://www.smbc-comics.com/?id=4130

Gigafactory의 미친(?) 투자계획

어제 이코노미스트지의 에스프레소를 보니 기가팩토리 투자자 초청 이벤트를 열었던 모양[1]이다.

제작년인가, 처음 기가팩토리 소식을 들었을 때는 엘론씨가 진짜로 미쳤다고 생각했다-_- 전세계 배터리 생산 총량보다도 더 많은 배터리를 네바다주에서 생산할 계획이라는데, 이건 도박의 범주를 넘어서는 거 아닌가. ㅋㅋㅋㅋ 이거 아귀 앞에서 밑장빼는 짓보다 더 간 큰 짓이다. ㅋ 뭐 여하간 2016년 7월에 공식 개소[2]하긴 했지만, 전체 공사 진척 비율이 1/3도 안 됐다니 앞으로 갈 날은 많다.

일전에 테슬라가 자동차를 꽤 팔았다[3]는 이야기를 했는데, 생산량을 2배로 늘려서 2016년에 이미 거의 10만대 달성을 했다고 한다. 근데 이보다도 속도를 더 내서 2018년까지 50만대를 생산할 계획이라고 한다. 더구나 파워 월 판매까지 나왔으니, 지금 돌이켜 생각하면 그의 통큰 계획이 아주 이해가 안 되는 건 아니다.

일전에 소개한 그의 전기[4]를 봐도 알 수 있듯이, 그의 전체적인 계획은 오직 영리만을 추구하는 투자가들의 관점[5]으로는 절대 파악할 수 없다. (허생전에서 “당신은 나를 장사치로 보는가?” 하는 대목이 생각나는구만-_-) 인류 전체와 문명이 어떤 방법으로 에너지를 만들고 번영해야 하는지, 또 지구라는 요람 밖으로 나와 어디로 걸어가야 하는지, 방향성을 제시하고 시도하는 인물의 관점으로 파악해야 할 것이다. 확실히 에디슨의 명언[6]이 딱 맞는 사람이라 할 수 있다.

여하간 인류 기술문명의 빅 픽쳐가 그의 계획에 달려있다고 생각하니 꽤나 흥분되지 않을 수 없다. 실패한 사업가가 될지, 인류 문명이 나아갈 방향을 제시할 사람이 될지 두고 볼 일이지만… ㅋ 뭐 테슬라의 적자가 어마어마 한 것도 사실이니…-_-

 


[1] 이코노미스트지 에스프레소 Megaoptimism at the Gigafactory: Tesla Jan 4th 2017
[2] 연합뉴스 테슬라, 리튬이온 배터리 생산 ‘기가 팩토리’ 공식 개소 2016/07/27 09:23
[3] 내 백과사전 캘리포니아 자동차 제조사별 판매량(2013 Q2) 2013년 8월 25일
[4] 내 백과사전 [서평] 일론 머스크, 미래의 설계자- 지구상에서 가장 먼저 미래에 도착한 남자, 일론 머스크가 제시하는 미래의 프레임 2015년 8월 1일
[5] 테슬라 전기자동차의 비전(1/2) in 증권투자서적토론방
[6] 내 백과사전 토머스 에디슨 탄생 164주년 2011년 2월 11일

Mad Science Fest

블로그 Secret Lab of a Mad Scientist를 운영하는 Mad Scientist님께서 과학 행사를 주최[1]하신다고 한다. 본인은 생물학에 대해 쥐똥만큼도 모르지만 왠지 가고 싶은데-_-, 지방에 살고 있을 뿐더러 먹고사니즘 관계상 주말에 빠져 나올 수가 없어서 안타깝다.

이런걸 열심히 듣는 서당개가 되어야 풍월을 읊을 텐데…-_- 못 가서 참 아쉽구만 쩝쩝

시간 되시는 분들은 참석해 보시기 바랍니다. ㅎㅎ

 


[1] 제 1회 Mad Science Fest in Secret Lab of a Mad Scientist