home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / speech / 359 < prev    next >
Encoding:
Internet Message Format  |  1992-12-13  |  1.9 KB
  1. Path: sparky!uunet!pipex!warwick!doc.ic.ac.uk!uknet!bcc.ac.uk!link-1.ts.bcc.ac.uk!ubacr45
  2. From: ubacr45@ucl.ac.uk (Mr G Toal)
  3. Newsgroups: comp.speech
  4. Subject: Re: Dynamic Programming
  5. Keywords: Dynamic Programming, Vitirbi, minimum cost path
  6. Message-ID: <1992Dec13.050508.24165@bas-a.bcc.ac.uk>
  7. Date: 13 Dec 92 05:05:08 GMT
  8. References: <Dec.10.00.19.43.1992.7925@caip.rutgers.edu> <1992Dec11.155402.17484@eng.cam.ac.uk>
  9. Sender: news@ucl.ac.uk (Usenet News System)
  10. Organization: Bloomsbury Computing Consortium, London
  11. Lines: 24
  12.  
  13. In article <1992Dec11.155402.17484@eng.cam.ac.uk> ajr@eng.cam.ac.uk (Tony Robinson) writes:
  14. >ergodic Markov model".  To take away some of the jargon, I want to recognise
  15. >a sentence as a sequence of phones.  This means allocating one phone to each
  16. >time slot.  This could be done by generating all possible sequences,
  17. >computing a cost for each one, and picking the one with the least cost.
  18. >This is horrendously inefficient, and that is where dynamic programming
  19. >comes in.  By computing an optimal cost to a partial solution, say from the
  20. >start to time t, then to find an optimal solution to time t+1 you only have
  21. >to look at the solutions to time t and all the possible extensions.  This is
  22. >the best I can put it in a reasonable amount of time, but it it this
  23. >"principle of optimality" that it is important to understand.  Dynamic
  24. >programming makes the problem linear in time, as opposed to exponential - a
  25. >huge win!
  26.  
  27. I've heard the phrase 'dynamic time warp' bandied around, but your
  28. description here of dynamic programming is what I thought was dynamic
  29. time warp.  (I'd been under the impression that dynamic programming
  30. was what we used to call in the seventies in AI 'memo functions')
  31.  
  32. If you know about dynamic time warp too, Tony, could I persuade you
  33. to jot down a few lines like you did for this (for which edification
  34. I thank you, by the way.)
  35.  
  36. Graham
  37.