ctc forward backward algorithm - why is it being used?
$begingroup$
as per ftp://ftp.idsia.ch/pub/juergen/icml2006.pdf fwd bw algo helps us speed up discovery of the happy path. For e.g. if the GT label is DOG and we have 10 time steps , the possible label sequences could be
_DD_OO_GG_
DD_OOO_GGG
DO__GGGGGG
etc ..so one path could be "_DO" (index 0, 1 and 2 from 3 example possibilities shown above). Assuming most tasks will have many more time steps (and hence a much higher number of paths), how is the fwd bw algo speeding things up ? Lets say the fwd variable is calculating the prob of obtaining an "O" at time step T, does it mean that it picks the best possible path of getting to "O" (recursively) ? for e.g. if the 3 paths to "O" were "_DD" , "DDD" and "blank D blank" with probabilities 0.3, 0.5 and 0.8, it would assume the best path till "O" is via "blank D blank" and move forward with the next character in the sequence ? Does it build on the highest probable prefix and then move forward ? hence for the next character, say "blank" or "O" it would choose "_D_O" ? I hope i have conveyed my query clearly, else i apologize for wasting your time. I couldn't find any good explanation about the nuts and bolts of the algo (neither could i find a good c++/python implementation of the same) ..any pointers in the direction will be greatly appreciated.
machine-learning deep-learning classification
asked 4 mins ago
Vikram MurthyVikram Murthy
534
$endgroup$
add a comment |
$begingroup$
as per ftp://ftp.idsia.ch/pub/juergen/icml2006.pdf fwd bw algo helps us speed up discovery of the happy path. For e.g. if the GT label is DOG and we have 10 time steps , the possible label sequences could be
_DD_OO_GG_
DD_OOO_GGG
DO__GGGGGG
etc ..so one path could be "_DO" (index 0, 1 and 2 from 3 example possibilities shown above). Assuming most tasks will have many more time steps (and hence a much higher number of paths), how is the fwd bw algo speeding things up ? Lets say the fwd variable is calculating the prob of obtaining an "O" at time step T, does it mean that it picks the best possible path of getting to "O" (recursively) ? for e.g. if the 3 paths to "O" were "_DD" , "DDD" and "blank D blank" with probabilities 0.3, 0.5 and 0.8, it would assume the best path till "O" is via "blank D blank" and move forward with the next character in the sequence ? Does it build on the highest probable prefix and then move forward ? hence for the next character, say "blank" or "O" it would choose "_D_O" ? I hope i have conveyed my query clearly, else i apologize for wasting your time. I couldn't find any good explanation about the nuts and bolts of the algo (neither could i find a good c++/python implementation of the same) ..any pointers in the direction will be greatly appreciated.
machine-learning deep-learning classification
asked 4 mins ago
Vikram MurthyVikram Murthy
534
$endgroup$
add a comment |
$begingroup$
as per ftp://ftp.idsia.ch/pub/juergen/icml2006.pdf fwd bw algo helps us speed up discovery of the happy path. For e.g. if the GT label is DOG and we have 10 time steps , the possible label sequences could be
_DD_OO_GG_
DD_OOO_GGG
DO__GGGGGG
etc ..so one path could be "_DO" (index 0, 1 and 2 from 3 example possibilities shown above). Assuming most tasks will have many more time steps (and hence a much higher number of paths), how is the fwd bw algo speeding things up ? Lets say the fwd variable is calculating the prob of obtaining an "O" at time step T, does it mean that it picks the best possible path of getting to "O" (recursively) ? for e.g. if the 3 paths to "O" were "_DD" , "DDD" and "blank D blank" with probabilities 0.3, 0.5 and 0.8, it would assume the best path till "O" is via "blank D blank" and move forward with the next character in the sequence ? Does it build on the highest probable prefix and then move forward ? hence for the next character, say "blank" or "O" it would choose "_D_O" ? I hope i have conveyed my query clearly, else i apologize for wasting your time. I couldn't find any good explanation about the nuts and bolts of the algo (neither could i find a good c++/python implementation of the same) ..any pointers in the direction will be greatly appreciated.
machine-learning deep-learning classification
asked 4 mins ago
Vikram MurthyVikram Murthy
534
$endgroup$
as per ftp://ftp.idsia.ch/pub/juergen/icml2006.pdf fwd bw algo helps us speed up discovery of the happy path. For e.g. if the GT label is DOG and we have 10 time steps , the possible label sequences could be
_DD_OO_GG_
DD_OOO_GGG
DO__GGGGGG
etc ..so one path could be "_DO" (index 0, 1 and 2 from 3 example possibilities shown above). Assuming most tasks will have many more time steps (and hence a much higher number of paths), how is the fwd bw algo speeding things up ? Lets say the fwd variable is calculating the prob of obtaining an "O" at time step T, does it mean that it picks the best possible path of getting to "O" (recursively) ? for e.g. if the 3 paths to "O" were "_DD" , "DDD" and "blank D blank" with probabilities 0.3, 0.5 and 0.8, it would assume the best path till "O" is via "blank D blank" and move forward with the next character in the sequence ? Does it build on the highest probable prefix and then move forward ? hence for the next character, say "blank" or "O" it would choose "_D_O" ? I hope i have conveyed my query clearly, else i apologize for wasting your time. I couldn't find any good explanation about the nuts and bolts of the algo (neither could i find a good c++/python implementation of the same) ..any pointers in the direction will be greatly appreciated.
machine-learning deep-learning classification
machine-learning deep-learning classification
asked 4 mins ago
Vikram MurthyVikram Murthy
534
asked 4 mins ago
Vikram MurthyVikram Murthy
534
asked 4 mins ago
Vikram MurthyVikram Murthy
534
asked 4 mins ago
Vikram MurthyVikram Murthy
534
asked 4 mins ago
Vikram MurthyVikram Murthy
534
534
add a comment |
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "557"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fdatascience.stackexchange.com%2fquestions%2f44547%2fctc-forward-backward-algorithm-why-is-it-being-used%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Data Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fdatascience.stackexchange.com%2fquestions%2f44547%2fctc-forward-backward-algorithm-why-is-it-being-used%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
