KR100446289B1

KR100446289B1 - 역 히든 마르코브 모델(ｉｈｍｍ)을 이용한 정보 탐색방법및 장치

Info

Publication number: KR100446289B1
Application number: KR10-2000-0060262A
Authority: KR
Inventors: 김보성; 조준동; 장영훈; 박선희
Original assignee: 삼성전자주식회사; 학교법인 성균관대학
Priority date: 2000-10-13
Filing date: 2000-10-13
Publication date: 2004-09-01
Also published as: KR20020029494A; US20020065959A1; US6735588B2

Abstract

역 히든 마르코브 모델을 이용한 정보 탐색 방법 및 장치가 개시된다. 이 방법은, 기준정보모델에 대한 상태격자에 존재하는 상태들중 이전시간 t-1에서 탐색된 유효상태들 각각이 가지며 이전 시간까지의 탐색경로상에서 누적된 확률인 최소상태확률을 이용하여 현재시간 t에서 탐색되는 해당상태의 최소상태확률을 구하고, 최소비유사성스코어보다 큰 해당상태의 최소상태확률을 소정값으로 갱신하는 (a)단계와,소정시간이 경과되었을때 구해진 최소상태확률들중에서 가장 작은 확률에 해당하는 적정경로값보다 큰 최소비유사성스코어를 적정경로값으로 갱신하는 (b)단계와,모든 기준정보모델들에 대하여 적정경로값들이 구해졌는가를 판단하여, 모두 구해지지 않았으면 적정경로값을 구할 다른 기준정보모델에 대하여 (a) 및 (b)단계들을 반복하여 수행하는 단계 및 모두 구해졌으면 최소비유사성스코어를 가장 나중에 갱신할 때 사용된 적정경로값이 구해진 기준정보모델을 미지정보에 가장 유사한 모델로서 결정하는 단계를 구비하고,(a)단계는 매 시간(t)에서 해당상태들에 대하여 소정시간 동안 수행되고, 유효상태란 이전시간에서 탐색된 임의상태가 갖는 최소상태확률이 최소비유사성스코어보다 적어 해당상태로 경로를 확장할 수 있는 임의상태에 해당하고, 해당상태가 갖는 최소상태확률은 유효상태들로부터 해당상태로 경로를 확장하기 위한 확률들중에서 가장 작은확률에 해당하는 것을 특징으로 한다.

Description

역 히든 마르코브 모델(ＩＨＭＭ)을 이용한 정보 탐색 방법 및 장치{Information search method and apparatus using Inverse Hidden Markov Model}

본 발명은 히든 마르코브 모델(HMM:Hidden Markov Model)을 이용하여 미지의 정보를 인식하는 방법 및 장치에 관한 것으로서, 특히, 음성이나 화상의 형태로 된 미지의 정보를 여러가지 확률들을 계산하여 비터비 방식으로 탐색할 수 있는 역 히든 마르코브 모델(IHMM:Inverse HMM)을 이용한 정보 탐색 방법 및 장치에 관한 것이다.

정보를 인식하기 위해 여러가지의 정보 인식 방법들이 사용된다. 예를 들어, 음성이라는 정보를 인식하기 위해 사용되는 음성 인식 방법에 대해 살펴보면 다음과 같다.

음성 인식 기술이란, 기계나 컴퓨터가 인간의 말을 인식할 수 있도록 관련되는 방법들을 개발하고 개발된 방법들을 실현하는 기술이다. 이 때, 음성을 통해 기계와 인간간의 자연스럽고 원활한 통신을 가능하게 하는 인터페이스를 구현하기 위하여 음성 신호 처리 기술 특히, 음성 인식 기술의 개발은 필수적이다. 음성 인식 기술에 대한 연구는 컴퓨터, 하드웨어 및 신호 처리 기술의 혁신적인 발전에 힘입어 비약적으로 발전되고 있다. 또한, 이러한 발전은 통계적 기법의 도입, 풍부한 음성 데이타의 사용, 음성과 언어 지식의 결합, 고속 탐색 알고리즘의 사용등에 의해 가능해지고 있다. 게다가, 반도체 산업의 발달로 매우 적은 크기를 갖고 적은 전지로도 오랫동안 사용될 수 있는 시스템이 등장하게 되었다. 따라서, 무선 통신기기와 같은 통신 분야에서는 하드웨어로 음성 인식을 구현하는 전용 칩을 이용하여 전력의 소모 및 기기의 크기를 줄일 수 있다.

HMM을 바탕으로 하는 음성 인식 방법은 음성 신호에 대한 강력한 모델링 능력과 높은 인식 정확도를 갖기 때문에 음성 인식 분야에서 널리 사용된다. 음성 인식을 위한 방법은 음향 확률을 구하는 단계 및 구해진 음향 확률을 이용하여 가장 가능성 있는 단어를 탐색하는 단계로 구성된다.

HMM을 사용한 고립 단어 인식은 학습(training) 단계 및 탐색(또는 인식)단계로 구성된다. 학습 단계에서는 HMM 파라미터를 예측하고 관측 학습 세트를 사용하여 단어사전내의 각 단어에 대해서 세분화된 HMM을 갖도록 한다. 탐색 단계에서는 사전내의 각 단어 모델에 대한 입력 단어의 발생 확률을 계산하고 가장 높은 확률을 갖는 단어 모델을 인식단어로서 선택한다. 이 때, 비터비(Viterbi) 방식은, 사전에 저장된 각 단어 모델 즉, 기본 음성 모델과 입력된 발음을 비교하여 가장 잘 매칭이 되는 단어를 선택하는 효율적인 탐색기술로서, 전술한 탐색 단계에서 사용된다.

음성 인식을 위한 방법을 더욱 세분화하면, 전처리단계, 인식 코어 단계 및 후처리 단계로 나누어진다. 각 단계에 사용되는 방법을 예를 들어 설명하면 먼저, 전처리 단계는 음성 신호로부터 시변적인 특성을 대표할 수 있는 기준 발음(reference utterance) 형태의 특징 파라미터를 추출하며, 이를 위해 시간 정렬(time alignment)과 정규화(normalization)와 끝점 검출 절차(end-point detection process)를 갖는 선형 예측 부호화(LPC:Linear Predictive Coding) 및필터 뱅크 프론트 엔드 절차(filter bank front-end procedure)로 구성된다. 음성 인식의 핵심 처리 단계인 인식 코어 단계는 매칭 및 학습 과정이다. 음성 기호 및 단어 수준으로 매칭되는 발음 특징(utterance feature)을 표현하는 추출된 파라미터는 전술한 매칭되고 학습된 데이타에 의해 표현된다. 후처리 단계는 탐색 과정으로서, 입력된 발음의 특징 파라미터와 기준 발음의 특징 파라미터를 비교하여 가장 잘 매칭된 발음열(utterance sequence)을 찾는다.

도 1은 종래에 HMM을 이용하여 입력 음성을 탐색하는 경로를 설명하기 위한 예시적인 상태 격자들을 나타내는 도면으로서, 다수개의 상태들(1 ∼ 24)로 구성되며, 각 상태는 참조 번호 순서대로 탐색된다.

예컨데, "abbat"라는 단어가 발음되었을 때, 일반적인 HMM은 도 1에 도시된 바와 같이 표현된다. 음성 인식에서 사용되는 HMM은 국부적인 변환 경로(local transition path)를 가지며, 다음 상태로의 전이는 이전에 누적된 상태 확률[S_t-1(i)](여기서, t는 시간을 나타내는 변수를 의미하고, i는 도 1에 도시된 상태 격자에서 시간 t에서 현재 탐색이 진행되고 있는 상태를 나타내는 변수로서, 가로축인 X축에 해당한다.), 전이 확률(a_ij)(여기서, j는 도 1에 도시된 상태 격자에서 시간 t-1에서 탐색이 된 상태를 나타내는 변수로서 가로축인 X축에 해당한다.) 및 다음 상태 관측 확률[b_ij(W_t)]에 의해 결정된다. 여기서, 다음 상태 관측 확률[b_ij(W_t)]은 확률 밀도 함수[P(y｜s⁽ⁱ⁾,Φ]에 의해서 결정된다. 이 때, 다음 상태로의 전이를 결정하는 규칙은 최대 유사성(maximum likelihood)을 기초로 하면서 비터비 방식으로 음성 정보를 탐색하는 종래의 음성 정보 탐색 방법을 기본으로 한다.

이하, 종래의 음성 정보 탐색 방법을 첨부한 도면을 참조하여 다음과 같이 설명한다.

도 2는 종래의 음성 탐색 방법을 설명하기 위한 슈도우 코드(pseudo code)로서, 제1 ∼ 제12 단계로 이루어진다.

도 2를 참조하면, 제1 단계에서 최대 유사성 스코어(maximum likelihood score)를 나타내는 변수(Max)의 값을 '0'으로 설정하고, 제2 단계에서 변수(all_reference_sequence)[여기서, all_reference_sequence는 전술한 바와 같이 사전에 저장된 기본 음성 모델들 각각의 위치를 나타내는 변수이다.]를 '1'로 설정하고, 제3 단계에서 변수(t)를 '1'로 설정하고, 제4 단계에서 변수(i)를 '1'로 설정한다. 이 때, 제5 단계에서 i번째 최대 상태 확률[Φ_i(t)]을 '0'으로 설정하고, 제6 단계에서 변수(j)를 '1'로 설정한다. 이와 같이 각 변수를 초기화시킨 다음, 시간 t-1에서 탐색된 j번째 상태의 누적확률을 고려하여 시간 t에서 i번째 상태의 최대 상태 확률[Φ_i(t)]을 구한다(제6 ∼ 제8 단계). 제8 단계의 'endfor'는 j=N이 아니면 제6 단계로 진행하고 그렇지 않으면 제9 단계로 진행하라는 것을 의미한다. 결국, 제5 ∼ 제8 단계들을 모든 i에 대해서 반복함으로서, N개의 최대 상태 확률들을 구한다(제4 ∼ 제9 단계). 시간 T동안 최대 상태 확률 값을 가지는 적정 경로가 찾아지며 주어진 기본 음성 모델과 입력 음성의 유사성이 구해진다.(제3 ∼ 제10 단계). 이와 같은 동작은 사전에 저장된 기본 음성 모델들 각각에 대해서 수행된다(제2 ∼ 제12 단계). 제11 단계는 Φ_{all_reference_sequence}(여기서, Φ_{all_reference_sequence}는 하나의 기본 음성 모델에 대해서 계산된 적정 경로 값을 의미한다.)와 최대 유사성 스코어(Max)를 비교하고, 비교한 두 값 중 큰 수가 최대 유사성 스코어(Max)로 갱신된다. 갱신된 최대 유사성 스코어를 가지고 동일한 절차(제2단계 ~ 제 12단계)가 진행된다.

도 2에 도시된 종래의 방법은 최대 유사성 스코어를 만들기 위하여 모든 상태들에 대한 확률 계산을 수행해야 하기 때문에 계산량이 많고 고속 탐색에는 적합하지 않는 문제점을 갖는다. 이와 같이, 종래의 음성 정보 탐색 방법은, 모든 음성 상태들을 탐색해야 하고, 각 음성 상태의 모든 최대 경로를 저장하고 있어야 하므로, 비효율적으로 많은 하드웨어 자원(hardware resource)과 많은 계산량으로 인해 전력의 소비가 증가하고 계산시간이 길어지는 문제점을 갖는다.

본 발명이 이루고자 하는 기술적 과제는, 미지의 정보를 인식하기 위해 HMM을 위한 경로 매트릭스에서 최대 유사성 스코어가 아닌 최소 비유사성 스코어(minimum unlikelihood score)를 이용하여 비터비 방식으로 경로를 탐색하여 불필요한 계산을 사전에 제거할 수 있도록 하는 IHMM을 이용한 정보 탐색 방법을 제공하는 데 있다.

본 발명이 이루고자 하는 다른 기술적 과제는, 상기 IHMM을 이용한 정보 탐색 방법을 수행하는 정보 탐색 장치를 제공하는 데 있다.

도 1은 종래에 HMM을 이용하여 입력 음성을 탐색하는 경로를 설명하기 위한 예시적인 상태 격자들을 나타내는 도면이다.

도 2는 종래의 음성 탐색 방법을 설명하기 위한 슈도우 코드이다.

도 3은 본 발명에 의한 IHMM을 이용한 정보 탐색 방법을 설명하기 위한 플로우차트이다.

도 4는 본 발명에 의한 저 전력 및 고속 정보 탐색 방법을 설명하기 위한 예시적인 상태 격자들을 나타내는 도면이다.

도 5는 도 3에 도시된 제100 단계의 본 발명에 의한 세부적인 과정을 설명하기 위한 플로우차트이다.

도 6은 도 5에 도시된 정보 탐색 방법의 본 발명에 의한 바람직한 일실시예의 플로우차트이다.

도 7은 도 5 또는 도 6에 도시된 방법을 수행하는 본 발명에 의한 IHMM을 이용한 정보 탐색 장치의 블럭도이다.

도 8은 도 6에 도시된 제i 연산부의 본 발명에 의한 일실시예의 블럭도이다.

상기 과제를 이루기 위해, 외부로부터 주어지며 히든 마르코브 모델(HMM)을 서로 연결하여 표현될 수 있는 미지의 정보가 학습에 의해 구해진 소정의 기준 정보 모델들중 어느 모델에 해당하는가를 확률적으로 탐색하는 역 HMM(IHMM)을 이용한 정보 탐색 방법에 있어서, 상기 기준 정보 모델에 대한 상태 격자의 HMM 체인에 존재하는 상태들중 이전 시간 t-1에서 탐색된 유효 상태들 각각이 가지며 이전 시간 t-1까지의 탐색경로 상에서 누적된 확률인 최소 상태 확률을 이용하여 현재 시간 t에서 탐색되는 해당 상태의 최소 상태 확률을 구하고, 최소 비유사성 스코어보다 큰 상기 해당상태의 최소 상태 확률을 소정값으로 갱신하는 (a) 단계와, 소정 시간(T〉t)이 경과되었을 때 구해진 상기 최소 상태 확률들중에서 가장 작은 확률에 해당하는 적정 경로 값보다 큰 상기 최소 비유사성 스코어를 상기 적정 경로 값으로 갱신하는 (b) 단계와, 모든 상기 기준 정보 모델들에 대하여 상기 적정 경로 값들이 모두 구해졌는가를 판단하여, 모든 상기 기준 정보 모델들에 대하여 상기 적정 경로 값들이 모두 구해지지 않았으면 상기 적정 경로 값을 구할 다른 기준 정보 모델에 대하여 상기 (a) 및 상기 (b) 단계들을 반복하여 수행하는 (c) 단계 및 모든 상기 기준 정보 모델들에 대하여 상기 적정 경로 값들이 모두 구해졌으면, 상기 최소 비유사성 스코어를 가장 나중에 갱신할 때 사용된 상기 적정 경로 값이 구해진 상기 기준 정보 모델을 상기 미지 정보에 가장 유사한 모델로서 결정하는 (d)단계로 이루어지고, 상기 (a)단계는 매 시간(t)에서 상기 해당 상태들에 대하여 상기 소정 시간(T) 동안 수행되고, 상기 유효 상태란 상기 이전 시간에서 탐색된 임의의 상태가 갖는 최소 상태 확률이 상기 최소 비유사성 스코어보다 적어 상기 해당 상태로 경로를 확장할 수 있는 상기 임의의 상태에 해당하고, 상기 해당 상태가 갖는 최소 상태 확률은 상기 유효상태들로부터 상기 해당 상태로 경로를 확장하기 위한 확률들 중에서 가장 작은 확률에 해당하는 것이 바람직하다.

여기서, 상기 해당 상태가 갖는 최소 상태 확률은 상기 유효 상태들 각각이 가지며 이전 시간 t-1까지의 탐색경로 상에서 누적된 확률인 상기 최소 상태 확률, 상기 유효 상태에서 상기 해당 상태로 천이하는 천이 확률, 상기 해당 상태에서의 관측 확률을 이용하여 상기 유효 상태들의 수만큼 구해진 상태 확률들중 가장 작은 확률에 해당하고, 상기 소정값은 상기 최소 비유사성 스코어보다 큰 것이 바람직하다.

상기 다른 과제를 이루기 위한 본 발명에 의한 IHMM을 이용한 정보 탐색 장치는, 상기 최소 비유사성 스코어, 상기 천이 확률과 관련되는 제1 값, 상기 상태 관측 확률과 관련되는 제2 값을 저장하는 저장부와, 제1 ∼ 제N 연산부들과, 제1 ∼ 제N 비교 선택부들과, 상기 제1 ∼ 제N 비교 선택부들 각각으로부터 출력되는 비교 플래그에 응답하여 제어 신호를 출력하고, 상기 저장부에 저장된 데이터의 독출을 제어하며, 상기 제1 ∼ 상기 제N 비교 선택부들로부터 출력되는 값들을 바이패스하는 제어부 및 상기 제어부에서 바이패스된 값들을 입력하여 버퍼링하고, 버퍼링된 값들을 상기 제어 신호에 응답하여 해당하는 상기 제1 ∼ 제N 연산부들로출력하는 버퍼로 구성되고, 상기 제i 연산부는 상기 버퍼로부터 출력되는 값과 상기 저장부로부터 입력한 상기 제1 값 및 상기 제2 값을 연산하고, 연산된 결과들중 가장 적은 연산된 결과를 상기 제어 신호에 응답하여 비교하여 선택하고, 제i 비교 선택부는 상기 제i 연산부로부터 출력되는 상기 가장 적은 연산된 결과와 상기 저장부로부터 입력한 상기 최소 비유사성 스코어를 비교하고, 비교된 결과에 응답하여 상기 소정값과 상기 가장 적은 연산된 결과중 하나를 선택하여 상기 제어부로 출력하고, 비교된 결과에 상응하는 레벨을 갖는 상기 비교 플래그를 상기 제어부로 출력하는 것이 바람직하다.

이하, 본 발명에 의한 IHMM을 이용한 정보 탐색 방법을 첨부한 도면들을 참조하여 다음과 같이 설명한다.

도 3은 본 발명에 의한 IHMM을 이용한 정보 탐색 방법을 설명하기 위한 플로우차트로서, 모든 기본 정보 모델들에 대한 적정 경로 값(optimal path value)들 중 가장 적은 적정 경로 값을 구하는 단계(제100 ∼ 제104 단계들) 및 미지의 정보를 가장 적은 적정 경로 값이 구해진 기준 정보 모델에 의해 인식하는 단계(제106 단계)로 이루어진다.

도 4는 본 발명에 의한 저 전력 및 고속 정보 탐색 방법을 설명하기 위한 임의의 기준 정보 모델에 대한 예시적인 상태 격자들을 나타내는 도면으로서, 제1 ∼ 제24 상태들(1 ∼ 24)로 구성된다. 여기서, 제1 상태부터 제24 상태까지 상태의 번호 순서로 탐색이 진행되고, W(t)는 심볼 시퀀스(symbol sequence)로서 시퀀스의 시간열에 대한 t번째 발음을 나타낸다.

도 4에서 어느 한 상태에서 다음 상태로 천이할 수 있는 상태의 수는 두개로 도시되어 있지만 두개의 상태로만 천이할 수 있는 것은 아니고 한 상태에서 모든 상태들로 경로를 선택할 수 있으며, 후술되는 바와 같이 선택할 수 있는 모든 경로들중에서 적정 경로가 찾아진다.

도 3을 참조하면, 히든 마르코브 모델(HMM)을 서로 연결하여 표현될 수 있는 미지의 정보가 외부로부터 주어졌다고 가정할 때, 본 발명에 의한 정보 탐색 방법은 미지의 정보가 학습에 의해 미리 구해진 소정의 기준 정보 모델들 중 어느 모델에 해당하는가를 확률적으로 비터비 방식에 의해 탐색한다(제100 ∼ 제106 단계들). 이를 위해 먼저, 임의의 기준 정보 모델에 대해 도 4에 도시된 바와 같은 상태 격자 형태의 HMM 체인에 존재하는 상태들중에서 이전 시간 t-1에서 탐색된 유효 상태들 각각이 가지며 이전 시간 t-1까지의 탐색경로 상에서 누적된 확률인 최소 상태 확률을 이용하여 현재 시간 t에서 탐색되는 상태(이하, 현재 시간에서 탐색되는 상태를 '해당 상태'라 함)의 최소 상태 확률[Φ'_i(t)]을 구하고, 최소 비유사성 스코어보다 큰 해당 상태의 최소 상태 확률[Φ'_i(t)]을 소정값으로 갱신한다(제100 단계).

이하, 전술한 유효 상태란 현재 시간을 t라고 할 때, 이전 시간 t-1에서 탐색된 상태들중에서, 현재 시간 t에서 탐색되는 해당 상태로 경로를 확장할 수 있는 상태들을 지칭한다. 그러므로, 현재 시간을 t+1이라고 하면, 유효 상태란 이전 시간 t에서 탐색된 상태들중에서, 현재 시간 t+1에서 탐색되는 해당 상태로 경로를확장할 수 있는 상태들을 지칭하게 된다. 이와 같이, 현재 시간 t에서 탐색되는 어느 해당 상태는 다음 시간 t+1에서 탐색될 상태의 최소 상태 확률을 구하기 위해 필요한 유효 상태가 될 수도 있고 그렇지 않을 수도 있다. 또한, 유효 상태는 소정값이 아닌 이전 시간 t-1까지의 탐색경로 상에서 누적된 확률인 최소 상태 확률을 가지며, 이는 그 유효 상태의 비유사성 정도가 최소 비유사성 스코어보다 작다는 것을 의미한다. 게다가, 맨 처음에 적정 경로가 구해질 기준 정보 모델에 대한 상태 격자에 존재하는 모든 상태들은 유효 상태로 간주한다. 여기서, 최소 비유사성 스코어(Min)는 상세하게 후술되며, 해당 상태가 갖는 최소 상태 확률은 유효 상태들로부터 해당 상태로 경로를 확장하기 위한 상태 확률들 중에서 가장 작은 확률에 해당한다.

이하, 현재 시간이 t라고 할 때, 해당 상태가 갖는 최소 상태 확률을 Φ'_i(t)(여기서, i는 도 4에 도시된 상태 격자에서 현재 시간 t에서 탐색을 해야하는 해당 상태를 나타내는 변수로서 가로축인 X축에 해당하며, 1≤i≤N의 범위를 갖고, N은 미지의 정보를 구성하는 정보 상태들의 수를 의미한다.)로 표현하자.

도 3에 도시된 제100 단계의 본 발명에 의한 세부적인 과정을 살펴보면 다음과 같다.

도 5는 도 3에 도시된 제100 단계의 본 발명에 의한 세부적인 과정을 설명하기 위한 플로우차트로서, 각 기본 정보 모델에 대해 소정 시간(T) 동안 매 시간(t)에서, 상태 격자의 상태들중 이전 시간 t-1에서 탐색된 유효 상태가 가지며 이전 시간 t-1까지의 탐색경로 상에서 누적된 확률인 최소 상태 확률을 이용하여 각 해당 상태에 대한 최소 상태 확률을 구하는 단계(제120 ∼ 제126 단계)로 이루어진다.

먼저, 현재 시간 t에서 탐색되는 해당 상태에 대한 최소 상태 확률[Φ'_i(t)]을 이전 시간 t-1에서 탐색된 유효 상태들 각각이 가지며 이전 시간 t-1까지의 탐색경로 상에서 누적된 확률인 최소 상태 확률을 이용하여 구한다(제120 단계). 즉, 유효 상태들 각각이 가지며 이전 시간 t-1까지의 탐색경로 상에서 누적된 확률인 최소 상태 확률[Φ_ij(t-1)], 유효 상태에서 해당 상태로 천이하는 천이 확률 및 해당 상태에서의 상태 관측 확률을 이용하여 유효 상태들의 수만큼 상태 확률들을 구한 다음, 상태 확률들중 가장 작은 확률을 해당 상태에 대한 최소 상태 확률로서 결정한다.

제120 단계후에, 해당 상태에 대한 최소 상태 확률[Φ'_i(t)]이 최소 비유사성 스코어(Min)보다 큰 경우에만 최소 상태 확률[Φ'_i(t)]을 소정값으로 갱신하고, 최소 상태 확률[Φ'_i(t)]이 최소 비유사성 스코어(Min)보다 크지 않은 경우에는 최소 상태 확률[Φ'_i(t)]을 갱신하지 않고 그대로 유지시킨다(제122 단계). 여기서, 소정값은 최소 비유사 스코어(Min)보다 커야 한다. 왜냐하면, 해당 상태의 최소 상태 확률은 다음 시간에서 탐색되는 상태의 최소 상태 확률을 구하기 위해 사용될 수 있는 바, 이전 시간에서 탐색된 어떤 상태가 갖는 최소 상태 확률이 최소 비유사 스코어(Min)보다 큰 소정값이면 이러한 소정값에 해당하는 최소 상태 확률을 갖는 그 상태는 유효 상태가 되지 못하도록 하기 위해서이다. 결국, 최소 비유사 스코어(Min)보다 큰 최소 상태 확률을 갖는 해당 상태는 다음 시간에서 유효 상태가 아닌 비유효상태가 된다. 그러므로, 본 발명에 의한 정보 탐색 방법에서는 이러한 비유사 상태에 대해서는 상태 확률을 계산을 수행하지 않기 때문에, 정보 탐색을 고속으로 저전력을 소모하면서 수행할 수 있게 된다. 즉, 도 4에 도시된 제13, 제14, 제17, 제18, 제21, 제22 및 제23 상태들(13, 14, 17, 18, 21, 22 및 23)은 유효하지 못한 비유효 상태들로서 해당 상태의 최소 상태 확률을 구하는데 사용되지 않는다.

제122 단계후에, 현재 시간 t동안 탐색해야 하는 모든 해당 상태들에 대한 최소 상태 확률들이 모두 구해졌는가를 판단한다(제124 단계). 만일, 해당 상태의 최소 상태 확률들이 모두 구해지지 않았으면 제120 단계로 진행하여, 아직 최소 상태 확률[Φ'_i(t)]을 갖지 못한 해당 상태에 대하여 제120 및 제122 단계를 수행한다. 그러나, 현재 시간 t에서 해당 상태들에 대한 최소 상태 확률들이 모두 구해졌으면, 소정 시간(T〉t)이 경과하였는가를 판단한다(제126 단계). 만일, 소정 시간(T)이 경과되지 않았으면 제120 단계로 진행하여 다음 시간 t+1에서 제120 ∼ 제124 단계들을 수행한다. 그러나, 소정 시간(T)이 경과되었으면, 도 3에 도시된 제102 단계로 진행한다.

한편, 제100 단계후에, 적정 경로 값(Φ'_{all_reference_sequence})보다 최소 비유사성 스코어(Min)가 클 경우, 최소 비유사성 스코어(Min)를 적정 경로 값으로 갱신한다(제102 단계). 예컨데, 최초에 최소 비유사성 스코어(Min)는 무한대(∞)의 값으로 설정된 후, 사전에 저장된 첫번째의 제1 기본 음성 모델과 입력된 미지의 정보를 비교 및 탐색한 후, 최초에 설정된 최소 비유사성 스코어의 값(∞)이 유효한 값으로 갱신된다. 즉, 첫번째의 제1 기본 음성 모델에 대한 적정 경로 탐색에서 찾아진 적정 경로상에서, 현재 시간이 T 일때 해당 상태들이 갖는 최소 상태 확률들중에서 가장 적은 값을 가지는 최소 상태 확률을 적정 경로 값(A)으로하고, 최소 비유사성 스코어(Min)를 무조건 이 값(A)으로 갱신한다. 즉, 첫번째의 제1 기준 정보 모델의 경우, 소정 시간(T)동안 상태 격자의 모든 상태들에 대해서 최소 상태 확률들을 구하는 연산이 수행된다. 하지만, 사전에 저장된 두번째의 제2 기준 정보 모델부터는 적정 경로 탐색 과정에서 임의의 유효 상태에 대하여 계산된 최소 상태 확률이 최소 비유사성 스코어(Min) 값보다 작은 경우에 유효 상태를 이용하여 계산된 확률을 그대로 최소 상태 확률[Φ'_i(t)]로 사용한다. 또한 두번째의 제2 기준 정보 모델에 대한 적정 경로에서 찾아진 적정 경로 값(B)이 최소 비유사성 스코어(Min=A)보다 작다면, 최소 비유사성 스코어(A)는 적정 경로 값(B)으로 갱신되지만, 그렇지 않은 경우 최소 비유사성 스코어(Min)는 기존의 확률(A)을 그대로 유지한다. 첫번째의 제1 기준 정보 모델을 제외한 사전에 저장된 모든 기준 정보 모델들에 대하여 이와 같은 동작들은 반복된다. 참고로, 적정 경로 값 및 적정 경로를 찾는 과정을 살펴보면, 하나의 기준 정보 모델에 대해 유효상태가 확장 가능한 경로들을 따라서 탐색을 진행하면서 시간 T가 경과했을 때 즉, 현재 시간 T에서 탐색된 해당 상태들의 최소 상태 확률들중 가장 작은 최소 상태 확률이 적정 경로 값으로 결정되고, 이적정 경로 값인 최소 상태 확률이 계산될 때까지 사용된 유효 상태들로 이루어진 경로가 적정 경로로서 찾아진다. 예를 들면, 도 4에 도시된 바와 같이 상태들(1, 5, 10, 15, 19 및 24)을 연결하여 적정 경로를 찾을 수 있으며, 적정 경로상에 존재하는 상태들(1, 5, 10, 15, 19 및 24)에서 시간의 흐름상 경로의 가장 끝에 있는 상태(24)의 최소 상태 확률이 적정 경로 값이다.

제102 단계 후에, 모든 기준 정보 모델들에 대하여 적정 경로 값들이 모두 구해졌는가를 판단한다(제104 단계). 즉, 적정 경로 값은 기준 정보 모델들의 수만큼 구해진다. 만일, 모든 기준 정보 모델들에 대하여 적정 경로 값들이 모두 구해지지 않았으면 제100 단계로 진행하여 나머지 기준 정보 모델에 대한 적정 경로 값들을 구하기 위해 제100 및 제102 단계들을 수행한다. 그러나, 적정 경로 값들이 모두 구해졌으면, 제122 단계에서 최소 비유사성 스코어(Min)를 가장 나중에 갱신할 때 사용한 적정 경로 값이 구해진 기준 정보 모델을 미지 정보에 가장 유사한 모델로서 결정한다(제106 단계). 예컨데, 모든 기준 정보 모델에 대한 적정 경로 값들이 모두 구해졌을 경우, 제102 단계에서 갱신된 최소 비유사성 스코어(Min)는 결국 모든 적정 경로 값들중 가장 작은 적정 경로 값에 해당하게 된다. 이 때, 적정 경로 값이 된 최소 상태 확률은 미지 정보와 상태가 가장 유사하지 않을 확률이 가장 적은 값이므로, 유사 확률이 가장 크다는 뜻과 동일한 의미이다. 그러므로 가장 작은 적정 경로 값이 구해진 기준 정보 모델은 미지의 정보와 가장 유사한 모델에 상당하게 된다.

도 6은 도 5에 도시된 정보 탐색 방법의 본 발명에 의한 바람직한 일실시예의 플로우차트로서, 제120 단계를 수행하는 단계(제146 ∼ 제164 단계들), 제122 단계를 수행하는 단계(제166 및 제168 단계들), 제124 단계를 수행하는 단계(제170 및 제172 단계들), 제126 단계를 수행하는 단계(제174 및 제176 단계들), 제102 단계를 수행하는 단계(제178 및 제180 단계들) 및 제104 단계를 수행하는 단계(제182 및 제184 단계들)로 이루어진다.

먼저 제120 단계를 수행하기 위해, 각종 변수들을 초기화한다. 예컨대, 최소 비유사성 스코어(Min)를 소정값 예를 들어, 무한대(∞)로 설정한다(제146 단계). 도 6에 도시된 바와 같이, 기준 정보 모델들중 첫 번째 기준 정보 모델에 대해서만 소정값은 무한대로 정해진다. 제146 단계후에, 변수 k(여기서, k는 현재 탐색되는 기준 정보 모델의 위치를 나타내는 변수로서 1≤k≤M이고, M은 기준 정보 모델들의 개수를 의미한다.)를 '1'로 설정한다(제148 단계). 제148 단계후에, 변수 t를 '1'로 설정한다(제150 단계). 제150 단계후에, 변수 i를 '1'로 설정한다(제152 단계). 제152 단계후에, 현재 시간이 t라고 할 때, 이 시간 t에서 탐색되는 i번째 해당 상태가 갖는 최소 상태 확률[Φ'_i(t)]을 소정값 예를 들면, 무한대(∞)로 설정한다(제154 단계). 제154 단계후에, 변수 j(여기서, j는 도 4에 도시된 상태 격자에서 이전 시간 t-1에서 탐색된 이전 상태를 나타내는 변수이며 j는 가로축인 X축에 해당하며, 1≤j≤N의 범위를 갖는다.)를 '1'로 설정한다(제156 단계). 제156 단계후에, 현재 시간이 t일 때 이전 시간 t-1에서 탐색된 상태가 갖는 최소 상태 확률 즉, 이전 시간 t-1까지의 탐색경로 상에서 누적된 확률[Φ_ij(t-1)]이 유효한가를 판단한다(제158 단계). 이를 위해, 이전에 누적된 상태 확률[Φ_ij(t-1)]이 무한대(∞)인가를 판단할 수 있다. 만일, 이전 시간 t-1까지의 탐색경로 상에서 누적된 확률[Φ_ij(t-1)]이 무한대(∞)가 아니면, 현재 시간 t에서 탐색된 해당 상태가 갖는 최소 상태 확률[Φ'_i(t)]은 다음 수학식 1과 같이 결정된다(제160 단계).

여기서, a_ij는 천이확률을 의미하고, b_ijW(t)는 상태 관측 확률을 의미한다. W(t)는 심볼 시퀀스(symbol sequence)로서 시퀀스의 시간 열에 대한 t번째 발음이라는 의미이며, b_ij는 그 심볼 시퀀스에 대한 확률 값을 나타내고, 수학식 1의 [ ]에서 계산된 결과는 상태 확률에 해당하고, min[ ]은 상태 확률들중 가장 적은 확률을 의미한다.

결국, 제160 단계에서는 이전 시간 t-1에서 탐색된 유효 상태들 각각이 가지며 이전 시간 t-1까지의 탐색경로 상에서 누적된 확률인 최소 상태 확률[Φ_ij(t-1)]을 수학식 1의 [ ]에 대입하여 i번째 해당 상태의 상태 확률을 시간 t-1에서 탐색된 유효 상태의 개수만큼 구한다. 이와 같이 구해진 i번째 해당 상태의 상태 확률들중 가장 작은(수학식 1에서 'min'이 의미한다.) 확률을 해당 상태의 최소 상태 확률[Φ'_i(t)]로서 결정한다. 이 때, 종래의 음성 탐색 방법은 도 2에 도시된 제7 단계에서 상태 확률들중 최대의 확률인 최대 상태 확률[Φ_i(t)]을 구하는 반면, 본발명에 의한 정보 탐색 방법은 수학식 1로부터 알 수 있듯이, 상태 확률들중에서도 최소의 확률을 최소 상태 확률[Φ'_i(t)]로서 구함을 알 수 있다. 즉, 본 발명에 의한 정보 탐색 방법은 사전에 저장된 기본 정보 모델이 미지의 정보일 확률'을 사용하는 것이 아니라 '기본 정보 모델이 미지의 정보가 아닐 확률'을 이용하여 입력된 미지의 정보가 어떤 기준 정보 모델과 유사한가를 즉, 유사성을 계산하고, 후술되는 바와 같이 계산된 결과를 이용하여 미지의 정보를 인식한다.

또한, 수학식 1로부터 알 수 있듯이, '1' 미만의 소수로 이루어진 확률을 계산할 때, 대수(logarithm)를 사용해서 로그(log)값으로 확률을 변환함을 알 수 있다. 이는 다음과 같은 두 가지의 잇점들을 갖는다. 첫 번째 이점으로, 전체적으로 확률을 계산할 때 자리수가 줄어들어 해상도(resolution) 측면에서 이득이 있다는 것이다. 예를 들면, 구해진 확률이 0.00000...001(1×10^-31) 이라면 이 값을 소수로 표현하기 위해 차지해야 하는 자리수는 소수점을 포함하여 32개이다. 그러나, 이 값을 로그값으로 변환하면 '-31'로 변환되어 이 값(-31)을 표현하기 위해 차지하는 자리수는 부호를 포함하여 3개면 충분하다. 두 번째 이점으로, 곱셈 연산들이 덧셈 연산들로 모두 바뀌어 후술되는 본 발명에 의한 정보 탐색 장치의 설명에서 언급되는 바와 같이 계산량이 줄어들 수 있음을 알 수 있다. 하드웨어의 설계시에 덧셈 연산은 곱셈 연산보다 계산량을 줄일 수 있을 뿐만 아니라 전력 소모도 줄일 수 있다.

한편, 제158 단계에서, 이전 시간 t-1까지의 탐색경로 상에서 누적된 확률[Φ_ij(t-1)]이 무한대(∞)이면, 즉, 이전 시간 t-1에서 탐색된 상태가 유효 상태가 아니면, 이전 시간 t-1에서 탐색된 상태들중 j번째 상태의 누적된 상태 확률[Φ_ij(t-1)]을 이용하여 시간 t에서의 i번째 상태의 상태 확률[Φ_ij(t)]을 구하는 것이 아니라 변수 j가 N이하인가를 판단한다(제162 단계). 이는 이전 시간 t-1까지의 탐색경로 상에서 누적된 확률[Φ_ij(t-1)]의 옆에 존재하는 또 다른 이전 시간 t-1까지의 탐색경로 상에서 누적된 확률[Φ_i(j+1)(t-1)]의 유효성을 판단하여 i번째 상태의 또 다른 상태 확률[Φ_i(j+1)(t)]을 구하기 위해서이다. 부연하면, 이전 시간인 t-1까지의 경로 탐색 과정에서 누적된 확률[Φ_ij(t-1)]이 무한대(∞)인 경우에는 이 상태 확률[Φ_ij(t-1)]을 이용하여 현재 시간 t에서의 i번째 상태의 상태 확률[Φ_ij(t)]을 구하지 않는다. 왜냐하면, Min이라는 값은 적정 경로를 찾았을 때, 적정 경로 상에서 가장 마지막 시간(T)에 존재하는 해당 상태들의 최소 상태 확률들중 가장 작은 최소 상태 확률에 의해 구해지고, 새로운 적정 경로를 찾는 중간단계에서 이 값(Min)보다 큰 값[Φ'_ij(t) 〉 Min]들은 이후로 계속해서 진행되는 적정 경로를 찾는 과정에서 값이 작아진다는 것은 불가능하므로, 더 이상 불필요한 계산이 이루어지지 않도록 탐색 경로에서 제거하기 위함이다. 예를 들면, 도 4에 도시된 바와 같이, 슬래쉬(/)가 그어진 비유효 상태들(13, 14, 17, 18, 21, 22 및 23)은 탐색 경로에서 제거되며, 이 상태들을 지나는 경로에 대해서는 확률을 계산하는 연산이 수행되지 않는다. 검은색의 상태들(1, 5, 10, 15, 19 및 24)로 이루어진 경로가 최소비유사성 스코어(Min)를 갱신할 때 사용될 수 있는 적정 경로 값이 구해지는 적정 경로에 해당한다. 결국, 현재 시간 t에서 탐색하는 해당 상태의 최소 상태 확률 계산을 수행할 때, 이전 시간 t-1까지의 탐색 경로상에서 누적된 확률[Φ_ij(t-1)]이 무한대인 비유효 상태의 최소 상태 확률을 이용하지 않으므로 정보 탐색을 위한 계산 시간 및 소비 전력이 절감될 수 있다. 만일, 변수 j가 N이하이면, 변수 j를 1만큼 증가시키고 제158 단계로 진행한다(제164 단계). 그러나, 변수 j가 N보다 크면, i번째 상태에 대해서는 탐색이 종료되었으므로 제166 단계로 진행한다.

제122 단계를 수행하기 위해, i번째 최소 상태 확률[Φ'_i(t)]이 최소 비유사성 스코어(Min)보다 큰가를 판단하여, 최소 상태 확률[Φ'_i(t)]이 최소 비유사성 스코어(Min)보다 크지 않으면, 제170 단계로 진행한다(제166 단계). 그러나, 최소 상태 확률[Φ'_i(t)]이 최소 비유사성 스코어(Min)보다 크면 i번째에 존재하는 상태의 최소 상태 확률[Φ'_i(t)]을 무한대(∞)로 설정한다(제168 단계).

제124 단계를 수행하기 위해, 최소 상태 확률[Φ'_i(t)]이 최소 비유사성 스코어(Min)보다 크지 않거나 제168 단계후에, 변수 i가 N이하인가를 판단하여 변수 i가 N이하가 아니면 제174 단계로 진행한다(제170 단계). 그러나, 변수 i가 N이하이면 변수 i를 1만큼 증가시키고 제154 단계로 진행한다(제172 단계). 이는, 현재 시간 t에 존재하는 N개 모든 해당 상태들(i=1 ∼ N)에 대해서 상태 확률을 구하기 위함이다.

제126 단계를 수행하기 위해서, 변수 i가 N이하가 아니면, 변수 t가 T이하인가를 판단하여 변수 t가 T이하가 아니면 제178 단계로 진행한다(제174 단계). 그러나, 변수 t가 T이하이면 변수 t를 1만큼 증가시키고 제152 단계로 진행한다(제176 단계). 이는, 소정 시간(T)동안 매 시간(t)마다 N개의 상태들에 대한 최소 상태 확률들을 모두 구하기 위함이다.

제102 단계를 수행하기 위해서, 적정 경로 값이 최소 비유사성 스코어(Min)보다 적은가를 판단하여, 적정 경로 값이 최소 비유사성 스코어(Min)보다 적지 않으면 최소 비유사성 스코어(Min)는 갱신되지 않고 그대로 유지되며 제182 단계로 진행한다(제178 단계). 그러나, 적정 경로 값이 최소 비유사성 스코어(Min)보다 적으면 최소 비유사성 스코어(Min)를 적정 경로 값으로 갱신한다(제180 단계).

제104 단계를 수행하기 위하여, 적정 경로 값이 최소 비유사성 스코어(Min)보다 적지 않거나 제180 단계후에, 변수 k가 M이하인가를 판단하여 변수 k가 M이하가 아니면 제106 단계로 진행한다(제182 단계). 그러나, 변수 k가 M이하이면 변수 k를 1만큼 증가시키고 제150 단계로 진행한다(제184 단계). 이는, 모든 기준 정보 모델들에 대한 적정 경로 값들중 가정 적은 적정 경로 값을 최소 비유사성 스코어(Min)의 갱신에 사용될 수 있도록, 나머지 기준 정보 모델에 대한 적정 경로 값을 구하기 위함이다.

결국, 전술한 본 발명에 의한 IHMM을 이용한 정보 탐색 방법은 현재 시간 t에서 탐색하는 어느 해당 상태의 최소 상태 확률을 구하기 위해서, 이전 시간 t-1에서 탐색된 상태들중 유효 상태들 각각이 가지며 이전 시간 t-1까지의 탐색경로상에서 누적된 확률인 최소 상태 확률만을 이용하고, 이전 시간 t-1에서 탐색된 상태들중 유효 상태가 아닌 비유효 상태들 각각이 가지며 이전 시간 t-1까지의 탐색경로 상에서 누적된 확률인 최소 상태 확률은 이용하지 않는다. 그러므로, 본 발명에 의한 정보 탐색 방법은, 불필요한 계산을 피할 수 있도록 하는 한편, 이러한 불필요한 계산에 소비되는 전력의 소모도 줄일 수 있다.

이하, 전술한 IHMM을 이용한 정보 탐색 방법을 수행하는 본 발명에 의한 IHMM을 이용한 정보 탐색 장치의 구성 및 동작을 첨부한 도면들을 참조하여 다음과 같이 설명한다.

도 7은 도 5 또는 도 6에 도시된 방법을 수행하는 본 발명에 의한 IHMM을 이용한 정보 탐색 장치의 블럭도로서, 저장부(200), 제1, 제2, ..., 제i, ... 및 제N 연산부들(210, 212, ..., 214, ... 및 216), 제1, 제2, ..., 제i, ... 및 제N 비교 선택부들(220, 222, ..., 224, ... 및 226), 제어부(228) 및 버퍼(230)로 구성된다.

도 7에 도시된 저장부(200)는 데이타들 즉, 최소 비유사성 스코어(Min)(206), 천이 확률(a_ij)과 관련되는 제1 값(a'_ij)(204), 상태 관측 확률과 관련되는 제2 값[b'_ijW'(t)](202)을 저장한다. 여기서, 제어부(228)로부터 출력되는 독출 제어 신호(232)에 응답하여, 저장부(200)는 데이타들중 제1 및 제2 값들(204 및 202)을 제1, 제2, ..., 제i, ... 및 제N 연산부들(210, 212, ..., 214, ... 및 216)로 출력하고, 최소 비유사성 스코어(Min)(206)를 제1, 제2, ..., 제i, ... 및제N 비교 선택부들(220, 222, ..., 224, ... 및 226)로 출력한다. 이 때, 저장부(200)는 천이 확률(a_ij) 및 상태 관측 확률[b_ijW(t)]을 로그값으로 변환하고, 변환된 값들에 대해 양수로 바뀐 결과들인 제1 및 제2 값들[a'_ij및 b_ij'W'(t)]을 저장할 수 있다. 즉, 천이 확률과 관련되는 제1 값 및 상태 관측 확률과 관련되는 제2 값은 양수값에 해당할 수 있다. 이와 같이 로그값으로 변환된 값을 양수값으로 다시 변환하는 이유는, '1' 보다 적은 소수로 표현되는 확률을 로그로 변환하면 음수가 발생하기 때문이다. 그러므로, 연산에 사용되어지는 수가 음수이기 때문에 발생할 수 있는 연산에 관련된 하드웨어 설계상의 문제점과 연산 과정에서의 오버 플로우(overflow)등의 문제점들을 미연에 방지할 수 있다. 결국, 본 발명에 의한 정보 탐색 장치는 음수를 양수로 변환하여 부호의 영향을 고려하지 않고 연산을 수행할 수 있다.

제1, 제2, ..., 제i, ... 및 제N 연산부들(210, 212, ..., 214, ... 및 216)중 하나인 제i 연산부(214)는, 버퍼(230)로부터 출력되는 값과 저장부(200)로부터 입력한 제1 값 및 제2 값(204 및 202)을 연산하고, 연산된 결과들중 가장 적은 연산된 결과를 제어 신호(C)에 응답하여 비교하고, 비교된 결과들중 가장 적은 연산된 결과를 i번째 해당 상태에 대한 가장 작은 상태 확률인 최소 상태 확률로서 제i 비교 선택부(224)로 출력한다. 예를 들어, 현재 시간이 t라고 할 때, 제i 연산부(214)는 버퍼(230)로부터 출력되는 값 예를 들면, [Φ_i1(t-1), Φ_i2(t-1), Φ_i3(t-1), ..., Φ_ij(t-1), ... 및 Φ_iN(t-1)]와 저장부(200)로부터 입력한 천이 확률과 관련되는 제1 값(a'_i1, a'_i2, a'_i3, ... 및 a'_iN)(204) 및 상태 관측 확률과 관련되는 제2 값[b'_i1W'(t), b'_i2W'(t), b'_i3W'(t), ... 및 b'_iNW'(t)](202)을 가산하고, 가산된 결과들을 제어부(228)로부터 출력되는 제어 신호(C)에 응답하여 비교하여 가장 적은 가산된 결과를 선택하고, 선택된 가장 적은 가산된 결과를 i번째 해당 상태에 대한 가장 작은 상태 확률인 최소 상태 확률[Φ'_i(t)]로서 제i 비교 선택부(224)로 출력한다. 여기서, 연산부들의 개수는 상태의 수(N)와 동일함을 알 수 있다. 이 때, 도 7에 도시된 각 연산부는 도 5에 도시된 제120 단계 또는 도 6에 도시된 제160 단계를 수행함을 알 수 있고, 도 6에 도시된 제170 및 제172 단계의 역할은 도 7에 도시된 바와 같이 N개의 연산부들을 병렬로 연결함으로서 수행될 수 있다. 즉, i를 1만큼 계속적으로 증가시킬 필요없이, 병렬로 연결된 연산부들 각각에서 하나의 해당 상태에 대한 최소 상태 확률을 출력시킴으로써 N개의 해당 상태들에 대한 N개의 최소 상태 확률이 동시에 출력된다.

이하, 현재 시간이 t이고, 이전 시간이 t-1라고 가정할 때, 현재 시간 t에서 탐색되는 해당 상태의 최소 상태 확률[Φ'_i(t)]을 구하는 도 7에 도시된 각 연산부의 본 발명에 의한 바람직한 일실시예의 구성 및 동작을 첨부한 도면을 참조하여 다음과 같이 설명한다.

도 8은 도 7에 도시된 제i 연산부(214)의 본 발명에 의한 일실시예의 블럭도로서, 제1, 제2, 제3, ... 및 제N 가산부들(250, 252, 254, ... 및 256) 및 최소값 선택부(258)로 구성된다. 여기서, 제1 가산부(250)는 두개의 가산기들(270 및 272)로 구성되고, 제2 가산부(252)는 두개의 가산기들(274 및 276)로 구성되고, 제3 가산부(254)는 두개의 가산기들(278 및 280)로 구성되고, 제N 가산부(256)는 두개의 가산기들(282 및 284)로 구성된다.

도 8에 도시된 가산부들(250, 252, 254, ... 및 256)중 하나인 제i 가산부는 버퍼(230)로부터 출력되는 이전 시간 t-1까지 누적된 상태 확률[Φ_ij(t-1)]과 제1 값(a'_ij)(204)과 제2 값[b'_ijW'(t)](202)을 가산하고, 가산된 결과를 최소값 선택부(258)로 출력한다. 예를 들어, 제1 가산부(250)의 제1 가산기(270)는 제1 값(a'_i1)과 제2 값[b'_i1W'(t)]을 가산하고, 가산된 결과를 제2 가산기(272)로 출력하며, 제2 가산기(272)는 제1 가산기(270)에서 가산된 결과와 버퍼(230)로부터 출력되는 이전 시간 t-1까지 누적된 상태 확률[Φ_i1(t-1)]을 가산하고, 가산된 결과를 최소값 선택부(258)로 출력한다. 제2, 제3, ... 및 제N 가산부들(252, 254, ... 및 256) 각각에 포함된 가산기들은 제1 가산부(250)와 동일하게 세개의 값들[Φ_ij(t-1), a'_ij및 b'_ijW'(t)]을 도 8에 도시된 바와 같이 가산하는 동작을 수행한다.

최소값 선택부(258)는 제1 ∼ 제N 가산부들(250, 252, 254, ... 및 256)에서 가산된 결과들을 제어부(228)로부터 출력되는 제어 신호(C)에 응답하여 비교하여 제1 ∼ 제N 가산부들(250, 252, 254, ... 및 256)에서 가산된 결과들중 가장 작은 가산된 결과를 선택하고, 선택된 가장 작은 가산된 결과를 현재 시간 t에서 탐색된 i번째 해당상태가 갖는 최소 상태 확률[Φ'_i(t)]로서 해당하는 제i 비교선택부(224)로 출력한다. 예를 들어, N=4인 경우, 최소값 선택부(258)는 제1, 제2 및 제3 비교기들(미도시)로 구성될 수 있으며, 제1 비교기(미도시)는 제2 가산기(272)에서 가산된 결과와 제4 가산기(276)에서 가산된 결과중 적은 값을 비교 동작에 의해 선택하고, 제2 비교기(미도시)는 제6 가산기(280)에서 가산된 결과와 제8 가산기(284)에서 가산된 결과중 적은 값을 비교 동작에 의해 선택한다. 이 때, 제3 비교기(미도시)는 제1 비교기(미도시)에서 선택된 값과 제2 비교기(미도시)에서 선택된 값중 적은 값을 비교 동작에 의해 선택하고, 선택된 결과를 최소 상태 확률[Φ'_i(t)]로서 출력한다.

한편, 버퍼(230)로부터 출력되어 도 8에 도시된 각 가산부로 입력되는 값은 전술한 바와 같이, 이전 시간 t-1까지 누적된 상태 확률[Φ_ij(t-1)]에 국한되지 않으며, 후술되는 바와 같이 이전 시간 t-2까지 누적된 상태 확률[Φ_ij(t-2)]이 될 수도 있다.

결국, 본 발명에 의한 정보 탐색 장치의 도 8에 도시된 각 연산부는 도 6에 도시된 제160 ∼ 제164 단계들 수행한다. 특히, 도 6에 도시된 제162 및 제164 단계들의 역할은 도 8에 도시된 바와 같이 가산부들(250, 252, 254,, .... 및 256)을 병렬로 마련함으로서 수행될 수 있다. 예를 들어, N=4인 경우 도 8에 도시된 각 연산부에서, 한 상태당 계산되어지는 단수는 2단이고, 병렬로 연산을 진행하면 덧셈기 8개와 비교기 3개가 필요함을 알 수 있다.

전술한 도 8에 도시된 제i 연산부(214)는 이전 시간 t-1까지 누적된 상태 확률[Φ_ij(t-1)], 제1 값(a'_i1) 및 제2 값[b'_i1W'(t)]을 입력하여 현재 시간 t에서 탐색된 i번째 해당 상태가 갖는 최소 상태 확률[Φ'_i(t)]을 출력하였다. 또한, 제i 연산부(214)는 현재 시간 t까지 누적된 상태 확률[Φ_ij(t)], 제1 값(a'_i1) 및 제2 값[b'_i1W'(t+1)]을 입력하여 다음 시간 t+1에서 탐색될 i번째 해당상태가 갖는 최소 상태 확률[Φ'_i(t+1)]을 출력할 수도 있다. 이와 같이, 제i 연산부(214)는 소정 시간(T)동안 매 시간 t에서 탐색된 i번째 상태가 갖는 최소 상태 확률을 구하는데 적용될 수 있다.

한편, 제i 비교 선택부(224)는 제i 연산부(214)로부터 출력되는 가장 적은 연산된 결과인 최소 상태 확률[Φ'_i(t)]과 저장부(200)로부터 입력한 최소 비유사성 스코어(Min)를 비교하고, 비교된 결과에 응답하여 최소 상태 확률[Φ'_i(t)]과 소정값 예를 들면 무한대(∞)중 하나를 선택하고, 선택된 결과를 제어부(228)로 출력하는 한편, 비교된 결과에 상응하는 레벨을 갖는 비교 플래그(flag)를 제어부(228)로 출력한다. 즉, 제i 비교 선택부(224)는 도 6에 도시된 제166 및 제168 단계들을 수행한다. 예를 들어, 제1 비교 선택부(220)는 제1 연산부(210)로부터 출력되는 최소 상태 확률[Φ'₁(t)]을 최소 비유사성 스코어(Min)와 비교하고, 비교된 결과에 응답하여 최소 상태 확률[Φ'₁(t)] 또는 소정값을 제어부(228)로 출력한다. 예컨데, 제i 비교 선택부(224)는 먼저 제i 연산부(214)로부터 출력되는 최소 상태 확률[Φ'_i(t)]이 최소 비유사성 스코어(Min)보다 큰가를 비교 동작에 의해 판별한다(제166 단계). 다음에, 제i 비교 선택부(224)는 최소 상태 확률[Φ'_i(t)]이 최소 비유사성 스코어(Min)보다 크다고 판단되면 소정값 즉, 무한대(∞)를 선택하여 제어부(228)로 출력한다. 즉, 제166 및 제168 단계들이 수행된다. 그러나, 제i 비교 선택부(224)는 최소 상태 확률[Φ'_i(t)]이 최소 비유사성 스코어(Min)보다 크지 않다고 판단되면 최소 상태 확률[Φ'_i(t)]을 선택하여 제어부(228)로 출력한다. 즉, 제i 비교 선택부(224)는 제166 단계를 수행한 결과 제168 단계를 생략시킨다.

이를 위해, 제i 비교 선택부(224)는 제i 연산부(214)로부터 출력되는 최소 상태 확률[Φ'_i(t)]과 최소 비유사성 스코어(Min)를 비교하고, 비교된 결과를 출력하는 비교부(미도시) 및 제i 연산부(214)로부터 출력되는 최소 상태 확률[Φ'_i(t)] 또는 소정값중 하나를 비교부(미도시)로부터 출력되는 비교된 결과에 응답하여 선택적으로 출력하는 선택부(미도시)로 구현될 수 있다. 이 때, 제i 비교 선택부(224)의 비교부(미도시)로부터 출력되는 비교된 결과는 비교 플래그(flag)가 될 수 있다.

제어부(228)는 제1 ∼ 제N 비교 선택부들(220, 222, ..., 224, ... 및 226) 각각으로부터 출력되는 비교 플래그에 응답하여 제어 신호(C)를 출력한다. 즉, 제어부(228)는 도 6에 도시된 제158 단계를 수행한다. 예를 들어, 제i 비교 선택부(224)의 비교부(미도시)가 최소 상태 확률[Φ'_i(t)]이 최소 비유사성스코어(Min)보다 클 때 "고" 논리 레벨을 갖는 비교된 결과를 비교 플래그로서 제어부(228)로 출력하고, 최소 상태 확률[Φ'_i(t)]이 최소 비유사성 스코어(Min)보다 크지 않을 때 "저" 논리 레벨을 갖는 비교된 결과를 비교 플래그로서 제어부(228)로 출력한다고 하자. 이 때, 제어부(228)는 제i 비교 선택부(224)로부터 출력되는 비교 플래그가 "고" 논리 레벨이면 다음 시간 t+1에서 도 8에 도시된 최소값 선택부(258)가 비교동작을 수행하지 않도록 제어 신호(C)를 발생한다. 그러나, 제어부(228)는, 제i 비교 선택부(224)에서 출력되는 비교 플래그가 "저" 논리 레벨이면 다음 시간 t+1에서 도 8에 도시된 최소값 선택부(258)가 비교 동작을 수행하도록 제어 신호(C)를 발생한다.

또한, 제어부(228)는 제1 ∼ 제N 비교 선택부들(220, 222, ..., 224, ... 및 226)로부터 출력되는 값들(234)을 그대로 버퍼(230)로 바이패스한다. 즉, 제어부(228)는 제i 비교 선택부(224)로부터 출력되는 최소 상태 확률[Φ'_i(t)] 또는 소정값을 그대로 버퍼(230)로 바이패스시킨다.

버퍼(230)는 제어부(228)로부터 바이패스된 값들(234)을 그대로 입력하여 버퍼링하고, 버퍼링된 값들을 제어부(228)로부터 출력되는 제어 신호(C)에 응답하여 제1 ∼ 제N 연산부들(210, 212, ..., 214, ... 및 216)로 출력한다. 즉, 제i 비교 선택부(224)로부터 출력되는 값이 최소 상태 확률[Φ'_i(t)]인 경우에 제어부(228)로부터 발생되는 제어 신호(C)에 응답하여, 버퍼(230)는 버퍼링된 결과[Φ'_i(t)]를 다음 시간 t+1에서 제i 연산부(214)로 출력한다.

그러나, 제i 비교 선택부(224)로부터 출력되는 값이 소정값인 경우에 제어부(228)로부터 발생되는 제어 신호(C)에 응답하여, 버퍼(230)는 시간 t에서 제i 연산부(214)로 출력했던 최소 상태 확률[Φ'_i(t-1)]을 다음 시간 t+1에서도 계속하여 제i 연산부(214)로 출력한다. 따라서, 제i 연산부(214)는 다음 시간 t+1에서 탐색되는 다음 상태의 최소 상태 확률[Φ'_i(t+1)]을 계산할 때 버퍼(230)로부터 이전에 출력되었던 최소 상태 확률[Φ'_i(t-1)]을 다시 한번 제1 및 제2 값들과 가산한다. 그러므로, 시간 t나 시간 t+1에서 제i 연산부(214)의 각 가산부는 동일한 값들을 가산하므로, 시간 t+1에서 불필요한 가산 동작을 수행하지 않는 것과 동일한 효과를 제공하여, 가산부들에서 소모되는 전력 소모 및 계산 시간을 절감시킬 수 있도록 한다.

결국, 본 발명에 의한 정보 탐색 장치는 제i 비교 선택부(224)로부터 출력되는 값이 소정값인 경우, 제어부(228)로부터 출력되는 제어 신호(C)에 응답하여 최소값 선택부(258)에 내장된 비교기들(미도시)을 동작시키지 않고, 버퍼(230)를 제어하여 가산부들에 내장된 각 가산기들이 가산동작을 수행하지 않는 것과 동일한 효과를 제공할 수 있도록 한다. 그러므로, 불필요한 비교 및 가산 동작들이 제거되어 전력 소모와 계산 시간이 단축될 수 있다.

전술한 본 발명에 의한 IHMM을 이용한 정보 탐색 방법 및 장치는 음성 정보를 탐색하기 위해 적용될 수도 있다. 여기서, 음성 정보는 고립 단어 또는 연속 음성이 될 수 있다. 이 경우, 기준 정보 모델은 기본 음성 모델에 해당하고, 미지의정보는 외부에서 주어지는 미지의 음성에 해당하고, 정보 상태는 음성 상태에 각각 해당하게 된다.

결국, 최대 유사성 스코어를 위해 사용되는 확률은 기준 정보 모델이 주어진 미지의 정보와 유사할 유사 확률을 의미한다. 그러므로, 유사성이 높을수록 확률의 크기를 크게되는 것이다. 그러나, 전술한 최소 비유사성 스코어에서 사용하는 확률은 주어진 미지의 정보가 기준 정보 모델이 아닐 확률 즉, '1'에서 유사 확률을 감산한 비유사성의 정도를 나타내는 확률을 의미한다. 이와 같이, 전술한 본 발명에 의한 IHMM을 이용한 정보 탐색 방법 및 장치는 유사 확률을 이용하지 않고 비 유사확률을 이용하였다. 그러므로, 주어진 미지의 정보가 기준 정보 모델과 유사하지 않을 확률이 적을수록 기준 정보 모델이 미지의 정보일 확률이 높아진다. 이와 같이, 유사 확률을 이용하여 최대 유사성 스코어를 갖는 기준 정보 모델을 찾는 종래의 방법과 비유사 확률을 이용하여 최소 비유사성 스코어를 갖는 기준 정보 모델을 찾는 본 발명에 의한 방법은 결과적으로 동일하게 미지의 정보를 인식하는 결과를 발생시킨다. 그러나, 본 발명에 의한 정보 탐색 방법은 종래의 방법과 달리 계산량과 계산시간에 있어서 차이가 매우 크다. 이러한 차이에 대해 다음과 같이 살펴본다.

1994년에 "A Real-Time Isolated Word Recognition System"라는 제목으로 Yun-Seok Cho와 Hwang-Soo Lee에 의해 공동으로 발표된 ISPACS 회보에 개시된 조건하에서 "ABBAT"라는 음성 정보를 탐색한다고 가정한다. 이러한 가정하에서, Synopsys 회사의 시뮬레이션 툴(tool)에 의해 종래의 방법과 본 발명에 의한 정보탐색 방법을 비교해 보면, 본 발명에 의한 정보 탐색 방법은 다음 표 1에 도시된 바와 같이 종래의 방법에 대비하여 계산량을 68.57%로 줄일 수 있음을 알 수 있다.

시간(t)에서 제거된 상태의 수	계산량(The consumption of computation)
0(총 계산)	P + 4 ×NC
1	P - (NA ×2 + NM × 1) × 4 + 4 × NC
2	P - (NA ×4 + NM × 2) × 4 + 4 × NC
3	P - (NA ×6 + NM × 3) × 4 + 4 × NC
4	- P

표 1에서, P는 최대 유사성에 기반한 종래의 비터비 탐색 방법에 의존할 경우의 총 계산량으로서 32개의 덧셈기들과 12개의 최대화 선택기들로 이루어지고, NC는 도 7에 도시된 장치에서 비교 연산의 횟수 즉, 비교 선택부들(220, 222, ..., 224, ... 및 226)의 수를 의미하고, NA는 도 8에 도시된 장치에서 덧셈 연산의 횟수 즉, 덧셈기들(270, 272, 274, 276, 278, 280, ..., 282 및 284)의 수를 의미하고, NM은 도 8에 도시된 최소값 선택부(258)에 마련될 수 있는 비교기들(미도시)의 수를 의미한다.

한편, 본 발명에 의한 방법 및 장치에 의존하여 정보를 탐색할 경우, 종래의 음성 정보를 탐색하는 방법에 대비하여, 비교 선택부들(220, 222, 224, ... 및 226) 및 제어부(228)의 부가로 인하여 게이트의 수가 다음 표 2와 같이 72.9% 증가하였음을 알 수 있다.

종래의 연산부(PE)에 마련되는 게이트 수	본 발명에 의한 장치에서 연산부에 마련되는 게이트의 수
3516 게이트	6080 게이트

이상에서 설명한 바와 같이, 본 발명에 의한 IHMM을 이용한 정보 탐색 방법 및 장치는 HMM 경로 매트릭스에서 최대 유사성 스코어 대신에 최소 비유사성 스코어를 이용하여 유효 경로들 각각이 가지며 이전 시간 t-1까지의 탐색경로 상에서 누적된 확률인 최소 상태 확률만을 이용하여 현재 시간 t에서 탐색되는 해당 상태의 최소 상태 확률의 계산을 수행하기 때문에 정보 탐색을 위한 계산 시간과 계산량을 줄일 수 있어 적은 전력을 소모하면서도 빠른 시간내에 정보를 탐색할 수 있고, 이로 인하여 정보 인식에 요구되는 비용들중 탐색에 필요한 계산 비용을 절감시킬 수 있고, 적은 소비 전력으로 긴 시간동안 정보를 탐색할 수 있는 효과를 갖는다.

Claims

외부로부터 주어지며 히든 마르코브 모델(HMM)을 서로 연결하여 표현될 수 있는 미지의 정보가 학습에 의해 구해진 소정의 기준 정보 모델들중 어느 모델에 해당하는가를 확률적으로 탐색하는 역 HMM(IHMM)을 이용한 정보 탐색 방법에 있어서,

(a) 상기 기준 정보 모델에 대한 상태 격자의 HMM 체인에 존재하는 상태들중 이전 시간 t-1에서 탐색된 유효 상태들 각각이 가지며 이전 시간 t-1까지의 탐색경로 상에서 누적된 확률인 최소 상태 확률을 이용하여 현재 시간 t에서 탐색되는 해당 상태의 최소 상태 확률을 구하고, 최소 비유사성 스코어보다 큰 상기 해당상태의 최소 상태 확률을 소정값으로 갱신하는 단계;

(b) 소정 시간(T〉t)이 경과되었을 때 구해진 상기 최소 상태 확률들중에서 가장 작은 확률에 해당하는 적정 경로 값보다 큰 상기 최소 비유사성 스코어를 상기 적정 경로 값으로 갱신하는 단계;

(c) 모든 상기 기준 정보 모델들에 대하여 상기 적정 경로 값들이 모두 구해졌는가를 판단하여, 모든 상기 기준 정보 모델들에 대하여 상기 적정 경로 값들이 모두 구해지지 않았으면 상기 적정 경로 값을 구할 다른 기준 정보 모델에 대하여 상기 (a) 및 상기 (b) 단계들을 반복하여 수행하는 단계; 및

(d) 모든 상기 기준 정보 모델들에 대하여 상기 적정 경로 값들이 모두 구해졌으면, 상기 최소 비유사성 스코어를 가장 나중에 갱신할 때 사용된 상기 적정 경로 값이 구해진 상기 기준 정보 모델을 상기 미지 정보에 가장 유사한 모델로서 결정하는 단계를 구비하고,

상기 (a)단계는 매 시간(t)에서 상기 해당 상태들에 대하여 상기 소정 시간(T) 동안 수행되고, 상기 유효 상태란 상기 이전 시간에서 탐색된 임의의 상태가 갖는 최소 상태 확률이 상기 최소 비유사성 스코어보다 적어 상기 해당 상태로 경로를 확장할 수 있는 상기 임의의 상태에 해당하고,

상기 해당 상태가 갖는 최소 상태 확률은 상기 유효상태들로부터 상기 해당 상태로 경로를 확장하기 위한 확률들 중에서 가장 작은 확률에 해당하는 것을 특징으로 IHMM을 이용한 정보 탐색 방법.
제1항에 있어서, 상기 해당 상태가 갖는 최소 상태 확률은

상기 유효 상태들 각각이 가지며 이전 시간 t-1까지의 탐색경로 상에서 누적된 확률인 상기 최소 상태 확률, 상기 유효 상태에서 상기 해당 상태로 천이하는 천이 확률, 상기 해당 상태에서의 관측 확률을 이용하여 상기 유효 상태들의 수만큼 구해진 상태 확률들중 가장 작은 확률에 해당하고,

상기 소정값은 상기 최소 비유사성 스코어보다 큰 것을 특징으로 하는 IHMM을 이용한 정보 탐색 방법.
제2항에 있어서, 상기 (a) 단계는

(a1) 상기 해당 상태에 대한 상기 최소 상태 확률을 구하는 단계;

(a2) 상기 (a1) 단계에서 구한 상기 최소 상태 확률이 상기 최소 비유사성 스코어보다 큰 경우에만 상기 해당 상태의 최소 상태 확률을 상기 소정값으로 갱신하는 단계;

(a3) 시간 t에서 탐색해야 하는 모든 상기 해당 상태들에 대한 상기 최소 상태 확률들이 모두 구해졌는가를 판단하여, 상기 해당 상태의 최소 상태 확률들이 모두 구해지지 않았으면 다른 해당 상태에 대하여 상기 (a1) 및 상기 (a2) 단계들을 반복하여 수행하는 단계; 및

(a4) 상기 해당 상태의 최소 상태 확률들이 모두 구해졌으면, 상기 소정 시간(T)이 경과하였는가를 판단하여, 상기 소정 시간(T)이 경과되었으면 상기 (b) 단계로 진행하고, 상기 소정 시간(T)이 경과되지 않았으면 다음 시간 t+1에서 상기 (a1)단계 ∼ (a3) 단계들을 반복하여 수행하는 단계를 구비하는 것을 특징으로 하는 IHMM을 이용한 정보 탐색 방법.
제3항에 있어서, 상기 (a1) 단계에서 상기 해당 상태의 최소 상태 확률[Φ'_i(t)]은 아래와 같이 구해지는 것을 특징으로 하는 IHMM을 이용한 정보 탐색 방법.

[여기서, a_ij는 상기 천이 확률을 의미하고, b_ij(W(t))는 상기 해당 상태에서의 상태 관측 확률을 의미한다. W(t)는 심볼 시퀀스(symbol sequence)로서 시퀀스의 시간 열에 대한 t번째 발음이라는 의미이며, b_ij는 그 심볼 시퀀스에 대한 확률 값을 나타낸다. 상기 Φ_ij(t-1)은 이전 시간 t-1까지의 탐색경로 상에서 누적된 확률인 최소 상태 확률을 의미하며, i는 시간 t에서 탐색되는 상태들을 나타내는 변수로서 1≤i≤N 이고, j는 시간 t-1에서 탐색되는 상태들을 나타내는 변수로서 1≤j≤N 이고, N은 상기 미지 정보를 구성하는 정보 상태들의 수를 의미하고, [ ]에서 계산된 결과는 상기 상태 확률에 해당하고, 상기 min[ ]은 상기 상태 확률들중 가장 적은 확률을 의미한다.]
제1항 내지 제4항중 어느 항에 있어서, 상기 IHMM을 이용한 정보 탐색 방법을 수행하는 IHMM을 이용한 정보 탐색 장치에 있어서,

상기 최소 비유사성 스코어, 상기 천이 확률과 관련되는 제1 값, 상기 상태관측 확률과 관련되는 제2 값을 저장하는 저장부;

제1 ∼ 제N 연산부들;

제1 ∼ 제N 비교 선택부들;

상기 제1 ∼ 제N 비교 선택부들 각각으로부터 출력되는 비교 플래그에 응답하여 제어 신호를 출력하고, 상기 저장부에 저장된 데이터의 독출을 제어하며, 상기 제1 ∼ 상기 제N 비교 선택부들로부터 출력되는 값들을 바이패스하는 제어부; 및

상기 제어부에서 바이패스된 값들을 입력하여 버퍼링하고, 버퍼링된 값들을 상기 제어 신호에 응답하여 해당하는 상기 제1 ∼ 제N 연산부들로 출력하는 버퍼를 구비하고,

상기 제i 연산부는 상기 버퍼로부터 출력되는 값과 상기 저장부로부터 입력한 상기 제1 값 및 상기 제2 값을 연산하고, 연산된 결과들중 가장 적은 연산된 결과를 상기 제어 신호에 응답하여 비교하여 선택하고,

제i 비교 선택부는 상기 제i 연산부로부터 출력되는 상기 가장 적은 연산된 결과와 상기 저장부로부터 입력한 상기 최소 비유사성 스코어를 비교하고, 비교된 결과에 응답하여 상기 소정값과 상기 가장 적은 연산된 결과중 하나를 선택하여 상기 제어부로 출력하고, 비교된 결과에 상응하는 레벨을 갖는 상기 비교 플래그를 상기 제어부로 출력하는 것을 특징으로 하는 IHMM을 이용한 정보 탐색 장치.
제5항에 있어서, 상기 제i 연산부는

제1 ∼ 제N 가산부들; 및

최소값 선택부를 구비하고,

상기 제i 가산부는 상기 버퍼로부터 출력되는 값, 상기 제1 및 상기 제2 값들을 모두 가산하고, 상기 최소값 선택부는 상기 제1 ∼ 제N 가산부들에서 가산된 결과들을 상기 제어 신호에 응답하여 비교하여 선택한 가장 작은 가산된 결과를 상기 가장 적은 연산된 결과로서 상기 제i 비교 선택부로 출력하는 것을 특징으로 하는 IHMM을 이용한 정보 탐색 장치.