It finally happened. Many wise grad students and research scholars foretold this would happen. Many circumstances gave hints and warning signs that this would happen. I was forced to change my topic of research. I will no longer be working on "Kernel Methods", sorry Dr Vapnik.
I will be working on formulating efficient methodologies to detect plagiarism in source code.Bleah!!!
So everybody take a deep breath in and chant with me....
"I love my project"
"I love my project"
"I love my project"
"I love my project"
I guess I will not kill myself today !
Tuesday, October 19, 2010
Sunday, October 10, 2010
History of Learning Theory
According to Vapnik, history of research of the learning problem can be thought of as:
1. Constructing the first learning machines
2. Constructing the fundamentals of the theory
3. Constructing neural networks
4. Constructing alternatives to neural network
You cannot always model learning theory by looking at neural networks and modelling the human brain. Not everything can be modeled from nature. Look at the aircraft. It cannot be modeled from studying birds.
And that's all Vapnik has to say about that.
1. Constructing the first learning machines
2. Constructing the fundamentals of the theory
3. Constructing neural networks
4. Constructing alternatives to neural network
You cannot always model learning theory by looking at neural networks and modelling the human brain. Not everything can be modeled from nature. Look at the aircraft. It cannot be modeled from studying birds.
And that's all Vapnik has to say about that.
SVM StuckUp
I think I hit a road block with VC dimension and VC theory. Planning to do a writeup on SVM that gives a simple introduction. I would like to get it printed in some low key Indian journal.
The tutorial by Burges: http://citeseerx.ist.psu.edu/viewdoc/su
The tutorial by Burges: http://citeseerx.ist.psu.edu/viewdoc/su
Sunday, June 27, 2010
Getting your feet wet with SVM
This is a direct copy-paste from the Kernel Machines site:
There are several introductions, review papers, and books. As usual, there is a trade-off between how much time you want to invest, and how much you will get out of it. The following list is ordered by increasing time. On the log(time) domain, the increase in effort should be pretty much linear. ;)
(a) The introduction of the book Advances in Kernel Methods - Support Vector Learning or the high level overview of Hearst et al. from IEEE Intelligent Systems
(b) The tutorial papers of Burges (SVM pattern recognition) or Smola and Schoelkopf (SVM regression estimation)
(c) The small book of Vapnik, published by Springer (1995, or, in second edition, 1999), or the one of Cristianini and Shawe-Taylor (2000).
Alternatives that can be downloaded free of charge are PhD theses on SVMs, such as the ones of Schoelkopf (1997), Smola (1998), Herbrich (2000, to be finished soon).
(d) The collection of papers presented at the NIPS workshop on SVMs and kernel methods, from 1997 (Advances in Kernel Methods, MIT Press, 1999), 1998 (Advances in Large Margin Classifiers, MIT Press, 2000 - to appear), or 1999 (these will appear in a special issue of the journal Machine Learning at some point of time in the future).
(e) The long book of Vapnik, the bible of statistical learning theory (Wiley, 1998).
There are several introductions, review papers, and books. As usual, there is a trade-off between how much time you want to invest, and how much you will get out of it. The following list is ordered by increasing time. On the log(time) domain, the increase in effort should be pretty much linear. ;)
(a) The introduction of the book Advances in Kernel Methods - Support Vector Learning or the high level overview of Hearst et al. from IEEE Intelligent Systems
(b) The tutorial papers of Burges (SVM pattern recognition) or Smola and Schoelkopf (SVM regression estimation)
(c) The small book of Vapnik, published by Springer (1995, or, in second edition, 1999), or the one of Cristianini and Shawe-Taylor (2000).
Alternatives that can be downloaded free of charge are PhD theses on SVMs, such as the ones of Schoelkopf (1997), Smola (1998), Herbrich (2000, to be finished soon).
(d) The collection of papers presented at the NIPS workshop on SVMs and kernel methods, from 1997 (Advances in Kernel Methods, MIT Press, 1999), 1998 (Advances in Large Margin Classifiers, MIT Press, 2000 - to appear), or 1999 (these will appear in a special issue of the journal Machine Learning at some point of time in the future).
(e) The long book of Vapnik, the bible of statistical learning theory (Wiley, 1998).
Sunday, June 20, 2010
Introduction to SVM
I was reading up on Statistical Learning theory before stepping into SVM. Vapnik's book is a little too much for me right now.
This looks like a good place to start:
http://www.isis.ecs.soton.ac.uk/resources/svminfo/
Downloaded the Technical report and the SVM Toolbox. I still have to figure out how to use the toolbox. There was some error which says:
"??? Invalid MEX-file 'D:\poject\codeings\qp.dll': D:\poject\codeings\qp.dll is not a valid Win32 "
A few google searches tells me that I have to do the following:
In the SVM toolbox directory,
1. Go into the optimiser directory and type,
2. Type mex -v qp.c pr_loqo.c
it should create a file called qp.mex***.
3. Copy paste this file into svm directory.
It does not complain much now. But I am still figuring out how can I use it.
Why cannot people write documentation for their own code and post it along with the software.
This looks like a good place to start:
http://www.isis.ecs.soton.ac.uk/resources/svminfo/
Downloaded the Technical report and the SVM Toolbox. I still have to figure out how to use the toolbox. There was some error which says:
"??? Invalid MEX-file 'D:\poject\codeings\qp.dll': D:\poject\codeings\qp.dll is not a valid Win32 "
A few google searches tells me that I have to do the following:
In the SVM toolbox directory,
1. Go into the optimiser directory and type,
2. Type mex -v qp.c pr_loqo.c
it should create a file called qp.mex***.
3. Copy paste this file into svm directory.
It does not complain much now. But I am still figuring out how can I use it.
Why cannot people write documentation for their own code and post it along with the software.
Friday, June 11, 2010
My first steps into PhD
So I have decided to take that plunge into serious PhD business.
My professor has asked me to work on structural SVMs. But I have to work my way upto there from the bottom. So the course is route is going to be something like:
Machine Learning -> Supervised Learning -> Statistical Learning theory -> Pattern Recognition, Classification, Regression -> SVM -> Structural SVM
So the first question that I find asking myself is: What is Machine Learning definition? And I find the following definitions:
Arthur Samuel(1959) Feild of study that gives computers the ability to learn without being explicitly programmed.
Tom Mitchell(1998) Well-posed Learning problem: A computer program is said to learn from experience E with respect to some task T and some performance measure P, if its performance on T, as measured by P, improves with experience E.
The fundamental concepts in Machine Learning are:
1. Supervised Learning: Learning from Examples
Supervised Learning can consist of
Regression Problems : Predict continous values
Classification Problems: Predict discrete values
2.1 Statistical learning theory :tries to give an understanding of how and why learning algorithms work. This field of study makes it possible to formulate theorms that will garuentee that a learning algorithm will work.
How well can you approximate the learning function
How much training data do you need
3. Unsupervised Learning: Learning without any Examples
4. Reinforcement Learning: Learning on the fly from experience
During the course of my work, I hope this blog maintains a record of the different things that I lay my hands on.
For starters, I installed the latex support for blogs so that I can do stuff like this:
$\sum_{i=1}^nx_i$
More later....
My professor has asked me to work on structural SVMs. But I have to work my way upto there from the bottom. So the course is route is going to be something like:
Machine Learning -> Supervised Learning -> Statistical Learning theory -> Pattern Recognition, Classification, Regression -> SVM -> Structural SVM
So the first question that I find asking myself is: What is Machine Learning definition? And I find the following definitions:
Arthur Samuel(1959) Feild of study that gives computers the ability to learn without being explicitly programmed.
Tom Mitchell(1998) Well-posed Learning problem: A computer program is said to learn from experience E with respect to some task T and some performance measure P, if its performance on T, as measured by P, improves with experience E.
The fundamental concepts in Machine Learning are:
1. Supervised Learning: Learning from Examples
Supervised Learning can consist of
Regression Problems : Predict continous values
Classification Problems: Predict discrete values
2.1 Statistical learning theory :tries to give an understanding of how and why learning algorithms work. This field of study makes it possible to formulate theorms that will garuentee that a learning algorithm will work.
How well can you approximate the learning function
How much training data do you need
3. Unsupervised Learning: Learning without any Examples
4. Reinforcement Learning: Learning on the fly from experience
During the course of my work, I hope this blog maintains a record of the different things that I lay my hands on.
For starters, I installed the latex support for blogs so that I can do stuff like this:
$\sum_{i=1}^nx_i$
More later....
Monday, March 05, 2007
Using Windows Live Writer
If you are a lazy bum, and you dont like to log into blogger each time to post a blog, then you could download and use Windows Live Writer like me. The geeks also call it WLW. Sounds cool huh?
Setting up WLW for the new blogger can be quite a pain. But here is what I found:
(WARNING: This is only for the NEW Blogger accounts using WLW version 1.0.1 6) )
1. Download the latest version of WLW. This looks like a good place to find out that latest version.
2. Install WLW. You will need .NET framework for this.
3. Start WLW. In the weblog homepage url, give a url that WILL NOT RESOLVE.
4. Give the correct username and password. Your username will be something like username@gmail.com and password will be like ******** :-)
5. WLW will try to resolve the url and will fail (what did you expect). It will then go to a window that displays " Type of weblog you are using". In the drop down menu, choose Blogger(Atom). The immediate field below is the "Remote posting for your web log:" and it will now contain something like this:
http://www.blogger.com/feeds/<blog-id>
6. Replace your blog id in the <blog-id> section in the above URL and you are all set. If you don't know your blog id, you can simply find it out by going to your blog, click on view source in your browser and searching for it. Here is what it looked like for me: href=http://www2.blogger.com/rsd.g?blogID=28880654
My blog id here is 28880654. Find out yours and place that number in the url.
I have not been able to figure out how to upload images though. Have to check that out.
Disclaimer: The information here is subject to change with versions, platforms and OS. I am not responsible for your frustration if it does not work. The information here is a result of experimentation and was performed by an amateur. Please do try this at home.
Tuesday, August 15, 2006
Complexity and Big O
Ok so you are a programmer. And you have coded thousands of lines. But are you sure you need to have neccessarily coded all those lines. In computer science, often the question is not how to solve a problem, but how to solve a problem well.
Whenever you are studying algorithms, you find that there are always two issues to be addressed:
1. Efficiency / Performance
2. Complexity
Efficiency or performance deals with the CPU time, available memory, the disk and network usage when the program is run. So this will depend on the machine hardware, the code generated by the compiler and the user code.
Complexity, on the other hand, deals with resource allocation to the program and how it scales with size of the problem. In other words, what happens when the size of the program gets larger.
As complexity increases, the CPU usage and memory usage increases, thereby affecting performance. But a change in machine hardware or increase in memory will not cause a change in complexity. A much faster CPU may execute the algorithm faster, but it is doing the same amount of work as a slower CPU. Hence we can safely say that:
Complexity affects performance but not vice versa
Measuring Complexity
Complexity analysis attempts to characterize the relationship between the number of data elements and resource usage (time or space) with a simple formula approximation.
Why is the realtion between size of the problem and resource usage important? Well, right from the time when the first program was written, many programmers have had ugly surprises when they moved from small test data to large data sets.
The Big O Notation
The definition from NIST is as follows:
Definition: A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = O(g(n)) means it is less than some constant multiple of g(n). The notation is read, "f of n is big oh of g of n".
Ok I admit, I had a tough time understanding that. A simpler explanation would be that Big O is concerened with what happens to the algorithm for very large values of N. Hence it will NEVER have constants or lower order terms. These terms are dropped. This is due to the fact that when N becomes large, these terms do not have a significant effect on the total complexity.
For example, if the number of operations is N^2 - N, for large values of N, the single N term is insignificant compared to N^2, therefore one of these sorts would be described as an O(N^2) algorithm. Similarly constant multipliers are ignored, so a O(4*N) algorithm is equivalent to O(N).
A list of common orders and corresponding examples can be found here!!
Can we blindly trust Big O
The answer is NO!! There are some problems with complexity analysis:
1. Too hard to analyze: Many algorithms are too hard to analyze mathematically
2. Average case unknown. There may not be sufficient information to know what the most important "average" case really is, therefore analysis is impossible.
3. Unknown constant. Both walking and traveling at the speed of light have a time-as-function-of-distance big-oh complexity of O(N). Altho they have the same big-oh characteristics, one is rather faster than the other. Big-oh analysis only tells you how it grows with the size of the problem, not how efficient it is.
4. Small data sets. If there are no large amounts of data, algorithm efficiency may not be important.
References:
1. Complexity and Big O Notation
2. uw-madson notes
3. Algorithms and Big O Notation
Whenever you are studying algorithms, you find that there are always two issues to be addressed:
1. Efficiency / Performance
2. Complexity
Efficiency or performance deals with the CPU time, available memory, the disk and network usage when the program is run. So this will depend on the machine hardware, the code generated by the compiler and the user code.
Complexity, on the other hand, deals with resource allocation to the program and how it scales with size of the problem. In other words, what happens when the size of the program gets larger.
As complexity increases, the CPU usage and memory usage increases, thereby affecting performance. But a change in machine hardware or increase in memory will not cause a change in complexity. A much faster CPU may execute the algorithm faster, but it is doing the same amount of work as a slower CPU. Hence we can safely say that:
Complexity affects performance but not vice versa
Measuring Complexity
Complexity analysis attempts to characterize the relationship between the number of data elements and resource usage (time or space) with a simple formula approximation.
Why is the realtion between size of the problem and resource usage important? Well, right from the time when the first program was written, many programmers have had ugly surprises when they moved from small test data to large data sets.
The Big O Notation
The definition from NIST is as follows:
Definition: A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = O(g(n)) means it is less than some constant multiple of g(n). The notation is read, "f of n is big oh of g of n".
Ok I admit, I had a tough time understanding that. A simpler explanation would be that Big O is concerened with what happens to the algorithm for very large values of N. Hence it will NEVER have constants or lower order terms. These terms are dropped. This is due to the fact that when N becomes large, these terms do not have a significant effect on the total complexity.
For example, if the number of operations is N^2 - N, for large values of N, the single N term is insignificant compared to N^2, therefore one of these sorts would be described as an O(N^2) algorithm. Similarly constant multipliers are ignored, so a O(4*N) algorithm is equivalent to O(N).
A list of common orders and corresponding examples can be found here!!
Can we blindly trust Big O
The answer is NO!! There are some problems with complexity analysis:
1. Too hard to analyze: Many algorithms are too hard to analyze mathematically
2. Average case unknown. There may not be sufficient information to know what the most important "average" case really is, therefore analysis is impossible.
3. Unknown constant. Both walking and traveling at the speed of light have a time-as-function-of-distance big-oh complexity of O(N). Altho they have the same big-oh characteristics, one is rather faster than the other. Big-oh analysis only tells you how it grows with the size of the problem, not how efficient it is.
4. Small data sets. If there are no large amounts of data, algorithm efficiency may not be important.
References:
1. Complexity and Big O Notation
2. uw-madson notes
3. Algorithms and Big O Notation
Monday, June 12, 2006
UnsupportedEncodingException
Java is an exceptional language. While working on my main project regarding search engines, I was drowned in various exceptions that were mericilessly thrown to me by Java.
The latest exception that I encountered was UnsupportedEncodingException cp437
It took some time for me to find out the cause.
If you have encountered this exception and still wondering what to do about it, then all you have to do is install the Java Runtime Environment (JRE) with support for all languages and fonts.
I think I got an endofblog exception now.
The latest exception that I encountered was UnsupportedEncodingException cp437
It took some time for me to find out the cause.
If you have encountered this exception and still wondering what to do about it, then all you have to do is install the Java Runtime Environment (JRE) with support for all languages and fonts.
I think I got an endofblog exception now.
Monday, May 29, 2006
Meet pagefile.sys
My first acquaintance with the infamous pagefile.sys was when windows rudely announced that I had no more free space on my C:\ drive. I was working on Photoshop and had just finished processing a new wallpaper for the college. A quick scan with showman told me that my pagefile.sys was around 1.5GB
My first reaction was to delete that space hogger from the face of my hard disk. But wait, I had a bad feeling about this. My geek instincts told me that I had to check on this first.
What is pagefile.sys
Do you what is RAM?
Do you know what is a hard disk?
Do you know what is a processor?
If you answered "No!!" to all the questions mentioned above, you may stop reading this page NOW. May the gods of computers strike ye down with lightning from a shorted SMPS.
If you answered "Yes!!" to any one of the questions, please treat yourselves to a cup of coffee and read on.
The simplest explanation to the purpose of pagefile.sys is that it acts like a swap file. Pagefile.sys is how Windows handles virtual memory using demand paging. Okay now you want to know what is demand paging and virtual memory...
Virtual Memory and Demand Paging
Virtual memory is an attempt to fool the computer to think that it has more RAM.
The Memory Management Unit(MMU) on the CPU has the ability to substitute space on the hard disk for actual RAM. This space is called swap space. And this mechanism is called demand paging.The swap space is contained in a file called swap file.
Hence swap files allow the operating system to simulate extra memory.
Physical memory + swap file = virtual memory
Why extra memory you greedy operating system?
I will share a profound truth, that dawned on me when in deep contemplation with lomax.
"Memory is like clean underwear. You never get to have enough of it."
Suppose you don't have enough RAM on your machine, you can create a large swap file and hence get a larger virtual memory. The advantage here is that you can load larger programs into your memory, and run more programs concurrently.
The downside is that if you have serious memory hogging programs, they will pull down the performance due to frequent swapping of files between RAM and swap disk.
Can I configure pagefile.sys settings
Sure you can!!
Please read: Tweaking and optimizing pagefile.sys
Other Useful Links
Page File Information
Optimising PageFile Performance
Purpose of PageFiles
Another Blog that contains useful information
My first reaction was to delete that space hogger from the face of my hard disk. But wait, I had a bad feeling about this. My geek instincts told me that I had to check on this first.
What is pagefile.sys
Do you what is RAM?
Do you know what is a hard disk?
Do you know what is a processor?
If you answered "No!!" to all the questions mentioned above, you may stop reading this page NOW. May the gods of computers strike ye down with lightning from a shorted SMPS.
If you answered "Yes!!" to any one of the questions, please treat yourselves to a cup of coffee and read on.
The simplest explanation to the purpose of pagefile.sys is that it acts like a swap file. Pagefile.sys is how Windows handles virtual memory using demand paging. Okay now you want to know what is demand paging and virtual memory...
Virtual Memory and Demand Paging
Virtual memory is an attempt to fool the computer to think that it has more RAM.
The Memory Management Unit(MMU) on the CPU has the ability to substitute space on the hard disk for actual RAM. This space is called swap space. And this mechanism is called demand paging.The swap space is contained in a file called swap file.
Hence swap files allow the operating system to simulate extra memory.
Physical memory + swap file = virtual memory
Why extra memory you greedy operating system?
I will share a profound truth, that dawned on me when in deep contemplation with lomax.
"Memory is like clean underwear. You never get to have enough of it."
Suppose you don't have enough RAM on your machine, you can create a large swap file and hence get a larger virtual memory. The advantage here is that you can load larger programs into your memory, and run more programs concurrently.
The downside is that if you have serious memory hogging programs, they will pull down the performance due to frequent swapping of files between RAM and swap disk.
Can I configure pagefile.sys settings
Sure you can!!
Please read: Tweaking and optimizing pagefile.sys
Other Useful Links
Page File Information
Optimising PageFile Performance
Purpose of PageFiles
Another Blog that contains useful information
Sunday, May 28, 2006
Hello World
/**
* I am starting this blog as a part of my venturing into the programming world.
* I will share my code and terrible...umm terrific insight on various other codes
* that I come across.
*/
#include
void main()
{
helloworld.programming();
}
* I am starting this blog as a part of my venturing into the programming world.
* I will share my code and terrible...umm terrific insight on various other codes
* that I come across.
*/
#include
void main()
{
helloworld.programming();
}
Subscribe to:
Posts (Atom)