마르코프 체인: 문장 생성: 과거는 현재, 현재는 미래에 영향을 준다

익명 사용자의 이미지

요새 시간 날때마다 마르코프 체인 공부를 시도하고 있습니다.(공부는 안 하고 공부 시도만;;)

한국 위키피디아보면...
마르코프 연쇄는 시간에 따른 시스템 상태의 변화를 나타낸다. 매 시간마다 시스템은 상태를 바꾸거나 같은 상태를 유지한다. 상태의 변화를 전이라 한다. 마르코프 성질은 과거와 현재 상태가 주어졌을 때의 미래 상태의 조건부 확률 분포가 과거 상태와는 독립적으로 현재 상태에 의해서만 결정된다는 걸 뜻한다.
라고 나와 있습니다.

마르코프 체인에 개념에 대한 쉬운 설명은...
http://turtleforward.blogspot.com/2008/03/blog-post.html
에 있습니다.

루비 퀴즈라는 사이트가 있는데 이곳에 마르코프 체인을 이용한 문장 생성의 예가 나와 있습니다.
http://www.rubyquiz.com/quiz74.html
소스에

File.read("Agatha Christie - The Mysterious Affair at Styles.txt")

라는 부분을 국문이 들어있는 파일(저작권 소멸 문학작품들)로 교체하고
word = "Murder"
라는 부분을
word = "저는"

으로 바꿔서 소스를 실행해봤습니다.

아래는 결과값입니다. 실행할 때마다 값이 다릅니다.
-------------------------------

저는 무슨 일을 도와 주는 것 같음은 내 눈에는 속일 수 있는 걸 그만두었을지 모른다. 그 종소리는 나의 일터로 가려 나 사람이 있다’는 것 같았다. 그런데 처음에 얼마를 가지고 방으로 들여보내고 하였다. 저녁때에 중대 사건이나 난 벼 한 분을 하얗 게 뭐요.


저는 새로 사온 것 같아서 더 좀 착하게 먹어. 이건 무슨 바쁜 사람이라 매양 윤이 곯아 보고, 능갈친 백씨는 즉시 답장을 받았다. 그럴수록 동혁은, “오는 사람을 못 잡어서 큰일났다. 글쎄 말이나 듣지 아니하였느냐? 화랑 모례 서방님과 ……』 『시님, 소승의 소원이 이루어질 수가 없을까요?” 하고 야만을 면치 못하였던 것이다.


저는 고향 생각에 잠겼다가 비장한 결심을 허구, 장릿 벼를 놔서, 이 그 소리 뿐 아니라, 타동에 와서두 양반 을 허실 필요가 없어. 마음대로 물을 긷습니다. 나는 한 끝에 부인이 그 학교에 남아 있어서 수장은 물론 한 자 아내는 경희의 손을 잡아 오는 토요일에는 교우회의 책임 무거운 짐이나 차려요.』 하고, 병정같이 벌떡 일어서서 안방 에서 썩고지고.

-------------------------------
요새 (광고 말고) 지능형 댓글들을 보면 마르코프 체인을 이용하여 S, O, V, C 등의 문장 성분, 품사를 적용하여 정교하게 만든 것이 아닌가... 그런 생각이 들곤 합니다. 인공신경망까지 가미되면 더욱 정교해질지도 모르겠군요.
CPU가 더욱 발전하여 코어가 100개 이상 박히고 메모리 속도 또한 더욱 빨라지면...인간처럼 생각하는 소프트웨어가 나올지도 모르겠습니다.

PS. 요새 떡밥들이 난무하고 있는데, 최고의 떡밥이 되기를 기대해봅니다.

익명 사용자의 이미지

저는 이라는 단어는 소설에서 "대화"에 주로 나오니 시점이 섞여서 그럴싸한 문장이 안 나오는 듯.
소설을 기반으로 해서 그런지...
word = "저는" 이라 하지 말고
word = "그는" 이라고 해놓으면 더욱 그럴싸한 문장이 나옵니다.
보통 소설이 3인칭 시점이 많아서 그런 듯.

아래는 "그는"으로 바꾼 예
-------------------------------
그는 벌떡 일어났습니다. 며칠 밤을 넘기지 못하리라는 데는 위 에 모으고 모든 일에 전혀 마음은 진하고 단망하는 마음이 생긴다. 어느 때 마음 괴로운 일을 할 뿐……. “내려들 가!” 하고 한사코 들어가지를 않았다.

그는 우뚝 선다. 그의 발길을 옮겼다. 영신의 얼굴은 분을 횟박같이 뒤집어쓴 기생들의 뺨을 대고 섰던 평목이 앞 다박솔 밑에 닿은 듯한데, 물끓듯 한다. 저의 고향이 몇이나 손을 옆구리에 뽕뽕 좀먹은 걸레)를 선뜻 반가운 맘이 바짝 비틀어 열고 들어서는데, 별안간 앙카슴 한복판에 화살이 콱 부딪친다. “엄마 엄마.”

익명 사용자의 이미지

제가 마르코브체인에 대해 아는게 적어서 궁금해서 여쭤보는건데
저걸로 뭘 할려는 건가요?
제가 하는 일에서는 베이지안 통계의 추정을 위해 사용하는데,
저기서는 뭘 위해서 하는 건지 알 수가 없어서요.

즉 해결하고 싶은 문제가 있으면
해결하는 방법이 이런거 저런거가 있고 그 중에 한 방법(어쩌면 유일한)방법이 MC이고
MC를 구현하기 위해 어떤 프로그램을 쓴다 또는 만든다라고 할텐데

저기서는 뭘 해결하고 싶은지를 몰라서 (말 그대로 제가 이해를 못해서)
저 방법이 왜 좋은지를 잘 모르겠습니다.

jick의 이미지

마르코프 체인을 이용해서 실제로 문장을 "생성"하는 건 제가 아는 한 큰 쓸모가 없고...

실제 용도는 그렇게 만들어진 마르코프 체인을 이미 존재하는 문장에 대고 돌려보는 경우가 많습니다. 즉, "한국어 문장을 랜덤으로 생성하는 마르코프 체인이 있다면, 이 문장을 만들어낼 확률은 얼마일까?" 이런 계산을 하는 거죠.

그래서 예를 들어 이 문장이 자연스러운 한국어 문장인가 아니면 아무렇게나 타자를 친 랜덤한 문자열인가를 구분하는 데 써먹을 수 있습니다.

좀 더 발전된 예로는, 그렇게 마르코프 체인을 돌리면서 어느 상태를 지나가는지 보면 "아 이 문장에 대해서는 동사->명사->명사->...의 상태변화가 확률이 가장 높으니 세번째 단어는 동사가 아니라 명사겠군!" 이런 분석을 할 수 있죠.

(말하자면... "아버지가방에들어가신다"의 키워드가 가방인가 방인가 알아내는 데 쓰일 수 있습니다.)

익명 사용자의 이미지

"문장 생성하는 것"이 쓸모가 있긴 있는데...
마케팅, 경영학 나온 사람들이 보면... 뭔가 금광을 발견할지도 모르겠지만, 현재로선 돈이 안 될 뿐. 마땅한 수익 모델이 없음.

익명 사용자의 이미지

심심해서 떡밥으로 턱하니 던져놓은 거구요...
형태소 분석에 응용 가능하고...
nandaro.tistory.com/entry/Hidden-Markov-Model

(만약 있다면 한국어) 워드넷( http://wordnet.princeton.edu/ )하고 연관하여 찝쩍거리면...
뭔가 재미있는 것이 나올 것 같네요.
신경망 결합하여 피드백 보내어 교정하면 좀더 재미있을 것 같아요.
컴퓨터가 힘들다고 버럭하겠지만.

익명 사용자의 이미지

이거 꽤 응용범위가 많습니다.

예를 들어, Captcha에서 랜덤으로 생성되는 문자열은 보통 아무 의미 없어서 키보드로 입력하기 상당히 불편한 반면,
마르코프 체인 알고리즘을 써서 문자열을 생성시키면 제법 그럴싸한 단어가 생성되어서 음성으로도 표현이 쉽게 되죠.
(제가 봤던 captcha 소스가 이런 식이었습니다. php로 만든 공개소프트웨어였는데 이름이 가물가물)

알고리즘이 널리 알려지고 단순한 편이기때문에, 패턴매칭 알고리즘과 함께 응용해서 검색엔진을 만든다면 꽤 재밌지 않을까 생각만 하고 있네요.

익명 사용자의 이미지

마코프 연쇄를 이용한 대화형 시스템의 시험 사례 생성 - DBPIA
http://www.dbpia.co.kr/view/ar_view.asp?arid=623261&funName=arScrap

Markov Model of Natural Language
http://www.cs.princeton.edu/courses/archive/spr05/cos126/assignments/markov.html

Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations
homepages.inf.ed.ac.uk/kousha/final_rmc_jacm_version.pdf

마르코프 체인과 계층적 클러스터링 기법을 이용한 작곡 기법
visualcomputing.yonsei.ac.kr/papers/domestic/HCI2008_Kwon.pdf

CA-Markov 기법을 이용한 기후변화에 따른 소양강댐 유역의 수문분석
http://www.lafent.com/lea/lea.php?id=10714

Markov Chain을 이용한 공동주택 재실자 예측모델
http://www.auric.or.kr/user/rdoc/doc_rdoc.asp?returnVal=RD_R&page=1&dn=224443

익명 사용자의 이미지

위에 주제를 잘 모르겠다고 적은 사람인데요.

뭔가 잔뜩 올려 주셨는데 왜 올렸는지 모르겠네요.

(계속 모르겠다 시리즈 ?? ^^; 하여튼 )

혹시 MC의 유용성에 대해서 올려주신 건가요?

이미 MC는 많은 분야에서 잘 써먹고 있는 유용한 방법이고요,
제 분야에서도 MCMC니 오픈벅이니 해가면서 많이 쓰고 있어요.

하지만 MC는 단순히 툴일 뿐입니다.

즉 어떤 문제를 풀기 위해 사용하느냐에 따라
MC가 적용될 상황인지, 적용된다면 어떤 부분에, 어떤 알고리즘으로 적용하느냐가 중요하다는 거지요.

주제를 보면
문장을 생성한다고 되어 있는데
MC를 돌려서 우리가 얻고자 하는 문장이 뭐냐는 거죠.
"즉 이렇게 나왔으니 문제가 해결됐어", 또는 "이렇게 나왔으니 다른 방법보다 못하군"
이렇게 풀고자 하는 문제가 궁금한 겁니다.

예를 들어 초기값과 관련이 있는 문장을 얻고자 한다면 MC법이 적절할까요?

아니, 초기값과 관련이 있는 문장이 나오면 잘 구현한 건가요? 아니면 잘못 구현한 건가요?


익명 사용자의 이미지

굳이 정한다면 주제는 그냥 마르코프 체인을 이용한 문장 생성에 대한 토의입니다.
마르코프 체인을 검색하다보면 마로코프 체인을 이용하여 문장을 분석하거나 생성하는 것들이 많이 걸립니다.
한국어로는 이러한 시도들이 많지 않은 것 같아서 떡밥으로 올린 것입니다.

그리고 질문이... 좀..., 계속 모르겠습니다. 죄송합니다. -_-;;

익명 사용자의 이미지

초기값과 관련있는 문장이 뭘 의미하는지는 모르겠습니다.
위의 문장 생성의 예는 요새 흔히 볼 수 있는 단순한 곳에 적용할 수 있습니다.
휴대전화로 문자 입력하다보면 자동으로 몇가지 단어들이 나오는데... 이러한 곳에 응용될 수 있습니다.
자, 생각해봅시다...

자신이 문자메시지를 보냅니다. 문자메시지 원문들으로부터 마르코프 체인을 만들어집니다.
다음 번에 문자메시지를 작성할 때 예상 단어, 문장들이 자동으로 튀어나옵니다.
입력하면서 단어,문장을 선택하는 방법으로 수고를 줄일 수 있습니다.
자신이 입력한 문자메시지만으로 마르코프 체인을 구성하였기 때문에 활용성이 매우 높을 겁니다.