Sage Day August 6 -- Status Report
system:sage

<font color='purple'><h1 align=center>Sage Day August 6 -- Status Report</h1></font>

<h1 align=center>William Stein</h1>

<font color='black'><h2  align=center>Cython</h2></font>
<table align=center width=50% border=1 cellpadding=10><tr><td>
<font size=+2>
<pre>
from    Robert Bradshaw <robertwb@math.washington.edu>
date	Tue, Aug 5, 2008 at 8:04 PM

The biggest project this summer has been Dag's GSoC project, and 
we now have working code for fast indexing into NumPy arrays 
(and any other object that supports the buffer protocol). As a 
byproduct of this, compilation is now driven by a pipeline of 
transformations, which should allow much more flexible development 
in the future. Under the surface there's also been a lot of talk 
and work about general re-factoring of things like utility code 
and temporary variable allocation, which should make the 
learning curve much less steep.

There have been several smaller optimizations, bugfixes, and 
features as well. For example, a long chain of if-elif-else 
statements is translated into a case statement in C when 
possible, integer/boolean literals are handled better, 
and optional arguments are fixed for C++. Unfortunately, we 
haven't yet made progress (implementation-wise) on the PeX 
ideas discussed at Dev Days, or on generators and closures. 
I hope to release the next version of Cython soon, but we'll 
see when I have the time.
</pre>
</font></td></tr></table>


<br><br><br>
<font color='black'><h2  align=center>Hidden Markov Models</h2></font>

<ol>
<li> Discovered <a target="_new" href="http://ghmm.sourceforge.net/">GHMM</a>, which is a mature highly optimized robust C library for
computing with Hidden Markov models developed by the Algorithmics group at the Max Planck Institute for Molecular Genetics
over the last ten or so years. 

<li> I have been wrapping GHMM using Cython, though GHMM has Swig bindings (which I don't like).

<li> I will propose it for inclusion in Sage soon (it builds in 30 seconds on windows, linux, os x, etc.), and it will
help Sage compete very well with Mathematica's "Inference Addon" (\$850 student discount price!) and Matlab's similar toolbox.  
This will also be very relevant to mathematical biology and possibly other areas (e.g., quantitative finance, machine 
learning, etc.). 

<li> Had to chop out the ghmm dependence on libxml2 for inclusion in Sage.

</ol>

{{{id=1|
# Create a model
A = [[0.1,0.9], [0.5,0.5]]
B = [[0.3,0.2,0.3,0.2,0,0], [0.1,0,0,0.3,0.3,0.3]]
pi = [1,0]
L = hmm.DiscreteHiddenMarkovModel(A, B, pi, [1,2,3,4,5,6])
L
///
Discrete Hidden Markov Model with 2 States and 6 Emissions
Transition matrix:
[0.1 0.9]
[0.5 0.5]
Emission matrix:
[0.3 0.2 0.3 0.2 0.0 0.0]
[0.1 0.0 0.0 0.3 0.3 0.3]
Initial probabilities: [1.0, 0.0]
Emission symbols: [1, 2, 3, 4, 5, 6]
}}}

{{{id=9|
L.sample_single(10)
///
[2, 5, 4, 3, 4, 4, 1, 1, 6, 2]
}}}

{{{id=17|

///
}}}

{{{id=18|

///
}}}

{{{id=19|

///
}}}

{{{id=2|
time v = L.sample_single(10^6)
///
CPU time: 0.29 s,  Wall time: 0.30 s
}}}

{{{id=10|
L.log_likelihood( [2,5,3,1,2,4] )
///
-10.699757753813707
}}}

{{{id=11|
L.viterbi([2,5,3,1,2,4])
///
([0, 1, 0, 1, 0, 1], -10.835755238933423)
}}}

{{{id=12|
L.baum_welch([[2,5,3,1,2,4]])
///
}}}

{{{id=3|
L.log_likelihood( [2,5,3,1,2,4] )
///
-5.2053793708887683
}}}

{{{id=16|
L
///
Discrete Hidden Markov Model with 2 States and 6 Emissions
Transition matrix:
[4.50717011602e-23               1.0]
[              1.0               0.0]
Emission matrix:
[           0.0 0.666666666667 0.333333333333            0.0            0.0            0.0]
[0.333333333333            0.0            0.0 0.333333333333 0.333333333333            0.0]
Initial probabilities: [1.0, 0.0]
Emission symbols: [1, 2, 3, 4, 5, 6]
}}}

{{{id=15|

///
}}}

{{{id=14|

///
}}}

{{{id=13|

///
}}}

{{{id=4|
html('<font size=+2><a target="_new" href="http://etext.virginia.edu/kjv.browse.html">Here is a good source of text..</a></font><br><br>')
@interact
def foo(phrase = 'sin cos tan', states=(3,(1..20)), 
        output = (1000,(100..2000)),
        show_model=False, seed=(0..100)):
    print "Type in a some text.  This will train a Hidden Markov Model with %s states to generate similar text."%states
    set_random_seed(seed)
    A = random_matrix(RDF, states).apply_map(abs)
    B = [[random() for _ in range(27)] for _ in range(states)]
    letters = [chr(97+i) for i in range(26)] + [' ']
    H = hmm.DiscreteHiddenMarkovModel(A,B, [1]*states, letters)
    H.normalize()
    phrase = (' ' + phrase + ' ').lower()
    phrase = [x for x in phrase if x in letters]
    try:
        H.baum_welch(phrase)
    except Exception, msg:
        pass
    #print H
    print "Here is the text:\n\n"
    print ''.join(H.sample_single(output))
    print '\n'*2
    if show_model:
        #print H
        show(matrix_plot(H.transition_matrix()))
        show(matrix_plot(H.emission_matrix()))
///

<html><font color='black'><font size=+2><a target="_new" href="http://etext.virginia.edu/kjv.browse.html">Here is a good source of text..</a></font><br><br></font></html>
<html><div padding=6 id='div-interact-4'> <table width=800px height=400px bgcolor='#c5c5c5'
                 cellpadding=15><tr><td bgcolor='#f9f9f9' valign=top align=left><table><tr><td align=right><font color="black">phrase&nbsp;</font></td><td><input type='text' value='sin cos tan' size=80 onchange='interact(4, "sage.server.notebook.interact.update(4, \"phrase\", 16, sage.server.notebook.interact.standard_b64decode(\""+encode64(this.value)+"\"), globals())")'></input></td></tr>
<tr><td align=right><font color="black">states&nbsp;</font></td><td><div id='slider-states-4' class='ui-slider-1' style='padding:0px;margin:0px;'><span class='ui-slider-handle'></span></div><script>setTimeout(function() { $('#slider-states-4').slider({
    stepping: 1, minValue: 0, maxValue: 19, startValue: 2,
    change: function () { var position = Math.ceil($('#slider-states-4').slider('value')); interact(4, "sage.server.notebook.interact.update(4, \"states\", 17, sage.server.notebook.interact.standard_b64decode(\""+encode64(position)+"\"), globals())"); }
});}, 1);</script></td></tr>
<tr><td align=right><font color="black">output&nbsp;</font></td><td><div id='slider-output-4' class='ui-slider-1' style='padding:0px;margin:0px;'><span class='ui-slider-handle'></span></div><script>setTimeout(function() { $('#slider-output-4').slider({
    stepping: 1, minValue: 0, maxValue: 1900, startValue: 900,
    change: function () { var position = Math.ceil($('#slider-output-4').slider('value')); interact(4, "sage.server.notebook.interact.update(4, \"output\", 18, sage.server.notebook.interact.standard_b64decode(\""+encode64(position)+"\"), globals())"); }
});}, 1);</script></td></tr>
<tr><td align=right><font color="black">show_model&nbsp;</font></td><td><input type='checkbox'  width=200px onchange='interact(4, "sage.server.notebook.interact.update(4, \"show_model\", 19, sage.server.notebook.interact.standard_b64decode(\""+encode64(this.checked)+"\"), globals())")'></input></td></tr>
<tr><td align=right><font color="black">seed&nbsp;</font></td><td><div id='slider-seed-4' class='ui-slider-1' style='padding:0px;margin:0px;'><span class='ui-slider-handle'></span></div><script>setTimeout(function() { $('#slider-seed-4').slider({
    stepping: 1, minValue: 0, maxValue: 100, startValue: 0,
    change: function () { var position = Math.ceil($('#slider-seed-4').slider('value')); interact(4, "sage.server.notebook.interact.update(4, \"seed\", 20, sage.server.notebook.interact.standard_b64decode(\""+encode64(position)+"\"), globals())"); }
});}, 1);</script></td></tr>
</table><div id='cell-interact-4'><?__SAGE__START>
        <table border=0 bgcolor='#white' width=100% height=100%>
        <tr><td bgcolor=white align=left valign=top><pre><?__SAGE__TEXT></pre></td></tr>
        <tr><td  align=left valign=top><?__SAGE__HTML></td></tr>
        </table><?__SAGE__END></div></td>
                 </tr></table></div>
                 </html>
}}}

{{{id=5|

///
}}}

{{{id=6|

///
}}}

<br><br><br>
<font color='black'><h2  align=center>Modular Forms Computation</h2></font>

<ol>
<li> I rewrote a lot of code for computing Hecke eigenvalues so it was vastly faster
than before.
<li> I haven't fully documented the result and got it into Sage.  I need to.
</ol>

{{{id=23|

///
}}}

{{{id=22|

///
}}}

{{{id=21|

///
}}}

{{{id=20|

///
}}}

{{{id=8|

///
}}}