Re: Q5, K dependency on N?

Re: Q5, K dependency on N?

Re: Q5, K dependency on N?

Re: Q5, K dependency on N?
got it...thank you.

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. 
Re: Q5, K dependency on N?
Speaking of computational complexity, some hard problems like boolean satisfiability (e.g. 3SAT) 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? 
Re: Q5, K dependency on N?
Quote:

All times are GMT 7. The time now is 10:20 AM. 
Powered by vBulletin® Version 3.8.3
Copyright ©2000  2021, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. AbuMostafa, Malik MagdonIsmail, and HsuanTien Lin, and participants in the Learning From Data MOOC by Yaser S. AbuMostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.