一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 725|回复: 9
收起左侧

[算法题] Viterbi(speech recognition)算法求助

[复制链接] |试试Instant~ |关注本帖
小A要当码农 发表于 2015-9-15 11:11:22 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
题目是这样的,给一个Graph,G=(V,E). 每个edge(u,v)都被labeled with a sound s(u,v) and a probability p(u,v).现在给定一个起点v0,和一套S <s1,s2,s3,s4....sk>,问如何找到一条path,使得经过的所有的edge集合满足S,且该条path的probability( 各个vertex的probability的乘积最大)?
求思路啊。。
stellari 发表于 2015-9-17 10:54:24 | 显示全部楼层
“满足S”的意思具体是什么呢?是说“经过路径上的edge上的s按顺序分别严格等于s1, s2, ... sk"吗?
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-9-17 11:46:52 | 显示全部楼层
Viterbi就是一个动态规划吧。
回复 支持 反对

使用道具 举报

cs900601 发表于 2015-9-17 13:51:01 | 显示全部楼层
是的!是DP,因为【每一步】都用到了【上一步】的结果;
也许可以参考俺在知乎上写的回答http://www.zhihu.com/question/20962240/answer/48444087
虽然不是Speech Recognition,但是应该数据结构差不多吧。
我里面主要有几张图:
t_1.jpg

t_2.jpg

t_3.jpg

t=[0,2]时用到了t=[0,1]时的结果;
t=[0,3]时用到了t=[0,2]时的结果
这样子的 :D


回复 支持 反对

使用道具 举报

 楼主| 小A要当码农 发表于 2015-9-18 10:47:05 | 显示全部楼层
stellari 发表于 2015-9-17 10:54
“满足S”的意思具体是什么呢?是说“经过路径上的edge上的s按顺序分别严格等于s1, s2, ... sk"吗?

对的,,
回复 支持 反对

使用道具 举报

 楼主| 小A要当码农 发表于 2015-9-18 10:47:25 | 显示全部楼层
Linzertorte 发表于 2015-9-17 11:46
Viterbi就是一个动态规划吧。

感觉最后不是用DP做的,你有标准DP做法吗
回复 支持 反对

使用道具 举报

 楼主| 小A要当码农 发表于 2015-9-18 10:51:05 | 显示全部楼层
cs900601 发表于 2015-9-17 13:51
是的!是DP,因为【每一步】都用到了【上一步】的结果;
也许可以参考俺在知乎上写的回答 (http ...

谢谢你的回答。但是感觉没看懂。 我最后的做法是用Stack来做的,找到任意一条路径后,记录机率,推出终点进行回溯,一直找到下一条路,进行机率对比,最后返回最大几率值对应的终点,然后再打印路径。这样是不是实际上没有用到DP呢?
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-9-18 12:50:44 | 显示全部楼层
coursera上有哥大的NLP课,你可以去看看,前几章就讲了。
回复 支持 反对

使用道具 举报

cs900601 发表于 2015-9-18 13:56:14 | 显示全部楼层
小A要当码农 发表于 2015-9-17 20:51
谢谢你的回答。但是感觉没看懂。 我最后的做法是用Stack来做的,找到任意一条路径后,记录机率,推出终点 ...

我认为DP或者不DP不在于搜索解空间的顺序(无论你是用队列来进行广度优先搜索或是用栈来深度优先搜索,或是别的算法,比如遗传算法),而是“在求解这条路径的代价时,有没有将求出的结果存起来,然后在下一次求这条路径的后续路径时,直接利用已经存起来的结果”…

所以如果你为每个点都存下了“到这个点的所有可能路径中最短的是哪条,代价又是多少”,那就是用到了DP…

以上是我的看法
回复 支持 反对

使用道具 举报

 楼主| 小A要当码农 发表于 2015-9-18 22:42:00 | 显示全部楼层
cs900601 发表于 2015-9-18 13:56
我认为DP或者不DP不在于搜索解空间的顺序(无论你是用队列来进行广度优先搜索或是用栈来深度优先搜索,或 ...

嗯 这道题里面我其实没有保存,我只保存了最大几率对应的路径的终点,以及其几率,并没有保存一路上每个点对应的几率。。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 01:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表