KR20040078595A

KR20040078595A - 블록 동기 디코딩

Info

Publication number: KR20040078595A
Application number: KR1020040014528A
Authority: KR
Inventors: 윌리엄에이치. 로켄베크; 줄리안제이. 오델
Original assignee: 마이크로소프트 코포레이션
Priority date: 2003-03-04
Filing date: 2004-03-04
Publication date: 2004-09-10
Also published as: JP2004272251A; EP1455341A2; US7529671B2; EP1455341A3; US20040176956A1; CN1532807A

Abstract

본 발명은 패턴 인식 시스템(pattern recognition system) 및 방법을 제공한다. 본 발명의 특징은 특히 다중 상태 은닉 마코프 모델(multi-state Hidden Markov Models)과 결합하면 유용하다. 패턴 인식은 은닉 마코프 모델 블록을 프로세싱함으로써 달성된다. 이 블록 프로세싱은, 데이터가 캐쉬 메모리에 있는 동안, 프로세서로 하여금 데이터에 대하여 더 많은 동작을 수행할 수 있게 한다. 이와 같이 캐쉬 로컬리티(locality)를 증가시킴으로써, 본 발명의 특징은 상당히 개선된 패턴 인식 속도를 제공한다.

Description

블록 동기 디코딩{BLOCK SYNCHRONOUS DECODING}

본 발명은 패턴 인식(pattern recognition)에 관한 것이다. 더욱 구체적으로는, 본 발명은 패턴 인식에 사용되는 신호를 프로세싱하는 것과 관련된다.

음성 인식 시스템(speech recognition system)과 같은 패턴 인식 시스템은 입력 신호를 받아 들여, 신호에 의하여 표현된 패턴을 찾기 위하여 신호를 디코딩하려고 시도한다. 예를 들어, 음성 인식 시스템에 있어서, (종종 시험 신호라고 하는) 음성 신호가 인식 시스템에 의하여 수신되고, 음성 신호에 의하여 표현된 단어들의 문자열(a string of words)를 식별하기 위하여 디코딩된다.

입력된 시험 신호를 디코딩하기 위하여, 대부분의 시스템은 시험 신호의 일부가 특정 패턴을 표현할 확률에 대해 기술하는 하나 이상의 모델을 이용한다. 이러한 모델의 예는, 신경망(Neural Nets), 동적 시각 워핑(Dynamic Time Warping), 세그먼트 모델(segment models), 및 은닉 마코프 모델(Hidden Markov Models, HMMs)을 포함한다.

대부분의 상업적으로 사용 가능한 음성 인식 시스템은 HMM들을 사용하여 음성의 음성 패턴을 대조하는데, 음성 패턴은 종종 대략 10ms로 서로 분리되는 중첩되는(overlapping) "프레임(frame)"으로 분할된다. 음성을 이와 같이 10ms의 프레임으로 분해하는 것은 입력을 일련의 시간 순차 프레임들(a series of time-sequenced frames)로 변환하는 일 예에 불과하다. 전통적으로, 한 번에 하나의 프레임에 대하여 이러한 프레임의 판정(evaluation)이 이루어진다; 모든 HMM들은, 다음 프레임으로 이동되기 전에 라운드-로빈 방식(round-robin fashion)으로 단일 프레임에 대하여 갱신된다.

도 3은, 예를 들어 Huang, Acero, 및 Hon의 "Spoken Language Processing"의 제8장을 포함하는 많은 문서에서 상세하게 설명된 것과 같은 HMM의 기본적인 표현을 도시한다. 임의의 주어진 시간에, 모델은 임의의 다양한 상태의 주어진 확률(probability)을 갖는다. 각 상태는 출력 확률 분포 및 다른 상태로의 전이(transition)를 갖는다. 음성의 경우에, 출력 분포는, 10ms 프레임으로 쪼개어진 로우 음성 파형(raw speech waveforms)으로부터 유도되는 음향 특성 세트(an acoustic feature set)를 모델링한다. 이러한 전이 및 출력 확률은 알려져 있는 기술에 따라 훈련 단계(training step)에 의하여 생성된다.

HMM들에 있어서의 디코딩 문제는, HMM 및 관찰들의 시퀀스(a sequence of observations)가 주어졌을 때, 가장 관찰들의 시퀀스를 생성할 것 같은 상태 시퀀스가 무엇인지이다. 이 문제를 해결하는 표준 방법은 동적 프로그래밍(Dynamic programming)이라고 하며, 도 4에 도시되어 있다. 도 3과 관련하여 설명한 6-상태 HMM이 측면에 기재되어 있으며, 시간은 수평축을 따라 진행된다. 이 격자에 있어서의 각 "점(point)"(상태와 시간의 조합)은, 주어진 관측에 대하여, 그 시간에 HMM이 그 상태에 있을 확률을 나타낸다. DP 행렬을 통한 한 가지 가능한 경로가 굵은 선(1-8-14-21-27-33-40-47-53-59-66)으로 강조되어 있고, 이는 특정 배열 또는 상태 시퀀스를 나타낸다. 점에 대한 확률은, 그 시간 단계에 대한 전이 확률및 출력 확률에 있어서, 이전 점들(previous points)의 확률에 의존한다. 각 점은 몇 개의 이전 점에 의존하기 때문에, 그 점에 대한 확률을 계산하는 것은 이전 점이 우선 계산될 것을 요구하고, 그럼으로써 계산의 순서(order)에 제한을 두게 된다. "시간 동기(time-synchronous)" 판정 순서는 도 4에 점 내의 번호에 의하여 도시되어 있다. 시스템은 다음 시간 단계에 다시 시작하기 전에 주어진 시간 단계 동안 모든 상태를 판정한다. 다만, 이전의 것(predecessors)이 계산된 후에만 점을 계산하는 임의의 순서가 허용되기 때문에, 이러한 순서는 단지 하나의 가능한 판정 순서임을 유의하여야 한다. 회색 점은, 도달할 수 없거나 가능한 최종 상태로 인도하지 않는 상태를 나타내고, 따라서 이들은 판정될 필요가 없다. 그러나 많은 구현 예에 있어서는 어쨌든 이들을 판정한다.

실시간 시스템에 있어서, 동시에 실행되는 이러한 HMM들이 수만 개 존재할 수 있다. 이러한 모델들은 충분한 컴퓨터 메모리를 소비하고, 전체 모델 세트를 각각 통과하는 것은 종종 CPU 캐쉬 용량을 다 써버린다. CPU 캐쉬만 관련된 메모리 동작은 보다 고 레벨 메모리와 관련된 메모리 동작보다 몇 배 빠르게 발생하기 때문에 이는 음성 처리를 상당히 지연시키게 된다.

이 문제를 해결하는 다른 방법은 Tony Robinson 및 James Christie의 논문 "Time-First Search For Large Vocabulary Speech Recognition"에 설명되어 있다. 이 방법은, 근본적으로 HMM 판정의 순서를 주어진 시간 프레임에 대한 복수의 모델을 판정하는 것으로부터 주어진 모델에 대한 복수의 시간 프레임을 판정하는 것으로 바꾼다. 이러한 방법은, 다수의 동작이 동일한 물리적 메모리 범위에 속하기때문에 표준 CPU 메모리 캐쉬 동작과 협동하는 동안, 프로세싱 메모리 요구를 감소시키는 것을 목적으로 한다.

대형 단어 애플리케이션(large vocabulary application)에 대하여, 실시간의 연속적인 음성 인식을 제공하기 위하여, CPU 캐쉬 사용의 효율뿐만 아니라 프로세싱 루틴 자체의 효율을 개선하기 위한 개발이 요구된다. 따라서 프로세싱 속도뿐만 아니라 프로세싱 정확도 또한 대단히 중요하다.

발명의 개요

본 발명은 패턴 인식 시스템 및 방법을 제공한다. 본 발명의 특징은 구체적으로 다중 상태 은닉 마코프 모델(multi-state Hidden Markov Models)과 결합하면 유용하다. 패턴 인식은 은닉 마코프 모델 블록을 프로세싱함으로써 달성될 수 있다. 이 블록-프로세싱은, 데이터가 캐쉬 메모리에 있는 동안 그러한 데이터에 대하여 더 많은 동작을 수행할 수 있게 한다. 캐쉬 로컬리티(locality)가 증가됨으로써, 본 발명의 특징은 상당히 개선된 패턴 인식 속도를 제공한다.

도 1은 본 발명이 실시될 수 있는 컴퓨팅 환경을 도시한 블록도.

도 2는 본 발명이 실시될 수 있는 다른 컴퓨팅 환경을 도시한 블록도.

도 3은 6-상태 HMM(six-state Hidden Markov Model)를 도표로 도시한 도면

도 4는 도 3의 HMM을 가로축에 시간과 함께 도표로 도시한 도면.

도 5는 3-상태(three-state) HMM의 3개로 이루어진 짝을 도표로 도시한 도면.

도 6은 본 발명의 실시예에 따른 은닉 마코프 모델 블록들(HMMBs)을 도표로 도시한 도면.

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

200 모바일 장치

202 프로세서

203 캐쉬 메모리

206 입출력 구성요소

208 통신 인터페이스

212 오퍼레이팅 시스템

214 애플리케이션

도 1은 본 발명이 구현될 수 있는 적절한 컴퓨팅 시스템 환경(100)의 예를 나타낸다. 컴퓨팅 시스템 환경(100)은 단지 적절한 컴퓨팅 환경의 일 예이며 본 발명의 사용 또는 기능의 범위에 제한을 가하도록 의도된 것은 아니다. 컴퓨팅 환경(100)은 예시적인 오퍼레이팅 환경(100)에 도시된 컴포넌트들 중의 임의의 하나 또는 조합에 관하여 임의의 종속성(dependency) 또는 요구사항(requirement)을 갖는 것으로 해석되어서는 안 된다.

본 발명은 많은 다른 범용 또는 특수목적 컴퓨팅 시스템 환경들 또는 구성들과 함께 동작될 수 있다. 본 발명과 함께 사용하기에 적합할 수 있는 잘 알려진 컴퓨팅 시스템, 환경, 및/또는 구성의 예로는, 퍼스널 컴퓨터, 서버 컴퓨터, 핸드헬드(hand-held) 또는 랩탑 장치, 멀티프로세서 시스템, 마이크로프로세서-기반 시스템, 셋 탑 박스(set top box), 프로그램 가능한 가전제품(programmable consumer electronics), 네트워크 PC, 미니컴퓨터, 메인프레임 컴퓨터, 상기의 시스템 또는 장치 중의 임의의 것을 포함하는 분산형 컴퓨팅 환경 등이 포함될 수 있지만, 이에 한정되지 않는다.

본 발명은 컴퓨터에 의해 실행되는, 프로그램 모듈과 같은 컴퓨터 실행가능 명령과 일반적으로 관련하여 기술될 수 있다. 일반적으로, 프로그램 모듈은 특정 태스크를 수행하거나 특정 추상 데이터 유형을 구현하는 루틴, 프로그램, 오브젝트, 컴포넌트, 데이터 구조 등을 포함한다. 본 발명은 또한 통신 네트워크를 통해 링크된 원격 프로세싱 장치에 의해 태스크를 수행하는 분산형 컴퓨팅 환경에서 실행될 수 있다. 분산 컴퓨팅 환경에서, 프로그램 모듈은 메모리 저장 장치를 포함하는 국부 및 원격 컴퓨터 저장 매체 내에 위치할 수 있다.

도 1을 참조하면, 본 발명을 구현하기 위한 예시적인 시스템은 컴퓨터(110)의 형태의 범용 컴퓨팅 장치를 포함한다. 컴퓨터(110)의 컴포넌트들로는, 캐쉬 메모리(122)(레벨 1 캐쉬) 및 캐쉬 메모리(123)(레벨 2 캐쉬)를 포함하는 프로세싱 유닛(120), 시스템 메모리(130), 및 시스템 메모리를 포함하는 다양한 시스템 컴포넌트를 프로세싱 유닛(120)에 연결시키는 시스템 버스(121)가 포함될 수 있지만, 이에 한정되는 것은 아니다. 캐쉬 메모리는, 데이터의 블록을 상대적으로 저속인 시스템 메모리로부터 상대적으로 고속인 캐쉬 메모리로 전송시키는 것을 가능하게 함으로써 프로세싱 속도를 증가시킨다. 현재 2가지 주요 유형의 캐쉬 메모리가 있다. 레벨 1 캐쉬 메모리는 마이크로프로세서 자체의 메모리의 일부이다. 이 메모리는 일반적으로 시스템의 다른 모든 메모리보다 고속이지만, 마이크로프로세서의 실리콘 풋프린트(footprint)에 직접 부가되어야 하기 때문에 비교적 고가이다. 레벨 2 캐쉬는 일반적으로 마이크로프로세서 근방에 배치되며, 마이크로프로세서 상에 배치되지는 않는다. 이 메모리는 전형적으로 시스템 메모리보다 고속이지만 레벨 1 캐쉬 메모리보다는 저속이다. 매우 대략적인 가이드라인으로서, 레벨 1 캐쉬는 레벨 2 캐쉬보다 수십배 정도(about an order of magnitude) 고속으로 동작하고, 레벨 2 캐쉬는 전체적인 시스템 RAM보다 수십배 정도 고속으로 동작한다. 따라서, 시스템 프로세싱 속도는 캐시 메모리가 가장 효율적으로 사용될 때 최대화된다.

시스템 버스(121)는 다양한 버스 아키텍처 중의 임의의 것을 사용하는 로컬 버스, 주변 버스, 및 메모리 버스 또는 메모리 컨트롤러를 포함하는 몇 가지 유형의 버스 구조 중의 임의의 것일 수 있다. 예로서, 이러한 아키텍처는 산업 표준 아키텍처(ISA) 버스, 마이크로 채널 아키텍처(MCA) 버스, 인핸스드 ISA(Enhanced ISA; EISA) 버스, 비디오 일렉트로닉스 표준 어소시에이션(VESA) 로컬 버스, 및 (메자닌(Mezzanine) 버스로도 알려진) 주변 컴포넌트 상호접속(PCI) 버스를 포함하지만, 이에 한정되는 것은 아니다.

컴퓨터(110)는 통상적으로 다양한 컴퓨터 판독가능 매체를 포함한다. 컴퓨터 판독가능 매체는 컴퓨터(110)에 의해 액세스될 수 있는 임의의 이용 가능한 매체일 수 있으며, 휘발성 및 비휘발성 매체, 분리형(removable) 및 비분리형(non-removable) 매체를 둘 다 포함한다. 예로서, 컴퓨터 판독가능 매체는 컴퓨터 저장 매체 및 통신 매체를 포함할 수 있지만, 이에 한정되는 것은 아니다. 컴퓨터 저장 매체는 컴퓨터 판독가능 명령, 데이터 구조, 프로그램 모듈 또는 다른 데이터와 같은 정보의 저장을 위한 임의의 방법 또는 기술로 구현되는 휘발성 및 비휘발성, 분리형 및 비분리형 매체를 둘 다 포함한다. 컴퓨터 저장 매체는 RAM, ROM, EEPROM, 플래쉬 메모리 또는 기타 메모리 기술, CD-ROM, DVD(digital versatile disk) 또는 기타 광학 디스크 저장장치, 자기 카세트, 자기 테이프, 자기 디스크 저장장치 또는 기타 자기 저장장치, 또는 컴퓨터(110)에 의해 액세스될 수 있고 원하는 정보를 저장하는 데 사용될 수 있는 임의의 기타 매체를 포함할 수 있지만, 이에 한정되지 않는다. 통신 매체는 통상적으로 반송파 또는 기타 전송 메카니즘 등의 변조된 데이터 신호에 컴퓨터 판독가능 명령, 데이터 구조, 프로그램 모듈, 또는 다른 데이터를 구현하며, 임의의 정보 전달 매체를 포함한다. "변조된 데이터 신호"라는 용어는 신호 내에 정보를 인코딩하도록 설정되거나 변환된 특성을 하나 또는 그 이상을 갖는 신호를 의미한다. 예로서, 통신 매체는 유선 네트워크 또는 직접 유선 접속 등의 유선 매체와, 음향, RF, 적외선 및 기타 무선 매체 등의 무선 매체를 포함하지만, 이에 한정되지 않는다. 상술한 것들 중의의 임의의 조합이 컴퓨터 판독가능 매체의 범위 내에 포함되어야 한다.

시스템 메모리(130)는 ROM(131) 및 RAM(132) 등의 휘발성 및/또는 비휘발성 메모리의 형태의 컴퓨터 저장 매체를 포함한다. 시동중과 같은 때에 컴퓨터(110) 내의 구성요소들간에 정보를 전송하는 것을 돕는 기본 루틴을 포함하는 기본 입출력 시스템(133; BIOS)은 일반적으로 ROM(131)에 저장된다. RAM(132)은 일반적으로 프로세싱 유닛(120)에 즉시 액세스될 수 있고 및/또는 프로세싱 유닛(120)에 의해 현재 작동되는 프로그램 모듈 및/또는 데이터를 포함한다. 예로서, (한정하고자 하는 것은 아님) 도 1은 오퍼레이팅 시스템(134), 애플리케이션 프로그램(135), 기타 프로그램 모듈(136), 및 프로그램 데이터(137)를 도시한다.

컴퓨터(110)는 또한 다른 분리형/비분리형, 휘발성/비휘발성 컴퓨터 저장 매체를 포함할 수 있다. 단지 예로서, 도 1에는 비분리형 비휘발성 자기 매체로부터 판독하거나 그 자기 매체에 기록하는 하드 디스크 드라이브(140), 분리형 비휘발성 자기 디스크(152)로부터 판독하거나 그 자기 디스크에 기록하는 자기 디스크 드라이브(151), 및 CD-ROM 또는 기타 광학 매체 등의 분리형 비휘발성 광학 디스크(156)로부터 판독하거나 그 광학 디스크에 기록하는 광학 디스크 드라이브(155)가 도시되어 있다. 예시적인 오퍼레이팅 환경에서 사용될 수 있는 다른 분리형/비분리형, 휘발성/비휘발성 컴퓨터 저장 매체는 자기 테이프 카세트, 플래쉬 메모리 카드, DVD(Digital versatile disk), 디지털 비디오 테이프, 고체 RAM, 고체 ROM 등을 포함하지만 이에 한정되지 않는다. 하드 디스크 드라이브(141)는 일반적으로 인터페이스(140)와 같은 비분리형 메모리 인터페이스를 통해 시스템 버스(121)에 접속되고, 자기 디스크 드라이브(151) 및 광학 디스크 드라이브(155)는 일반적으로 인터페이스(150)와 같은 분리형 메모리 인터페이스에 의해 시스템 버스(121)에 접속된다.

앞서 기술되고 도 1에 도시된 드라이브 및 그 관련 컴퓨터 저장 매체는 컴퓨터(110)를 위한 컴퓨터 판독가능 명령, 데이터 구조, 프로그램 모듈 및 기타 데이터의 저장을 제공한다. 도 1에서, 예를 들어, 하드 디스크 드라이브(141)는 오퍼레이팅 시스템(144), 애플리케이션 프로그램(145), 기타 프로그램 모듈(146), 및 프로그램 데이터(147)를 저장하는 것으로 도시된다. 이들 컴포넌트는 오퍼레이팅 시스템(134), 애플리케이션 프로그램(135), 기타 프로그램 모듈(136), 및 프로그램 데이터(137)와 동일할 수도 있고 다를 수도 있다. 오퍼레이팅 시스템(144), 애플리케이션 프로그램(145), 다른 프로그램 모듈(146), 및 프로그램 데이터(147)는 최소한 다른 복사본(different copies)임을 나타내기 위하여 다른 번호를 부여하였다.

사용자는 일반적으로 마우스, 트랙볼, 또는 터치 패드와 같은 포인팅 장치(161), 키보드(162) 및 마이크로폰(163)과 같은 입력 장치를 통해 컴퓨터(110)에 명령 및 정보를 입력할 수 있다. (도시되지 않은) 기타 입력 장치는 마이크로폰, 조이스틱, 게임 패드, 위성 안테나, 스캐너 등을 포함할 수 있다. 이들 입력 장치 및 그외의 입력 장치는 시스템 버스에 연결된 사용자 입력 인터페이스(160)를 통해 종종 프로세싱 유닛(120)에 접속되지만, 병렬 포트, 게임 포트 또는 유니버설 시리얼 포트(USB) 와 같은 기타 인터페이스 및 버스 구조에 의해 접속될 수 있다.모니터(191) 또는 다른 유형의 디스플레이 장치는 또한 비디오 인터페이스(190) 등의 인터페이스를 통해 시스템 버스(121)에 접속된다. 모니터 외에도, 컴퓨터는 또한 출력 주변 인터페이스(195)를 통해 접속될 수 있는 스피커(197) 및 프린터(196) 등의 기타 주변 출력 장치를 포함할 수 있다.

컴퓨터(110)는 원격 컴퓨터(180)와 같은 하나 이상의 원격 컴퓨터로의 논리적 접속을 이용한 네트워크 환경에서 동작할 수 있다. 원격 컴퓨터(180)는 퍼스널 컴퓨터, 핸드핼드 장치(hand-held device), 서버, 라우터, 네트워크 PC, 피어(peer) 장치, 또는 기타 공통 네트워크 노드일 수 있으며, 컴퓨터(110)에 관하여 상술한 구성요소 중 다수 또는 모든 구성요소를 일반적으로 포함할 수 있다. 도 1에 도시된 논리적 접속은 근거리 통신망(LAN; 171) 및 원거리 통신망(WAN; 173)을 포함하지만, 그 외의 네트워크를 포함할 수도 있다. 이러한 네트워크 환경은 사무실, 기업 광역 컴퓨터 네트워크(enterprise-wide computer network), 인트라넷, 및 인터넷에서 일반적인 것이다.

LAN 네트워크 환경에서 사용되는 경우, 컴퓨터(110)는 네트워크 인터페이스 또는 어댑터(170)를 통해 LAN(171)에 접속된다. WAN 네트워크 환경에서 사용되는 경우, 컴퓨터(110)는 일반적으로 인터넷 등의 WAN(173)을 통해 통신을 구축하기 위한 모뎀(172) 또는 기타 수단을 포함한다. 내장형 또는 외장형일 수 있는 모뎀(172)은 사용자 입력 인터페이스(160) 또는 기타 적절한 메카니즘을 통해 시스템 버스(121)에 접속될 수 있다. 네트워크 환경에서, 컴퓨터(110)에 관하여 도시된 프로그램 모듈 또는 그 일부분은 원격 메모리 저장 장치에 저장될 수 있다. 예로서 (한정하고자 하는 것은 아님), 도 1은 메모리 장치(181)에 상주하는 원격 애플리케이션 프로그램(185)을 도시한다. 도시된 네트워크 접속은 예시적인 것이며, 컴퓨터들간의 통신 링크를 구축하는 그 외의 수단이 사용될 수 있다.

도 2는 모바일 장치(mobile device, 200)의 블록도인데, 이는 예시적인 컴퓨팅 환경을 나타낸다. 모바일 장치(200)는, 캐쉬 메모리(203)를 포함하는 마이크로프로세서(202), 메모리(204), 입출력(I/O) 구성요소(206), 및 원격 컴퓨터 또는 다른 모바일 장치와 통신하기 위한 통신 인터페이스(208)를 포함한다. 일 실시예에 있어서, 상술한 구성요소는 적절한 버스(210)를 통하여 서로 통신하기 위하여 연결되어 있다.

메모리(204)는 랜덤 액세스 메모리(RAM)와 같은 비휘발성 전자 메모리로서 (도시하지 않은) 배터리 백업 모듈과 함께 구현되어, 모바일 장치(200)로의 전체적인 전원이 끊겼을 때 메모리(204)에 저장된 정보가 손실되지 않도록 한다. 메모리(204)의 일부는 바람직하게는 프로그램 실행을 위하여 액세스 가능한 메모리로서 할당되는 것이 좋지만, 메모리(204)의 나머지 부분은 바람직하게는 디스크 드라이브의 저장부(storage)를 시뮬레이션하도록 저장부를 위해 사용되는 것이 좋다.

메모리(204)는 객체 스토어(object store, 216)뿐만 아니라, 오퍼레이팅 시스템(212), 애플리케이션 프로그램(214)을 포함한다. 동작 중, 오퍼레이팅 시스템(212)은 바람직하게는 메모리(204)로부터 프로세서(202)에 의하여 실행된다. 바람직한 실시예에 있어서, 오퍼레이팅 시스템(212)은 Microsoft사로부터 상업적으로 사용 가능한 WINDOWS? CE 상표 오퍼레이팅 시스템이다. 오퍼레이팅시스템(212)은 모바일 장치를 위하여 설계되는 것이 바람직하고, 공개된 애플리케이션 프로그래밍 인터페이스 및 방법의 세트를 통하여 애플리케이션(214)에 의해서 사용될 수 있는 데이터 베이스 특성을 구현한다. 객체 스토어(216)의 객체는 공개된 애플리케이션 프로그래밍 인터페이스 및 방법의 호출에 적어도 부분적으로 응답하여 애플리케이션(214) 및 오퍼레이팅 시스템(213)에 의하여 유지된다.

통신 인터페이스(208)는, 모바일 장치가 정보를 전송하고 수신할 수 있도록 하는 수많은 장치 및 기술을 나타낸다. 장치는 몇 가지 예를 들자면, 유선 및 무선 모뎀, 위성 수신기, 방송 튜너를 포함한다. 모바일 장치(200)는 데이터를 교환하기 위하여 컴퓨터로 직접 접속될 수도 있다. 이러한 경우에는, 통신 인터페이스(208)는 스트리밍 정보를 전송할 수 있는 모든 적외선 송수신기, 직렬 또는 병렬 통신 접속일 수 있다.

입출력 구성요소(206)는 오디오 생성기(audio generator), 진동 장치(vibrating device) 및 디스플레이와 같은 다양한 출력 장치뿐만 아니라, 터치 감지 스크린(touch-sensitive screen), 버튼, 롤러(rollers), 및 마이크로폰과 같은 입력 장치도 포함한다. 위에 열거한 장치는 예시를 위한 것이며, 모바일 장치(200)에 모두 존재할 필요는 없다. 또한, 본 발명의 범위 내에서 다른 입출력 장치가 모바일 장치(200)에 부착되거나 모바일 장치(200)에 있을 수 있다.

본 발명의 특징 하에서, 시스템 캐쉬 로컬리티를 상당히 증가시키기 위하여 HMM 프로세싱에 적용되는 시스템 및 방법이 제공된다. 이에 따라, 시스템 캐쉬가 플러시(flush)되기 전에 더 많은 수의 HMM 동작이 행해진다. 따라서, 일반 시스템메모리를 호출하는 횟수가 과거에 요구되던 것에 비하여 적어진다. 따라서, 프로세싱 속도가 상당히 증가한다. 이러한 개선점에 대하여 음성 프로세싱과 관련하여 설명하겠지만, 본 발명의 실시예는 HMM을 사용하는 임의의 형태의 패턴 인식을 위한 프로세싱을 개선하기 위하여 실시될 수 있다.

음성을 모델링하기에 유용한 몇몇 모델은 "3-상태의, 건너뜀 없이 좌에서 우로의 진행(three-state left-to-right without skipping)"으로 알려진 특정 HMM 토폴로지(topology)를 사용한다. 이 토폴로지는 도 5 및 도 6에 도시되어 있다. 본 발명의 실시예는 근본적으로 HMM 판정을 재정리하여, 다른 HMM을 판정하기 전에 하나의 HMM 동안 3개의 프레임이 판정되도록 한다. 이는 캐쉬 로컬리티를 상당히 개선하고, 따라서 프로세싱 속도를 증가시킨다.

도 6은 은닉 마코프 모델 블록들(Hidden Markov Model Blocks, HMMBs)로 그룹핑된 도 5의 모델을 나타낸다. 굵은 선으로 나타낸 각 마름모꼴(rhombus, 400)은 음성 단위(speech unit)(즉, 음소(phoneme))에 해당하는 HMMB를 나타낸다. 각 HMMB에 있어서, 각 상태의 프레임의 고유의 번호가 제공된다. 따라서 HMMB #1에는 0 상태의 3개의 프레임, 1 상태의 3개의 프레임, 및 2 상태의 3개의 프레임이 있다. 본 발명의 실시예의 장점은 HMM에서의 상태의 수와 다른 수의 프레임으로 실현될 수 있다는 것일 수 있지만, 프레임의 수는 HMM 상태의 수와 동일한 것이 바람직하다. 또한, 상술한 바와 같이 임의의 주어진 점은 그 이전 점에 대하여 판정이 되어야만 판정이 되기 때문에 마름모꼴 형상을 취하고 있다. 도 6에 도시된 HMMB들의 크기는 사용되는 상태의 수(3-상태의, 좌에서 우로의 HMMs)에 일치시켜 선택되었다. 본 발명의 사상 및 범위에 속하는, 다른 HMM 토폴로지는 다른 형상의 HMMB들을 발생시킬 수 있다는 것을 주의하여야 한다. 예를 들어, 10-상태의, 좌에서 우로의 HMM(필기 인식과 같은 몇몇 다른 형태의 패턴 인식을 위하여 유용할 수 있음)은 10-프레임 HMMB들로 수정될 수 있을 것이다. 또한, 5개의 상태를 갖는 가끔 사용되는 토폴로지는 각 프레임 상에서, 그 상태 자신 또는 다음 상태 또는 그 다음 상태로 전이할 수 있다. 이 경우에, 3-상태의 HMMB들은 (HMM으로의 임의의 입력은 출력에 도달하기 위하여 적어도 3개의 프레임을 거치기 때문에) 여전히 유용하지만, HMMB의 형상은 3 프레임의 "폭(wide)"과 5 상태의 "높이(high)"를 가질 것이다.

본 발명의 실시예에 따르면, 각 HMMB은 하나의 단위로서 판정된다. 여기서 사용되는 것과 같이, HMMB는 HMM 프로세싱 시스템의 모든 점의 부분집합이다. 블록은, 시간 및 상태 모두에 있어서 서로 다른 적어도 2개의 점을 포함한다. 각 HMMB의 판정은 오로지 이전의 HMMB들의 출력에 의존한다.

각 HMMB는 인터 블록 입구점(inter-block entry points), 인트라 블록 입구점(intra-block exit points), 인터 블록 출구점(inter-block exit points), 및 인트라 블록 출구점(intra-block exit points)을 포함한다. 도 6을 참조하면, 점(402, 408, 및 414)이 인터 블록 입구점이며, 이들은 다른 HMMB들로부터 점수(scores) 또는 값을 수신할 수 있다. 점(402, 404, 및 406)은 인트라 블록 입구점인데, 이들은 같은 HMM의 이전 블록으로부터 점수를 수신할 수 있다. 블록 4와 관련하여, 블록 1은 동일한 HMM에서 이전 블록으로 고려된다. 점(402)은 인터블록 입구점일 뿐만 아니라 인트라 블록 입구점이기도 하다. 점(406, 412, 및 418)은 인터 블록 출구점인데, 이들은 블록 5와 같이 다른 블록의 인터 블록 입구점으로 그들의 값을 제공할 수 있기 때문이다. 마지막으로, 점(414, 416, 및 418)은 인트라 블록 출구점으로 볼 수 있다.

블록의 프로세싱이 개시되기 전에, 인터 블록 입구점 및 인트라 블록 입구점에서 끝나는 최적의 경로에 대한 점수가 미리 결정된다. 또한, 이 최적의 경로에 따른 선행 상태로의 포인터가 입구점에 저장된다.

블록의 프로세싱은 시간 상으로 첫 번째 점에서 시작된다. 도 6에 있어서, 그 점은 "402"로 나타내었다. 점(402)은, 점(402, 404, 406)으로부터 전이될 수 있는 각 점에 대한 전이 확률과 그 점수를 곱함으로써 프로세싱된다. 그리고 이 점수가 전이된 점의 현재 존재하는 값과 비교되어, 점(402)을 통한 점수가 전이된 점의 현재 존재하는 점수보다 높은지 여부가 결정된다. 점(402)을 통한 점수가 더 크다면, 전이된 점은 새로운 최대값을 반영하여 갱신되고, 점(402)과 관련된 포인터가 설정된다.

점(402)이 프로세싱되면, 점(404)이 프로세싱될 수 있다. 점(404)은 동일한 HMM의 직전 블록 및 블록(402)의 점수로부터 대응하는 인트라 블록 출구점 중 큰 쪽으로 초기에 설정된다는 점에서, 점(404)의 프로세싱은 비교적 수월하다(straightforward). 점(406)은 점(404)과 유사하게 프로세싱된다. 그러나, 점(406)은 인터 블록 출구점이기 때문에, 다른 블록의 몇몇 인터 블록 입구점을 갱신하기 위하여 그 점수가 사용된다.

점(402)이 처리되면, 점(408)도 처리될 수 있다. 점(404)과 점(408) 사이의 프로세싱의 상대적인 순서는 설계 선택 상의 문제이다. 점(408)은 그 전이 확률과 조합되어 점(404)으로 접속될 수 있는 모든 출구점 및 점(402) 중에서 최대 점수를 취한다는 점에서, 점(408)은 점(402)과 어느 정도 유사하게 프로세싱된다. 최대 점수를 보증하는 점을 표시하기 위하여 포인터 또는 다른 적당한 레코드가 다시 설정된다. 점(408)을 프로세싱하는 것은 그 점수와 전이 확률을 곱하는 것을 포함하고, 이를 통하여 점(408)은 점(410 및 414)의 값을 잠정적으로 갱신하기 위하여 전이될 수 있다.

점(410, 412, 416, 및 418)은 점(404, 및 406)과 유사하게 프로세싱된다. 또한, 점(414)의 프로세싱은 점(408)과 관련하여 설명한 것과 유사하다.

블록 1 내의 모든 프로세싱이 완료되면, 출구 점수 프로세싱(exit score processing)이 행해진다. 구체적으로는, 각 인터 블록 출구점에 대하여, 언어 모델이 참고된다. 언어 모델은, 음성 단위 사이에서 전이되는 전이 확률뿐만 아니라 어느 전이가 허용 가능한지를 보여준다. 따라서, 예를 들어, 언어 모델은 블록 1의 음성 단위로부터 다른 음성 단위로 전이되는 허용 확률 및 확률을 나타낸다. 이 확률은 점(406)과 같은 인터 블록 출구점의 점수와 조합되어, 다음 시간 프레임의 (언어 모델에 의하여) 임의의 허용 가능한 인터 블록 입구점에 현재 존재하는 점수보다 그 조합이 큰지 여부가 결정된다. 조합이 실제로 더 크다면, 새로운 최대값, 및 관련 포인터 또는 다른 적절한 레코드가 설정된다. 인터 블록 출구점(412 및 418)에 대해서도 이 프로세스가 반복된다. 도 6에 점선으로 나타낸바와 같이, 인터 블록 출구점이 동일한 음성 단위에 대하여 시간상 다음 블록의 인터 블록 입구점에 접속될 수도 있다(즉, 406이 420으로 접속됨).

점(416 및 418)은 동일한 음성 단위에 대하여, 시간상 다음 블록의 인트라 블록 입구점으로 그들의 점수를 제공한다. 마지막으로, 점(420)이 점(402)에 대하여 설명한 바와 같이 프로세싱되고, 다음 블록에서 프로세스가 계속된다.

블록 1의 프로세싱이 완료되면, 또 다른 음성 단위에 해당하는 블록의 프로세싱이 개시되는 것이 바람직하다. 예시적인 블록 프로세싱 순서가 도 6에 블록 1-2-3-4-5-6-7-8-9로 도시되어 있다. 그러나, 본 발명의 범위를 벗어나지 않고 다른 순서가 실행될 수 있다. 점들의 일부는 회색으로 표시되어 있는데, 이들은 도달 가능하지 않거나 가능한 최종 상태로 유도되지 않는 경우이다. 추가적인 프로세싱 효율은 이러한 점들을 실제로 프로세싱하지 않음으로써 달성될 수 있다.

특정 실시예와 관련하여 본 발명에 대하여 설명하였지만, 당업자라면 본 발명의 사상 및 범위를 벗어나지 않고 형태 및 세부사항에 있어서 변경이 가해질 수 있다는 것을 인식할 것이다.

은닉 마코프 모델 블록의 프로세싱은, 데이터가 캐쉬 메모리에 있는 동안, 프로세서로 하여금 데이터에 대하여 더 많은 동작을 수행할 수 있게 하며, 이와 같이 캐쉬 로컬리티(locality)를 증가시킴으로써, 본 발명은 상당히 개선된 패턴 인식 속도를 제공한다.

Claims

연속 패턴 인식 시스템(a continuous pattern recognition system)에 있어서,

입력의 디지털 표시(digital representation)를 제공하기에 적합한 입력 장치;

상기 입력 장치에 동작 가능하게(operably) 연결되는, 상기 디지털 표시 및 상기 디지털 표시와 관련된 복수의 다중 상태 모델들(multi-state models)을 저장하기 위한 메모리; 및

상기 입력 장치 및 상기 메모리에 연결되고, 캐쉬 메모리(cache memory)를 포함하는, 상기 디지털 표시를 복수의 시간 순차 프레임(time-sequenced frames)으로 변환하기에 적합한 프로세서

를 포함하고,

상기 프로세서는 상기 캐쉬 메모리에 저장된 상기 다중 상태 모델들의 블록들 및 상기 시간 순차 프레임의 프로세싱에 기초하여 인식된 패턴의 출력을 생성하기에 적합한 시스템.
제1항에 있어서, 상기 다중 상태 모델은 3-상태 은닉 마코프 모델들(three-state Hidden Markov Models)인 시스템.
제1항에 있어서, 상기 입력 장치는 마이크로폰인 시스템.
제1항에 있어서, 상기 인식된 패턴의 출력은 단어(words)를 포함하는 시스템.
제1항에 있어서, 상기 시스템은 컴퓨터 내에 내장되는 시스템.
제1항에 있어서, 상기 시스템은 모바일 장치(mobile device)에 내장되는 시스템.
시간 순차 프레임의 형태의 입력에서 패턴을 인식하는 방법에 있어서,

복수의 다중 상태 은닉 마코프 모델을 사용하여 패턴을 모델링하는 단계; 및

상기 시간 순차 프레임 중 모델링된 패턴을 인식하기 위하여 은닉 마코프 모델 블록들(Hidden Markov Model Blocks; HMMBs)을 프로세싱하여, 인식된 모델링된 패턴의 시퀀스를 생성하는 단계

를 포함하는 방법.
제7항에 있어서, 상기 시간 순차 프레임은 음성(speech)에 해당하는 방법.
제7항에 있어서, 상기 다중 상태 은닉 마코프 모델은 3-상태 은닉 마코프 모델인 방법.
제9항에 있어서, 각 HMMB는, 상태 대 시간 도표(state vs. time chart)로 도시할 때 3 대 3의 마름모꼴(three by three rhombus)인 방법.
제9항에 있어서, 각 블록을 프로세싱하는 단계는 시스템 캐쉬 메모리와만 상호 작용하는 단계를 포함하는 방법.
제7항에 있어서, 상기 HMMB들을 프로세싱하는 단계는 언어 모델(language model)을 액세스하는 단계를 포함하는 방법.
패턴 인식 방법에 있어서,

시간 순차 프레임들의 시리즈(a series of time-sequenced frames)로서 입력을 표시하는 단계; 및

HMMB들 및 상기 시리즈를 프로세싱하여, 상기 입력에 대응하는 인식된 패턴의 출력 시퀀스를 생성하는 단계

를 포함하는 방법.
제13항에 있어서, 상기 입력은 음성에 해당하는 방법.
제13항에 있어서, 각 HMMB는 3개의 상태를 포함하는 방법.
시간 순차 프레임의 형태의 입력에서 패턴을 인식하는 방법에 있어서,

a) 복수의 다중 상태 은닉 마코프 모델로서 패턴을 모델링하는 단계;

b) 제1 다중 상태 은닉 마코프 모델의 제1 점을 프로세싱하는 단계;

c) 상기 제1 다중 상태 은닉 마코프 모델의 제2 점- 상기 제2 점은 상태 및 시간에 있어서 상기 제1 점과 다름 -을 프로세싱하는 단계; 및

d) 상기 시간 순차 프레임 중 상기 모델링된 패턴을 인식하여, 인식된 모델링된 패턴을 생성하기 위하여, 제1 은닉 마코프 모델의 나머지 점 및 복수의 다중 상태 은닉 마코프 모델의 점들을 프로세싱하는 단계

를 포함하는 방법.
제16항에 있어서, 상기 제1 점 및 제2 점은 HMMB를 포함하는 방법.