您好,欢迎来到独旅网。
搜索
您的当前位置:首页动态规划详解

动态规划详解

来源:独旅网
在日常的生活中我们最经常使用的距离毫无疑问应该是欧式距离,但是对于一些特殊情况,欧氏距离存在着其很明显的缺陷,比如说时间序列,举个比较简单的例子,序列A:1,1,1,10,2,3,序列B:1,1,1,2,10,3,如果用欧氏距离,也就是distance[i][j]=(b[j]-a[i])*(b[j]-a[i])来计算的话,总的距离和应该是128,应该说这个距离是非常大的,而实际上这个序列的图像是十分相似的,这种情况下就有人开始考虑寻找新的时间序列距离的计算方法,然后提出了DTW算法,这种方法在语音识别,机器学习方便有着很重要的作用。

这个算法是基于动态规划(DP)的思想,解决了发音长短不一的模板匹配问题,简单来说,就是通过构建一个邻接矩阵,寻找最短路径和。 还以上面的2个序列作为例子,A中的10和B中的2对应以及A中的2和B中的10对应的时候,distance[3]以及distance[4]肯定是非常大的,这就直接导致了最后距离和的膨胀,这种时候,我们需要来调整下时间序列,如果我们让A中的10和B中的10 对应,A中的1和B中的2对应,那么最后的距离和就将大大缩短,这种方式可以看做是一种时间扭曲,看到这里的时候,我相信应该会有人提出来,为什么不能使用A中的2与B中的2对应的问题,那样的话距离和肯定是0了啊,距离应该是最小的吧,但这种情况是不允许的,因为A中的10是发生在2的前面,而B中的2则发生在10的前面,如果对应方式交叉的话会导致时间上的混乱,不符合因果关系。

接下来,以output[6][6](所有的记录下标从1开始,开始的时候全部置0)记录A,B之间的DTW距离,简单的介绍一下具体的算法,这个算法其实就是一个简单的DP,状态转移公式是output[i][j]=Min(Min(output[i-1][j],output[i][j-1]),output[i-1][j-1])+distance[i][j];最后得到的output[5][5]就是我们所需要的DTW距离. DTW的C语言实现 #include

#include

using namespace std;

#define NUM 6 //序列中样本点的个数简单起见,假设2个序列的样本点一样多

#define Min(a,b) (a

voidaprint(int**, int,int);

int main() {

cout<<\"adfewro\"<inti,j,k;

int a[NUM],b[NUM];

int distance[NUM+1][NUM+1];

int output[NUM+1][NUM+1];

memset((int**)distance,0,sizeof(distance));

memset((int**)output,0,sizeof(output));

aprint((int**)distance,NUM+1,NUM+1);

aprint((int**)output,NUM+1,NUM+1);

for(i=0;i>a[i];

for(i=0;i>b[i];

for(i=1;i<=NUM;i++)

for(j=1;j<=NUM;j++)

distance[i][j]=(b[j-1]-a[i-1])*(b[j-1]-a[i-1]); //计算点与点之间的欧式距离

for(i=1;i<=NUM;i++) {

for(j=1;j<=NUM;j++)

cout<cout<} //输出整个欧式距离的矩阵

aprint((int**)distance,NUM+1,NUM+1);

cout<for(i=1;i<=NUM;i++)

for(j=1;j

output[i][j]=Min(Min(output[i-1][j-1],output[i][j-1]),output[i-1][j])+distance[i][j];

//DP过程,计算DTW距离

for(i=0;i<=NUM;i++) {

for(j=0;j<=NUM;j++)

cout<cout<} //输出整个欧式距离的矩阵

aprint((int**)distance,NUM+1,NUM+1);

cout<for(i=1;i<=NUM;i++) for(j=1;j

output[i][j]=Min(Min(output[i-1][j-1],output[i][j-1]),output[i-1][j])+distance[i][j]; //DP过程,计算DTW距离

for(i=0;i<=NUM;i++) {

for(j=0;j<=NUM;j++) cout<} //输出最后的DTW距离矩阵,其中output[NUM][NUM]为最终的DTW距离和

aprint((int**)output,NUM+1,NUM+1); return 0; }

voidaprint(int** array_n, intlen,intwid) {

cout<<\"the print function\\n\"; inti=1,j=1;

int (*array)[wid];

array=(int (*)[wid])array_n; intelem[wid]; while(i {

// elem=(*array);

memset(elem,1,sizeof(elem)); j = 1; while(j {

// cout<<*((int*)array+i*wid+j)<<'\'; //cout<<*(*(array+i)+j)<<'\'; cout<<(*array)[i*wid+j]<<'\'; // cout<cout<// array++; } }

动态时间规整DTW

动态时间规整DTW(dynamic time warping)曾经是语音识别的一种主流方法。

其思想是:由于语音信号是一种具有相当大随机性的信号,即使相同说话者对相同的词,每一次发音的结果都是不同的,也不可能具有完全相同的时间长度。因此在与已存储模型相匹配时,未知单词的时间轴要不均匀地扭曲或弯折,以使其特征与模板特征对正。用时间规整手段对正是一种非常有力的措施,对提高系统的识别精度非常有效。 动态时间规整DTW是一个典型的优化问题,它用满足一定条件的的时间规整函数W(n)描述输入模板和参考模板的时间对应关系,求解两模板匹配时累计距离最小所对应的规整函数。

™将时间规整与距离测度结合起来,采用动态规划技术,比较两个大小不同的模式,解决语音识别中语速多变的难题;

™一种非线性时间规整模式匹配算法;

DTW ( Dynamic Time Warping ),即「动态时间扭曲」或是「动态时间规整」。这是一套根基于「动态规划」(Dynamic Programming,简称DP)的方法,可以有效地将搜寻比对的时间大幅降低。

DTW 的目标就是要找出两个向量之间的最短距离。一般而言,对于两个 n 维空间中的向量 x 和 y,它们之间的距离可以定义为两点之间的直线距离,称为尤拉距离(Euclidean Distance)。 dist(x, y) = |x – y| ,

但是如果向量的长度不同,那它们之间的距离,就无法使用上述的数学式來计算。一般而言,假設这两个向量的元素位置都是代表时间,由于我们必須容忍在时间轴的偏差,因此我们並不知道两个向量的元素对应关系,因此我们必須靠着一套有效的运算方法,才可以找到最佳的对应关系。

DTW是用于与说话人有关(Speaker Dependent)的语音识别,使用者自行录音然后再以自己的声音來比对之前录好的语音资料。此方法比較适合同一位说话人的声音來进行比較,因此应用范围比较狭隘,譬如目前手机 Name Dialing 等等。

DTW的问题: ™运算量大;

™识别性能过分依赖于端点检测; ™太依赖于说话人的原来发音; ™不能对样本作动态训练;

™没有充分利用语音信号的时序动态特性;

DTW适合于特定人基元较小的场合,多用于孤立词识别;

在日常的生活中我们最经常使用的距离毫无疑问应该是欧式距离,但是对于一些特殊情况,欧氏距离存在着其很明显的缺陷,比如说时间序列,举个比较简单的例子,序列A:1,1,1,10,2,3,序列B:1,1,1,2,10,3,如果用欧氏距离,也就是distance[i][j]=(b[j]-a[i])*(b[j]-a[i])来计算的话,总的距离和应该是128,应该说这个距离是非常大的,而实际上这个序列的图像是十分相似的,这种情况下就有人开始考虑寻找新的时间序列距离的计算方法,然后提出了DTW算法,这种方法在语音识别,机器学习方便有着很重要的作用。

这个算法是基于动态规划(DP)的思想,解决了发音长短不一的模板匹配问题,简单来说,就是通过构建一个邻接矩阵,寻找最短路径和。

还以上面的2个序列作为例子,A中的10和B中的2对应以及A中的2和B中的10对应的时候,distance[3]以及distance[4]肯定是非常大的,这就直接导致了最后距离和的膨胀,这种时候,我们需要来调整下时间序列,如果我们让A中的10和B中的10 对应,A中的1和B中的2对应,那么最后的距离和就将大大缩短,这种方式可以看做是一种时间扭曲,看到这里的时候,我相信应该会有人提出来,为什么不能使用A中的2与B中的2对应的问题,那样的话距离和肯定是0了啊,距离应该是最小的吧,但这种情况是不允许的,因为A中的10是发生在2的前面,而B中的2则发生在10的前面,如果对应方式交叉的话会导致时间上的混乱,不符合因果关系。

接下来,以output[6][6](所有的记录下标从1开始,开始的时候全部置0)记录A,B之间的DTW距离,简单的介绍一下具体的算法,这个算法其实就是一个简单的DP,状态转移公式是

output[i][j]=Min(Min(output[i-1][j],output[i][j-1]),output[i-1][j-1])+distance[i][j];最后得到的output[5][5]就是我们所需要的DTW距离.

DTW的C语言实现

#include #include

using namespace std;

#define NUM 6 //序列中样本点的个数简单起见,假设2个序列的样本点一样多 #define Min(a,b) (a voidaprint(int**, int,int); int main() {

cout<<\"adfewro\"<int a[NUM],b[NUM];

int distance[NUM+1][NUM+1]; int output[NUM+1][NUM+1];

memset((int**)distance,0,sizeof(distance)); memset((int**)output,0,sizeof(output));

aprint((int**)distance,NUM+1,NUM+1); aprint((int**)output,NUM+1,NUM+1);

for(i=0;i>a[i]; for(i=0;i>b[i]; for(i=1;i<=NUM;i++) for(j=1;j<=NUM;j++)

distance[i][j]=(b[j-1]-a[i-1])*(b[j-1]-a[i-1]); //计算点与点之间的欧式距离 for(i=1;i<=NUM;i++) {

for(j=1;j<=NUM;j++) cout<} //输出整个欧式距离的矩阵

aprint((int**)distance,NUM+1,NUM+1);

cout<output[i][j]=Min(Min(output[i-1][j-1],output[i][j-1]),output[i-1][j])+distance[i][j]; //DP过程,计算DTW距离

for(i=0;i<=NUM;i++) {

for(j=0;j<=NUM;j++) cout<cout<} //输出整个欧式距离的矩阵

aprint((int**)distance,NUM+1,NUM+1);

cout<for(i=1;i<=NUM;i++) for(j=1;j

output[i][j]=Min(Min(output[i-1][j-1],output[i][j-1]),output[i-1][j])+distance[i][j]; //DP过程,计算DTW距离

for(i=0;i<=NUM;i++) {

for(j=0;j<=NUM;j++) cout<} //输出最后的DTW距离矩阵,其中output[NUM][NUM]为最终的DTW距离和

aprint((int**)output,NUM+1,NUM+1); return 0; }

voidaprint(int** array_n, intlen,intwid) {

cout<<\"the print function\\n\"; inti=1,j=1;

int (*array)[wid];

array=(int (*)[wid])array_n; intelem[wid]; while(i {

// elem=(*array);

memset(elem,1,sizeof(elem)); j = 1; while(j {

// cout<<*((int*)array+i*wid+j)<<'\'; //cout<<*(*(array+i)+j)<<'\'; cout<<(*array)[i*wid+j]<<'\'; // cout<cout<// array++; } }

动态时间规整DTW

动态时间规整DTW(dynamic time warping)曾经是语音识别的一种主流方法。 其思想是:由于语音信号是一种具有相当大随机性的信号,即使相同说话者对相同的词,每一次发音的结果都是不同的,也不可能具有完全相同的时间长度。因此在与已存储模型相匹配时,未知单词的时间轴要不均匀地扭曲或弯折,以使其特征与模板特征对正。用时间规整手段对正是一种非常有力的措施,对提高系统的识别精度非常有效。

动态时间规整DTW是一个典型的优化问题,它用满足一定条件的的时间规整函

数W(n)描述输入模板和参考模板的时间对应关系,求解两模板匹配时累计距离最小所对应的规整函数。

™将时间规整与距离测度结合起来,采用动态规划技术,比较两个大小不同的模

式,解决语音识别中语速多变的难题; ™一种非线性时间规整模式匹配算法;

DTW ( Dynamic Time Warping ),即「动态时间扭曲」或是「动态时间规整」。这是一套根基于「动态规划」(Dynamic Programming,简称DP)的方法,可以有效地将搜寻比对的时间大幅降低。

DTW 的目标就是要找出两个向量之间的最短距离。一般而言,对于两个 n 维空间中的向量 x 和y,它们之间的距离可以定义为两点之间的直线距离,称为尤拉距离(Euclidean Distance)。 dist(x, y) = |x – y| ,

但是如果向量的长度不同,那它们之间的距离,就无法使用上述的数学式來计算。一般而言,假設这两个向量的元素位置都是代表时间,由于我们必須容忍在时间轴的偏差,因此我们並不知道两个向量的元素对应关系,因此我们必須靠着一套有效的运算方法,才可以找到最佳的对应关系。

DTW是用于与说话人有关(Speaker Dependent)的语音识别,使用者自行录音然后再以自己的声音來比对之前录好的语音资料。此方法比較适合同一位说话人的声音來进行比較,因此应用范围比较狭隘,譬如目前手机 Name Dialing 等等。

DTW的问题: ™运算量大;

™识别性能过分依赖于端点检测; ™太依赖于说话人的原来发音; ™不能对样本作动态训练;

™没有充分利用语音信号的时序动态特性;

DTW适合于特定人基元较小的场合,多用于孤立词识别;

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- dcrkj.com 版权所有 赣ICP备2024042791号-2

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务