KR20060045349A - 논리 형식에 대한 통계적 언어 모델 - Google Patents

Abstract

본 발명은 출력 의미 구조를 생성하기 위한 입력 의미 구조를 디코드하는 방법에 관한 것이다. 전송 매핑들의 집합이 제공된다. 스코어(score)는 전송 매핑의 집합 내의 적어도 하나의 전송 매핑에 대해서 통계적 모델을 사용하여 계산된다. 적어도 하나의 전송 매핑은 스코어에 기초하여 선택되고, 출력 의미 구조를 구성하기 위해 사용된다.

Description

논리 형식에 대한 통계적 언어 모델{STATISTICAL LANGUAGE MODEL FOR LOGICAL FORMS}

본 발명은 자동화된 언어 시스템에 관한 것이다. 더욱 구체적으로, 본 발명은 통계적 언어 시스템에서 언어 모델에 관한 것이다.

자동화된 언어 시스템은 음성 인식(speech recognition), 필체 인식(handwriting recognition), 음성 생성, 문법 검사(grammar checking) 및 기계 번역(Machine translation; MT)을 포함한다.

기계 번역 시스템은 하나의 언어("소스(source)" 언어)로 입력을 수신받고, 입력을 제2 언어("타겟(target)" 언어)로 번역하며, 제2 언어로 출력을 제공하는 시스템이다.

MT 시스템의 하나의 예는, 번역에서의 중간 단계로서 문자열에서 의미 단어들(content words) 사이의 라벨(label)이 붙여진 의존성(labeled dependency)을 설명하는 의존 그래프(dependency graph)인 논리 형식(logical form; LF)을 사용한다. 이 시스템 하에서, 소스 언어의 문자열은 우선 소스 LF를 생성하기 위해서 자연 언어 구문 분석기(natural language parser)로 분석된다. 소스 LF는 그 후, 타겟 언어 LF로 변환되어야 한다. (몇몇 트레이닝(training) 집합 내의 매핑의 사이즈 및 매핑의 빈도와 같은 다른 메타데이터(metadata)와 더불어) 소스 언어 LF 피스들(pieces)로부터 타겟 언어 LF 피스들로의 매핑(mapping) 데이터베이스가 이 변환을 위해서 사용된다. 자신의 소스 언어 LF 피스들이 소스 LF의 서브그래프인 모든 매핑이 우선 검색된다. 일반적으로, 단일 매핑의 소스 언어 LF 피스는 전체 소스 LF를 커버하지 않는다. 그 결과, 매핑들의 집합(중첩될 수 있음)이 선택되어야 하고, 그들의 타겟 언어 LF 피스들은 완전한 타겟 LF를 형성하기 위해서 조합되어야 한다.

타겟 논리 형식의 집합을 식별하기 위해서, MT 시스템은 그리디(greedy) 검색 알고리즘을 사용하여, 자신의 소스 언어 LF 피스들이 소스 LF에 부합하는 가능한 매핑들로부터 매핑들의 조합을 선택한다. 이 그리디 검색은 사이즈, 빈도 및 매핑의 소스 언어 LF 피스들이 소스 LF에 얼마나 잘 부합하는 지를 측정하는 다른 특징들에 의해 매핑들을 분류하는 것으로 시작한다. 그러면 분류된 리스트는 하향식(top-down manner)으로 트래버스되고(traversed), 소스 논리 형식을 커버하는 것으로 발견된 양립 가능한 매핑들의 제1 집합이 선택된다. 그러나 이러한 발견적(heuristic) 시스템은 인풋 매핑들의 모든 가능한 조합들을 테스트하지 않지만, 소스 LF를 완전히 커버하는 매핑들의 제1 집합을 단순히 선택한다.

매핑들의 집합이 선택된 후, 매핑들의 타겟 언어 LF 피스들은 타겟 LF를 생성하기 위해서 소스 LF와 합치하는 방식으로 조합된다. 끝으로, 타겟 LF 상의 자연 언어 생성 시스템을 가동하는 것은 타겟 언어 출력을 생산한다.

그러나 MT 시스템이 항상 중간적 표현(intermediate representation)과 같은 논리 형식 또는 다른 구문 분석된 구조를 채용하는 것은 아니다. 또한, 번역의 애매함을 해결하기 위해서 필연적으로 발견적 방법을 사용하는 것도 아니다. 몇몇 다른 MT 시스템은 통계적 모델을 사용하는 소스 언어에서 주어진 입력 문자열에 대해서 타겟 언어를 가장 유사하게 예측하려고 한다. 그러한 MT 시스템은 주어진 소스 문장 S에 대한 가장 그럴듯한 번역인 타겟 언어 T를 디코드(decode)하고 찾아내기 위해서, 잡음채널 플레임워크(noisy-channel framework)와 같은 종래의 통계적 프레임워크 및 모델을 사용한다. 그 확률을 최대화하는 것은 수학식(1)에 의해 표현된다.

T`는 타겟 언어에서 문장들에 걸쳐있다. 베이즈 룰(Bayes Rule)을 사용하여, 이 확률을 최대화하는 것은 수학식(2)에 의해 표현된다.

P(S│T`)는 주어진 타겟 언어 문자열 T`에 대한 소스 언어 문자열 S의 확률이고, P(T`)는 타겟 언어 문자열 T`의 확률이다. 문자열 기반의 통계적 MT(어떠한 구문 분석된 중간적 표현도 사용되지 않은 MT)에서, 한 언어로 된(monolingual) 타겟 언어 데이터 상에서 학습된(trained) 타겟 언어 모델은 P(T)의 추정치를 계산하기 위해 사용되고, 가변 복잡성의 정렬 모델(alignment models of varying complexity)은 P(S│T)의 추정치를 계산하기 위해 사용되었다.

종래의 문자열 기반의 통계적 MT 시스템과 연관된 수많은 문제점이 있다. 구체적으로, 검색 영역(search space)(타겟 언어의 모든 가능한 문자열)은 상당히 넓다. 이 검색 영역을 제한하지 않고는 모든 가능한 번역 문자열을 고려하기에는 시간이 오래 걸리기 때문에, 실용적인 MT 시스템을 만들 수 없다. 이를 해결하고자, 많은 시스템은, 전체 문자열에 대한 채널 모델 및 타겟 언어 모델의 확률이 문자열 내의 서브 문자열들의 확률의 곱으로 결정될 수 있다는 단순화 가정을 사용한다. 이 가정은 문자열들 내에서 및 문자열들 사이에서 의존성이 서브 문자열에 의해서 정의된 로컬(local) 영역에 제한되는 경우에 한해서만 유효하다. 그러나 때때로 많은 양의 소스 언어 텍스트에 대한 가장 좋은 번역은 예측되는 요소들로부터 상대적으로 멀리 떨어진 소스 및 타겟 언어의 요소들에 좌우된다. 문자열 기반 통계적 MT 모델에서 만들어진 단순화 가정은 문자열 지역성(locality)에 많은 부분을 기초하기 때문에, 때때로 이 조건 요소들(conditioning elements)은 예측되는 요소로부터 너무 멀리 떨어져 있기 때문에, 조건 요소들은 상기 모델들에 의해 고려되지 못한다.

예를 들어, 몇몇 문자열 기반 통계적 MT 시스템은 시스템의 언어 모델(LM)에 대한 문자열 n-gram 모델을 사용한다. 이러한 n-gram모델은 학습하고, 사용 및 최적화가 단순하다. 그러나 n-gram 모델은 몇 가지 제한이 있다. 비록 하나 또는 두 개의 중간적 프로세서들로부터 하나의 단어를 정확하게 예측하는 것이 가능하지만, 많은 언어 구조는, 고도로 예상되는 단어들(highly predictive words)을 그들이 예측한 단어들로부터 너무 멀리 배치하기 때문에, 그 단어들은 문자열 n-gram 모델의 범위로부터 제외된다. 이하의 능동 및 수동형 문장들을 고려하자

1. John hit the ball.

2. The balls were hit by Lucy.

이하의 트라이그램(trigram)이, 제시된 빈도들로 이러한 문장들에서 발생한다.

"<P>"는 문장의 시작에서 문장 시작 콘텍스트를 제공하는 가상의 토큰(token)이고, "<POST>"는 문장의 끝에서의 가상의 토큰이다. 모든 경우에서의 이벤트(공을 치는 것)는 동일하지만, 이러한 트라이그램 각각은 오직 한 번씩만 발생한다는 것을 알아야 한다.

다른 통계적 MT 시스템에서, 소스 언어에서의 신택스(syntax) 구조는 타겟 언어에서의 문자열로 매핑된다. 신택스 기반의 모델들은 문자열 기반 모델들에 비해 몇 가지 장점을 갖는다. 하나의 측면은, 신택스 기반 모델들은 렘마(lemma)를 표준화하여 부족한 데이터(sparse data) 문제의 정도를 줄일 수 있다는 것이다. 다른 측면은, 신택스 기반 모델은 언어의 신택스 구조를 고려할 수 있다는 것이다. 따라서 서로 의존하는 이벤트들은, 종종 표면 문자열(surface string)에서의 경우보다 신택스 트리(tree) 내에서 서로 더 가까운데, 이는 문자열에서의 거리보다 공통 부모(common parent)에 대한 거리가 짧을 수 있기 때문이다.

그러나 신택스 기반 모델의 경우라도 단점이 있다. 즉, 상호 의존하는 단어들 사이의 거리가 로컬 모델에 의해 캡쳐(capture)되기에는 여전히 너무 길고, 또한 유사한 개념들이 상이한 구조들로 표현되어(예를 들면, 능동과 수동 표현), 같이 모델화될 수 없다는 것이다. 이에 따라 모델 학습의 악화 및 번역 수행의 악화가 발생한다.

[문헌1] 미국 특허 제 5,966,686 호, 헤이돈 외, 신택스 트리로부터의 논리적 의미 형태를 계산하기 위한 방법 및 시스템(METHOD AND SYSTEM FOR COMPUTING SEMANTIC LOGICAL FORMS FROM SYNTAX TREES)

[문헌2] Computer Journal, "An Efficient Method of Finding the Minimum of a Function of Several Variables without Calculating Derivates.", 7:155-162.

[문헌3] 파피네니 외, IBM 기술 리포트 RC22176(WO109-022), "Blue: a method for automatic evaluation of machine translation.", 2001, IBM 리서치 부, 토마스 J. 왓슨 리서치 센터.

[문헌4] 네이 에센 및 크네서, Computer Speech and Language, "On structuring probabilistic dependences in stochastic language modeling.", 1994, 8:1-38.

본 발명은 출력 의미 구조(output semantic structure)를 생성하기 위해 입력 의미 구조(input semantic structure)를 디코드하는 방법을 포함한다. 이 기술은 입력 의미 구조의 부분에 대한 전송 매핑들(transfer mappings)의 집합을 채용한다. 스코어는, 통계적 모델을 사용하는 전송 매핑들의 집합 내에서 적어도 하나의 전송 매핑에 대하여 계산된다. 적어도 하나의 전송 매핑은 스코어에 기초하여 선택되고, 출력 의미 구조를 만들기 위해 사용된다. 또한, 본 발명은 컴퓨터 구현 방법 및 기계 번역 시스템으로 구현될 수 있다. 본 발명의 향상된 측면은 의미 구조들로부터 구성된 언어 모델이다.

본 발명이 기계 번역 시스템의 콘텍스트로 설명된 범위에서는, 본 발명은 단어들을 생성하거나 언어 모델을 필요로 하는 다른 시스템들에도 적용될 수 있다는 것을 알아야 한다. 예를 들어, 시스템들은 음성 인식(speech recognition), 광문자인식(optical character recognition; OCR), 문법 검사(grammar checking) 등을 포함한다. 본 발명을 자세히 설명하기에 앞서, 본 발명이 적용될 수 있는 도시적인 컴퓨팅 환경의 실시예를 설명한다.

도 1은 본 발명이 구현될 수 있는 적합한 컴퓨팅 시스템 환경(100)의 예시도이다. 컴퓨팅 시스템 환경(100)은 적합한 컴퓨팅 환경의 하나의 예일 뿐이며, 사용의 범위나 본 발명의 기능을 제한하도록 의도된 것은 아니다. 또한, 컴퓨팅 환경(100)은 예시적 운영 환경(100)에 도시된 구성 요소들의 임의의 하나 또는 그 조합과 관련된 어떠한 의존성 또는 요구사항을 갖는 것으로 해석되어서도 안 된다.

본 발명은 수많은 다른 일반 목적 또는 특별 목적의 컴퓨팅 시스템 환경 또는 구성(configuration)과 함께 작동 가능하다. 본 발명과 함께 사용되기에 적합할 수 있는 주지된 컴퓨팅 시스템, 환경 및/또는 구성의 예는 개인용 컴퓨터, 서버 컴퓨터, 포켓용(hand-held) 또는 랩탑 장치, 멀티프로세서 시스템, 마이크로프로세서 기반 시스템, 세트톱 박스(set top boxes), 프로그램 가능한 소비자 전자기기(programmable consumer electronics), 네트워크 PC, 미니컴퓨터, 메인프레임 컴퓨터(mainframe computers), 전화 통신 시스템(telephony system), 임의의 상기 시스템 또는 장치 등을 포함하는 분산 컴퓨팅 환경 등을 포함하지만 이에 한정되지 않는다.

본 발명은 프로그램 모듈과 같은 컴퓨터에 의해 실행되는 컴퓨터 실행 가능한 명령어들의 일반적인 콘텍스트로 서술될 수 있다. 일반적으로, 프로그램 모듈은 특정한 임무를 수행하거나 특정한 추상 데이터 타입(abstract data types)을 구현하는 루틴(routine), 프로그램, 객체(object), 구성 요소, 데이터 구조(data structure) 등을 포함한다. 본 발명은 임무가 통신 네트워크를 통해서 링크된 원격 프로세싱 장치에 의해 수행되는 분산 컴퓨팅 환경에서 실시되도록 설계되었다. 분산 컴퓨팅 환경에서, 프로그램 모듈은 메모리 저장 장치를 포함하는 로컬 및 원격 컴퓨터 저장 매체 모두에 위치한다.

도 1과 관련하여, 본 발명을 구현하기 위한 예시적 시스템은 컴퓨터(110)의 형태인 일반 목적의 컴퓨팅 장치를 포함한다. 컴퓨터(110)의 구성 요소들은 프로세싱 유닛(120), 시스템 메모리(130) 및 시스템 메모리를 포함하는 다양한 시스템 구성 요소를 프로세싱 유닛에 결합하는 시스템 버스(121)를 포함하지만 이에 한정되지는 않는다. 시스템 버스(121)는 메모리 버스 또는 메모리 컨트롤러를 포함하는 버스 구조, 주변 장치 버스 및 임의의 다양한 버스 구조를 사용하는 로컬 버스의 임의의 몇 가지 유형일 수 있다. 예를 들어, 그러한 구조는 ISA(Industry Standard Architecture) 버스, Micro Channel Architecture(MCA) 버스, Enhanced ISA(EISA) 버스, Video Electronics Standards Association(VESA) 로컬 버스 및 Mezzanine 버스로 또한 알려진 Peripheral Component Interconnect(PCI) 버스를 포함하지만 이에 한정되지는 않는다.

일반적으로, 컴퓨터(110)는 다양한 컴퓨터 판독 가능 매체를 포함한다. 컴퓨터 판독가능 매체는 컴퓨터(110)에 의해 액세스 가능한 임의의 적용 가능한 매체일 수 있고, 휘발성 및 비휘발성 매체, 분리성 및 비분리성 매체 모두를 포함한다. 예를 들어, 컴퓨터 판독 가능 매체는 컴퓨터 저장 매체 및 통신 매체를 포함하지만 이에 한정되지 않는다. 컴퓨터 저장 매체는 컴퓨터 판독 가능 명령어, 데이터 구조, 프로그램 모듈 또는 다른 데이터와 같은 정보의 저장을 위한 임의의 방식 또는 기술로 구현되는 휘발성 및 비휘발성 그리고 분리식 및 비분리식 매체 모두를 포함한다. 컴퓨터 저장 매체는 RAM, ROM, EEPROM, 플래쉬 메모리 또는 다른 메모리 기술, CD-ROM, DVD 또는 다른 광디스크 저장, 마그네틱 카세트, 마그네틱 테이프, 마그네틱 디스크 저장 또는 다른 마그네틱 저장 장치, 또는 원하는 정보를 저장하는데 사용될 수 있고 컴퓨터(110)에 의해 액세스 될 수 있는 임의의 다른 중간체를 포함하지만 이에 한정되지는 않는다. 일반적으로, 통신 매체는 컴퓨터 판독 가능 명령어, 데이터 구조, 프로그램 모듈 또는 캐리어 웨이브(carrier wave), 또는 다른 전달 메커니즘과 같은 변조된(modulated) 데이터 신호의 다른 데이터로 구체화되고, 임의의 정보 전달 매체를 포함한다. 용어 "변조된 데이터 신호"는 신호의 정보를 인코드(encode)하도록 설정되거나, 변경된 하나 이상의 특성을 갖는 신호를 의미한다. 예를 들어, 통신 매체는 유선(wired) 네트워크 또는 직접 유선(direct wired) 연결과 같은 유선 매체 및 음향(acoustic), RF, 적외선 및 다른 무선 매체와 같은 무선 매체를 포함하지만 이에 한정되지는 않는다. 또한, 상기의 임의 조합은 컴퓨터 판독 매체의 범위 내에 포함될 수 있다.

시스템 메모리(130)는 ROM(131) 및 RAM(132)과 같은 휘발성 및/또는 비휘발성 메모리의 형태인 컴퓨터 저장 매체를 포함한다. 스타트업하는 동안에서와 같이 컴퓨터(110) 내의 소자들 사이의 정보를 전달하는 것을 돕는 기초 루틴을 포함하는 바이오스(BIOS; 133)는 일반적으로 ROM(131)에 저장된다. 일반적으로, RAM(132)은 데이터 및/또는 즉시 액세스 가능하고 그리고/또는 현재 프로세싱 유닛(120)에 의해 동작되는 프로그램 모듈을 포함한다. 예를 들어, 도 1은 운영 체제(134), 응용 프로그램(135), 다른 프로그램 모듈(136) 및 프로그램 데이터(137)를 도시하지만 이에 한정되지는 않는다.

또한, 컴퓨터(110)는 다른 분리식/비분리식 휘발성/비휘발성 컴퓨터 저장 매체를 포함할 수 있다. 단지 예로서, 도 1은 비분리식, 비휘발성 마그네틱 매체로부터 읽고, 또는 그러한 매체에 쓰는 하드 디스크 드라이브(141), 분리식, 비휘발성 마그네틱 디스크(152)로부터 읽고, 또는 그러한 디스크에 쓰는 마그네틱 디스크 드라이브(151) 및 CD ROM 또는 다른 광학 매체와 같은 분리식, 비휘발성 광디스크(156)로부터 읽고, 또는 그러한 광디스크에 쓰는 광디스크 드라이브(155)를 도시한다. 예시적 운영 환경에서 사용될 수 있는 다른 분리식/비분리식, 휘발성/비휘발성 컴퓨터 저장 매체는 마그네틱 테이프 카세트, 플래시 메모리 카드, DVD, 디지털 비디오테이프, solid state RAM, solid state ROM 등을 포함하지만 이에 한정되지는 않는다. 일반적으로, 하드 디스크 드라이브(141)는 인터페이스(140)와 같은 비분리식 메모리 인터페이스를 통해 시스템 버스(121)에 접속되고, 마그네틱 디스크 드라이브(151) 및 광디스크 드라이브(155)는 인터페이스(150)와 같은 분리식 메모리 인터페이스에 의해 시스템 버스(121)에 접속된다.

위에서 논의되고 도 1에서 도시된 드라이브 및 그와 연관된 컴퓨터 저장 매체는 컴퓨터 판독 가능 명령어, 데이터 구조, 프로그램 모듈 및 컴퓨터(110)에 대한 다른 데이터 저장을 제공한다. 예를 들어, 도 1에서, 하드 디스크 드라이브(141)가 저장 운영 체제(144), 응용 프로그램(145), 다른 프로그램 모듈(146) 및 프로그램 데이터(147)로 도시된다. 이러한 구성 요소들은 운영 체제(134), 응용 프로그램(135), 다른 프로그램 모듈(136) 및 프로그램 데이터(137)와 동일하거나 상이할 수 있다는 것을 알아야 한다. 운영 체제(144), 응용 프로그램(145), 다른 프로그램 모듈(146) 및 프로그램 데이터(147)는 최소한, 그것들이 상이한 복사 본들이란 것을 설명하기 위해 다른 부호로 표시했다.

사용자는 키보드(162)와 마이크로폰(163)과 마우스, 트랙볼 또는 터치패드와 같은 포인팅 디바이스(pointing device; 161)의 입력 장치를 통해서 컴퓨터(110)에 명령어 및 정보를 입력할 수 있다. 다른 입력 장치들(도시하지 않음)은 조이스틱, 게임 패드, satellite dish, 스캐너 등을 포함할 수 있다. 이러한 입력 장치 및 다른 입력 장치들은 종종 시스템 버스에 결합된 사용자 입력 인터페이스(160)를 통해서 프로세싱 유닛(120)에 접속되지만, 다른 인터페이스 및 패러렐 포트, 게임 포트 또는 유니버설 시리얼 버스(USB)와 같은 버스 구조에 의해 접속될 수도 있다. 또한, 모니터(191) 또는 다른 유형의 디스플레이 장치는 비디오 인터페이스(190)와 같은 인터페이스를 통해 시스템 버스(121)에 접속된다. 또한, 모니터에 더하여 컴퓨터들은 출력 주변 장치 인터페이스(195)를 통해 접속될 수 있는 스피커(197) 및 프린터(196)와 같은 다른 주변 출력 장치를 포함할 수 있다.

컴퓨터(110)는 원격 컴퓨터(180)와 같이 하나 이상의 원격 컴퓨터들로의 논리적 접속을 사용하는 네트워크 환경에서 운영될 수 있다. 원격 컴퓨터(180)는 개인용 컴퓨터, 포켓용 장치, 서버, 라우터, 네트워크 PC, 피어 장치(peer device) 또는 다른 공통 네트워크 노드(common network node)일 수 있고, 일반적으로 컴퓨터(110)와 관련하여 상기에 서술한 요소의 다수 또는 모두를 포함한다. 도 1에서 도시된 논리적 접속은 LAN(local area network; 171) 및 원거리통신망(wide area network; WAN)을 포함하지만, 다른 네트워크들도 포함할 수 있다. 그러한 네트워크 환경들은 사무실, 기업규모의 컴퓨터 네트워크, 인트라넷 및 인터넷에서 평범한 것이다.

LAN 네트워크 환경에서 사용될 경우, 컴퓨터(110)는 네트워크 인터페이스 또는 어댑터(170)를 통해서 LAN(171)에 접속된다. WAN 네트워크 환경에서 사용될 경우, 컴퓨터(110)는 일반적으로 모뎀(172) 또는 인터넷과 같이 WAN(173) 상에서 통신을 하기 위한 다른 수단들을 포함한다. 내부형 또는 외부형일 수 있는 모뎀(172)은 사용자 입력 인터페이스(160) 또는 다른 적절한 메커니즘을 통해서 시스템 버스(121)에 접속될 수 있다. 네트워크 환경에서, 컴퓨터(110) 또는 그 부분과 관련되어 서술된 프로그램 모듈은 원격 메모리 저장 장치에 저장될 수 있다. 예를 들어, 도 1은 원격 컴퓨터(180)에 상주하는 원격 응용 프로그램(185)을 도시하지만 이에 한정되지는 않는다. 도시된 네트워크 접속은 예시적이고, 컴퓨터들 사이에 통신 링크를 만들기 위한 다른 수단이 사용될 수 있다는 것을 알아야 한다.

도 2는 이동 장치(200)의 블록도로서, 예시적 컴퓨팅 환경을 나타낸다. 이동 장치(200)는 마이크로프로세서(202), 메모리(204), 입출력(I/O) 구성 요소(206) 및 원격 컴퓨터들 또는 다른 이동 장치들과 통신하기 위한 통신 인터페이스(208)를 포함한다. 하나의 실시예에서, 상술한 구성 요소들은 적합한 버스(210)를 통해 서로 통신하기 위해 연결되었다.

메모리(204)는 예비 전지 모듈(battery back-up module; 도시하지 않음)이 있는 RAM과 같은 비휘발성 전자 메모리로 구현되어, 메모리(204) 내에 저장된 정보는 이동 장치(200)에의 일반 전력(general power)이 셧다운(shut down)되는 경우라도 소실되지 않는다. 바람직하게, 메모리(204)의 일부분은 프로그램 수행을 위한 어드레스 가능한(addressable) 메모리로 할당되고, 메모리(204)의 다른 부분은 디스크 드라이브 상에서 저장 장치를 시뮬레이트(simulate)하기 위한 것과 같이 저장 장치로 사용된다.

메모리(204)는 운영 체제(212), 애플리케이션 프로그램(214) 및 객체 저장 장치(object store; 216)를 포함한다. 바람직하게는, 작동하는 동안, 운영 체제(212)는 메모리(204)의 프로세서(202)에 의해 실행될 수 있다. 하나의 바람직한 실시예에서, 운영 체제(212)는 마이크로소프트사의 상업적으로 구입 가능한 WINDOWS^® CE 브랜드 운영 체제이다. 바람직하게는, 운영 체제(212)는 이동 장치를 위해 설계되었고, 노출된(exposed) 응용 프로그램 인터페이스들 및 방법들의 집합을 통해서 애플리케이션(214)에 의해 이용될 수 있는 데이터베이스 특성을 구현한다. 객체 저장 장치 내의 객체들은 애플리케이션(214) 및 노출된 애플리케이션 프로그램 인터페이스들 및 방법들에 대한 호출에 적어도 부분적으로 반응하는 운영 체제(212)에 의해 유지된다.

통신 인터페이스(208)는 이동장치(200)가 정보를 송신 및 수신하도록 하는 수많은 장치 및 기술들을 제시한다. 장치는 몇 가지 예를 들자면, 유선 및 무선 모뎀, 인공위성 수신기 및 브로드캐스트 튜너(broadcast tuner)를 포함한다. 또한, 이동 장치(200)는 데이터를 교환하기 위해 컴퓨터에 직접적으로 접속될 수 있다. 이러한 경우에, 통신 인터페이스(208)는 스트리밍(streaming) 정보를 전송할 수 있는 적외선 송수신기(infrared transceiver) 또는 시리얼이나 패러렐 통신 접속일 수 있다.

입출력 구성 요소(206)는 터치스크린(touch-sensitive screen), 버튼, 롤러(rollers) 및 마이크로폰과 같은 다양한 입력 장치들과 오디오 생성기(audio generator), 진동 장치(vibrating device) 및 디스플레이를 포함하는 출력 장치들을 포함한다. 상기에 열거된 장치들은 예시적인 것이고, 이동 장치(200) 상에 모두 있을 필요는 없다. 부가하면, 다른 입출력 장치들이 부착될 수 있거나 또는 본 발명의 범위 내에서 이동 장치(200)에서 발견될 수 있다.

논리 형식

본 발명을 더욱 자세하게 설명하기에 앞서서, 논리 형식에 대한 간단한 설명이 도움이 될 것이다. 논리 형식과 시스템, 그리고 이들 형식과 시스템을 생성하기 위한 방법에 관한 전체적이고 세부적인 논의는 1999년 10월 12일에 등록되고, 발명의 명칭이 신택스 트리로부터의 논리적 의미 형식을 계산하기 위한 방법 및 시스템(METHOD AND SYSTEM FOR COMPUTING SEMANTIC LOGICAL FORMS FROM SYNTAX TREES)인 헤이돈 외의 미국 특허 제 5,966,686 호에서 찾을 수 있다. 그러나 간단하게, 논리 형식은 입력 텍스트 상의 어형론적 분석(morphological analysis)을 수행하여 생성되고, 문법적 관계가 첨가된 종래의 구문(phrase) 구조 분석을 생성한다. 신택스 분석은, 텍스트 입력에서 내용 단어들(content words) 사이의 라벨이 부여된 의존성(labeled dependencies)을 설명하는 데이터 구조인 논리 형식을 얻기 위해 프로세스를 더 겪게 된다.

일반적으로, 논리 형식은 문장 또는 그 부분과 같이 단일한 입력을 나타내는 연결된 논리적 관계의 데이터 구조이다. 최소한, 논리 형식은 하나의 논리적 관계로 구성되고, 구조적 관계(즉, 신택스 및 의미 관계), 구체적으로, 입력 문자열의 중요한 단어들 사이의 아규먼트(argument) 및 수식어구(adjunct) 관계(들)를 묘사한다.

논리 형식은 특정 신택스적 변경(syntactical alternations)을 표준화할(normalize) 수 있고(예를 들어, 능동/수동), 문장 내부의 대용어(anaphora) 및 먼 거리 의존성(long distance dependencies)을 분석할 수 있다. 예를 들어, 도 3 및 도 4는 논리 형식의 요소를 이해하는데 도움이 되기 위해 종래 기술 부분(section)에서의 예로 주어진 능동 및 수동 문장들에 대한 논리 형식 또는 의존 그래프(300 및 400)를 도시한다. 그러나 당해 분야에서 통상의 지식을 갖춘 자는, 컴퓨터 판독 가능 매체에 저장될 경우, 논리 형식은 곧 그래프를 제시하는 것처럼 이해되는 것은 아니라는 것을 이해할 수 있을 것이다. 도 3 및 도 4는 종래 기술 부분에서 설명한 바와 같이 표면 문자열 및 신택스 모델이 캡쳐할 수 없는 중요한 일반화를 도시한다.

의존 그래프가 문자열 기반 n-gram 모델 또는 신택스 트리보다 좋은 언어 모델을 제공할 수 있다는 것을 보기 위해, 이하의 문장을 고려하자.

1. John hit the ball.

2. The balls were hit by Lucy.

표면 문자열 기반 3-gram 모델은 이하의 셈(count)을 생성한다.

이벤트가(볼을 치는 것) 양쪽의 경우에 동일하더라도 이러한 각각의 트라이그램은 오직 한 번만 일어난다.

만약 신택스 트리를 본다면, 다소 상이한 그림을 얻을 수 있다. 구체적으로, 상기의 문장들에 있어서, 이하의 신택스 트리가 얻어진다.

여기서도 알 수 있듯이, 볼을 치는 것은 두 개의 개별 버킷(bucket)(능동태에 대한 규칙의 한 집합 및 수동태에 대한 규칙의 다른 집합)으로 분리되어서, 시스템은 유용한 일반화를 얻지 못한다.

도 3 및 도 4는 논리 형식들(300 및 400)을 도시한다. LF(300 및 400)는 부모 노드들(parent node; 302 및 402), 자식 노드들(children node; 304, 308, 404 및 408) 및 의미 관련 노드들(306, 307, 406 및 407)을 포함한다. 의미 관련 노드들(306 및 406)은 자식 노드들(304, 308, 404 및 408)을 부모 노드들(302 및 402)에 연결하기 위해 동작하고, 부모 및 자식 노드들 사이의 의미 관련을 설명한다.

부모 노드(302 및 402)는 단어 형식들 또는 렘마(lemma)를 포함한다. 예를 들어, 부모 노드(302 및 402)의 렘마는 단어 "hit"이다. 또한, 자식 노드들(304, 308, 404 및 408)도 단어 형식들 또는 렘마를 포함한다. 의미 관련 노드들(306 및 406)은 자식 노드들(304 및 404)이 깊은 주어(subject)임을 도시하고, 의미 관련 노드(307 및 407)는 자식 노드들(308 및 408)이 부모 노드들(302 및 402)의 깊은 목적어들임을 나타낸다. 또한, 부가하면, LF(300 및 400)는 각각의 노드에서의 각각의 렘마에 부착된 바이너리 특성들(또는 "비트")을 포함한다. 예를 들어, 바이너리 특성들은 각각의 LF(300 및 400)의 렘마에 부착되고, 삽화적으로 도시되었다. 바이너리 특성들은 렘마의 신택스 속성(property)을 설명한다. 예를 들어, 노드(302)의 단어 형태는 과거 시제(past tense) 및 주제(proposition)로서 단어 "hit"를 설명하는 비트들을 포함한다.

문자열 및 신택스 트리와 대조적으로, 논리 형식(300 및 400)은 동일한 그래프 구조의 능동태 구조 및 수동태 구조 모두를 포함한다. LF 구조는 트리를 생산하기 위해 디그래프(degraph)될 수 있어서, 어떠한 노드도 두 개의 부모들을 가질 수 없다. 논리 형식(300 및 400)은 대응하는 문장들(또는 문장 부분들)의 계층적 논리 표현이다. 각각의 노드는 노드의 모든 조상들에 의존한다. (타겟) 언어 모델을 만들어 내기 위해서, 로컬 구조는 각각의 자식 노드가 오직 그 부모(또는 n-gram LF 모델에서 n-1 조상)에만 의존한다는 근사(approximation)에 기초한 모델이다.

하나의 예시적 실시예에서, 신택스 분석으로부터 논리 형식을 만드는 특정 코드가 기계 번역 시스템이 작동하는 타겟 언어 및 다양한 소스에 걸쳐 공유된다. 두 개의 언어에서 피상적으로 별개인 구성은 유사 또는 동일한 논리 형식 표현으로 종종 합쳐지기 때문에, 공유된 구조는 상이한 언어로부터의 논리 형식 부분(segment)을 정렬하는 임무를 크게 단순화한다.

기계 번역

도 5는 본 발명의 하나의 실시예에 따른 기계 번역 시스템(500)의 예시적 구조에 대한 블록도이다. 시스템(500)은 구문 분석 구성 요소(parsing component; 504 및 506), 통계적 단어 연관 학습 구성 요소(statistical word association learning component; 508), 논리 형식 정렬 구성 요소(510), 어휘적 지식 기초(lexical knowledge base; LKB) 형성(building) 구성 요소(512), 두 언어로 된 사전(bilingual dictionary; 514), 연관 리스트(520) 및 전송 매핑 데이터베이스(518)를 포함한다. 번역을 런타임하는 동안, 시스템(500)은 구문 분석 구성 요소(522), 검색 구성 요소(524), 디코드 구성 요소(decoding component; 554), 전송 구성 요소(526) 및 생성 구성 요소(528)를 이용한다.

하나의 도시적인 실시예에서, 두 언어로 된 언어 자료(corpus)가 시스템을 학습시키기(train) 위해 사용된다. 두 언어로 된 언어 자료(또는 "바이텍스트(bitext)")는 정렬된 번역 문장들(예를 들어, 스페인어와 같은 다른 소스 또는 타겟 언어로 사람이 생성한 번역과 1 대 1 대응하는 영어와 같은 소스 또는 타겟 언어의 문장)을 포함한다. 트레이닝 동안, 문장들이 정렬된 두 언어로 된 언어 자료로부터 소스 문장들(530; 번역될 문장들) 및 타겟 문장들(532; 소스 문장들의 번역)로 시스템(500)에 제공된다. 구문 분석 구성 요소(504 및 506)는 소스 논리 형식(534) 및 타겟 논리 형식(536)을 생산하기 위해 정렬된 두 언어로 된 언어 자료로부터 소스 문장 및 타겟 문장을 구문 분석한다.

구문 분석하는 동안, 문장들의 단어들은 표준화된 단어 형식 또는 렘마로 변환되고, 통계적 단어 연관 학습 구성 요소(508)에 제공될 수 있다. 단일한 단어 및 다수의 단어 연관(multi-word association) 모두 학습 구성 요소(508)에 의해 각각의 신뢰 가능한 집합이 얻어질 때까지 반복적으로 가정되고, 스코어된다. 통계적 단어 연관 학습 구성 요소(508)는 학습된 단어 번역 쌍들(538)을 출력한다.

단어 쌍들은 연관 리스트(520)에 추가되는데, 이 리스트는 업데이트된 두 언어로 된 사전과 같이 동작한다.

단어 쌍들(538)은 소스 논리 형식(534) 및 타겟 논리 형식(536)과 함께 논리 형식 정렬 구성 요소(510)에 제공된다. 간단하게, 구성 요소(510)는 우선 각각의 소스 및 타겟 논리 형식들(530 및 536)의 노드들 사이의 임시적인 대응을 정한다. 이것은 통계적 단어 연관 학습 구성 요소(508)로부터의 단어 쌍들(538)이 부가될 수 있는 두 언어로 된 어휘 목록(lexicon; 514)(예를 들어, 두 언어로 된 사전)의 번역 쌍들을 사용하여 행해진다. 가능한 대응들을 정한 후, 정렬 구성 요소(510)는 어휘적 및 구조적 고려에 따라 논리 형식 노드들을 정렬하고, 단어 및/또는 논리 형식 전송 매핑(542)을 생성한다.

근본적으로, 정렬 구성 요소(510)는 두 언어로 된 사전 정보(514) 및 단어 쌍들(538)을 이용하는 논리 형식들 사이의 링크를 도출시킨다. 전송 매핑들은 소스 및 타겟 논리 형식(534 및 536)으로 발견되는 빈도에 기초하여 부가적으로 필터링(filtered)되고, 어휘적 지식 기초 형성 구성 요소(512)로 제공된다.

하나의 예에서, 필터링이 부가적이지만, 만약 전송 매핑이 트레이닝 데이터에서 적어도 두 번 이상(기타 다른 원하는 빈도가 필터로 사용될 수 있음) 보이지 않는다면, 전송 매핑 데이터베이스(518)를 만드는데 사용되지 않는다. 출현의 빈도 대신 다른 필터링 기술도 사용될 수 있다는 것을 알아야 한다. 예를 들어, 전송 매핑은 소스 문장의 완전한 구문 분석으로부터 형성되었는지에 기초하여 필터링될 수 있고, 전송 매핑을 생성하는데 사용된 논리 형식이 완전히 정렬되었는지에 기초하여 필터링 될 수도 있다.

구성 요소(512)는 하나의 언어로 된 단어들 및/또는 논리 형식들을 제2 언어로 된 단어들 및/또는 논리 형식에 근본적으로 링크시키는 전송 매핑을 포함하는 전송 매핑 데이터베이스(518)를 만든다. 따라서 전송 매핑 데이터베이스(518)가 생성되고, 시스템(500)은 런타임 번역을 위하여 구성된다(configured).

번역 런타임동안, 번역되어질 소스 텍스트(550)는 구문 분석 구성 요소(522)로 제공된다. 구문 분석 구성 요소(522)는 소스 텍스트(550)를 수신하고, 소스 텍스트 입력에 기초한 소스 논리 형식(552)을 생성한다.

소스 논리 형식(552)은 검색 구성 요소(524)에 제공된다. 검색 구성 요소(524)는 소스 논리 형식(552)의 전부 또는 일부를 커버하는 전송 매핑을 얻기 위해 전송 매핑 데이터베이스(518)에 대한 검색을 시도한다. 다중 매핑(multiple mapping)이 소스 논리 형식(552)의 하나 이상의 노드들에서 발견될 수 있다.

가능한 전송 매핑들의 집합 및 전송 매핑의 가능한 조합들의 집합을 발견한 후, 디코드 구성 요소(554)는 다수의 모델을 사용하는 각각의 전송 매핑들의 조합을 스코어한다. 하나의 실시예 하에서, 개별 전송 매핑들 및 전송 매핑들의 조합들은 이하에 아주 자세하게 설명할 선형 추정(linearly interpolated) 스코어로 스코어된다. 스코어가 생성된 후에, 디코드 구성 요소(554)는 가장 좋은 전송 매핑들의 집합을 선택하고 저장한다.

전송 구성 요소(526)는 디코드 구성 요소(554)로부터 가장 좋은 후보 매핑의 조합을 수신하고, 타겟 번역의 기초를 형성할 타겟 논리 형식(556)을 만든다. 이것은 선택된 전송 매핑들의 노드들을 조합함으로써 행해진다.

검색 구성 요소(524)에 의해 적용 가능한 전송 매핑들이 발견되지 않은 경우, 소스 논리 형식(552)의 노드들 및 그와 관계된 것들은 단순히 타겟 논리 형식(556)으로 복사된다. 디폴트(default)의 단일 단어 번역은 이러한 노드들에 대한 전송 매핑 데이터베이스(518)에서 여전히 발견될 수 있고, 타겟 논리 형식(556)에 삽입된다. 그러나 발견되는 것이 없을 경우, 예시적으로, 번역은 정렬하는 동안 사용된 연관 리스트(520)로부터 얻을 수 있다.

예시적으로, 생성 구성 요소(528)는 타겟 논리 형식(556)으로부터 타겟 텍스트(또는 타겟 문자열)(558)로 매핑하는 규칙 기반(rule-based), 애플리케이션 독립(application-independent) 생성 구성 요소이다. 대안으로 생성 구성 요소(528)는 문장 실현(sentence realization)에 대한 기계 학습 접근 방법을 이용할 수 있다. 예시적으로, 생성 구성 요소(528)는 입력 논리 형식의 소스 언어와 관련된 정보를 갖지 않을 수 있고, 전송 구성 요소(527)에 의해 전해진 정보와 배타적으로 동작한다. 또한, 예시적으로, 생성 구성 요소(528)는 타겟 텍스트(558)를 생산하기 위해 한 언어로 된(예를 들어, 타겟 언어) 사전과 관련된 상기 정보를 사용한다. 따라서 하나의 일반적(generic) 생성 구성 요소(528)면 각각의 언어에 대해 충분하다.

논리 형식들의 통계적 기계 번역

이하의 논의와 관련하여, 당해 분야에서 통상의 지식을 갖춘 자는 의존 그래프, 논리 형식, 의미 구조, 의미 관련(semantic relationship) 및 의미 표현(semantic representations) 모두가, 런타임동안 제공된 입력 논리 형식과 관련되고 그것을 설명한다는 것을 인식할 수 있다. 부가하면, 당해 분야에서 통상의 지식을 갖춘 자는 전송 매핑들 또는 매핑들이 트레이닝 동안 형성된 그러한 매핑들을 언급한다는 것을 인식할 수 있다.

수학식 2를 회상하면서, 이하의 식은 상위 레벨에서 본 발명의 실시예이다.

T`는 타겟 언어의 논리 형식이고, P(S│T`)는 주어진 타겟 언어 논리적 형식 T`에 대하여 소스 논리 형식 S의 확률이며, P(T`)는 타겟 언어 논리 형식 T`의 확률로서, μ<sub>T</sub>가 타겟 언어 모델인 경우에 또한 P<sub>μT</sub>(T`)로 쓰여진다. 상기 수학식은 수학식(4)와 동일하다.

본 발명의 실시예는 채널 모델 또는 번역 모델 P_μc(S,T`), 퍼틸리티(fertility) 모델 P<sub>μF</sub>(S,T`), 매핑 사이즈 정보 소스(mapping size information source) Score_μS(S,T`) 및 바이너리 특성 부합(또는 "랭크(rank)") 정보 소스(binary features matching information source) Score<sub>μB</sub>(S,T`)인 몇 가지 지식 소스를 포함하여 P(S│T`)를 근사한다. 이러한 지식 소스를 포함하면, P(S│T`)는 수학식(5)으로 근사된다.

따라서,

각각의 스코어 또는 로그 확률의 상대적인 기여는 인수(factor)(λ_T, λ_C, λ_F, λ_S 및 λ_B)로 가중치가 부여되고, 결과적인 선형 추정 근사(resulting linear interpolated approximation)는 다음과 같다.

실시에 있어서, 이 실시예는 전체 소스 논리 형식 및 타겟 언어 논리 형식 모두를 한번에 스코어 계산하지 않는다. 오히려, 검색(상기 수학식에서 "argmax"로 표현됨)은 한번에 하나의 번역 매핑으로서, 타겟 언어 논리 형식을 만든다. 그렇게 함으로써, 각각의 매핑에 대한 스코어를 채택한다. 전송 매핑 m 에 대해 전체 선형적으로 삽입된 스코어는 이하와 같이 제시된다.

완전 근사(full approximation)에 있어서, 그리고, 상술한 바와 같이, 각각의 정보 소스 스코어 또는 확률은 인수에 의해 가중치가 부여된다. 이러한 인수들(λ_T, λ_C, λ_F, λ_S 및 λ_B) 또는 가중치들은 파월(powell)의 알고리즘을 사용하여 시스템의 출력에 BLEU 스코어를 최대화하기 위해 처리된다. 파월의 알고리즘은 당해 기술 분야에서 공지된 것이다. 이 알고리즘의 예는 파월의 "An Efficient Method of Finding the Minimum of a Function of Several Variables without Calculating Derivates."(Computer Journal, 7:155-162)에서 설명된다. 또한, BLEU 스코어 역시 당해 기술 분야에서 공지된 것이고, 파피네니, 로우코수, 와드 및 추의 "Blue: a method for automatic evaluation of machine translation." 2001, IBM 기술 리포트 RC22176(WO109-022), IBM 리서치 부, 토마스 J. 왓슨 리서치 센터에서 설명된다.

모델들

하나의 실시예 하에서, 타겟 언어 모델은, 주어진 일련의 n-1개의 선행하는 노드들 및 관계에 대하여 타겟 의존 그래프에서의 노드 확률을 제공하는 n-gram 모델이다. 도 6은 전송 매핑 데이터베이스(518)의 타겟 측에서 발견될 수 있는 예시적 타겟 의존 그래프(600)를 도시한다. 도 6에서 노드들(A, B, C 및 D)은 단어 형식을 포함한다. 노드들(B, C 및 D)은 자식 노드들이고, 노드(A)는 부모 노드 또는 루트 노드(root node)이다. 노드들(R1 및 R2)은 의미 관련 노드들이다.

이 n-gram 모델을 사용하여, 주어진 타겟 언어 모델에 대한 전체 타겟 의존 그래프τ(600)는 각각의 노드들의 n-gram 확률들의 곱과 동등하다. 따라서 주어진 타겟 언어 모델에 대한 타겟 의존 그래프(600)의 확률은 이하의 식에 의해 제시된다.

i는 논리 형식τ의 모든 노드들에 대한 인덱스이다. 각각의 노드(C_i)에 있어서, 타겟 언어 모델에 따른 스코어는 주어진 n-1의 가장 가까운 조상들 C_i부터 C_i-(n-1)까지에 대한 C_i의 확률이다. 예를 들어, 이런 종류의 트라이그램 모델에 따른 타겟 논리 형식(600)의 확률은 이하와 같다.

이 트라이그램 모델에서, 의미 관련(R1 및 R2)은 제1 분류 개체(first-class entity)로 취급되어, 타겟 모델은 단순화되고, 렘마 및 의미 관련에 대한 별개의 모델은 필요가 없게 된다. 타겟 모델은 자주 발생하지 않는 n-gram을 제거하여 다듬어지고, 당해 기술 분야에서 공지되고, 네이 에센 및 크네서의 논문 "On structuring probabilistic dependences in stochastic language modeling." 1994. (Computer Speech and Language, 8:1-38)에서 설명된 추정된 절대적 디스카운팅(interpolated absolute discounting)을 이용하여 매끄러워진다.

채널 모델은 주어진 타겟 논리 형식 P(S│T)에 대하여 소스 논리 형식의 확률을 예측한다. 하나의 실시예에서, 해당 소스 논리 형식 S 및 타겟 논리 형식 T에 대한 전송 매핑 커버 M을 S에서 T로의 전송 매핑 집합으로 정의(M:S→T로 표시)한다. 주어진 타겟 논리 형식 T에 대하여 소스 논리 형식 S의 확률은 다음과 같이 추정된다.

i는 (잠재적으로) 모든 전송 매핑 커버 M_i:S→T의 범위이다.

수학식(12)은 채널 모델μ_C에 따른 매핑 m의 확률을 정의한다. 표현 count(m_S, m_T)는 매핑 m의 소스 측 상의 구조가 트레이닝 데이터 집합 내에서 매핑 m의 타겟 측 상의 구조로 매핑된 횟수이고, count(m_T)는 매핑 m의 타겟 측 상의 구조가 트레이닝 데이터 내에서 임의 매핑에서 타겟 측으로 발견된 횟수이다.

바꾸어 말하면, 전송 매핑 m의 채널 모델μ_C에 따른 확률은 전송 매핑의 소스 측이 (논리 형식 바이텍스트(bitext)에서) 전송 매핑의 타겟 측에 몇 번을 마주쳤는지(encountered)인 count(m_S, m_T)를 그 전송 매핑의 타겟 측을 몇 번 마주쳤는지인 count(m_T)로 나누어 추정된다.

또한, 채널 모델은 중첩 전송 매핑(overlapping transfer mappings)을 사용한다. 따라서 수학식(12)에서 계산된 확률은 표준화되지 않은(unnormalized) 확률이다. 표준화되지 않은 확률은 표준화될 수 있어서 채널 모델은 다른 매핑들 보다 더 많이 중첩되는 특정 매핑들을 선호하지 않는다.

도 7은 입력 LF(700)를 도시하고, 도 8은 전송 매핑 데이터베이스(518)에서 발견된 전송 매핑(800)을 도시한다. 전송 매핑(800)은 매핑들(802, 803, 804, 806 및 808)을 포함한다. 도시의 편의를 위해서 오직 전송 매핑들의 렘마에 대한 노드들만 현 애플리케이션의 도면에 도시하고, 의미 관련 노드들은 도시하지 않는다. 전송 매핑들은 의미 관련에 대한 추가적인 노드들을 포함한다는 것을 알아야 한다. 그러나 이러한 노드들이 동일한 방식으로 본 발명 하에서 렘마에 대한 노드들과 같이 취급되기 때문에, 도면 및 이하의 논의는 렘마 노드들에 대해서만 논의한다.

매핑(800)은 소스 LF(700)의 모든 노드들을 커버하기 위한 수많은 상이한 방법으로 조합될 수 있다. 예를 들어, 매핑(802)은 매핑(808)과 조합될 수 있고, 매핑(803)은 매핑(806)과 조합될 수 있으며, 매핑들(804, 806 및 808)은 서로 조합될 수 있다. 이러한 각각의 조합들은 소스 LF(700)의 각각의 노드가 단일한 전송 매핑에 의해서만 커버되기 때문에 중첩되지 않는다. 그러나 소스 LF(700)의 모두를 커버하기 위해 매핑(800)을 조합하는 다른 방법은 매핑(802)을 매핑(803)과 조합하는 것이다. 이것은 소스 노드(A)가 매핑(802) 및 매핑(803) 모두에 의해 커버되기 때문에 중첩하는 매핑을 형성한다.

채널 모델이 중첩하는 매핑들을 선호하는 것을 방지하기 위해, 채널 모델은 표준화 된다. 주어진 채널 모델 μ_C에 대한 매핑 m의 표준화된 확률 은 이하와 같이 계산된다.

"new"는 입력 그래프의 이전에 커버되지 않은 구성 요소(constituent) 또는 노드의 수이고, "total"은 소스 측의 전송 매핑들의 전체 구성 요소(constituent)의 수이며, Pμ_C(m)은 이전에 정의된 바와 같이 채널 모델에 따른 전송 매핑의 표준화되지 않은 확률이다. 따라서 수학식(13)은 채널 모델에 따른 전송 매핑의 표준화된 확률이 설명한 것과 같이 채널 모델에 따른 전송 매핑의 표준화되지 않은 확률과 동일하다는 것을 설명한다.

이전에 논의한 바와 같이, 몇몇 예에 있어서, 입력 LF의 노드는 트레이닝 데이터에서 발견되지 않는데, 왜냐하면 구문 분석될 수 없거나, 단순히 나타나지 않은 것이거나 또는 그 빈도가 미리 정해진 문턱(threshold)(일반적으로 하나) 이하이어서 전송 매핑 데이터베이스(518)로부터 필터링되기 때문이다. 이 경우, 사전으로부터의 단일 단어 번역을 사용하여 형성된 디폴트 노드가 삽입된다. 이런 디폴트 매핑에 대한 확률은 두 언어로 된 텍스트 상에서 학습된 IBM Model 1을 사용하여 결정될 수 있다. 이 확률은 다른 채널 확률들과 상이한 방식으로 얻어지기 때문에, 디폴트 매핑 확률은 다른 채널 확률들과 조합되기 전에, 가중치 (λ_L)에 의해 조정된다. 부가하면, 만약 디폴트 매핑에 대한 어떠한 확률도 결정되지 않으면, 디폴트 (λ_A)가 사용된다. 번역 시스템에서 사용되는 나머지 가중치와 동일하게, 가중치(λ_L 및 λ_A)는 트레이닝 문자의 집합에 대한 BLEU 스코어를 최대화하기 위해 파월의 알고리즘을 사용하여 학습된다. 이러한 파라미터들은 도 8에서 도시된 바와 같이 전송 매핑에 대한 최종 스코어를 계산함에 있어서 채널 모델과 연관된 가중치(λ_C)와는 별개임을 알아야 한다.

채널 모델은 타겟 언어 모델과 상이하게 동작한다. 구체적으로, 채널 모델은 번역의 정확성(accuracy)을 증진시키지만, 타겟 언어 모델은 소스 언어에 관련없이 타겟 언어의 유창함(fluency)을 증진시킨다.

타겟 언어 모델은 작은 그래프를 큰 것보다 선호하기 때문에 신뢰성(liability)이 문제된다. 그 결과, 타겟 언어 모델은 소스 및 타겟 구조의 노드의 동일한 수를 유지거나 또는 타겟 구조에 노드를 추가하는 매핑에 대한 타겟 구조의 노드를 지우는 매핑을 선호한다. 예를 들어, 도 9 및 도 10은 트레이닝 데이터베이스(518)가 전송 매핑(900 및 1000)을 포함한다는 것을 도시한다. 전송 매핑(900)은 소스 측에서보다 타겟 측에서 하나 적은 노드가 있다는 것을 도시한다. 전송 매핑(1000)은 매핑의 소스 측 및 타겟 측에서의 노드들이 동일한 수가 있다는 것을 도시한다. 타겟 언어 모델은 매핑(1000)보다 매핑(900)을 더 높게 스코어하는데, 이것은 매핑(1000)에서 생긴 부분(fragment)에서보다 매핑(900)에서 생긴 타겟 LF 부분에 대한 결과물에서의 확률이 더 작기 때문이다.

퍼틸리티 모델은 트레이닝 데이터의 매핑에서 노드들이 삭제된 횟수에 기초하여 스코어를 제공함으로써 이 문제를 극복한다. 만약 노드들이 트레이닝 데이터에서 거의 삭제되지 않는다면, 퍼틸리티 모델은 삭제된 노드가 없는 매핑에 대해 더 높은 스코어를 부여한다.

퍼틸리티 모델은, 트레이닝 데이터를 검토하고, 전송 매핑의 소스 측에서 얼마나 많은 대응 노드들이 얼마나 있는지를, 전송 매핑의 타겟 측에서의 노드들 각각에 대해서 셈하는 것에 의해 계산된다. 부족한 데이터의 문제를 피하기 위해서, 렘마에 대한 셈은 음성(speech) 부분으로 서로 그룹화되고, 의미 관련에 대한 셈(음성 부분들의 수와 대략적으로 동등한 수)이 별도로 유지된다. 그러면 이러한 빈도들은 삭제(deletion)가 발생하는 확률을 추정하는데 사용된다.

음성 또는 의미 관련 라벨 x의 각각의 부분에 대해서, 퍼틸리티 테이블의 엔트리(entry)가 이하와 같이 제시된다.

바꾸어 말하면, 구성 요소(constituent) x에 대한 퍼틸리티 테이블 엔트리는, x가 타겟 구조 및 소스 구조 모두에서 마주친 횟수와 구성 요소(constituent) x가 소스 구조에서 마주친 횟수의 비율로 계산하여 얻어진다(populated). 그러므로 퍼틸리티 모델μ_F에 따른 전송 매핑 m의 확률은 이하에 의해 계산된다.

여기서,

이다.

바꾸어 말하면, 만약 타겟의 노드가 소스의 노드에 대응한다면, f(c)는 퍼틸리티 테이블 엔트리 F[x]이다. 그렇지 않으면 f(c)는 1-F[x]이다.

다음 정보 소스는 매핑 사이즈 스코어로, 이는 전송 매핑의 소스 측에서의 노드들의 수를 고려한다. 이런 정보 소스는 이하의 수학식에 의해 계산되는 스코어를 할당한다(assign).

본질적으로, 사이즈 스코어는 더 많은 콘텍스트 정보를 갖는 매핑들이 적은 콘텍스트 정보를 갖는 매핑들보다 더 좋을 수 있다는 가정 하에서 더 큰 매핑들을 선호한다. 도 9 및 도 10과 관련하여, 전송 매핑(900)은 소스 측에 두 개의 노드가 있기 때문에 2의 스코어를 얻는다. 또한, 전송 매핑(1000)은 소스 측에서 두 개의 노드가 있기 때문에 2의 스코어를 얻는다.

바이너리 특성(또는 비트들) 정보 소스는 입력 의존 그래프 및 전달 매핑의 소스 측 사이에 부합하는 바이너리 특성(비트들)의 수를 고려한다. 바이너리 특성 소스는 전송 매핑의 소스 측의 비트들에 부합하는 소스 의존 그래프의 입력 비트들의 합인 랭크 스코어(rank score)를 제공한다. 도 11은 입력 LF(1100)를 도시하고, 도 12는 전송 매핑 데이터베이스(518)에 저장된 전송 매핑(1200)을 도시한다. 입력 LF(1100)의 노드(A)는 노드(A)의 렘마가 수동(passive) 비트 및 단수(singular)의 비트를 갖는다는 것을 명기한다. 전송 매핑(1200)의 소스 측의 노드(A)는 노드(A)의 렘마가 단수의 비트를 갖는다는 것을 명기한다. 그러므로 전송 매핑(1200)의 랭크 스코어는 1이고, 이는 입력 LF(1100)의 노드(A) 및 매핑(1200)의 소스 측의 노드(A) 모두가 부합하는 단수의 비트를 가지고 있기 때문이다.

도 13은 도 5의 디코드 구성 요소(554)에 의해 구현된 것과 같은 디코드 알고리즘을 도시하는 흐름도(1300)이다. 디코드 구성 요소(554)는 본 발명의 실시예에 따라 전송 매핑의 집합들을 선택하고 스코어한다. 디코드 구성 요소(554)는 검색 구성 요소(524)에 의해 발견된 전송 매핑의 집합으로부터 가장 적절한 매핑들의 집합을 발견하기 위해 기억(memorization)을 사용하여 하향식(top-down)으로 검색한다. 도 14는 본 발명의 예에 따른 소스 LF(1400)를 도시한다. 도 15 내지 도 21은 소스 LF(1400)에 관련하여 검색 구성 요소(524)에 의해 발견된 전송 매핑의 예시적 집합을 도시한다.

도 5의 디코드 구성 요소(554)는 블록(1302)에 도시한 바와 같이 소스 LF(1400)의 최상 노드를 선택하여 시작한다. 도 14에서, 최상 노드는 노드(A)이다. 노드(A)를 선택한 후, 디코드 구성 요소(554)는 블록(1304)으로 가고, 이 콘텍스트의 이 노드에 대한 가장 좋은 매핑이 이전에 식별되었는지를 판단한다. 이 예에서, 노드(A)에 대해 어떠한 매핑도 스코어된 적이 없다.

그러면 프로세스는 단계(1306)에서 계속되고, 본 단계에서 선택된 노드를 커버하는 소스 측을 갖는다고 검색 구성 요소(524)에 의해 발견된 매핑들의 집합으로부터 전송 매핑이 선택된다. 예를 들어, 디코드 구성 요소(554)는 도 15의 전송 매핑(1500)을 선택한다.

블록(1308)에서, 디코드 구성 요소(554)는 선택된 매핑에 의해 커버되지 않고, 선택된 매핑에서부터 직접 확장된 노드들이 소스 LF(1400)에 있는지를 판단한다. 상기 예에서, 매핑(1500)은 오직 노드(A 및 B)만 커버한다. 그것으로서, 자식 노드(C)는 선택된 매핑에 의해 커버되지 않지만, 선택된 매핑에 의해 커버되는 노드(A)에서부터 직접 확장된다. 만약 커버되지 않는 자식 노드가 단계(1308)에 있다면, 프로세스는 블록(1310)에서 계속된다.

블록(1310)에서, 디코드 구성 요소(554)는 자식 노드(C)를 선택하고 블록(1304)으로 돌아간다. 블록(1304)에서 디코드 구성 요소(554)는 가장 좋은 매핑이 선택된 콘텍스트의 선택된 노드에 대해 이미 식별되었는지를 판단한다. 구체적으로, 3-gram 타겟 모델에서, "선택된 콘텍스트"는 노드(C)의 n-1 타겟 측 조상들(이 경우, <PRE_ROOT, PRE_ROOT, A`>)로 구성된다. 노드(C)에 관해서, 가장 좋은 매핑이 식별되지 않아서, 프로세스는 디코드 구성 요소(554)가 자식 노드(C)를 커버하는 전송 매핑의 집합으로부터의 전송 매핑을 선택하는 단계(1306)에서 계속된다. 예를 들어, 디코드 구성 요소(554)는 도 16에 도시된 전송 매핑(1600)을 선택할 수 있다. 단계(1306) 이후에, 디코드 구성 요소(554)는 블록(1308)으로 가고, 매핑에 의해서 커버되는 노드들로부터 확장된 커버되지 않은 자식 노드들이 있는지 여부를 판단한다. 상기 예에서, 노드들(E 및 F)은 매핑(1600)에 의해 커버된 노드들로부터 확장된 커버되지 않은 자식 노드들이다. 커버되지 않은 자식 노드들을 발견하였으면, 디코드 구성 요소(554)는 블록(1310)으로 간다.

블록(1310)에서, 디코드 구성 요소(554)는 커버되지 않은 노드들, 예를 들어, 노드(E), 중의 하나를 선택하고, 블록(1304)으로 돌아간다. 블록(1304)에서, 디코드 구성 요소(554)는 현재 진행중인(active) 타겟 콘텍스트(이 경우, <PRE_ROOT, A`, C`>)에서 노드(E)에 대한 가장 좋은 매핑이 판단되지 않았다고 판단한다. 그러면 프로세스는 블록(1306)에서 계속되고, 디코드 구성 요소(554)는 노드(E)를 커버하는 전송 매핑의 집합으로부터 전송 매핑을 선택한다. 예를 들어, 디코드 구성 요소(554)는 도 17에 도시된 전송 매핑(1700)을 선택한다. 그러면 디코드 구성 요소(554)는 블록(1308)으로 가고, 전송 매핑이 커버되지 않은 자식 노드들을 남겼는지 여부를 판단한다.

소스 LF(1400)에 따라, 노드(E)는 자식들이 없다. 따라서 디코드 구성 요소(554)는 블록(1312)으로 가서 선택된 전송 매핑에 대한 스코어를 계산한다. 이 스코어는 상술한 모든 모델들을 채택하여 상술한 바와 같이 수학식(8)을 사용하여 계산된다. 도 13의 하향식 접근 방법을 채택한 하나의 이유는 (스코어되는 매핑들에서) 노드들의 콘텍스트가 알려져서 (콘텍스트를 요구하는) 타겟 모델이 타겟 모델 스코어를 계산하기 위해 사용될 수 있다는 것을 보장하기 위해서임을 알아야 한다.

매핑을 스코어한 후, 디코드 구성 요소(554)는 블록(1314)으로 가고, 선택된 노드들을 커버하는 전송 매핑이 더 있는지를 판단한다. 이 예에서, 도 18은 선택된 노드(E)에 대한 다른 전송 매핑(1800)을 도시한다. 만약, 다른 전송 매핑이 있다면, 디코드 구성 요소(554)는 다시 블록(1306)으로 돌아가서, 추가적인 전송 매핑을 선택한다. 예를 들어, 매핑(1800)이 선택될 수 있다. 이 예에서, 매핑(1800)은 커버되지 않은 자식 노드들을 갖지 않는다. 따라서 디코드 구성 요소(554)는 블록(1308)을 지나 블록(1312)으로 가고, 여기서 디코드 구성 요소(554)는 수학식(3)을 사용하여 전송 매핑(1800)의 스코어를 계산한다.

그러면, 디코드 구성 요소(554)는 블록(1314)으로 가서 선택된 노드에 대한 전송 매핑이 더 있는지를 판단한다. 이 예에서, 도 19는 노드(E)를 커버하는 전송 매핑(1900)을 도시한다. 다시, 디코드 구성 요소는 블록(1306)으로 돌아간다. 이 예에서, 전송 매핑(1900)은 커버되지 않은 자식 노드들을 갖지 않는다. 따라서 디코드 구성요소(554)는 수학식(3)을 사용하여 전송 매핑(1900)에 대한 스코어를 계산한다. 스코어가 계산 된 후, 디코드 구성 요소(554)는 블록(1314)으로 간다.

디코드 구성 요소(554)가 단계(1314)에 더 이상의 매핑들이 없다고 판단하면, 프로세스는 단계(1316)에서 계속되고, 여기서 선택된 노드를 커버하는 전송 매핑으로부터 가장 높은 스코어의 전송 매핑을 비교하고, 선택한다. 상기 예에서, 매핑들(1700, 1800, 1900)에 대한 스코어가 비교되고, 가장 높은 스코어의 매핑이 선택된다. 이 예에서, 가장 높은 스코어의 전송 매핑은 전송 매핑(1700)이라고 가정한다. 디코드 구성 요소(554)는 매핑의 헤드(head)에서의 노드, 가장 높은 스코어의 매핑의 콘텍스트(소스 LF에서 매핑이 전개되는 노드), 가장 높은 스코어의 매핑에 대한 스코어 및 가장 높은 스코어의 매핑에 대한 각각의 개별 모델 확률 또는 정보 소스 스코어를 저장한다. 따라서 선택된 매핑에 대한 타겟 모델 확률, 채널 모델 확률, 퍼틸리티 모델 확률, 사이즈 스코어 및 랭크 스코어가 모두 저장된다. 비록 각각의 모델에 대한 각각의 확률 또는 스코어가 저장되지만, 당해 분야에서 통상의 지식을 갖춘 자는 수학식(8)에서 결정된 스코어를 저장하는 것이 가장 중요하다는 것을 인식하여야 한다.

선택된 매핑에 대한 스코어가 저장된 후, 디코드 구성 요소(554)는 블록(1318)으로 가고, 여기서 선택된 노드 위의 레벨들이 존재하는지를 판단한다. 상기 예에서, 노드(C)는 노드(E)의 위에 있다. 현재 선택된 노드 위에 노드들의 다른 레벨이 존재하면, 디코드 구성 요소(554)는, 블록(1320)에서 그 노드가 고려되었던 바로 전의 매핑으로 돌아간다. 상기 예에서, 이것은 도 16의 매핑(1600)으로 돌아가는 것을 포함한다.

블록(1322)에서, 디코드 구성 요소(554)는 이 매핑이 탐색되지 않은 다른 커버되지 않은 자식 노드들을 갖는지 여부를 판단한다. 탐색하여야 할 추가적인 커버되지 않은 자식 노드들이 있다면, 디코드 구성 요소(554)는 블록(1310)에서 계속되고, 여기서 디코드 구성 요소(554)는 커버되지 않은 자식 노드를 선택한다. 상기 예에서, 이것은 자식 노드(F)를 선택하는 것을 포함한다. 그러면 디코드 구성 요소(554)는 블록(1304)으로 가서 주어진 그 콘텍스트에 대해서 가장 좋은 매핑이 이 노드에 대해 식별되었는지 판단한다. 가장 좋은 매핑이라고 판단되지 않으면, 디코드 구성 요소(554)는 단계(1306)에서 선택된 자식 노드를 커버하는 전송 매핑(예를 들어, 도 20의 매핑(2000))을 선택한다. 이 예에서, 전송 매핑(2000)은 이전에 스코어된 적이 없다. 블록(1308)에서, 디코드 구성 요소(554)는 노드(F)가 커버되지 않은 자식 노드가 없는지를 판단한다. 따라서 디코드 구성 요소(554)는 블록(1312)으로 가고, 수학식(3)을 사용하여 노드(F)에 대한 스코어를 계산한다.

디코드 구성 요소(554)는 블록(1314)으로 가서 노드(F)가 전송 매핑이 더 있는지를 판단한다. 이 예에서, 노드(F)를 커버하는 다른 전송 매핑이 없다. 따라서 디코드 구성 요소(554)는 전송 매핑(2000)에 대한 스코어를 저장하고, 매핑(2000)에 대한 각각의 개별 모델 확률 또는 정보 소스 스코어, 전송 매핑(2000)이 평가되는 타겟 측 콘텍스트의 n-a 노드들, 전송 매핑(2000)의 헤드 노드와 대응하는 입력 노드 및 전송 매핑(2000)에 대한 전체 스코어를 저장한다.

이 예에서, 노드(F) 위에 소스 LF(1400)의 더 많은 레벨이 존재한다. 그래서 디코드 구성 요소(554)는 블록(1320)으로 가고, 고려 하에 있는 노드(C)에 대한 바로 전의 매핑으로 돌아간다. 블록(1322)에서 디코드 구성 요소(554)는 노드(C)에 대한 선택된 매핑이 더 이상의 커버되지 않은 자식들이 없는지를 판단한다. 그래서 디코드 구성 요소(554)는 블록(1312)으로 가고 전송 매핑(1600)에 대한 전체 스코어를 계산한다.

만약 선택된 매핑이 커버되지 않은 자식들을 갖는다면, 매핑에 대한 스코어는 커버되지 않은 자식 노드들에 대한 가장 높은 스코어의 매핑들 스코어와 선택된 매핑의 스코어를 조합하여 판단된다. 예를 들어, 매핑(1700 및 2000)에 대한 스코어는 매핑(1600)에 대한 스코어와 조합되어 소스 LF의 노드(C) 밑의 전체 매핑들에 대한 총합 스코어를 제공한다.

하나의 실시예 하에서, 매핑 스코어의 각각의 구성 요소는 별개로 조합된다. 따라서 매핑(1600)의 전체 타겟 모델 확률은 다음과 같다.

P_μT(m₁₇₀₀)는 매핑(1700)에 대한 타겟 모델 확률이고, P_μT(m₂₀₀₀)은 매핑(2000)에 대한 타겟 모델 확률이며, logP_μT(m₁₆₀₀)은 매핑(16000)에 대한 타겟 모델 확률이다.

유사하게, 매핑(1600)에 대한 전체 채널 모델 확률은 다음과 같다.

매핑(1600)의 전체 퍼틸리티 모델 확률은 다음과 같다.

매핑(1600)에 대한 전체 매핑 사이즈 스코어는 자식 매핑 사이즈 스코어들의 평균이고, 매핑(1600)만에 대한 매핑 사이즈 스코어는 다음과 같다.

전체 매핑 사이즈 스코어와 동일하게, 매핑(1600)의 전체 랭크 스코어는 자식 랭크 스코어의 평균이고, 매핑(1600)만에 대한 랭크 스코어는 다음과 같다.

각각의 구성 요소에 대한 전체 스코어가 결정되면, 그 전체 스코어는 상기 수학식(8)을 사용하여 선택된 매핑에 대한 단일한 스코어로 조합된다.

그러면 디코드 구성 요소(554)는 블록(1314)으로 가고, 노드(C)에 대해서 더 많은 전송 매핑이 존재하는지를 판단한다. 이 예에서, 노드(C)에 대해 다른 전송 매핑이 더 없고, 디코드 구성 요소(554)는 전송 매핑(1600)을 가장 높은 스코어의 매핑을 갖는 것으로 선택하고, 매핑(1600)에 대한 전체 스코어, 매핑(1600)의 콘텍스트(노드(A)), 매핑(1600)의 헤드 노드(노드(C)) 및 매핑(1600)에 대한 개별적인 전체 구성 요소 스코어를 저장한다.

블록(1318)에서, 디코드 구성 요소(554)는 소스 LF(1400)의 노드(C) 위의 더 많은 레벨이 존재하는지를 판단한다. 이 예에서, 노드(A)는 노드(C) 위에 있다. 따라서 디코드 구성 요소(554)는 블록(1320)에서 도시된 바와 같이, 매핑의 한 단계 위의 레벨로 복귀한다. 상기 예에서, 이것은 도 15의 매핑(1500)으로 돌아가는 것을 포함한다. 블록(1322)에서, 디코드 구성 요소(554)는 선택된 매핑이, 탐색되어야 할 필요가 있는 커버되지 않은 기타 다른 자식 노드들을 갖는지를 판단한다. 이 예에서, 커버되지 않은 다른 자식 노드들이 없어서, 디코드 구성 요소(554)는 블록(1312)으로 가고, 전송 매핑(1500)에 대한 전체 스코어를 계산한다. 매핑(1600)에서와 동일하게, 전송 매핑(1500)에 대한 전체 스코어는 매핑(1600)에 대한 스코어와 매핑(1500)에 대한 스코어를 조합하여 형성된다.

그러면 디코드 구성 요소(554)는 블록(1314)으로 가고 노드(A)에 대한 전송 매핑이 더 존재하는지를 판단한다. 또한, 이 예에서, 전송 매핑(2100)은 노드(A)를 커버한다. 그 결과, 프로세스는 단계(1306)로 돌아가서 전송 매핑(2100)을 선택한다.

단계(1308)에서, 프로세스는 매핑(2100)이 커버되지 않은 자식 노드를 갖는지를 판단한다. 구체적으로, 노드(E 및 F)는 매핑(2100)에 의해 커버되지 않는다. 단계(1310)에서, 노드(E)가 선택되고, 프로세스는 단계(1304)로 돌아가서, <PRE_ROOT, A`, C`>되는 주어진 매핑(2100)에 대한 현재 콘텍스트의 노드(E)에 대해서 가장 좋은 매핑이 선택되었는지를 판단한다. 그러한 가장 좋은 매핑이 선택된다(매핑(1700)). 그러면 이 가장 좋은 매핑 및 그 스코어가 선택되고, 프로세스는 단계(1320)의 매핑(2100)으로 돌아간다.

그러면 프로세스는 고려하여야 할 더 많은 커버되지 않은 자식 노드들이 있는지를 판단한다. 매핑(2100)에 대해서, 자식 노드(F)는 고려되지 않았고, 단계(1310)에서 선택되었다. 단계(1304)에서, 노드(D)의 콘텍스트의 노드(F)에 대한 가장 좋은 매핑(매핑(2000))이 결정되었다고 판단되었다. 그러면 이 가장 좋은 매핑이 선택되고, 프로세스는 단계(1320)에서 매핑(2100)으로 돌아간다.

단계(1322)로 돌아가면, 더 이상 고려하여야 할 커버되지 않은 자식 노드들이 없고, 매핑(2100)에 대한 스코어가 매핑(1700 및 2000)에 대한 저장된 스코어 및 매핑(2100)에 대한 개별 매핑 스코어들을 사용하여 계산된다. 상기와 같이, 매핑 스코어의 개별 구성 요소들은 개별적으로 조합된다.

단계(1314)에서, 다른 전송 매핑이 존재하지 않으면, 디코드 구성 요소(554)는 블록(1316)으로 가고, 전송 매핑(1500)에 의해 시작된 전송 매핑 구조 및 전송 매핑(2100)에 의해 시작된 전송 매핑 구조 사이에서, 이 두 개의 매핑 구조에 대한 전체 스코어에 기초하여 선택을 행한다. 디코드 구성 요소(554)는 가장 높은 스코어의 전송 매핑 구조에 대한 전체 스코어를 저장하고, 블록(1318)으로 간다. 블록(1318)에서, 디코드 구성 요소는 노드(A) 위에 더 많은 레벨이 존재하는지를 판단한다. 이 예에서, 노드(A)는 소스 LF(1400)의 최상 노드이어서, 디코드 구성 요소(554)는 디코드를 끝내고, 노드(A)에 대해서 판단된 가장 높은 스코어의 전송 매핑 구조를 반환한다.

도 15 내지 도 21에서 도시된 가장 높은 스코어의 전송 매핑에 기초하여, 전송 구성 요소(526)는 타겟 LF를 만들 수 있다. 예를 들어, 만약 전송 매핑(1500, 1600, 1700 및 1900)이 가장 높은 스코어의 전송 매핑들로 선택되어져서, 타겟 번역의 가장 높은 확률을 갖는다면, 그것들은 타겟 LF를 형성하기 위해 조합된다.

통계적 모델들 및 다른 스코어 기술들과 같은 정보 소스들은 의미 구조에 대한 가장 좋은 번역을 판단하기 위해 본 발명에서 채용되었다. 입력 의미 구조는 (하나의 실시예에서) 전송 매핑들의 집합에 대해서 그리디 검색 알고리즘을 사용하여 출력 의미 구조를 생성하기 위해서 채용되었다. 그러나 그리디 검색 알고리즘은 전송 매핑들의 모든 가능한 조합들을 테스트하지 않고, 입력 의미 구조를 완전히 커버하는 전송 매핑의 첫 번째 집합을 단순히 선택한다. 통계적 모델들은 주어진 입력 문자열에 대하여 가장 유사한 출력을 예측하기 위해서 사용되었다. 그러나 문자열 기반의 시스템에서 사용된 통계적 모델들은 하나의 요소(element)가 다른 인접하거나 또는 거의 인접한 요소에 기초하여 예측될 수 있다고 가정한다. 따라서 본 발명은 통계적 모델을 사용하여 의미 구조에 대한 가장 좋은 번역을 예측한다.

비록 본 발명에서 의미 구조에 적용된 것과 같이 타겟 언어 모델이 출력 단어 문자열(output word string)을 만드는데 사용될 수 있지만, 의미 구조에 적용된 것과 같이 타겟 언어 모델은 다른 언어 프로그램에서 사용될 수도 있다. 예를 들어, 다른 시스템들은 음성 인식, 광문자인식, 필체 인식, 정보 추출(information extraction) 및 문법 검사 등을 포함한다.

비록 본 발명이 특정 실시예와 관련하여 설명되었지만, 당해 분야에서 통상의 지식을 갖춘 자는 본 발명의 정신과 범위에서 벗어나지 않고, 형태나 세부 사항에 변경을 가할 수 있음을 인식할 것이다.

본 발명은 출력 의미 구조(output semantic structure)를 생산하기 위해 입력 의미 구조(input semantic structure)를 디코드하는 방법을 포함한다. 이 기술은 입력 의미 구조의 부분에 대한 전송 매핑들(transfer mappings)의 집합을 채용한다. 스코어는 통계적 모델을 사용하는 전송 매핑들의 집합 내에서의 적어도 하나의 전송 매핑으로 계산된다. 적어도 하나의 전송 매핑은 스코어에 기초하여 선택되고, 출력 의미 구조를 만들기 위해 사용된다. 또한, 본 발명은 컴퓨터 구현 방법 및 기계 번역 시스템으로 구체화된다. 본 발명의 향상된 측면은 의미 구조들로부터 구성된 언어 모델이다.

도 1은 본 발명이 실시될 수 있는 일반적인 컴퓨팅(computing) 환경에 대한 블록도.

도 2는 본 발명이 실시될 수 있는 이동 장치(mobile device)에 대한 블록도.

도 3 및 도 4는 논리 형식(logical form)의 예시도.

도 5는 본 발명의 실시예에 따른 기계 번역 구조의 블록도.

도 6은 전송 매핑(transfer mapping)의 타겟 측에서의 타겟 논리 형식의 예시도.

도 7은 입력 논리 형식의 예시도.

도 8은 전송 매핑 데이터베이스에 저장된 전송 매핑의 예시도.

도 9 및 도 10은 전송 매핑 데이터베이스에 저장된 전송 매핑의 예시도.

도 11은 입력 논리 형식의 예시도.

도 12는 전송 매핑 데이터베이스에 저장된 전송 매핑의 예시도.

도 13은 본 발명의 실시예에 따른 디코드(decoding) 알고리즘의 흐름도.

도 14는 도 13의 흐름도가 이용할 수 있는 소스 논리 형식의 예시도.

도 15 내지 도 21은 도 13의 흐름도가 이용할 수 있는 전송 매핑 데이터베이스에 저장된 전송 매핑의 예시도.

< 도면의 주요 부분에 대한 부호 설명 >

100 : 컴퓨팅 시스템 환경

200 : 이동 장치

300 : 논리 형식 및 의존 그래프

400 : 논리 형식 및 의존 그래프

500 : 기계 번역 시스템

600 : 타겟 의존 그래프

700 : 입력 논리 형식

800 : 전송 매핑

1300 : 디코드 알고리즘

1400 : 소스 논리 형식

1500 : 전송 매핑

Claims (38)

1. 출력 의미 구조(output semantic structure)를 생성하기 위해 입력 의미 구조(input semantic structure)를 디코드하는 방법에 있어서,

   전송 매핑들의 집합을 제공하는 단계;

   통계적 모델을 사용하여 상기 전송 매핑들의 집합 내에서 적어도 하나의 전송 매핑에 대한 스코어를 계산하는 단계;

   상기 스코어(score)에 기초하여 적어도 하나의 전송 매핑을 선택하는 단계; 및

   상기 출력 의미 구조를 구성하기 위해 상기 선택된 전송 매핑을 사용하는 단계

   를 포함하는 방법.
2. 제1항에 있어서, 전송 매핑들의 집합을 제공하는 단계는, 각각의 전송 매핑이 상기 입력 의미 구조의 노드들을 설명하는 입력 의미 측(input semantic side) 및 상기 출력 의미 구조의 노드들을 설명하는 출력 의미 측(output semantic side)을 갖는, 전송 매핑들의 집합을 제공하는 단계를 포함하는 방법.
3. 제1항에 있어서, 적어도 하나의 전송 매핑에 대한 스코어를 계산하는 단계는, 상기 출력 의미 구조에 있는 노드들의 집합의 확률을 제공하는 타겟 언어 모델(target language model)을 사용하여 스코어를 계산하는 단계를 포함하는 방법.
4. 제2항에 있어서, 적어도 하나의 전송 매핑에 대한 스코어를 계산하는 단계는, 주어진 전송 매핑의 출력 의미 측에 대하여, 상기 전송 매핑의 입력 의미 측의 확률을 제공하는 채널 모델(channel model)을 사용하여 스코어를 계산하는 단계를 포함하는 방법.
5. 제4항에 있어서, 상기 채널 모델을 사용하여 스코어를 계산하는 단계는, 전송 매핑들 사이에 중첩하는(overlapping) 노드들의 수에 기초하여 채널 모델 스코어를 표준화하는(normalizing) 단계를 포함하는 방법.
6. 제2항에 있어서, 적어도 하나의 전송 매핑에 대한 스코어를 계산하는 단계는, 전송 매핑에서 노드 삭제(node deletion)의 확률을 제공하는 퍼틸리티 모델(fertility model)을 사용하여 스코어를 계산하는 단계를 포함하는 방법.
7. 제2항에 있어서, 적어도 하나의 전송 매핑에 대한 스코어를 계산하는 단계는, 상기 전송 매핑의 상기 입력 의미 측의 노드들 수에 기초하여 사이즈 스코어(size score)를 계산하는 단계를 포함하는 방법.
8. 제2항에 있어서, 적어도 하나의 전송 매핑에 대한 스코어를 계산하는 단계는, 상기 전송 매핑의 상기 입력 의미 측과 상기 입력 의미 구조에서 부합하는 바이너리 특성들(matching binary features) 수에 기초하여 랭크 스코어(rank score)를 계산하는 단계를 포함하는 방법.
9. 제2항에 있어서, 상기 전송 매핑들의 집합들 내에서 적어도 하나의 전송 매핑에 대한 스코어를 계산하는 단계는,

   다수의 모델들에 대한 개별의 스코어들(separate scores)을 계산하는 단계;

   상기 전송 매핑에 대한 상기 스코어를 결정하기 위해 상기 개별 스코어들을 조합하는 단계

   를 포함하는 방법.
10. 제9항에 있어서, 상기 다수의 모델들은 주어진 전송 매핑의 출력 의미 측에 대하여, 상기 전송 매핑의 입력 의미 측의 확률을 제공하는 채널 모델을 포함하는 방법.
11. 제9항에 있어서, 상기 다수의 모델들은 전송 매핑에서 노드 삭제의 확률을 제공하는 퍼틸리티 모델을 포함하는 방법.
12. 제9항에 있어서, 상기 다수 모델들은 상기 출력 의미 구조에 있는 노드들의 집합의 확률을 제공하는 타겟 언어 모델을 포함하는 방법.
13. 제9항에 있어서,

    상기 전송 매핑에 대한 사이즈 스코어를 계산하는 단계로서, 상기 사이즈 스코어는 상기 전송 매핑의 상기 입력 의미 측의 노드들 수에 기초하는 단계; 및

    상기 전송 매핑에 대한 상기 스코어를 결정하기 위해 상기 사이즈 스코어를 상기 다수의 모델들에 대한 상기 개별 스코어들과 조합하는 단계

    를 더 포함하는 방법.
14. 제9항에 있어서,

    상기 전송 매핑에 대한 랭크 스코어를 계산하는 단계로서, 상기 랭크 스코어는 상기 전송 매핑의 상기 입력 의미 측과 상기 입력 의미 구조에서 부합하는 바이너리 특성들 수에 기초하는 단계; 및

    상기 전송 매핑에 대한 상기 스코어를 결정하기 위해 상기 랭크 스코어를 상기 다수의 모델들에 대한 상기 개별 스코어들과 조합하는 단계

    를 더 포함하는 방법.
15. 제9항에 있어서, 상기 스코어들을 조합하는 단계는,

    각각의 스코어를 가중치로 곱하여 가중치가 부여된 모델(weighted model score) 스코어들을 형성하는 단계; 및

    각각의 전송 매핑에 대한 상기 스코어를 결정하기 위해 상기 가중치가 부여된 모델 스코어들을 더하는 단계

    를 포함하는 방법.
16. 제2항에 있어서, 전송 매핑들의 집합을 제공하는 단계는, 루트(root) 전송 매핑 및 서브트리들(subtrees)을 포함하는 트리(tree) 구조로서, 각각의 서브 트리는 루트 전송 매핑을 포함하고, 상기 전송 매핑들의 집합 내의 각각의 전송 매핑은 상기 트리 및 서브 트리들 중의 적어도 하나에서 루트 전송 매핑으로 나타나는 트리구조로 정렬되는 전송 매핑들의 집합을 제공하는 단계를 포함하는 방법.
17. 제16항에 있어서, 전송 매핑들의 집합을 트리 구조로 제공하는 단계는, 포개진(nested) 서브 트리들의 다중 레벨을 제공하는 단계를 포함하는 방법.
18. 제17항에 있어서, 적어도 하나의 전송 매핑에 대한 스코어를 계산하는 방법은,

    포개진 서브 트리들의 각각의 레벨에 대한 스코어를 반복적으로 계산하는 단계로서, 하나의 서브 트리에 대한 스코어를 계산하는 단계가,

    상기 서브 트리의 상기 서브 트리들을 반복적으로 스코어를 계산하는 단계;

    상기 서브 트리의 상기 루트 전송 매핑에 대한 스코어를 계산하는 단계; 및

    상기 서브 트리의 상기 서브 트리들에 대한 상기 스코어들을 상기 서브 트리의 상기 루트 전송 매핑에 대한 상기 스코어와 조합하는 단계

    를 포함하는 단계;

    상기 루트 전송 매핑에 대한 스코어를 계산하는 단계; 및

    각각의 서브 트리에 대한 상기 스코어를 상기 루트 전송 매핑에 대한 상기 스코어와 조합하는 단계

    를 포함하는 단계들을 통해서, 전송 매핑들의 트리에 대한 스코어를 계산하는 단계를 포함하는 방법.
19. 제18항에 있어서, 루트 전송 매핑에 대한 스코어를 계산하는 단계는, 상기 루트 전송 매핑의 상기 입력 의미 측에서의 노드들 수에 기초하여 상기 루트 전송 매핑에 대한 사이즈 스코어를 계산하는 단계를 포함하는 방법.
20. 제18항에 있어서, 서브 트리들의 상기 스코어를 루트 전송 매핑에 대한 상기 스코어와 조합하는 단계는, 상기 서브 트리들에 대한 사이즈 스코어들을 상기 루트 전송 매핑에 대한 상기 사이즈 스코어와 함께 평균 내어, 상기 서브 트리들에 대한 상기 사이즈 스코어들을 상기 루트 전송 매핑들에 대한 상기 사이즈 스코어와 조합하는 단계를 포함하는 방법.
21. 제18항에 있어서, 루트 전송 매핑에 대한 스코어를 계산하는 단계는 상기 루트 전송 매핑의 상기 입력 의미 측과 상기 입력 의미 구조에서 부합하는 바이너리 특성 수에 기초하여 상기 루트 전송 매핑에 대한 랭크 스코어를 계산하는 단계를 포함하는 방법.
22. 제21항에 있어서, 서브 트리들의 상기 스코어를 루트 전송 매핑에 대한 상기 스코어와 조합하는 단계는, 상기 서브 트리들에 대한 랭크 스코어들을 상기 루트 전송 매핑의 상기 랭크 스코어와 함께 평균 내어, 상기 서브 트리들에 대한 상기 랭크 스코어들을 상기 루트 전송 매핑들의 상기 랭크 스코어와 조합하는 단계를 포함하는 방법.
23. 제1 언어로 된 입력을 제2 언어로 된 출력으로 번역하기 위한 기계 번역 시스템에 있어서,

    상기 입력을 입력 의미 표현(input semantic representation)으로 구문 분석(parsing)하기 위한 구문 분석부;

    전송 매핑들의 집합을 찾도록 구성되는(configured) 갖춘 검색 구성 요소로서, 각각의 전송 매핑은 상기 입력 의미 표현의 일부와 대응하는 검색 구성 요소;

    다수의 전송 매핑들을 스코어 계산하고, 상기 스코어에 기초하여 적어도 하나의 전송 매핑을 선택하도록 구성되는(configured) 디코드 구성 요소; 및

    상기 선택된 전송 매핑에 기초하여 상기 출력을 생성하도록 구성되는(configured) 생성 구성 요소

    를 포함하는 기계 번역 시스템.
24. 제23항에 있어서, 상기 디코드 구성 요소는 다수의 통계적 모델들을 사용하여 각각의 전송 매핑을 스코어 계산하는 기계 번역 시스템.
25. 제24항에 있어서, 상기 출력은 출력 의미 표현(output semantic representation)을 포함하고, 상기 다수의 통계적 모델들은 상기 출력 의미 표현에 있는 일련의 노드들의 확률을 제공하는 타겟 모델을 포함하는 기계 번역 시스템.
26. 제24항에 있어서, 상기 다수의 통계적 모델들은, 전송 매핑 내에서 출력 측에서의 주어진 의미 노드들의 집합에 대하여, 상기 전송 매핑들의 입력 측에서의 의미 노드들의 집합의 확률을 제공하는 채널 모델을 포함하는 기계 번역 시스템.
27. 제24항에 있어서, 상기 다수의 통계적 모델들은 상기 전송 매핑의 노드 삭제의 확률을 제공하는 퍼틸리티 모델을 포함하는 기계 번역 시스템.
28. 제24항에 있어서, 상기 디코드 구성 요소는 상기 전송 매핑의 입력 측에서의 노드들의 수에 기초하는 사이즈 스코어를 사용하여 각각의 전송 매핑을 스코어 계산하는 기계 번역 시스템.
29. 제24항에 있어서, 상기 디코드 구성 요소는 상기 입력과 상기 전송 매핑의 입력 측 사이에 부합하는 바이너리 특성들 수에 기초하는 랭크 스코어를 사용하여 각각의 전송 매핑을 스코어 계산하는 기계 번역 시스템.
30. 단어 문자열(word string)에 대한 스코어를 결정하는 컴퓨터에 의해 구현되는 방법에 있어서,

    상기 단어 문자열에 관련된 다수의 노드들을 갖는 의미 구조를 계산하는 단계; 및

    상기 단어 문자열을 스코어 계산하기 위해, 상기 단어 문자열을 상기 의미 구조의 일련의 노드들의 확률을 제공하는 타겟 언어 모델로 스코어하는 단계

    를 포함하는 컴퓨터 구현 방법.
31. 제30항에 있어서, 다수의 노드들을 갖는 의미 구조를 제공하는 단계는, 다수의 단어 노드(word node)들 및 단어들 사이의 의미 관련(semantic relationship)을 설명하는 적어도 하나의 관련 노드(relationship node)를 갖는 의미 구조를 제공하는 단계를 포함하는 컴퓨터 구현 방법.
32. 제30항에 있어서, 단어 노드들을 제공하는 단계는, 렘마들(lemmas)에 대한 단어 노드들을 제공하는 단계를 포함하는 컴퓨터 구현 방법.
33. 제30항에 있어서, 상기 단어 문자열을 타겟 언어 모델로 스코어 계산하는 단계는 기계 번역(machine translation)의 상기 타겟 언어 모델로 상기 단어 문자열을 스코어 계산하는 단계를 포함하는 컴퓨터 구현 방법.
34. 제30항에 있어서, 상기 단어 문자열을 타겟 언어 모델로 스코어 계산하는 단계는 음성 인식(speech recognition)의 상기 타겟 언어 모델로 상기 단어 문자열을 스코어 계산하는 단계를 포함하는 컴퓨터 구현 방법.
35. 제30항에 있어서, 상기 단어 문자열을 타겟 언어 모델로 스코어 계산하는 단계는 광문자인식(optical character recognition)의 상기 타겟 언어 모델로 상기 단어 문자열을 스코어 계산하는 단계를 포함하는 컴퓨터 구현 방법.
36. 제30항에 있어서, 상기 단어 문자열을 타겟 언어 모델로 스코어 계산하는 단계는 문법 검사(grammar checking)의 상기 타겟 언어 모델로 상기 단어 문자열을 스코어 계산하는 단계를 포함하는 컴퓨터 구현 방법.
37. 제30항에 있어서, 상기 단어 문자열을 타겟 언어 모델로 스코어 계산하는 단계는 필체 인식(handwriting recognition)의 상기 타겟 언어 모델로 상기 단어 문자열을 스코어 계산하는 단계를 포함하는 컴퓨터 구현 방법.
38. 제30항에 있어서, 상기 단어 문자열을 타겟 언어 모델로 스코어 계산하는 단계는 정보 추출(information extraction)의 상기 타겟 언어 모델로 상기 단어 문자열을 스코어 계산하는 단계를 포함하는 컴퓨터 구현 방법.