Popular Posts

Sunday, March 4, 2012

Difference between Self-taught learning and semi-supervised learning settings

There are 2 common type of unsupervised learning settings:
  • Self-taught learning
  • Semi-supervised learning
   Self-taught learning setting is more versatile, broadly applicable and does not assume that your unlabeled data has to be drawn from the same distribution as your labeled data. In Self-taught learning setting it is not necessary that most of the unlabelled data belongs to at least one class, it may happen that appreciable amount of data does not belong to any class. 

   Semi-supervised learning setting assumes that unlabeled data comes from exactly the same distribution as the labeled data. In  Semi-supervised learning setting most of the unlabelled data belongs to one of the classes.

These two methods are most powerful in problems where we have a lot of unlabeled data, and a smaller amount of labeled data.

Saturday, March 3, 2012

closed-form expression for nth term of the Fibonacci sequence

Generally we all know what a Fibonacci series is. I had 1st seen it in my computer science class where I used the recursive relation to find nth term of Fibonacci series, when I was 1st taught recursive functions. Today my friend told me that he solved the recurrence using power series method to get the golden ratio's and the relation. So I also wanted to write about it and derive the same with z-transform which I learned in my DSP class, one of the few classes I read the books of. So here we are and lets get started.

So lets see the Fibonacci series first...


If y(n) be the nth term of the Fibonacci sequence then the recurrence relation below clearly satisfies the relation below...
y(n) = y(n-1) + y(n-2)            --------------(1)

we also have 2 initial conditions:
1) y(0) = y(-1) + y(-2) = 1
2) y(1) = y(0)  + y(-1) = 1

from these conditions we see that y(-1) = 0 and y(-2)=1 work this out and make sure u get this.

 To take the z-transform of the eq. (1) we need to know about one-sided or unilateral z-transform. Its not very different from two-sided z-transform. Its just that in two-sided z-transform needs signal to be specified in the range (-∞,∞). Since input is applied at a finite time sequence say n0 therefore we need signal to be specified in the range [n0,∞).

The unilateral or one-sided z-transform may be defined as:
 and the time shifting property is also a bit different just a bit modified and can be intuitively proved.Which I am not going to do here.

Taking z-transform by applying time delay property,  we get..

Y(z) = [z-1 Y(z) + y(-1)]  + [z-2Y(z) + y(-2) + y(-1)z-1]
Y(z) = 1/(1 - z-1 - z-2)
Y(z) = z2/(z2 – z1 -1)
Y(z) = z2/(z - p1)(z - p2)        where p1=(1 + √5)/2     and     p2=(1 – √5)/2
Y(z) = 1/(1 - p1 z-1)(1 - p2 z-1)
using partial fraction, we get :
Y(z) = A1/(1 - p1 z-1)  +  A2/(1 - p2 z-1)
where A1 = 1/(1 – p2p1-1) = p1/(p1 – p2) = p1 / √5
and     A2 = 1/(1 – p1p2-1) = p2/(p2 – p1) = -p2 / √5

 Now we know that or can be easily verified that:
UZ(an u(n)) = 1/(1 – az-1)  where UZ(.) is unilateral z-transform

so we finally get, 

y(n) = [A1(p1)n   + A2(p2)n ]u(n)

substituting A1 and A2 we get:
 y(n) = (1/√5)[(p1)n+1   - (p2)n+1 ]u(n)    ---------------(2)
 y(n) = (1/√5)[(p1)n+1   - ( p1_conjugate)n+1 ]u(n)  
 where p1=(1 + √5)/2     and     p2 = p1_conjugate=(1 – √5)/2
equation (2) above is the formula which works as nth term of Fibonacci series.