LFD Book Forum Q5, K dependency on N?
 Register FAQ Calendar Mark Forums Read

#1
01-26-2013, 07:50 PM
 ctallardc Junior Member Join Date: Jan 2013 Posts: 9
Q5, K dependency on N?

Only to clarify my thoughts in question 5.
k (break point) is a fix value for a given type of hypothesis (problem) .
k do not depend of N, it is bound to N. Correct?

Also there is 2 option for growth function:

1-if there is not a break point then
2-if there is break point , which is polynomial of degree k

So a grow function which it is polynomial with degree variable and depending of N could not be limited by because for big value of N the bound will not be valid.

Am I right?
#2
01-26-2013, 09:14 PM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,478
Re: Q5, K dependency on N?

Quote:
 Originally Posted by ctallardc k (break point) is a fix value for a given type of hypothesis (problem) . k do not depend of N, it is bound to N. Correct?
You are correct, but I am not sure what you mean by the last part. The bound creates is on the growth function .

Quote:
 Also there is 2 option for growth function: 1-if there is not a break point then 2-if there is break point , which is polynomial of degree k
Correct.
__________________
Where everyone thinks alike, no one thinks very much
#3
01-27-2013, 12:49 AM
 Suhas Patil Senior Member Join Date: Dec 2012 Posts: 57
Re: Q5, K dependency on N?

didn't quite get this part. Does large N have impact on the bound?

Quote:
 Originally Posted by ctallardc So a grow function which it is polynomial with degree variable and depending of N could not be limited by because for big value of N the bound will not be valid.
#4
01-27-2013, 12:55 AM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,478
Re: Q5, K dependency on N?

Quote:
 Originally Posted by Suhas Patil Does large N have impact on the bound?
The bound is valid for all , and being polynomial in means being bounded by some fixed polynomial for all values of .
__________________
Where everyone thinks alike, no one thinks very much
#5
01-27-2013, 12:56 AM
 Suhas Patil Senior Member Join Date: Dec 2012 Posts: 57
Re: Q5, K dependency on N?

got it...thank you.
#6
01-27-2013, 04:13 PM
 gah44 Invited Guest Join Date: Jul 2012 Location: Seattle, WA Posts: 153
Re: Q5, K dependency on N?

Much of computer science (computational complexity) has to do with algorithms that are exponential (hard) vs. polynomial (not so hard). A favorite example of an exponentially hard problem is the traveling salesman. As N increases to infinity, an exponential will eventually be greater than a polynomial, but in real problems N doesn't usually get so large. With three cities to visit, it isn't hard to find an optimal path. For small N, a polynomial can easily beat an exponential.

As I understand it here, the problem is different. As I understand it here, the problem is different. As long as the growth function is exponential, you can never learn. For coin flip, roulette wheels, and lotteries, no matter how many examples you have, they don't help in predicting what comes next.

If there is a break point, then past samples have useful predictive value. The higher the breakpoint, the more samples you need to make good predictions.

Blackjack with a finite number of cards has a breakpoint. Predictions on future cards become better as you see more cards played. Even so, the polynomial solution stays close to the exponential for quite a while.

At least that is the way I understand it.
#7
01-28-2013, 07:20 AM
 palmipede Member Join Date: Jan 2013 Posts: 13
Re: Q5, K dependency on N?

Speaking of computational complexity, some hard problems like boolean satisfiability (e.g. 3-SAT) have been observed to have easy solution times for the average random instances of the problem but is no practical upper bound on the solution times of the worst cases.

I wonder what does that mean for learning? Are there known cases of phase transition in learning time?

 Thread Tools Display Modes Hybrid Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home General     General Discussion of Machine Learning     Free Additional Material         Dynamic e-Chapters         Dynamic e-Appendices Course Discussions     Online LFD course         General comments on the course         Homework 1         Homework 2         Homework 3         Homework 4         Homework 5         Homework 6         Homework 7         Homework 8         The Final         Create New Homework Problems Book Feedback - Learning From Data     General comments on the book     Chapter 1 - The Learning Problem     Chapter 2 - Training versus Testing     Chapter 3 - The Linear Model     Chapter 4 - Overfitting     Chapter 5 - Three Learning Principles     e-Chapter 6 - Similarity Based Methods     e-Chapter 7 - Neural Networks     e-Chapter 8 - Support Vector Machines     e-Chapter 9 - Learning Aides     Appendix and Notation     e-Appendices

All times are GMT -7. The time now is 10:24 AM.