General Comments

Solutions are by Mike Soss.

Problem 1

Basically, the theory is useless. With the tweaking involved, it's very similar to the Medial Axis Transform after you use a threshold.

As for the Morphological Shape Congruence, note that there is no topological information in terms of the tree structure of the triangulation. For example,


are all congruent by this theory, but


are not!


Problem 2

Part (a)

The decision rule is indeed linear. Let M = (m1, m2, ..., md) be the mean, and X = (x1, x2, ..., xd) be some binary vector. We will show that the 1st-order Minkowski distance from M to X is a linear function in terms of X.

We know the distance is SUMi {|mi - xi|}.

We also know that xi is either 0 or 1, and that 0 <= mi <= 1. Thus, we can rewrite |mi - xi| as:

|mi - xi| = mi   if xi is 0
|mi - xi| = 1 - mi   if xi is 1

This expression can be rewritten as (1 - xi)(mi) + (xi)(1 - mi), which can be simplified to (1-2mi)xi + mi. Our distance function can then be rewritten as

SUMi {(1-2mi)xi + mi}

which is indeed linear.
Parts (b & c)

Basically, any density which behaves such that the probability is proportional to the distance to the mean will work. You can modify the Gaussian by throwing the 1st order Minkowski distance in instead of the Euclidean distance.

Also, a priori class probabilities will have to be fairly close to equal in order for the rule to work, as will most "distance-to-mean" classifiers.
Problem 3

The conjecture is true.

Lemma 1. Let there be a segment of length l inside a circle O of radius R. The probability of a line hitting the segment given that it hits the circle is Proof. Assume we have a segment of length l.



Now we select a random line m that intersects the circle. When choosing a random line that intersects a circle, we select a normal vector from angle [0, pi) and a radius from [-R, R], both with uniform distribution.





Over all angles theta and radii r, the chance of line m hitting the line segment given that it intersects the circle is

Integral0pi Integral-R+R      l cos theta dr dtheta             (That's 0 to pi; -R to +R.)

This integral comes out to: 2(l)/2*pi*R, and so the probability of hitting a segment of length l is l/pi*R.
For brevity, we take the convention of assuming that Prob(line m hits "something") to mean Prob(line m hits "something" | m intersects circle O).

Now let's find the probability of hitting a convex polygon P in a circle. If a line m hits a convex polygon, then it must hit exactly two segments of the polygon. (It could hit a point, but this occurs with probability zero, so I'll ignore it.) Let the segments be labelled pi, i = 1, ..., N. because there are always two segments hit at a time. Likewise, the probability of hitting any segment Pi is

As we said earlier, the chance that line m hits the convex polygon is equal to the chance that it hits exactly two segments. So to find this probability, we list every pair of segments:

Prob(m hits P) = Multiplying both sides by 2 gives us
2 * Prob(m hits P) = Since each line is Sumj != i [Prob(line m hits pi and pj)], by equation 1 this reduces to
Now place two polygons, B and S (big and small), into a big circle O, such that S is inside B. If line m hits S, then it must also hit B, which means it must also hit O. Therefore: 

           Pr(S & B)     Pr(S)     Pr(S & O)     Pr(S|O) * Pr(O)     Pr(S|O)
Pr(S|B) = ----------- = ------- = ----------- = ----------------- = ---------
             Pr(B)       Pr(B)     Pr(B & O)     Pr(B|O) * Pr(O)     Pr(B|O)


 Pr(S|O)     perimeter(S) / circumference(O)     perimeter(S)
--------- = --------------------------------- = --------------
 Pr(B|O)     perimeter(B) / circumference(O)     perimeter(B)

QED





Nope, not a counter-example
In the past, I have seen some students claim the following counter-example:





The problem arose when someone says, "Select an angle with uniform distribution. Then select a radius that hits the square." Since in your probabilistic space, the allowable radius is different for each angle, you can no longer select angles with uniform distribution. A better example to illustrate this concept is this:



Here we have a square in a rectangle. For half of my choices of angle, I always hit the square, so the probability of hitting the square given the rectangle is at least one-half.

Now take a rectangle of infinite length. Still, for half my choices of angle, I always hit the square. But the probability is zero in this case. Why? Because it is much more likely that a line slices the long part of the rectangle than slicing along its infinite length. This means that given a random line that intersects the rectangle, a line whose normal is near horizontal is more likely than a line whose normal is vertical, so we cannot select an angle with uniform distribution.



Problem 4

This is just one of those "plug-and-chug" problems. Just plug in the Gaussian distribution, play with the math, and the answer comes falling out.


Back to the CS644 page.