daniel bigham.ca

Exercise 40: Mathematical analysis of the Adjacent Pair Permutation method
December 2, 2008

Summary

The APP algorithm processes each each pair permutation. Each pair permutation forms a search tree. Perform an analysis on the number of nodes in a typical pair permutation tree given that:

There are W words

There are E entity types per word

The fraction of pair permutations that transform is Q

Solution

I wasn't quite sure how to solve this one, so I called on Mr. Vaughn Climenhaga for some help, and he delivered! Thanks Vaughn!

The following solution assumes that only the first two pair permutations are considered, which is a best-case scenario. (I'm unclear on whether the algorithm is feasible with this limitation)

So basically O(E^2W * Q^W).

In the case where W = 15, E = 10, and Q = 0.1, we have:

344,926,315,789,473,684,201 = 344,926 * 316 trillion

In the case where W = 15, E = 10, and Q = 0.01, we have:

6,553,401

In the case where W = 15, E = 10, and Q = 1/150, we have:

44,175

In the case where W = 7, E = 10, and Q = 0.01, we have:

25,401

In the case where W = 7, E = 10, and Q = 1/150, we have:

3,892

Discussion

In practice, the algorithm's search tree appears to be much, much smaller than this, so perhaps Q can't be modeled as a constant.

The other important consideration is that Unique APP avoids branching to fragments it has already searched, which heavily prunes the tree.

Exercise 39: Alternative transformation algorithm
December 2, 2008

Summary

Implement an alternative transformation algorithm that doesn't start by permuting each of the entity type sets, but rather works by permuting the entity type sets of each adjacent words.

This alternative approach will be known as the Adjacent Pair Permutation algorithm, or APP algorithm. As part (b), add a hash that will track what fragments have already been considered so that they aren't re-considered. This in effect prunes the tree. The resulting algorithm will be called Unique Adjacent Pair Permutation.

The original approach will be known as the Exhaustive Permutation algorithm, or EP algorithm.

Motivation

It is impractical to permute each of the entity type sets of a sentence, since a 15 word sentence with 10 entity types per word results in 10^15 permutations. That's one thousand trillion, and the initial permutations are only the first level of a tree!

Google taking spoken queries?
November 15, 2008

This article hints that Google is working on a voice interface for the iPhone. Very interesting. I guess cell phones are an ideal candidate since you hold them right up to your face, so the proximity to a person's mouth is great, and cell phones already need to have decent quality microphones since that's part of their core functionality: To record a voice into a digitized format and transmit it.

Prediction: The years 2010 to 2020 will see very significant developments in the area of voice interfaces.

older >>