Markov Chains Are the Original Language Models

<h1>Transformation-based Learning for POS Tagging</h1>
<img src="/images/ctlm.webp" alt="CTLM">
<a href="https://writewithharper.com/">Harper</a> is cur­rently un­der­go­ing some pretty rad­i­cal changes when it comes to its lan­guage analy­sis. These im­prove­ments will im­prove the out­put of our ex­ist­ing rule en­gine, in ad­di­tion to mak­ing en­tirely new cor­rec­tions pos­si­ble. This post will cover our ex­ist­ing NLP pipeline, the re­cent changes and im­prove­ments to our ma­chine learn­ing ap­proach, and what will come next.
While AI is a com­mon topic of dis­cus­sion on­line, I don’t hear much about ac­tual ma­chine learn­ing. In that light, I hope this post piques some­one’s in­ter­est.
<h2>What is POS Tagging?</h2>
POS (Part-of-speech) tag­ging is the ﬁrst step of most NLP (Natural Language Processing) pipelines. For any gram­mar checker worth its salt, POS tag­ging is es­sen­tial. Apart from the ba­sic cor­rec­tions you’re ca­pa­ble of do­ing with sim­ple string ma­nip­u­la­tion, most gram­mar check­ing di­rectly or in­di­rectly de­pends on POS tag­ging. High-quality tag­ging re­sults in high-qual­ity sug­ges­tions.
What is POS tag­ging? It is the process of iden­ti­fy­ing which pos­si­ble de­f­i­n­i­tion of a word is be­ing used, based on the sur­round­ing con­text. For those un­fa­mil­iar with the ter­ri­tory, I’m cer­tain an ex­am­ple is the best way to ex­plain.
<blockquote>
“I am go­ing to go tan in the sun.”
</blockquote>
Here we have a sim­ple, English sen­tence. In this case, it is clear the word “tan” is be­ing used as verb. The lin­guists in the au­di­ence would point out that it is specif­i­cally in the ﬁrst-per­son fu­ture tense. Consider this sim­i­lar sen­tence:
<blockquote>
“I am al­ready very tan, so I will stay in­side.”
</blockquote>
In this sen­tence, the word “tan” is be­ing used as an ad­jec­tive. How can we tell?
As in­tel­li­gent hu­mans, some of whom have been speak­ing English their en­tire lives, it is easy for us to de­ter­mine which words are serv­ing which roles. It’s not as easy for a com­puter to do the same. From an al­go­rith­mic stand­point, there are a num­ber of ways to go about it, each with dif­fer­ing lev­els of “machine learn­ing” re­quired.
Before this week, Harper pri­mar­ily took a dic­tio­nary-based ap­proach. In short: we ship a “dictionary” of English words to the user’s ma­chine and use hash table lookups to de­ter­mine the pos­si­ble roles each word could as­sume. The au­thors to our rule en­gine could then use rudi­men­tary de­duc­tive rea­son­ing to nar­row the pos­si­bil­i­ties down. This strat­egy is re­mark­ably ef­fec­tive and it has scaled to tens of thou­sands of users with sur­pris­ingly few hic­cups.
That said, there are edge-cases and sys­tems (which I’ll cover next week when I dis­cuss chunk­ing) which re­quire ex­treme speci­ﬁcity from POS tags. My mis­sion: im­prove our POS tag­ging to in­crease the con­ﬁ­dence of Harper’s out­put and open the door for more ad­vanced al­go­rithms.
<h2>Why Transformation-based Learning?</h2>
The lit­er­a­ture high­lights four un­der­ly­ing ma­chine learn­ing model strate­gies that seem to work well for POS tag­ging.
<ul>
<li>Hidden Markov Models (probabilistic mod­els that pre­date the mod­ern deep learn­ing era)</li>
<li>Maximum Entropy Models (statistical mod­els closely re­lated to lo­gis­tic re­gres­sion).</li>
<li>Transformer-based Models (which use deep neural net­works)</li>
<li>Transformation-based Rule Models (which are based on learned rules)</li>
</ul>
While I heav­ily con­sid­ered us­ing a neural net­work (either via an HMM or MEM), I dis­carded the tech­nol­ogy for three rea­sons.
<ul>
<li>TRMs are typ­i­cally more ac­cu­rate (barely; mea­sured in ba­sis points).</li>
<li>TRMs are more amenable to ﬁne-tun­ing.</li>
<li>TRMs are ex­cep­tion­ally low-la­tency and can be com­pressed quite small.</li>
</ul>
Transformation-based learn­ing is re­mark­ably sim­ple. It boils down to just four steps:
<ul>
<li>Use a sim­ple, sto­chas­tic model to la­bel your data. This can be as sim­ple as tag­ging each to­ken (or other dis­crete com­po­nent) with that vari­ant’s most com­mon tag. It does­n’t need to su­per ac­cu­rate, just enough to es­tab­lish a base­line.</li>
<li>Identify the er­rors be­tween the tags in your canon­i­cal data and that which pro­duced by your base­line model.</li>
<li>Using a ﬁ­nite list of hu­man-de­ﬁned tem­plates, gen­er­ate can­di­date rules that trans­form the out­put of the base­line model into some­thing else. This is where the term “transformation-based” comes from.</li>
<li>Apply each of the can­di­date rules to the base­line mod­el’s out­put. Check if the re­sult is more ac­cu­rate than be­fore. If so, save the rule for fu­ture use.</li>
</ul>
These saved can­di­dates be­come your model.
<h2>POS-Tagging us­ing Transformation-based Learning</h2>
Let’s ap­ply these steps to build a POS-tagging sys­tem.
For our base­line model, we will just as­sign each word in our dataset the most com­mon POS tag as­so­ci­ated with that word. If the word is “tan”, we’ll as­sign it’s most com­mon POS tag (verb). It will of­ten be in­cor­rect, but those cases will be han­dled by our rules.
To iden­tify the base­line mod­el’s er­rors, we’ll use an off-the-shelf tree-bank from the Universal Dependencies pro­ject.
Our rule tem­plates will take the form of these <code>PatchCriteria</code>. By ini­tial­iz­ing our can­di­dates with any one of these enum vari­ants and ini­tial­iz­ing the child vari­ables to ran­dom val­ues, we can cover a good num­ber of cases.
<pre><code class="hljs language-rust">#[derive(Debug, Clone, Serialize, Deserialize, Hash, PartialEq, Eq)]
pub enum PatchCriteria {
 WordIsTaggedWith {
 /// Which token to inspect.
 relative: isize,
 is_tagged: UPOS,
 },
 AnyWordIsTaggedWith {
 /// The farthest relative index to look
 max_relative: isize,
 is_tagged: UPOS,
 },
 SandwichTaggedWith {
 prev_word_tagged: UPOS,
 post_word_tagged: UPOS,
 },
 WordIs {
 relative: isize,
 word: String,
 },
 /// Not applicable to the Brill Tagger, only the chunker
 NounPhraseAt {
 is_np: bool,
 relative: isize,
 },
 Combined {
 a: Box&#x3C;PatchCriteria>,
 b: Box&#x3C;PatchCriteria>,
 },
}
</code></pre>
Finally, we’ll ap­ply each of the hun­dreds of thou­sands of can­di­dates to our tree­bank to see if the re­sult of their trans­for­ma­tions have a lower er­ror rate than the base­line.
Here are a cou­ple of the can­di­dates we found:
<pre><code class="hljs language-json">[
 {
 "from": "PRON",
 "to": "SCONJ",
 "criteria": {
 "Combined": {
 "a": {
 "WordIs": {
 "relative": 0,
 "word": "that"
 }
 },
 "b": {
 "WordIsTaggedWith": {
 "relative": -1,
 "is_tagged": "VERB"
 }
 }
 }
 }
 },
 {
 "from": "PART",
 "to": "ADP",
 "criteria": {
 "Combined": {
 "a": {
 "WordIs": {
 "relative": 1,
 "word": "there"
 }
 },
 "b": {
 "AnyWordIsTaggedWith": {
 "max_relative": -4,
 "is_tagged": "NOUN"
 }
 }
 }
 }
 }
]
</code></pre>
That’s the whole process! With it, I was able to bring our pre­vi­ous ac­cu­racy all the way up to 95% (from 40%) with­out a mean­ing­ful change in lint­ing la­tency or com­piled bi­nary size.

Harper is currently undergoing some pretty radical changes when it comes to its language analysis. These improvements will improve the output of our existing rule engine, in addition to making entirely new corrections possible.

Harper is cur­rently un­der­go­ing some pretty rad­i­cal changes when it comes to its lan­guage analy­sis. These im­prove­ments will im­prove the out­put of our ex­ist­ing rule en­gine, in ad­di­tion to mak­ing en­tirely new cor­rec­tions pos­si­ble.

Transformation Based Learning

<h1>How I Designed (and built) My Own Pen Plotter</h1>
For the last few months, af­ter read­ing Preslav Rachev’s book <a href="https://p5v.gumroad.com/l/generative-art-in-golang">Generative Art in Go</a>, I have been play­ing around with writ­ing al­go­rithms that cre­ate in­ter­est­ing graph­ics. I even­tu­ally ended up build­ing a <a href="https://github.com/elijah-potter/denim">mod­u­lar can­vas li­brary</a> for Rust to make that eas­ier to do, for me and other peo­ple.
After mak­ing a few al­go­rithms and post­ing them to the web, I started look­ing around for more in­spi­ra­tion. I hap­pened upon a video with this pen plot­ter:
<img src="/images/reddit_pen_plotter.png" alt="A screencap of a pen plotter from Reddit">
I was amazed. A ro­bot that could draw vec­tor graph­ics? I had been nerd sniped.
<img src="/images/xkcd_nerd_sniping.png" alt="XKCD Comic #356">
<h2>The Math</h2>
The math­e­mat­ics in­volved in­ter­ested my es­pe­cially. How do you trans­late <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo fence="true">[</mo><mtable rowspacing="0.16em" columnalign="center center" columnspacing="1em"><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mi>x</mi></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mi>y</mi></mstyle></mtd></mtr></mtable><mo fence="true">]</mo></mrow><annotation encoding="application/x-tex">\begin{bmatrix} x &#x26; y \end{bmatrix}</annotation></semantics></math>[x​y​] to ro­ta­tions of mo­tors? It in­tim­i­dated me a lit­tle at ﬁrst, but once I sat down and worked it out, I re­al­ized it was sur­pris­ingly sim­ple.
<img src="/images/plotter_math_diagram.png" alt="A diagram of the math involved to create the plotter">
We con­sider that the two mo­tors are sim­ply length­en­ing or short­en­ing each string a spe­ciﬁc amount. Here are the equa­tions that dic­tate the length of each string, given a point <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo fence="true">[</mo><mtable rowspacing="0.16em" columnalign="center center" columnspacing="1em"><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mi>x</mi></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mi>y</mi></mstyle></mtd></mtr></mtable><mo fence="true">]</mo></mrow><annotation encoding="application/x-tex">\begin{bmatrix} x &#x26; y \end{bmatrix}</annotation></semantics></math>[x​y​], and a dis­tance <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math>m be­tween the two mo­tors.
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msqrt><mrow><msup><mi>x</mi><mn>2</mn></msup><mo>+</mo><msup><mi>y</mi><mn>2</mn></msup></mrow></msqrt><mo>=</mo><msub><mi>r</mi><mn>0</mn></msub></mrow><annotation encoding="application/x-tex">\sqrt{x^2+y^2} = r_0</annotation></semantics></math>x2+y2<svg xmlns="http://www.w3.org/2000/svg" width="400em" height="1.28em" viewbox="0 0 400000 1296" preserveaspectratio="xMinYMin slice"><path d="M263,681c0.7,0,18,39.7,52,119
c34,79.3,68.167,158.7,102.5,238c34.3,79.3,51.8,119.3,52.5,120
c340,-704.7,510.7,-1060.3,512,-1067
l0 -0
c4.7,-7.3,11,-11,19,-11
H40000v40H1012.3
s-271.3,567,-271.3,567c-38.7,80.7,-84,175,-136,283c-52,108,-89.167,185.3,-111.5,232
c-22.3,46.7,-33.8,70.3,-34.5,71c-4.7,4.7,-12.3,7,-23,7s-12,-1,-12,-1
s-109,-253,-109,-253c-72.7,-168,-109.3,-252,-110,-252c-10.7,8,-22,16.7,-34,26
c-22,17.3,-33.3,26,-34,26s-26,-26,-26,-26s76,-59,76,-59s76,-60,76,-60z
M1001 80h400000v40h-400000z"/></svg>​=r0​
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msqrt><mrow><mo stretchy="false">(</mo><mi>x</mi><mo>−</mo><mi>m</mi><msup><mo stretchy="false">)</mo><mn>2</mn></msup><mo>+</mo><msup><mi>y</mi><mn>2</mn></msup></mrow></msqrt><mo>=</mo><msub><mi>r</mi><mn>1</mn></msub></mrow><annotation encoding="application/x-tex">\sqrt{(x-m)^2+y^2} = r_1</annotation></semantics></math>(x−m)2+y2<svg xmlns="http://www.w3.org/2000/svg" width="400em" height="1.28em" viewbox="0 0 400000 1296" preserveaspectratio="xMinYMin slice"><path d="M263,681c0.7,0,18,39.7,52,119
c34,79.3,68.167,158.7,102.5,238c34.3,79.3,51.8,119.3,52.5,120
c340,-704.7,510.7,-1060.3,512,-1067
l0 -0
c4.7,-7.3,11,-11,19,-11
H40000v40H1012.3
s-271.3,567,-271.3,567c-38.7,80.7,-84,175,-136,283c-52,108,-89.167,185.3,-111.5,232
c-22.3,46.7,-33.8,70.3,-34.5,71c-4.7,4.7,-12.3,7,-23,7s-12,-1,-12,-1
s-109,-253,-109,-253c-72.7,-168,-109.3,-252,-110,-252c-10.7,8,-22,16.7,-34,26
c-22,17.3,-33.3,26,-34,26s-26,-26,-26,-26s76,-59,76,-59s76,-60,76,-60z
M1001 80h400000v40h-400000z"/></svg>​=r1​
<h2>Is This Actually Going to Happen?</h2>
I ini­tially sat down and did the math out of cu­rios­ity. I was­n’t plan­ning on build­ing any­thing. After re­al­iz­ing the el­e­gant sim­plicty of the math, I falt em­pow­ered to go through with it. I threw to­gether a parts list.
<img src="/images/pen_plotter_parts.png" alt="A visual of all the parts needed for the plotter">
<h3>Materials</h3>
<ul>
<li>Whiteboard</li>
<li>Expo Marker</li>
<li>2 Stepper Motors</li>
<li>3D Printer Timing Belt</li>
<li>Arduino</li>
<li>Adafruit Motor Shield</li>
<li>12V 2A Power Adapter</li>
<li>Duct Tape (as any pro­ject re­quires)</li>
</ul>
I wanted to build this from scratch, with­out us­ing any­one else’s de­signs or soft­ware.
I or­der the ma­te­ri­als off Amazon and soon enough, I had every­thing I needed.
<h2>Putting It All Together</h2>
The ﬁrst step was to sol­der the mo­tor shield onto the Arduino, and wiring up step­per mo­tors. I used my school’s laser cut­ter to make a lit­tle bracket.
<img src="/images/mounted_motors_pen_plotter.jpeg" alt="The stepper motors mounted to a bracket">
I am us­ing weights to bal­ance the belts on the mo­tors. I mounted it to a white­board so I can it­er­ate in soft­ware faster/​eas­ier.
<img src="/images/mounted_bracket_on_whiteboard_pen_plotter.jpeg" alt="Everything taped onto an old whiteboard. It&#x27;s super rough, but that&#x27;s OK">
I ini­tially did­n’t have the tim­ing belt, so I pro­to­typed with an old length of wire. This is the last pic­ture be­fore I wrote all the soft­ware, which I want to talk about be­fore I show you that ver­sion.
<h2>The Software</h2>
There are two, sep­a­rate pro­grams that, to­gether, make the plot­ter work. The ﬁrst is run­ning on the Arduino, ac­cept­ing com­mands over se­r­ial from the sec­ond, which is run­ning on a USB-connected com­puter (my lap­top).
There are three main rea­sons there needs to be a lap­top in the sys­tem:
<ol>
<li>The Arduino does­n’t have enough pro­gram mem­ory</li>
<li>The Arduino can­not eas­ily ac­cept ﬁles (like SVGs)</li>
<li>It takes for­ever for an Arduino pro­gram to com­pile and up­load, which makes it­er­a­tion frus­trat­ing.</li>
</ol>
<h3>Arduino</h3>
The Arduino is run­ning a very sim­ple loop:
<ol>
<li>Receive two 32 bit signed in­te­gers over se­r­ial (one for each mo­tor)</li>
<li>Linear in­ter­po­late the step­per mo­tors to po­si­tions de­scribed by re­ceived in­te­gers</li>
</ol>
That’s it. It’s im­por­tant that the time it takes for each mo­tor to reach it’s des­ti­na­tion is the same.
<h3>Laptop</h3>
The lap­top is do­ing all the math.
I am used my can­vas li­brary <a href="https://github.com/elijah-potter/denim">Denim</a> to do all the vir­tual draw­ing. I just added a ren­derer that:
<ol>
<li>Converts all points to a se­quence of belt-lengths</li>
<li>Converts belt-lengths to se­quence of mo­tor move­ments</li>
</ol>
And sent the re­sult­ing mo­tor move­ments over se­r­ial to the Arduino.
I also wrote a quick lit­tle parser us­ing <a href="https://github.com/Geal/nom">nom</a> to parse and ex­e­cute the math com­mands you can ﬁnd in­side SVG <code>&#x3C;path></code> el­e­ments.
<h2>Final Results</h2>
<img src="/images/pen_plotter_drawing_a.jpeg" alt="The first drawing on the plotter: the letter A">
As you can see, I also made a big, rec­tan­gu­lar box, to hold the marker. It worked al­right, but not great. You also prob­a­bly no­ticed the main lim­i­ta­tion of my de­sign: it can­not lift the marker off the white­board.
I ﬁg­ured the rough­ness was mainly due to un­bal­anced weights and the slant of the white­board. I ad­justed every­thing and tried again.
<h3>Take Two</h3>
<img src="/images/pen_plotter_drawing_a2.jpeg" alt="A slightly improved letter A">
This one is much bet­ter. The lines are crisp, and ex­actly where they are sup­posed to be. At this point I wanted to try some­thing a lit­tle more ad­vanced out. Something a lit­tle more gen­er­a­tive.
<h3>The First Hilbert Curve</h3>
<img src="/images/pen_plotter_drawing_hilbert.jpeg" alt="An attempt at drawing a hilbert curve">
After see­ing the plot­ter draw a Hilbert Curve, I felt proud and a lit­tle dis­ap­pointed. The cor­ners aren’t crisp, the lines aren’t straight. Frankly, it looks like it was drawn by a two-year old.
<h3>Solving the Issue</h3>
<img src="/images/pen_plotter_drawing_hilbert2.jpeg" alt="The final attempt at a Hilbert Curve">
It worked! Now all the lines are pre­cise, crisp, smooth. The biggest is­sue is that the marker it­self ro­tates as it moves. That would­n’t nor­mally be an is­sue, but the marker is chis­eled, so it re­sults in vary­ing lev­els of pres­sure on the white­board.
<h2>Conclusion</h2>
This was a re­ally cool pro­ject. I learned a lot. I am not very ex­pe­ri­enced with ro­bot­ics, so this re­ally chal­lenged me. I in­tend on con­tin­u­ing work­ing on it. I want to add the abil­ity for the pen to lift off the can­vas, and re­ally so­lid­ify the marker holder. Most of all, I look for­ward to tak­ing my pro­jects into the real world.

In which I go through the process of designing, building, and testing a vector graphic pen plotter.

In which I go through the process of de­sign­ing, build­ing, and test­ing a vec­tor graphic pen plot­ter.

I Designed my Own Pen Plotter

harper_for_firefox_through_spellbolt

<h1>Harper in Firefox Through SpellBolt</h1>
<img src="/images/ford_street.webp" alt="Ford Street, Golden, Colorado">
We de­signed Harper to be the ul­ti­mately portable gram­mar checker, but we’re still work­ing on liv­ing up to that promise.
As the Harper Chrome ex­ten­sion be­comes more ca­pa­ble day-by-day, it has one crit­i­cal weak­ness: it does­n’t sup­port Firefox.
Since Chrome has a much larger mar­ket share, it is­n’t a pri­or­ity at the mo­ment (although we ac­cept con­tri­bu­tions).
This is a won­der­ful ex­am­ple of where the open-source na­ture of the Harper’s core en­gine re­ally shines.
Some­one has taken <a href="https://www.npmjs.com/package/harper.js"><code>harper.js</code></a> and put it into their own ex­ten­sion.
<a href="https://addons.mozilla.org/en-US/firefox/addon/spellbolt/">SpellBolt</a> is a Firefox ex­ten­sion that de­liv­ers Harper’s fan­tas­tic gram­mar check­ing straight into your Firefox browser.
My ini­tial test­ing shows that it’s a solid ex­ten­sion.
I am de­lighted to see peo­ple mak­ing use of the plug­gable ar­chi­tec­ture Harper has adopted, and I can’t wait to see what SpellBolt does next.

SpellBolt is a Firefox extension that delivers Harper's fantastic grammar checking straight into your Firefox browser.

SpellBolt is a Firefox ex­ten­sion that de­liv­ers Harper’s fan­tas­tic gram­mar check­ing straight into your Firefox browser.

Elijah Potter

Harper in Firefox Through SpellBolt

Other Stuff

Markov Chains Are the Original Language Models

Transformation Based Learning

I Designed my Own Pen Plotter