문법 유도

시리즈의 일부
기계 학습 및 데이터 마이닝
문제 분류 클러스터링 회귀 이상 검출 데이터 클리닝 자동 ML 어소시에이션 규칙 강화 학습 구조화된 예측 기능 엔지니어링 기능 학습 온라인 학습 준지도 학습 비지도 학습 순위 매기기 학습 문법 유도
지도 학습 (분류 • 회귀) 의사결정 트리 앙상블 배깅 부스팅 랜덤 포레스트 k-NN 선형 회귀 네이비 베이즈 인공신경망 로지스틱 회귀 분석 퍼셉트론 관련 벡터 머신(RVM) 서포트 벡터 머신(SVM)
클러스터링 버치 치유하다 계층적 k자형 기대 최대화(EM) DBSCAN 광학 평균 이동
치수 축소 인자 분석 CCA ICA LDA NMF PCA PGD t-SNE
구조화된 예측 그래픽 모델 베이즈 네트 조건부 랜덤 필드 히든 마르코프
이상 검출 k-NN 국소 특이치 계수
인공신경망 자동 인코더 인지 컴퓨팅 딥 러닝 딥 드림 다층 퍼셉트론 RNN LSTM GRU ESN 저장고 계산 제한 볼츠만 기계 GAN somerset. 컨볼루션 뉴럴 네트워크 유넷 트랜스포머 비전. 스파이킹 뉴럴 네트워크 메모리 트랜지스터 전기화학 RAM(ECRAM)
강화 학습 Q-러닝 사사 시간차(TD) 멀티 에이전트 셀프 플레이
인간과의 학습 액티브 러닝 크라우드 소싱 휴먼 인 더 루프
모델 진단 학습 곡선
이론. 커널 머신 바이어스-분산 트레이드오프 컴퓨터 학습 이론 경험적 리스크 최소화 오컴 러닝 PAC 학습 통계학 학습 VC 이론
기계학습장 NeurolIPS ICML ML JMLR ArXiv:cs.LG
관련 기사 인공지능 용어집 기계 학습 연구를 위한 데이터 세트 목록 기계학습의 개요
v t

관찰 집합 중에서 공식적인 문법(re-write 규칙이나 생산량의 컬렉션을 보통 또는 일종의 유한 상태 기계나 automaton으로로)를 배우는 기계 학습에 문법 유도(이나 문법적인 추론)[1]는 과정 때문이 관찰된 o.의 특성을 설명하는 모델 건설bjects. 보다 일반적으로 문법적 추론은 인스턴스 공간이 문자열, 트리 및 그래프와 같은 이산 조합 객체로 구성된 기계 학습의 한 분야이다.

문법 수업

문법적 추론은 1980년대부터 이 문제에 대한 효율적인 알고리즘이 있었기 때문에 종종 다양한 유형의 유한 상태 기계를 학습하는 문제에 매우 집중되어 왔다.

세기 초부터, 이러한 접근법은 문맥이 없는 문법과 다중 문맥이 없는 문법과 병렬이 있는 문맥이 없는 문법과 같은 더 풍부한 형식주의의 추론 문제로 확장되었다.문법적 추론이 연구되어 온 다른 종류의 문법은 조합 범주형 문법,^[2] 확률적 문맥 자유 문법,^[3] 문맥 문법 및 패턴 언어이다.

학습 모델

학습의 가장 간단한 형태는 학습 알고리즘이 단지 해당 언어에서 도출된 일련의 예시를 받는 것입니다. 목적은 언어를 예시로부터 학습하는 것입니다(그리고 드물게 반례로부터 언어를 학습하는 것, 즉 언어에 속하지 않는 예).하지만 다른 학습 모델들이 연구되었다.자주 연구되는 대안 중 하나는 학습자가 ^[4]앵글루인에 의해 도입된 정확한 질의 학습 모델 또는 최소한의 적절한 교사 모델에서와 같이 구성원 자격 쿼리를 할 수 있는 경우이다.

방법론

문법적 추론에는 매우 다양한 방법이 있다.고전적인 자료 중 두 가지는 푸와 푸이다.Duda, Hart & Stork(2001)도 이 문제에 대해 간단한 섹션을 할애하고 많은 참고 문헌을 인용한다.여기서 제시하는 기본적인 시행착오 방법은 다음과 같습니다.특히 정규 언어의 하위 클래스를 추론하는 방법은 정규 언어의 유도를 참조하십시오.더 최근의 교과서는 정규 언어와 유한 상태 오토마타의 문법적 추론 이론을 다루는 de la Higuera (2010)^[1]이다.D'Ulizia, Ferri, Grifoni는^[5] 자연어에 대한 문법적 추론 방법을 탐구하는 조사를 제공합니다.

시행착오를 통한 문법적 추론

Duda, Hart & Stork(2001) 섹션 8.7에서 제안된 방법은 문법 규칙(제작물)을 연속적으로 추측하고 긍정 및 부정 관찰에 대해 테스트하는 것을 제안한다.규칙 집합은 각 긍정적인 예를 생성할 수 있도록 확장되지만 특정 규칙 집합에서 부정적인 예도 생성할 경우 해당 규칙 집합은 폐기해야 합니다.이 특별한 접근방식은 "hypothesis testing"으로 특징지어질 수 있으며 Mitchel의 버전 공간 알고리즘과 어느 정도 유사합니다.Duda, Hart & Stork(2001) 텍스트는 프로세스를 잘 설명하는 간단한 예를 제공하지만, 보다 실질적인 문제에 대한 이러한 안내 없는 시행착오 접근방식의 실현 가능성은 의심스럽다.

유전 알고리즘에 의한 문법적 추론

진화 알고리즘을 이용한 문법적 귀납은 어떤 진화 과정을 통해 대상 언어의 문법 표현을 발전시키는 과정이다.형식 문법은 진화 연산자의 영향을 받을 수 있는 생산 규칙의 트리 구조로 쉽게 표현될 수 있습니다.이런 종류의 알고리즘은 존 코자에 의해 ^{[citation needed]}개척된 유전 프로그래밍 패러다임에서 비롯되었다.단순한 형식 언어에 대한 다른 초기 연구는 유전 알고리즘의 이진 문자열 표현을 사용했지만, EBNF 언어로 결합된 문법의 본질적으로 계층 구조는 나무를 더 유연하게 만들었다.

코자는 리스프 프로그램을 나무로 표현했다.그는 나무 연산자의 표준 집합 내에서 유전 연산자와 유사점을 찾을 수 있었다.예를 들어 서브트리의 교환은 유전자 코드의 서브스트링이 차세대 개인에게 이식되는 유전자 크로스오버의 대응 프로세스와 동등하다.적합성은 리스프 코드의 함수의 출력을 점수화하여 측정합니다.나무 구조화된 리스프 표현과 나무로서의 문법 표현 사이의 유사한 유사점은 문법 유도를 위한 유전자 프로그래밍 기술의 적용을 가능하게 했다.

문법 유도의 경우, 하위 트리의 이식은 일부 언어에서 구문을 구문 분석할 수 있는 생산 규칙의 교환에 해당합니다.문법의 적합성 연산자는 대상 언어에서 일부 문장의 그룹을 구문 분석하는 데 얼마나 잘 수행되었는지를 나타내는 몇 가지 척도에 기초한다.문법의 트리 표현에서 작성 규칙의 종단 심볼은 트리의 리프 노드에 대응한다.상위 노드는 규칙 집합의 비말단 기호(예: 명사 구 또는 동사 구)에 해당합니다.최종적으로 루트 노드는 비말단 문장에 대응합니다.

탐욕 알고리즘에 의한 문법적 추론

모든 탐욕스러운 알고리즘과 마찬가지로 탐욕스러운 문법 추론 알고리즘은 반복적인 방식으로 그 단계에서 가장 좋은 것으로 보이는 결정을 내립니다.결정은 보통 새로운 규칙의 작성, 기존 규칙의 삭제, 적용할 규칙의 선택 또는 기존 규칙의 병합과 같은 것들을 다룬다.'단계'와 '최고'를 정의하는 몇 가지 방법이 있기 때문에, 탐욕스러운 문법 추론 알고리즘도 몇 가지 있다.

다음 문맥 없는 문법 생성 알고리즘은 모든 읽기 기호 후에 결정합니다.

• Lempel-Ziv-Welch 알고리즘은 생성된 문법의 시작 규칙만 저장해야 하는 결정론적 방법으로 문맥이 없는 문법을 만듭니다.
• 시퀀서와 그 수정.

이러한 문맥 없는 문법 생성 알고리즘은 먼저 주어진 기호 시퀀스 전체를 읽은 후 결정을 내리기 시작합니다.

• 바이트 쌍 인코딩 및 그 최적화.

분포 학습

보다 최근의 접근법은 분포 학습에 기초하고 있다.이러한 접근방식을 사용하는 알고리즘은 문맥이 없는 문법과 약간의 문맥에 민감한 언어를 학습하는 데 적용되었으며 이러한 문법의 ^[6]큰 하위 클래스에 정확하고 효율적인 것으로 입증되었다.

패턴 언어 학습

앙글루인은 패턴을 "δ의 상수 기호와 분리된 집합의 변수 기호 문자열"로 정의합니다.이러한 패턴의 언어는 비어 있지 않은 모든 그라운드 인스턴스의 집합이다. 즉, 변수 기호가 ^{[note 1]}비어 있지 않은 문자열로 일관되게 대체되어 발생하는 모든 문자열이다.패턴은 입력 집합을 포함하는 모든 패턴 언어 중에서 해당 언어가 최소(세트 포함에 관해)인 경우 문자열의 유한 입력 집합을 설명하는 것으로 불립니다.

앙글루인은 주어진 입력 문자열 세트에 대해 하나의 변수 ^{[note 2]}x에서 모든 설명 패턴을 계산하는 다항식 알고리즘을 제공합니다.이를 위해 그녀는 가능한 모든 관련 패턴을 나타내는 자동화를 구축한다. x가 유일한 변수인 단어 길이에 대한 정교한 인수를 사용하여 상태 수를 획기적으로 ^[7]줄일 수 있다.

Erlebach 등은 병렬화된 ^[8]버전뿐만 아니라 앙글루인의 패턴 학습 알고리즘의 보다 효율적인 버전을 제공한다.

아리무라 등은 제한된 패턴 조합에서 얻은 언어 클래스가 다항식 ^[9]시간에 학습될 수 있음을 보여준다.

패턴 이론

Ulf ^[10]Grenander에 의해 공식화된 패턴 이론은 세계에 대한 지식을 패턴으로 묘사하기 위한 수학적 형식주의이다.그것은 패턴을 인식하고 분류하기 위한 알고리즘과 기계를 규정하는 것으로 시작하지 않는다는 점에서 인공지능에 대한 다른 접근법과는 다르다. 대신에, 그것은 패턴 개념을 정확한 언어로 명확하게 표현하고 다시 표현하기 위한 어휘를 규정한다.

새로운 대수적 어휘 외에도, 통계적 접근법은 다음과 같은 목적을 위해 참신했다.

• 당시에는 일반적인 인공 자극이 아닌 실제 데이터를 사용하여 데이터 세트의 숨겨진 변수를 식별한다.
• 숨겨진 변수에 대한 사전 분포와 깁스 유사 그래프의 정점을 형성하는 관측 변수에 대한 모형을 공식화합니다.
• 이 그래프의 랜덤성과 변동성을 연구합니다.
• 패턴의 변형을 나열하여 적용된 확률 모델의 기본 클래스를 만듭니다.
• 모델을 사용하여 신호를 분석하는 것이 아니라 모형에서 합성(표본)할 수 있습니다.

수학적 적용범위가 넓은 패턴 이론은 대수와 통계뿐만 아니라 국지적 위상 및 전역 엔트로픽 특성에 걸쳐 있습니다.

적용들

문법 귀납의 원리는 자연어 처리의 다른 측면에 적용되어 의미 해석,^[2] 자연어 이해,^[11] 예문 기반 번역,^[12] 형태소 분석, 지명 파생 ^{[citation needed]}등에 적용되어 왔다.문법 인덕션은 최소 메시지 길이(MML) 및 최소 설명 길이(^{[citation needed]}Minimum Description Length) 원칙을 통한 문법 기반 압축^[13] 및 통계 추론에도 사용됩니다.문법 귀납법은 언어 ^[14]습득의 일부 확률론적 모델에서도 사용되어 왔다.

「 」를 참조해 주세요.

• 인공문법학습#인공지능
• 샘플 기반의 기계 번역
• 유도 프로그래밍
• 콜모고로프 복잡도
• 제한 내 언어 식별
• 직선 문법
• 구문 패턴 인식

메모들

레퍼런스

원천

• Duda, Richard O.; Hart, Peter E.; Stork, David G. (2001), Pattern Classification (2 ed.), New York: John Wiley & Sons
• Fu, King Sun (1982), Syntactic Pattern Recognition and Applications, Englewood Cliffs, NJ: Prentice-Hall
• Fu, King Sun (1977), Syntactic Pattern Recognition, Applications, Berlin: Springer-Verlag
• Horning, James Jay (1969), A Study of Grammatical Inference (Ph.D. Thesis ed.), Stanford: Stanford University Computer Science Department, ProQuest 302483145
• Gold, E. Mark (1967), Language Identification in the Limit, vol. 10, Information and Control, pp. 447–474, archived from the original on 2016-08-28, retrieved 2016-09-04
• Gold, E. Mark (1967), Language Identification in the Limit (PDF), vol. 10, Information and Control, pp. 447–474