Re: [sage-support] possible bug in DiscreteHiddenMarkovModel - NaN produced in output matrices
On Thu, May 8, 2014 at 4:57 PM, Jesse Hersch wrote: > On Thursday, May 8, 2014 4:14:32 PM UTC-7, William wrote: >> >> I could be wrong, but I don't think the implementation of Baum-Welch >> is wrong. The BM algorithm [1] using double precision numbers (which >> is all the HMM algorithm in Sage uses) can lead to overflow, given the >> sort of computations that are involved. > > > Thanks for the reply! > > My understanding is that it's underflow that's more common with HMM stuff, > due to all the products of small probabilities running around. In some > implementations I've seen this handled by the logsumexp trick: > http://machineintelligence.tumblr.com/post/4998477107/the-log-sum-exp-trick > > Also in the Rabiner tutorial there's a section on scaling where he talks > about underflow and how to handle it. that's on page 16 (272) here: > http://people.sabanciuniv.edu/berrin/cs512/reading/rabiner-tutorial-on-hmm.pdf > > Do you recall if you handled the underflow problem in your implementation? I believe it does not. > I haven't studied the code yet, but it seems like this could be the culprit. I think you're right. You should implement it! -- William > > -- > You received this message because you are subscribed to the Google Groups > "sage-support" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sage-support+unsubscr...@googlegroups.com. > To post to this group, send email to sage-support@googlegroups.com. > Visit this group at http://groups.google.com/group/sage-support. > For more options, visit https://groups.google.com/d/optout. -- William Stein Professor of Mathematics University of Washington http://wstein.org -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
Re: [sage-support] possible bug in DiscreteHiddenMarkovModel - NaN produced in output matrices
On Thursday, May 8, 2014 4:14:32 PM UTC-7, William wrote: > > I could be wrong, but I don't think the implementation of Baum-Welch > is wrong. The BM algorithm [1] using double precision numbers (which > is all the HMM algorithm in Sage uses) can lead to overflow, given the > sort of computations that are involved. > Thanks for the reply! My understanding is that it's underflow that's more common with HMM stuff, due to all the products of small probabilities running around. In some implementations I've seen this handled by the logsumexp trick: http://machineintelligence.tumblr.com/post/4998477107/the-log-sum-exp-trick Also in the Rabiner tutorial there's a section on scaling where he talks about underflow and how to handle it. that's on page 16 (272) here: http://people.sabanciuniv.edu/berrin/cs512/reading/rabiner-tutorial-on-hmm.pdf Do you recall if you handled the underflow problem in your implementation? I haven't studied the code yet, but it seems like this could be the culprit. -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
[sage-support] Re: posible bug in Tachyon.show() at aleph/sagecell?
Hi kcrisman and sage community! I've just reported this issue at https://github.com/sagemath/sagecell/issues/444 Best regards, -- Share_The_Sage! -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
Re: [sage-support] possible bug in DiscreteHiddenMarkovModel - NaN produced in output matrices
On Thu, May 8, 2014 at 3:50 PM, Jesse Hersch wrote: > Hi there, > > I think I may have found a bug in the class hmm.DiscreteHiddenMarkovModel. > The repro is below. It probably has something to do with one emission value > being much more common than the others, but that shouldn't be invalid from > my understanding of HMMs. I could be wrong, but I don't think the implementation of Baum-Welch is wrong. The BM algorithm [1] using double precision numbers (which is all the HMM algorithm in Sage uses) can lead to overflow, given the sort of computations that are involved. [1] http://en.wikipedia.org/wiki/Baum%E2%80%93Welch_algorithm You can see the Sage implementation of Baum-Welch by typing model.baum_welch?? after running your code below, or visiting this link: https://github.com/sagemath/sage/blob/master/src/sage/stats/hmm/hmm.pyx The entire implementation starting around line 1250 is only about 1-2 pages, and a straightforward translation of the standard thing. -- William > > I am running Sage Version 6.2 on Linux (CentOS). I built it from source > yesterday. I am a sage newbie! > > Why am I reporting the bug here? Because the "report a problem" link in the > sage notebook points here: http://ask.sagemath.org/questions/ but I cannot > post there because of being a new user (karma < 10) That page says to use > this list instead. :) > > repro: > > print version() > > # here are two emisison sequences. each observable has 4 possible values: > 0-3. > # 1 is much more common then 0,2,3 obviously > sequences = [ > [1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, > 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, > 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, > 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 3, 1, 1, > 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], > [1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 1, 1, 3, 1, 1, 1, 1, 1, 1, > 3, 1, 1, 1, 1, 1, 3, 3, 2, 3, 1, 3, 1, > 3, 1, 3, 3, 3, 1, 1, 3, 3, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, > 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, > 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1]] > > transitions = [[0.2, 0.8], [0.2, 0.8]] > pi = [.4, .6] > b = [[.1, .7, .1, .1], [.1, .7, .1, .1]] > model = hmm.DiscreteHiddenMarkovModel(A=transitions, B=b, pi=pi, > emission_symbols=None, normalize=True) > > print 'initial state for hmm:\n', model > > # training on the first sequence goes ok. > # but after the second sequence, all elements of the transition, emission, > and pi matrices are NaN. > for i, seq in enumerate(sequences): > print '\nbaum_welch on sequence ', i > model.baum_welch(obs=seq, max_iter=1000) > print model > > > And here is the output. see the many NaN in the final model > > Sage Version 6.2, Release Date: 2014-05-06 > initial state for hmm: > Discrete Hidden Markov Model with 2 States and 4 Emissions > Transition matrix: > [0.2 0.8] > [0.2 0.8] > Emission matrix: > [0.1 0.7 0.1 0.1] > [0.1 0.7 0.1 0.1] > Initial probabilities: [0.4000, 0.6000] > > baum_welch on sequence 0 > (-18.660162393780404, 128) > Discrete Hidden Markov Model with 2 States and 4 Emissions > Transition matrix: > [0.195469702114 0.804530297886] > [0.197500250574 0.802499749426] > Emission matrix: > [0.0001956779127210.999217288349 0.0 0.000587033738163] > [ 0.01363219259310.945471229628 0.0 0.040896594] > Initial probabilities: [0.9812, 0.0188] > > baum_welch on sequence 1 > (nan, 1000) > Discrete Hidden Markov Model with 2 States and 4 Emissions > Transition matrix: > [NaN NaN] > [NaN NaN] > Emission matrix: > [NaN NaN NaN NaN] > [NaN NaN NaN NaN] > Initial probabilities: [nan, nan] > > -- > You received this message because you are subscribed to the Google Groups > "sage-support" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sage-support+unsubscr...@googlegroups.com. > To post to this group, send email to sage-support@googlegroups.com. > Visit this group at http://groups.google.com/group/sage-support. > For more options, visit https://groups.google.com/d/optout. -- William Stein Professor of Mathematics University of Washington http://wstein.org -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
[sage-support] possible bug in DiscreteHiddenMarkovModel - NaN produced in output matrices
Hi there, I think I may have found a bug in the class hmm.DiscreteHiddenMarkovModel. The repro is below. It probably has something to do with one emission value being much more common than the others, but that shouldn't be invalid from my understanding of HMMs. I am running Sage Version 6.2 on Linux (CentOS). I built it from source yesterday. I am a sage newbie! Why am I reporting the bug here? Because the "report a problem" link in the sage notebook points here: http://ask.sagemath.org/questions/ but I cannot post there because of being a new user (karma < 10) That page says to use this list instead. :) *repro:* print version() # here are two emisison sequences. each observable has 4 possible values: 0-3. # 1 is much more common then 0,2,3 obviously sequences = [ [1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 1, 1, 3, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 3, 2, 3, 1, 3, 1, 3, 1, 3, 3, 3, 1, 1, 3, 3, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1]] transitions = [[0.2, 0.8], [0.2, 0.8]] pi = [.4, .6] b = [[.1, .7, .1, .1], [.1, .7, .1, .1]] model = hmm.DiscreteHiddenMarkovModel(A=transitions, B=b, pi=pi, emission_symbols=None, normalize=True) print 'initial state for hmm:\n', model # training on the first sequence goes ok. # but after the second sequence, all elements of the transition, emission, and pi matrices are NaN. for i, seq in enumerate(sequences): print '\nbaum_welch on sequence ', i model.baum_welch(obs=seq, max_iter=1000) print model *And here is the output. see the many NaN in the final model* Sage Version 6.2, Release Date: 2014-05-06 initial state for hmm: Discrete Hidden Markov Model with 2 States and 4 Emissions Transition matrix: [0.2 0.8] [0.2 0.8] Emission matrix: [0.1 0.7 0.1 0.1] [0.1 0.7 0.1 0.1] Initial probabilities: [0.4000, 0.6000] baum_welch on sequence 0 (-18.660162393780404, 128) Discrete Hidden Markov Model with 2 States and 4 Emissions Transition matrix: [0.195469702114 0.804530297886] [0.197500250574 0.802499749426] Emission matrix: [0.0001956779127210.999217288349 0.0 0.000587033738163] [ 0.01363219259310.945471229628 0.0 0.040896594] Initial probabilities: [0.9812, 0.0188] baum_welch on sequence 1 (nan, 1000) Discrete Hidden Markov Model with 2 States and 4 Emissions Transition matrix: [NaN NaN] [NaN NaN] Emission matrix: [NaN NaN NaN NaN] [NaN NaN NaN NaN] Initial probabilities: [nan, nan] -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
Re: [sage-support] reflexive @interact controls (control values update)
On Thursday, May 8, 2014 12:01:23 PM UTC-4, William wrote: > > On Thu, May 8, 2014 at 7:39 AM, Pedro Cruz > > > wrote: > > Is possible that after user action on interaction control X the function > > that updates > > the "interact screen" could also update the X control possible values ? > > In SageMathCloud, one can do that by deleting the control and > recreating it, e.g., in this one if you change the function, then the > list of buttons changes accordingly: > > Interesting. It would be great to have a cheat sheet on what new-style interact stuff works on Sage cell versus SMC. I understand there are some discrepancies in the syntax? -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
[sage-support] reflexive @interact controls (control values update)
Is possible that after user action on interaction control X the function that updates the "interact screen" could also update the X control possible values ? Thank you, Pedro -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
Re: [sage-support] Irreducibility of polynomials
Hi Martin,
danke für die schnelle Rückmeldung. So wie es scheint basiert der Test auf
DDF, was vermutlich langsamer ist im Vergleich zu Rabins Test wenn grad(f)
= p = prim. Im allgemeinen Fall aber die schnellere Variante.
Danke nochmal,
viele Grüße
Am Mittwoch, 7. Mai 2014 15:35:45 UTC+2 schrieb Martin Albrecht:
>
> Here's how to find out:
>
> sage: P. = GF(2)[]
> sage: f = P.random_element()
> sage: f.is_irreducible??
>
> if 0 == GF2X_IterIrredTest(self.x):
> return False
> else:
> return True
>
> Okay, what's GF2X_IterIrredTest?
>
> sage: search_src("GF2X_IterIrredTest")
> libs/ntl/ntl_GF2X_decl.pxd:62:long GF2X_IterIrredTest "IterIrredTest"
> (GF2X_c f)
>
> This leads us to NTL's IterIrredTest, searching for it leads to:
>
> http://www.shoup.net/ntl/doc/GF2XFactoring.txt
>
> long IterIrredTest(const GF2X& f);
>
> // performs an iterative deterministic irreducibility test, based on
> // DDF. Fast on average (when f has a small factor).
>
> Gruß,
> Martin
>
> On Wednesday 07 May 2014 05:51:11 Silke Johler wrote:
> > Hi everyone,
> >
> > I would like to know which test Sage uses to test irreducibility of a
> > polynomial over GF(2). Is it Rabin`s Test? How to compute the first
> > condition? I am not asking for the command, just the
> > technique .
> >
> > Thanks.
--
You received this message because you are subscribed to the Google Groups
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.
