CRF with ruby based on https://gist.github.com/neubig/7352832

crf.rb

#!/usr/bin/env ruby
# -*- encoding: utf-8 -*-

L2_COEFF = 1
RATE     = 10

TAGIDS = Hash.new { |hash, key| hash[key] = hash.size }
TAGIDS['<S>'] = 0

def dot(x, y)
  x.reduce(0.0) do |a, e|
    k, v = e
    a + (y.key?(k) ? v * y[k] : 0)
  end
end

def add(a, b)
  t = Hash.new(0)
  t.merge(a).merge(b) { |k, sv, ov| sv + ov }
end

def logsumexp(x)
  k = x.max
  Math.log(x.reduce(0.0) do |a, e|
    a + Math.exp(e - k)
  end) + k
end

def calc_feat(x, i, l, r)
  { ['T', l, r] => 1, ['E', r, x[i]] => 1 }
end

def calc_e(x, i, l, r, w, e_prob)
  e_prob[[i, l, r]] = dot(calc_feat(x, i, l, r), w) unless e_prob.key?([i, l, r])
  e_prob[[i, l, r]]
end

def calc_f(x, i, l, w, e, f)
  unless f.key?([i, l])
    if i == 0
      f[[i, 0]] = 0
    else
      prev_states = (i == 1 ? [0] : 1...TAGIDS.size)
      f[[i, l]] = logsumexp(
        prev_states.map { |k| calc_f(x, i - 1, k, w, e, f) + calc_e(x, i, k, l, w, e) }
      )
    end
  end
  f[[i, l]]
end

def calc_b(x, i, r, w, e, b)
  unless b.key?([i, r])
    if i == x.size - 1
      b[[i, 0]] = 0
    else
      prev_states = (i == x.size - 2 ? [0] : 1...TAGIDS.size)
      b[[i, r]] = logsumexp(
        prev_states.map { |k| calc_b(x, i + 1, k, w, e, b) + calc_e(x, i, r, k, w, e) }
      )
    end
  end
  b[[i, r]]
end

def calc_gradient(x, y, w)
  f_prob = { [0, 0] => 0 }
  b_prob = { [x.size - 1, 0] => 0 }
  e_prob = {}
  grad   = Hash.new(0)

  (1...x.size).each do |i|
    calc_feat(x, i, y[i - 1], y[i]).each { |k, v| grad[k] += v }
  end

  norm = calc_b(x, 0, 0, w, e_prob, b_prob)
  lik  = dot(grad, w) - norm

  (1...x.size).each  do |i|
    (i == 1 ? [0] : 1...TAGIDS.size).each do |l|
      (i == x.size - 1 ? [0] : 1...TAGIDS.size).each do |r|
        p = Math.exp(calc_e(x, i, l, r, w, e_prob) +
                calc_b(x, i, r, w, e_prob, b_prob) +
                calc_f(x, i - 1, l, w, e_prob, f_prob) -
                norm)
        calc_feat(x, i, l, r).each { |k, v| grad[k] -= v * p }
      end
    end
  end
  [grad, lik]
end

corpus = []
ARGF.each do |line|
  words = ['<S>']
  tags  = [0]
  line.strip!
  line.split(' ').each do |w_t|
    w, t = w_t.split('_')
    words << w
    tags  << TAGIDS[t]
  end
  words << '<S>'
  tags << 0
  corpus << [words, tags]
end

w = Hash.new(0)
(1..50).each do |iternum|
  grad = Hash.new(0)
  reg_lik = 0
  w.each do |k, v|
    grad[k] -= 2 * v * L2_COEFF
    reg_lik -= v * v * L2_COEFF
  end
  lik = 0
  corpus.each do |x, y|
    my_grad, my_lik = calc_gradient(x, y, w)
    my_grad.each { |k, v| grad[k] += v }
    lik += my_lik
  end
  l1 = grad.values.reduce(0.0) { |a, e| a + e.abs }
  STDERR.print "Iter %f likelihood: lik=%f, reg=%f, reg+lik=%f gradL1=%f\n" % [iternum, lik, reg_lik, lik + reg_lik, l1]
  grad.each { |k, v| w[k] += v / l1 * RATE }
end

strs = {}
TAGIDS.each { |k, v| strs[v] = k }

w.sort_by { |k, v| v }.each do |k, v|
  if k[0] == 'E'
    print "%s %s %s\t%f\n" % [k[0], strs[k[1]], k[2], v]
  else
    print "%s %s %s\t%f\n" % [k[0], strs[k[1]], strs[k[2]], v]
  end
end