Markov가 생성 된 콘텐츠를 식별하기위한 알고리즘?

Question

Markov 체인은 (거의 표준) 생성 방법입니다. 임의의 횡설수설 훈련받지 않은 눈에 똑똑해 보입니다. 인간의 서면 텍스트에서 Markov가 생성 된 텍스트를 식별하는 방법은 무엇입니까?

당신이 가리키는 자원이 파이썬 친화적이라면 굉장 할 것입니다.

Answer 1

"Brute Force"접근 방식을 사용하여 생성 된 언어를 생성 된 Markov 모델보다 고차의 N-Gram에서 수집 된 데이터와 비교할 수 있습니다.

즉, 제 2 차 마르코프 모델로 언어가 생성 된 경우 최대 3 그램까지 올바른 주파수가 있지만 4 그램은 아마 그렇지 않을 것입니다.

Google의 공개에서 최대 5 그램 빈도를 얻을 수 있습니다. N- 그램 데이터 세트. 그래도 거대합니다 -24g 압축 - DVD에 게시하여 가져와야합니다. LDC.

편집 : 구현 세부 정보가 추가되었습니다

N- 그램은 이미 계산되었으므로 빠르게 검색하는 방식으로 카운트 (또는 주파수)를 저장하면됩니다. 적절하게 색인 된 데이터베이스 또는 루센 인덱스가 작동해야합니다.

텍스트 조각이 주어지면 텍스트를 스캔하고 데이터베이스에서 각 5 그램의 빈도를 찾아서 동일한 4 단어로 시작하는 다른 5 그램에 비해 순위가 위치한 위치를 확인하십시오.

실제로, 더 큰 장애물은 데이터 세트의 라이센스 용어 일 수 있습니다. 상용 앱에 사용하는 것은 금지 될 수 있습니다.

Answer 2

한 가지 간단한 접근 방식 중 하나는 많은 인간 그룹이 귀하를 위해 입력 텍스트를 읽고 텍스트가 의미가 있는지 확인하는 것입니다. 나는 단지 반 농담입니다. 이것은 까다로운 문제입니다.

Markov-chain 생성 된 텍스트는 단어 주파수와 단어 순서 사이의 간단한 관계 측면에서 실제 인간 텍스트의 동일한 속성을 많이 갖기 때문에 이것이 어려운 문제라고 생각합니다.

Markov 체인에 의해 생성 된 실제 텍스트와 텍스트의 차이점은 더 높은 수준의 문법 규칙과 의미 론적 의미에 있으며, 이는 프로그래밍 방식으로 인코딩하기가 어렵습니다. 또 다른 문제는 Markov 체인이 문법적이고 의미 적으로 올바른 진술을 제시 할 수있는 텍스트를 생성하는 데 충분하다는 것입니다.

예를 들어, 여기에 있습니다 Kantmachine의 격언:

오늘날 그는 인간의 뜻이 자유 롭다고 확신 할 것입니다. 내일은 불용성의 자연 사슬을 고려할 때, 자유를 단순한 환상으로보고 자연을 모두 알리겠다고 선언 할 것입니다.

이 문자열은 컴퓨터 프로그램에 의해 작성되었지만 인간이 결코 이것을 말하지 않을 것이라고 말하기는 어렵습니다.

컴퓨터와 인간 생성 된 텍스트에 대한보다 구체적인 세부 정보를 제공 할 수 없다면 더 명백한 차이를 드러내는 것이 컴퓨터 프로그래밍을 사용하여이를 해결하기가 어려울 것이라고 생각합니다.

Answer 3

Evan의 답변 일반화를 제안합니다. 자신의 Markov 모델을 만들고 나머지 샘플을 "테스트 데이터"로 예약하는 (매우 큰) 샘플의 큰 덩어리로 훈련하십시오. 이제 훈련 된 모델이 테스트 데이터에서 얼마나 잘 수행하는지, 예를 들어, "맞는 것이 너무 우수하다"(테스트 데이터가 실제로이 모델에 의해 생성되는 것을 제안 함)를 제안 할 수있는 카이 스퀘어 테스트를 통해 얼마나 잘 수행하는지 확인하십시오. 착용감이 매우 나쁘다 (모델 구조의 오류를 제안한다-잘못된 구조를 가진 과도한 훈련 된 모델은 그러한 경우에 악명 높은 나쁜 일을한다).

물론 모델의 구조와 같은 교정에 대한 많은 문제가 여전히 있습니다. 단어의 ntuples 등을 기반으로 한 간단한 모델 또는 문법 상태 등이있는 더 정교한 모델을 의심하고 있습니다. 다행스럽게도 알려진 자연적인 텍스트의 대형 회사와 다양한 구조의 모델로 자신을 생성함으로써 물건을 잘 교정 할 수 있습니다.

다른 접근법은 사용하는 것입니다 NLTK 주어진 문장을 구문 분석하려면-자연스러운 텍스트에서도 적은 수의 잘못된 부분이 예상됩니다 (인간은 불완전하고 구문 분석기도 마찬가지입니다. 단어 X가 동사로 사용될 수 있다는 것을 알 수 없습니다. 그리고 그것을 명사 등으로 만 분류하십시오) 그러나 대부분의 Markov 모델 (본질적으로 파서가 사용하는 동일한 문법 구조를 모델링하지 않는 한 여러 파서를 사용하여이를 시도하고 반대 할 수 있습니다!-). 난독증 인간보다 훨씬 더 많은 불행을 일으킬 것입니다. 다시, 자연 대 합성 텍스트에서 그것을 보정하면, 내가 의미하는 바를 볼 수 있습니다!-)

Answer 4

몇 개의 큰 Markov 생성 텍스트가 있다면, 각 샘플 사이의 단어 주파수를 비교하여 그렇게했는지 확인할 수 있습니다. Markov 체인은 일정한 단어 확률에 의존하기 때문에, 주어진 단어의 비율은 샘플에서 샘플까지 거의 동일해야합니다.

Answer 5

크라우드 소싱. 기계적 터크를 사용하고 많은 인간이 이에 투표 할 수 있도록하십시오. 이것을 뽑아내는 데 도움이되는 라이브러리도 있습니다. 예를 들어:

• 터키 - 기계적 투르크에 대한 반복적 인 작업

다음은 O'Reilly Radar의 블로그 게시물입니다. 기계식 터크를 사용하여 작업을 완료하기위한 팁입니다.

• 기계적 터크 모범 사례

Answer 6

일련의 기호에서 Markovian 전환 확률을 생성하는 프로그램을 작성한 다음 Markov 매트릭스의 엔트로피 속도를 계산합니다. (보다 http://en.wikipedia.org/wiki/entropy_rate#entropy_rates_for_markov_chains) 이것은 기본적으로 Markov 체인 만 사용하여 텍스트를 얼마나 쉽게 예측할 수 있는지에 대한 추정치입니다 (높은 엔트로피 수단 더 어렵다 예측하기). 따라서 Markov 매트릭스의 엔트로피가 낮을수록 텍스트 샘플이 Markov 행렬에 의해 제어 될 가능성이 높다고 생각합니다. 이 코드를 작성하는 방법에 대해 궁금한 점이 있으면 내 컴퓨터에서 정확히이 작업을 수행하는 Python의 프로그램이 있으므로 도와 드릴 수 있습니다.