I'm writing a small program that implements a trigram HMM model and apply it by using Viterbi Algorithm. It's very standardized. However, I have never written anything like this before, and I get confused of what I should use as the START (*) and STOP symbols.

I tried to search for the answer online but apparently people who know the answer don't need to ask online, and people who don't know the answer don't need to know.

I primarily use Scala as my choice of implementation language. Scala has a program called ScalaNLP, but it's nowhere being mature, and it does not have HMM implementation as far as I can tell. So I decide to include a statistic package of Scala and write one by myself.

I recently watched Michael Collins' NLP class on Coursera and I thought he explained HMM model very well and I could possibly try to implement that by myself.

The "apply-part" of program itself on the outmost surface (structure) should look like the Viterbi Algorithm described in Collins' video. I do need to explain. HMM has two parts: training and applying. Training part is implemented to get emission variable: $e - e(x^i|y^i)$ and the parameter $q(v|w, u)$. The applying part is to take in a sentence: x1x2...xn and add two start symbols ** to the beginning of the sentence and a STOP symbol at the end.

I don't know if I am truly capable of doing such, but these great professors never mentioned any real implementation because people will just go and use a library created by someone else.

  • 1
    $\begingroup$ I get the feeling there is context missing here. Unless these symbols are standard terminology in the NLP field, please explain their purpose. $\endgroup$ – Raphael Mar 11 '14 at 20:54
  • 2
    $\begingroup$ Wind Dweller, I share Raphael's reaction. I suggest you edit your question to try to provide the full context. Develop the full problem, without assuming we know what you mean by START/STOP symbols or why they are relevant or where on earth they come from. (Your comment didn't help me.) You might also want to clarify what you are trying to achieve. "apply it by using Viterbi algorithm" is unclear -- what do you mean by "apply it"? What are you trying to accomplish? I know what a trigram HMM model is, and what the Viterbi algorithm is, but I can't understand what you're trying to achieve. $\endgroup$ – D.W. Mar 11 '14 at 23:32
  • 1
    $\begingroup$ It doesn't really matter. It would make sense to either use a non-alphabetic character (something that never appears in the text), or some rare character such as $Z$, $Q$ or $\%$. $\endgroup$ – Yuval Filmus Mar 12 '14 at 5:33
  • 1
    $\begingroup$ So your question is, what to chose as special characters to denote start and end? As Yuval said, yuo can choose any characters that do not appear in your texts (or rare ones, if you can't rule out any). $\endgroup$ – FrankW Mar 14 '14 at 7:49
  • 2
    $\begingroup$ You should use something that you can guarantee that will not appear in your texts - so strings '*' and 'stop' are not okay, but you can use any specific strings that you could check for and eliminate or replace with escape sequences in the original text. I've seen '<s>' and '</s>' used, xml-style; I've seen '__ START __ ' (with underscores), I've seen specific low-ascii-range characters used. Using rare characters without verification is dangerous - I've seen too much NLP software that unexplainably breaks down just because the original text included symbols such as '|' or '['. $\endgroup$ – Peteris Mar 14 '14 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.