구속조건모형

제약 조건 모델(CCM)은 선언적 제약 조건을 가진 조건부(확률론적 또는 차별적) 모델의 학습을 증가시키는 기계 학습 및 추론 프레임워크이다. 제약조건은 표현적^{[clarification needed]} 사전 지식을 모델에 통합하고 학습된 모델에 의해 이루어진 과제를 편향하여 이러한 제약조건을 충족시키는 방법으로 사용될 수 있다. 프레임워크는 훈련과 추론의 모듈성과 트랙터성을 유지하면서 표현형 출력 공간에서 결정을 지원하는 데 사용될 수 있다.

이런 종류의 모델들은 최근^[when?] 자연어 처리 커뮤니티 내에서 많은 관심을^{[citation needed]} 받고 있다. 학습된 모델의 산출물에 대해 제한된 최적화 문제로 문제를 공식화하는 것은 몇 가지 장점이 있다. 제1 순서 언어를 사용하여 도메인별 지식을 글로벌 제약조건으로 통합할 수 있는 기회를 제공함으로써 문제의 모델링에 집중할 수 있도록 한다. 이 선언적 프레임워크를 사용하면 개발자가 낮은 수준의 피쳐 엔지니어링으로부터 해방되는 동시에 문제의 도메인별 특성을 포착하고 정확한 추론을 보장할 수 있다. 머신러닝(machine learning) 관점에서 모델 생성(학습) 단계를 제한된 추론 단계와 분리할 수 있으므로, 해결책의 품질을 향상시키면서 학습 단계를 단순화하는 데 도움이 된다. 예를 들어, 압축 문장을 생성하는 경우, 단순히 언어 모델에 의존하여 문장에서 가장 일반적으로 사용되는 n그램들을 유지하는 것이 아니라, 한정자를 압축 문장에 보관할 경우 그 주제 또한 유지되도록 하기 위해 제약조건을 사용할 수 있다.

동기

많은 영역(자연어 처리 및 컴퓨터 비전 문제 등)에서 의사결정을 내리는 것은 표현적 종속성 구조가 어떤 과제가 가능한지에 영향을 미치거나 심지어 지시할 수 있는 상호의존적 변수 집합에 값을 할당하는 것을 포함한다. 이러한 설정은 의미론적 역할 라벨링과 같은 체계화된 학습 문제뿐만 아니라 요약, 텍스트 포함 및 질문 답변과 같이 미리 학습된 여러 구성요소를 사용해야 하는 사례에도 적용된다. 이러한 모든 경우에, 영역별 또는 문제별 제약조건에 따라 학습한 모델로 구성된 객관적 기능을 가진 제약적 최적화 문제로 의사결정 문제를 공식화하는 것은 당연하다.

제약 조건 모델은 선언적 제약조건(예: 1차 표현 사용)을 가진 조건부(확률론적 또는 차별적) 모델의 학습을 확장하는 학습 및 추론 프레임워크를 형성하며, 모듈성과 추적성을 유지하면서 표현적 출력 공간에서 의사결정을 지원하는 방법이다. 훈련과 추론 이러한 제약조건은 일부 과제를 완전히 금지하는 하드 제한사항 또는 소프트 제한사항 중 하나를 표현하여 가능성이 없는 과제를 벌충할 수 있다. NLP에서 이 프레임워크의 대부분의 애플리케이션에서는 다른 알고리즘이 그러한 목적을 위해 사용될 수 있지만, 다음의 경우 추론 프레임워크로 ILP(Integent Linear Programming)가 사용되었다.^[1]

형식 정의

Given a set of feature functions $\{\phi _{i}(x,y)\}$ and a set of constraints $\{C_{i}(x,y)\}$ , defined over an input structure $x\in X$ and an output structure $y\in Y$ , a constraint conditional model is w 및 $\rho$ ${\displaystyle \rho$ $\rho$ 의 두 무게 벡터로 특징지어지며, 다음과 같은 최적화 문제에 대한 해결책으로 정의된다.

argmax_{y}\sum _{i}w_{i}\phi _{i}(x,y)-\sum \rho _{i}C_{i}(x,y)

argmax_{y}\sum _{i}w_{i}\phi _{i}(x,y)-\sum \rho _{i}C_{i}(x,y)

argmax_{y}\sum _{i}w_{i}\phi _{i}(x,y)-\sum \rho _{i}C_{i}(x,y)

argmax_{y}\sum _{i}w_{i}\phi _{i}(x,y)-\sum \rho _{i}C_{i}(x,y)

argmax_{y}\sum _{i}w_{i}\phi _{i}(x,y)-\sum \rho _{i}C_{i}(x,y)

argmax_{y}\sum _{i}w_{i}\phi _{i}(x,y)-\sum \rho _{i}C_{i}(x,y)

argmax_{y}\sum _{i}w_{i}\phi _{i}(x,y)-\sum \rho _{i}C_{i}(x,y)

argmax_{y}\sum _{i}w_{i}\phi _{i}(x,y)-\sum \rho _{i}C_{i}(x,y)

i

argmax_{y}\sum _{i}w_{i}\phi _{i}(x,y)-\sum \rho _{i}C_{i}(x,y)

argmax_{y}\sum _{i}w_{i}\phi _{i}(x,y)-\sum \rho _{i}C_{i}(x,y)

(

argmax_{y}\sum _{i}w_{i}\phi _{i}(x,y)-\sum \rho _{i}C_{i}(x,y)

, y

argmax_{y}\sum _{i}w_{i}\phi _{i}(x,y)-\sum \rho _{i}C_{i}(x,y)

)

argmax_{y}\sum _{i}w_{i}\phi _{i}(x,y)-\sum \rho _{i}C_{i}(x,y)

-

argmax_{y}\sum _{i}w_{i}\phi _{i}(x,y)-\sum \rho _{i}C_{i}(x,y)

argmax_{y}\sum _{i}w_{i}\phi _{i}(x,y)-\sum \rho _{i}C_{i}(x,y)

i

argmax_{y}\sum _{i}w_{i}\phi _{i}(x,y)-\sum \rho _{i}C_{i}(x,y)

(

argmax_{y}\sum _{i}w_{i}\phi _{i}(x,y)-\sum \rho _{i}C_{i}(x,y)

, y

argmax_{y}\sum _{i}w_{i}\phi _{i}(x,y)-\sum \rho _{i}C_{i}(x,y)

) { i (x ,

argmax_{y}\sum _{i}w_{i}\phi _{i}(x,y)-\sum \rho _{i}C_{i}(x,y)

)

{\displaystyle argmax_{y}\sum _{i}w_{i}\i}-\i

}-\i

} \rho_{i}C_{i}(x,y

각 제약조건 C $C_{i}\in C$ $C_{i}\in C$ $C_{i}\in C$ ${\displaystyle C_{i}\in C$ $(x,y)$ 은 공동 할당( $(x,y)$ , y $(x,y)$ ) ${\displaystyle(x,y)}$ 이 제약조건을 위반하는지 $(x,y)$ 여부를 나타내는 부울 매핑이며 $C_{i}\in C$ , $\rho$ $\rho$ 은 제약조건을 $\rho$ 위반하여 발생하는 벌칙이다. 무한정 벌칙이 할당된 제약조건은 하드 제약조건으로 알려져 있으며, 최적화 문제에 대한 실현 불가능한 할당을 나타낸다.

교육 패러다임

로컬 및 글로벌 모델 학습

CCM이 사용하는 객관적 기능은 제약을 동반한 모델의 완전한 공동훈련에서부터 학습과 추론 단계를 완전히 분리하는 것까지 여러 가지 방법으로 분해하고 학습할 수 있다. 후자의 경우, 여러 로컬 모델을 독립적으로 학습하며, 이러한 모델 간의 의존성은 글로벌 의사결정 프로세스를 통해 의사결정 시에만 고려된다. 반면 IBT(합동 훈련)가장 제한에는 이론적으로 실험적으로, 일부 조건에서(기본적으로,"good" 구성 요소)각 접근법의 장점[2]에 대한 것 두 훈련 패러다임:(1)국내형 모델:L+I(+추론 학습)과(2)지구적인 모형:IBT(추론 기반 훈련)공부한다 논의된다 L.+I 일반화할 수 있다

지역 모델을 결합하는 CCM의 능력은 공동 학습이 계산적으로 난해하거나 공동 학습에 훈련 데이터를 이용할 수 없는 경우에 특히 유용하다. 이러한 유연성은 CCM을 마르코프 논리 네트워크와 같이 공동 훈련을 강조하는 선언적 제약조건과 통계 정보도 결합하는 다른 학습 프레임워크와 구별한다.

최소 감독 CCM

CCM은 학습을 추진하기 위해 도메인 지식(제한조건으로 표현)을 사용하여 감독을 줄이는 데 도움을 줄 수 있다. 이러한 환경은 에서 그리고 에서 연구되었다^[3].^[4] 이 작품들은 반 감독 제약 주도 학습(CODL)을 도입하고, 도메인 지식을 통합함으로써 학습된 모델의 성능이 크게 향상된다는 것을 보여준다.

잠재된 표현에 대한 학습

CCM은 또한 잠재된 표현 계층에 걸쳐 학습 문제가 정의되는 잠재 학습 프레임워크에도 적용되었다. 올바른 표현에 대한 개념은 본질적으로 잘못 정의되어 있기 때문에, 표현 결정에 관한 금본위제의 데이터는 학습자가 이용할 수 없다. 올바른(또는 최적의) 학습 표현을 식별하는 것은 구조화된 예측 과정으로 간주되며 따라서 CCM으로 모델링된다. 이 문제는 감독^[5] 및 감독되지 않은 환경에서 여러 논문에서 다루어졌다. 모든 사례 연구에서 제약을 통해 대표 결정들 사이의 상호의존성을 명시적으로 모델링하는 것이 성과를 향상시킨다는 것을 보여주었다.

자연 언어 처리 응용 프로그램을 위한 정수 선형 프로그래밍

그 CCM을 선언적 준비와 기성품인 해결사들의 가용성의 장점은 자연 언어 처리 작업의 의미 역할 labeling,[7]통사 parsing,[8]동일 지시어 resolution,[9]summarization,[10][11][12]transliteration,[13]자연 언어 비롯한 다양한 틀 내에서 추진 중,로 이어졌다.세대[14]과의 이음매.형질 ^[15]^[16]추출

이들 작품의 대부분은 의사결정 문제를 해결하기 위해 정수 선형 프로그래밍(ILP) 해결기를 사용한다. 이론적으로 정수 선형 프로그램을 푸는 것은 의사결정 문제의 크기에 있어서 기하급수적이긴 하지만, 실제로 최첨단 해결기와 대략적인 추론 기법을 사용하는 연습에서는 대규모 문제를 효율적으로 해결할 수 있다.

제한된 조건부 모델에 의해 정의되는 최적화 문제를 해결하기 위해 ILP 해결기를 사용하는 주요 장점은 선형 목표 함수와 일련의 선형 제약조건으로 구성된 ILP 해결사의 입력으로 사용되는 선언적 공식이다.

자원.

CCM 자습서 NLP에서의 구조 예측 : 제한조건모델과 NLP에서의 정수선형 프로그래밍

외부 링크

참조

^ Dan Roth and Wen-tau Yih, "자연어과제에 있어서의 세계 추론을 위한 선형 프로그래밍 공식화" CoNLL, (2004)
^ Vasin Punyakanok과 Dan Roth와 Wen-Tau Ih와 Dav Zimak, "제한된 출력에 대한 학습과 추론". IJCAI, (2005년)
^ 밍웨이 장과 레프 라티노프, 댄 로스 "제약 주도 학습으로 세미 슈퍼비전 안내" ACL, (2007)
^ Ming-Wei Chang과 Lev Ratinov and Dan Roth, "사전 지식으로서의 개념" ICML 텍스트 및 언어 처리를 위한 사전 지식 워크숍(2008)
^ 밍웨이 장과 댄 골드워서, 댄 로스와 비벡 스리쿠마르, "잠재적 표현에 대한 차별적 학습" NAACL, (2010)
^ 밍웨이 장 단 골드워서 댄 로스(Dan Roth)와 위안청 투(Yuanchung Tu), "변환성 발견을 위한 감독되지 않은 제약 주도 학습"^{[permanent dead link]} NAACL, (2009)
^ Vasin Punyakanok, Dan Roth, Wen-tau Ih, Dav Zimak, "Instant Linear Programming 추론을 통한 대서양 역할 라벨링" COLING, (2004)
^ 사개 겐지, 미야오 유스케, 츠지이 준이치, 「HPSG의 얄팍한 의존성 제약으로 파싱」. ACL, (2007)
^ Pascal Denis와 Jason Baldridge, "Instant Programming을 이용한 무수성 및 핵심적 해석의 공동 결정" 2010-06-21 Wayback Machine NAACL-HLT, (2007)에 보관.
^ 제임스 클라크와 미렐라 라파타 "문장 압축에 대한 글로벌 추론: 정수 선형 프로그래밍 접근법." 인공지능 연구 저널 (JAIR), (2008)
^ 카타 필리포바와 마이클 스트루베, "의존 트리 기반 문장 압축"^{[permanent dead link]} INLG, (2008)
^ Katja Fillippova와 Michael Strube, "상속성 그래프 압축을 통한 Sentence Fusion." EMNLP, (2008)
^ Dan Goldwasser와 Dan Roth, "제한된 최적화로서의 변환" EMNLP, (2008)
^ Regina Barzilay와 Mirrela Lapata, "자연어 생성을 위한 세트 파티셔닝을 통한 인종차별" NAACL, (2006)
^ Dan Roth and Wen-tau Yih, "자연어과제에 있어서의 세계 추론을 위한 선형 프로그래밍 공식화" CoNLL, (2004)
^ 최예진, 에릭 브렉, 클레어 카디 「여론인식을 위한 실체·관계의 공동 추출. EMNLP, (2006)
^ 앙드레 F. T. 마틴스, 노아 A. Smith, and Eric P. Xing, "Concise 정수 선형 프로그래밍 for Dependency Parsing." ACL, (2009)

[1] Dan Roth and Wen-tau Yih, "자연어과제에 있어서의 세계 추론을 위한 선형 프로그래밍 공식화" CoNLL, (2004)

[2] Vasin Punyakanok과 Dan Roth와 Wen-Tau Ih와 Dav Zimak, "제한된 출력에 대한 학습과 추론". IJCAI, (2005년)

[3] 밍웨이 장과 레프 라티노프, 댄 로스 "제약 주도 학습으로 세미 슈퍼비전 안내" ACL, (2007)

[4] Ming-Wei Chang과 Lev Ratinov and Dan Roth, "사전 지식으로서의 개념" ICML 텍스트 및 언어 처리를 위한 사전 지식 워크숍(2008)

[5] 밍웨이 장과 댄 골드워서, 댄 로스와 비벡 스리쿠마르, "잠재적 표현에 대한 차별적 학습" NAACL, (2010)

[6] 밍웨이 장 단 골드워서 댄 로스(Dan Roth)와 위안청 투(Yuanchung Tu), "변환성 발견을 위한 감독되지 않은 제약 주도 학습"^{[permanent dead link]} NAACL, (2009)

[7] Vasin Punyakanok, Dan Roth, Wen-tau Ih, Dav Zimak, "Instant Linear Programming 추론을 통한 대서양 역할 라벨링" COLING, (2004)

[8] 사개 겐지, 미야오 유스케, 츠지이 준이치, 「HPSG의 얄팍한 의존성 제약으로 파싱」. ACL, (2007)

[9] Pascal Denis와 Jason Baldridge, "Instant Programming을 이용한 무수성 및 핵심적 해석의 공동 결정" 2010-06-21 Wayback Machine NAACL-HLT, (2007)에 보관.

[10] 제임스 클라크와 미렐라 라파타 "문장 압축에 대한 글로벌 추론: 정수 선형 프로그래밍 접근법." 인공지능 연구 저널 (JAIR), (2008)

[11] 카타 필리포바와 마이클 스트루베, "의존 트리 기반 문장 압축"^{[permanent dead link]} INLG, (2008)

[12] Katja Fillippova와 Michael Strube, "상속성 그래프 압축을 통한 Sentence Fusion." EMNLP, (2008)

[13] Dan Goldwasser와 Dan Roth, "제한된 최적화로서의 변환" EMNLP, (2008)

[14] Regina Barzilay와 Mirrela Lapata, "자연어 생성을 위한 세트 파티셔닝을 통한 인종차별" NAACL, (2006)

[15] Dan Roth and Wen-tau Yih, "자연어과제에 있어서의 세계 추론을 위한 선형 프로그래밍 공식화" CoNLL, (2004)

[16] 최예진, 에릭 브렉, 클레어 카디 「여론인식을 위한 실체·관계의 공동 추출. EMNLP, (2006)

[17] 앙드레 F. T. 마틴스, 노아 A. Smith, and Eric P. Xing, "Concise 정수 선형 프로그래밍 for Dependency Parsing." ACL, (2009)

[1]

[3]

[4]

[5]

[15]

[16]

Search