Оглавление.

Компьютерное распознавание и порождение речи

Глава 4. Алгоритмы распознавания.

Реализация СММ на компьютере

Приведем пример реализации решения основных задач для скрытых Марковских моделей на языке C.

#include "stdio.h"
#include "stdlib.h"

//Структура, описывающая скрытую Марковскую модель

typedef struct{
int N; //Число состояний
int M; //Число вариантов наблюдений
double**A; //Матрица вероятностей переходов между состояниями
double**B; //Матрица вероятностей каждого наблюдения в каждом состоянии
double*pi; //Вектор вероятностей начальных состояний
}HMM;

//Функция инициализации скрытой Марковской модели из N состояний и M вариантов наблюдений

HMM* InitHMM(int N, int M)
{
HMM* ret=(HMM*)malloc(sizeof(HMM));
ret->pi=(double*)malloc(N*sizeof(double));
ret->A=(double**)malloc(N*sizeof(double*));
ret->B=(double**)malloc(N*sizeof(double*));
for(int i=0;i {
ret->A[i]=(double*)malloc(N*sizeof(double));
ret->B[i]=(double*)malloc(M*sizeof(double));
}
return ret;
}

//Функция, возвращающая для указанной модели Lambda
//вероятность появления заданной последовательности Seq длиной tau,
//содержащей номера вариантов наблюдений, методом прямого хода

double Seq_Probability_Forward(HMM* Lambda, int* Seq, int tau)
{
double ret=0;
double *alpha=(double*)malloc((Lambda->N)*sizeof(double));
double *alpha_next=(double*)malloc((Lambda->N)*sizeof(double));
for(int i=0;i<(Lambda->N);i++)
alpha[i]=Lambda->pi[i]*Lambda->B[i][0];
for(int t=0;t {
for(int j=0;jN;j++)
{
alpha_next[j]=0;
for(i=0;iN;i++)
alpha_next[j]+=alpha[i]*Lambda->A[i][j];
alpha_next[j]*=Lambda->B[j][Seq[t]];

}
free(alpha);
alpha=alpha_next;
alpha_next=(double*)malloc((Lambda->N)*sizeof(double));
}
return(ret);
}

//Функция, возвращающая для указанной модели Lambda
//вероятность появления заданной последовательности Seq длиной tau,
//содержащей номера вариантов наблюдений, методом обратного хода

double Seq_Probability_Backward(HMM* Lambda, int* Seq, int tau)
{
double ret=0;
double *beta=(double*)malloc((Lambda->N)*sizeof(double));
double *beta_prev=(double*)malloc((Lambda->N)*sizeof(double));
for(int i=0;i<(Lambda->N);i++)
beta[i]=1;
for(int t=tau-1;t>0;t--)
{
for(i=0;iN;i++)
{
beta_prev[i]=0;
for(int j=0;iN;i++)
beta_prev[i]+=Lambda->A[i][j]*Lambda->B[j][t]*beta[i];
}
free(beta);
beta=beta_prev;
beta_prev=(double*)malloc((Lambda->N)*sizeof(double));
}
return(ret);
}

//Функция, возвращающая для указанной модели Lambda наиболее
// вероятную цепочку номеров событий
//по заданной последовательности Seq длиной tau,
//содержащей номера вариантов наблюдений, по алгоритму Витерби

int* Viterbi(HMM* Lambda, int* Seq, int tau)
{
int *ret=(int*)malloc(tau*sizeof(int));
double **gamma=(double**)malloc(tau*sizeof(double*));
int **fi=(int**)malloc(tau*sizeof(int*));
for(int t=0;t {
gamma[t]=(double*)malloc((Lambda->N)*sizeof(double));
fi[t]=(int*)malloc((Lambda->N)*sizeof(int));
}
for(int i=0;i<(Lambda->N);i++)
{
gamma[0][i]=(Lambda->pi[i])*(Lambda->B[i][0]);
fi[0][i]=0;
}

for(t=1;t {
for(int j=0;j<(Lambda->N);j++)
{
double Max=gamma[t-1][0]*(Lambda->A[0][j]);
int Max_ind=0;
for(i=0;i<(Lambda->N);i++)
{
if(gamma[t-1][i]*(Lambda->A[i][j])>Max)
{
Max=gamma[t-1][i]*(Lambda->A[i][j]);
Max_ind=i;
}
}
gamma[t][j]=Max;
fi[t][j]=Max_ind;
}
}
double P=gamma[tau][0];
int P_arg=0;
for(i=0;i<(Lambda->N);i++)
{
if(gamma[tau-1][i]>P)
{
P=gamma[tau-1][i];
P_arg=i;
}
}
ret[tau-1]=P_arg;
for(t=t-2;t>=0;t--)
{
ret[t]=fi[t+1][ret[t+1]];
}
return(ret);
}

//Функция, настраивающая заданную модель Lambda
//по заданной последовательности Seq длиной tau,
//содержащей номера вариантов наблюдений, по алгоритму Баума-Уэлша


void Baum_Welsh(HMM* Lambda, int* Seq, int tau)
{
// Инициализация вспомогательных переменных

double ***ksi=(double***)malloc((Lambda->N)*sizeof(double**));
double **alpha=(double**)malloc(tau*sizeof(double*));
double **beta=(double**)malloc(tau*sizeof(double*));
double **psi=(double**)malloc((Lambda->N)*sizeof(double*));
for(int t=0;t {
ksi[t]=(double**)malloc((Lambda->N)*sizeof(double*));
psi[t]=(double*)malloc((Lambda->N)*sizeof(double));
for(int i=0;i<(Lambda->N);i++)
{
ksi[t][i]=(double*)malloc((Lambda->N)*sizeof(double));
}
}


for(t=0;t {
alpha[t]=(double*)malloc((Lambda->N)*sizeof(double));
beta[t]=(double*)malloc((Lambda->N)*sizeof(double));
}

//Рассчитываем вспомогательные коэффициенты Альфа

for(int i=0;i<(Lambda->N);i++)
alpha[0][i]=Lambda->pi[i]*Lambda->B[i][0];
for(t=0;t {
for(int j=0;jN;j++)
{
alpha[t+1][j]=0;
for(i=0;iN;i++)
alpha[t+1][j]+=alpha[t][i]*Lambda->A[i][j];
alpha[t+1][j]*=Lambda->B[j][Seq[t]];

}
}
//Рассчитываем вспомогательные коэффициенты Бета

for(i=0;i<(Lambda->N);i++)
beta[tau-1][i]=1;
for(t=tau-1;t>0;t--)
{
for(i=0;iN;i++)
{
beta[t-1][i]=0;
for(int j=0;iN;i++)
beta[t-1][i]+=Lambda->A[i][j]*Lambda->B[j][t]*beta[t][i];
}
}

//Рассчитываем вспомогательные переменные Кси

for(t=0;t {
for(i=0;i<(Lambda->N);i++)
{
for(int j=0;j<(Lambda->N);j++)
{
double Sum=0;
for(int i2=0;i2<(Lambda->N);i2++)
{
for(int j2=0;j2<(Lambda->N);j2++)
{
Sum+=alpha[t][i2]*
Lambda- >A[i2][j2]*Lambda->B[j2][t+1]*
beta[t+1][j2];
}
}
ksi[t][i][j]=alpha[t][i]*Lambda->A[i][j]*Lambda->B[j][t+1]*beta[t+1][j]/Sum;
}
}
}

//Рассчитываем вспомогательные переменные Пси

for(t=0;t {
for(i=0;i<(Lambda->N);i++)
{
double Sum=0;
for(int j=0;j<(Lambda->N);j++)
{
Sum+=ksi[t][i][j];
}
psi[t][i]=Sum;
}
}

//Вычисляем уточненные параметры марковской модели

for(i=0;i<(Lambda->N);i++)
{
Lambda->pi[i]=psi[0][i];
}

for(i=0;i<(Lambda->N);i++)
for(int j=0;j<(Lambda->N);j++)
{
double Sum1=0;
double Sum2=0;
for(t=0;t {
Sum1+=ksi[t][i][j];
Sum2+=psi[t][j];
}
Lambda->A[i][j]=Sum1/Sum2;
}
for(int j=0;j<(Lambda->N);j++)
for(int k=0;k<(Lambda->M);k++)
{
double Sum1=0;
double Sum2=0;
for(t=0;t {
Sum2+=psi[t][j];
if(Seq[t]==k)
{
Sum1+=psi[t][j];
}
}
Lambda->B[i][j]=Sum1/Sum2;
}

}

Распознавание речи. Обработка текстов на естественном языке.