Video on remembering periodic table

The intent of above video is to demonstrate the power of mnemonics.



For more details: see http://niketanblog.blogspot.com/2006/07/remembering-periodic-table.html

Moshe Vardi's talk on P v/s NP

Just attended a very interesting talk by Moshe Vardi on P v/s NP. Thought of summarizing it:
- He introduced the concept P (solvable in polynomial time) v/s NP (verifiable in polynomial time) and then compared them to "discovering v/s checking" a proof and which is easier. Say for some reason, P = NP, it would be as easy to discover the proof for a given problem than to read/check the proof given in textbook (as said by Scott Aaronson, everyone would be Gauss). Also gave some examples of P v/s NP problems (hamiltonian/eulerian cycles) and some history.
- Then introduced some basic concepts of finite-model theory, first order logic and k-SAT problem. Then discussed nomenclature of 'phase transition' wrt statistical physics, random k-SAT and XOR-objection on Deolalikar's paper.
- If you don't intend to read Deolalikar's paper, here is what he is trying to say: "9-SAT cannot be in P" (in which he uses Immerman's theorem and random k-SAT), which clearly is not the case if we replace disjunction by XORs (which can be solved by Gauss elimination ... still have to think about this). For more details read Lipton's blog.
- Then Vardi discusses the importance of P v/s NP:
1. If we prove P = NP, still there can be problems of size (10n)^10000 which are in P but take way too long to solve.
2. If we prove P != NP, again there can be NP problems of size n^(log log log n), which then becomes a way faster solution.
- On his closing note, Vardi cites the industry SAT solvers. Though the industry SAT solvers are capable to solve SAT instances with million variables, there are some SAT instances with few hundred variables which are extremely difficult to solve. According to Vardi, identifying those difficult cases is way more important than proving SAT is P (or not in P).

Now, let me quote few of his comments:
=> The argument is using induction to prove set of natural numbers is finite ... set of zero elements is finite, add a natural number to it and it will be finite, then add another and so on ... hence QED.
=> Are they same in theory and practice, well it depends ... in theory they are same, but in practice they are different.
=> Finite model theory ... number of variables ... arbitrary long, but STILL finite.

An Attempt to understand Machine Learning (Part 1)

I still remember the excitement when I took "Theory of Automata" course in my undergrad and was introduced to Turing machine. Few days after digging a little, I read Church-Turing thesis which stated "Every algorithms can be expressed in terms of Turing machine". This was like saying ... well you have framework for understand everything you will eventually learn in your Masters or PhD. However, mapping everything to Turing machine kept on becoming difficult as I started doing research and particularly when I took Machine Learning course. Most people come up with different perception when they take Machine Learning or Artificial Intelligence course.

Before I begin let me make you aware that Machine "Learning" is not same as human "learning". Humans learn something is a way that is not fully understood by scientific community. Let's say two persons X and Y see a mango tree. X has never seen a mango tree before so he will create a mental picture of it as a medium sized tree with green leaves. Y on other hand will create a mental image of tree and associate it with a mental image of mango or may be even with other senses like "it taste like mango shake". Any further discussion between X and Y will be based on their mental images and not reality. Note: information in mental images is less than information in reality and the reasons for this information loss are:
- We cannot store or process all the information in the world (due to lack of 'infinite' focus)
- Everyone filters information from reality according to their past experiences or beliefs.

Hence, since it is virtually impossible to have two person with exactly same experiences, it is impossible to have two people with exactly same mental images or information. If we treat the mental image as an output or even intermediate variable that we use to spit out an output, there is no "common" theory/algorithm that will generate a common output for all humans for same problem. Hence, this huge diversity (which makes life interesting) makes humans difficult to understand.

Most scientists (at least the neurologist/psychiatrist/psychologist) use abstraction (i.e. weed out details and rely on central theme i.e. "tree") to specify a theory/algorithm that applies to all. Yet there is another problem with human learning, humans don't learn or process with objects but with patterns. Furthermore, humans use association (and not exhaustive search through all the patterns) to interpret a situation. This process of association is somewhat random or at least extremely diverse (i.e. every person associates object A to object B using different sets of patterns and these patterns change over a period of time). Hence, it is extremely difficult to play around with such diversity using a single unifying theory. So, machine learning is not about building a machine that will always pass the "Turing test" for all the humans and in all the situations (though that is the ultimate goal of Machine Learning). (Btw, if you don't know about Turing test, read http://en.wikipedia.org/wiki/Turing_test.)

Having said that, it is also very important not to be too humble while defining what Machine Learning is, especially if you compare every machine learning situation to Turing machine. Remember, assumptions for Turing machine are (that are not necessarily applicable to all Machine Learning problems):
- Entire input is available at the beginning of computation.
- No state is maintained between execution of two (same or different) programs.
Especially interesting case where it is very difficult to define the problem in terms of Turing machine is Reinforcement Learning that we will study later. Also paper by Leeuwen and Wiedermann that discusses Turing machine in comparison to contemporary computing would be a nice read.

By now I made two key points (or mental images :)):
1. Machine Learning != Human Learning
2. Machine Learning != Turing machine

References:
1. The Turing Machine Paradigm in Contemporary Computing - Leeuwen and Wiedermann.

The Last Lecture

Carnegie Mellon Professor Randy Pausch (Oct. 23, 1960 - July 25, 2008) gave his last lecture at the university Sept. 18, 2007, before a packed McConomy Auditorium. In his moving presentation, "Really Achieving Your Childhood Dreams," Pausch talked about his lessons learned and gave advice to students on how to achieve their own career and personal goals.

If you haven't seen the video, I highly recommend it: http://www.youtube.com/watch?v=ji5_MqicxSo

These are some of the points that I found enlightening:
- We don't beat the reaper by living longer, but by living well, and living fully — for the reaper will come for all of us. The question is: what do we do between the time we're born and the time he shows up.
- It is not the things we do in life that we regret on our death bed. It is the things we do not. Find your passion and follow it.
- The brick walls are there for a reason. The brick walls are not there to keep us out; the brick walls are there to give us a chance to show how badly we want something.
- Experience is what you get when you didn't get what you wanted.
- When you see yourself doing something badly and nobody's bothering to tell you anymore, that's a very bad place to be. Your critics are the ones telling you they still love you and care.
- When you are pissed off at somebody, and you're angry at them, you just haven't given them enough time. Just give them a little more time — and they'll almost always impress you.
- Never lose the child-like wonder. It's just too important. It's what drives us.
- Don't complain; just work harder.
- Show gratitude.
- It's not about how to achieve your dreams. It's about how to lead your life. If you lead your life the right way, the karma will take care of itself. The dreams will come to you.
- If I could only give three words of advice, they would be, "tell the truth." If I got three more words, I'd add: "All the time."
- Do not tell people how to live their lives. Just tell them stories. And they will figure out how those stories apply to them.

May GOD rest his soul and bless his family.

Preparing a new Windows machine

I am writing this mail to serve as backup in case I have to create a fresh installation.

I recently purchased a new laptop: Lenovo U350 for following reasons:
cheap ($600 + tax because of a coupon), extremely light (around 4 pound), no CD/DVD drive (which makes it light. Also, I have rarely used it on my previous laptops and it seemed to be dead weight), 13" laptop (another reason why it's light, also 13" is almost about the right size between netbook and 15" laptop), 8 cell battery (with netbook like power-saving circuit, which makes the battery last "really" long), core 2 duo + 320 GB HDD + 4GB RAM (for my programming needs), VGA output (to connect to projector for presentations), other useful accessories (HDMI (to connect to my home TV), 3USB slots, kensington lock slot, webcam, mic/headphone slot, card reader)

I have an iPhone 3Gs + a ubuntu machine (another reason I did not want a CD/DVD drive on my laptop) in office. So, I have installed following "free" softwares on new Windows 7 machine:
1. Java: JDK, Netbeans, Eclipse
2. Reader / Writer: Openoffice (for doc), Latex (Miktex, Texnicenter), Adobe Reader (for reading pdfs), PDF X-Change Viewer (for marking/highlighting pdfs), CutePDF (for creating PDF), GSView (for PS), DJVU Viewer
3. Educational: Mendeley (for maintaining my bibliography), Sciplore (for mindmaps -> Using PDF X-Change I can create a printable version of my mindmap)
4. Synchronization: Evernote (for notes), Dropbox + TortoiseSVN (for documents), Firefox + Xmarks (for bookmarks)
5. Fun: VLC, Divx, Real player, Adobe Flash, iTunes
6. Communication: GTalk, Zimbra (for managing my Personal + Rice mails) ... Since I don't chat much I didnot install Yahoo Messenger and Skype.
7. Protection: AVG Antivirus, Zone Alarm Firewall, Also created a restore point using Lenovo's once click software
8. Others: R, WinSCP, Putty (Also will install Magic Disc in case I have to work with CD/DVD image)

I also use Toodledo (for my TODO list) and Eternity (for time logging) on my iPhone.

Long term research goals

My previous post discussed why I decided to do PhD ? This post discusses what I want to do after my PhD. During Sigmod, I was thinking about a question that was troubling me last year: "Whether to apply for faculty position or industry job"

Somehow "academia" seems more sense for me. So, I started asking people what are skills required to get a faculty position. Here is a summarized version of collective advices from my advisor and colleagues.

I had a discussion with one of my friend in which I made a really important point. If you want to understand any major events (political, personal, social, ...), ask yourself a simple question: "How does this relate to money ?". This principle applies in academic hiring position as well. Whether or not you will be hired as a faculty or not will solely be decided by one fundamental question: "Can you get funding during and after your tenure ?"

If the answer is "may be", then and then only the hiring committee will look into teaching skills and managerial/mentoring skills.

Let's revisit the funding question. Your chances of funding will be significantly decided by three questions:
1. Is your research worth funding ?
2. How well can you present your research ?
3. How many people know about you and your research ?

The people who are involved in your hiring process will try to extrapolate the answers to these questions based on following indicators:
a. They already know you or your advisor or have at least heard about you.
b. You can give an interesting 1 hour presentation on your central research idea.
c. You have good number of first author papers.
d. You have recommendation letters from well known researchers from your field.

Here is list of things I believe a PhD student can to to improve these indicators.

1. Find as soon as possible the topic you want to expertise in and publish as many first author papers as possible in that field.
   
2. Give as many (paper, poster, demo) presentations as possible in well known conferences.
   
3. Collaborate and also go for research internship. Your mentors will be the ones who will write you the recommendations. It is necessary to have strong recommendation letters from people other than your advisor.
   
4. Be a (dummy) reviewer for conferences and also learn skills necessary for writing proposals.
5. Work as hard as you can and think about your research all the time.

The corollary to above points are:
1. Number of first author papers are more important than publication count.
2. Bad papers may haunt you during hiring process.
3. Know the list of current hot topics --> also what "good" researchers are working on (Indexing)
4. Nobody cares about your GPA, courses you took or your extra-curricular activities.
5. You can give an interesting 1 hour presentation only if you have one research theme rather than papers scattered all over the field.


Of course there are exceptions to all above rules. So, don't be hard on yourself :)

Pragmatism to Perspective

Work hard(???) at what others are doing
Then tried to do it better
Then tried to do something that many ppl were not doing
However, road less travelled doesnot always make a difference.

Doing something different might also not work
Invested or may be wasted time on pointless, but different things
Convinced myself that what I am doing is what I really want
Then realized I didnot know what I really want.

Dreams turned out to be too ambitious
Or may be reality turned out to be too harsh
Running away from truth seemed simpler choice
Since rationality has hit a road-block.

Answer hopefully is mixture of all:
Cup of pragmatism and hardwork,
a spoon of perspective and a entire jar of passion
Also, bulk load of unknown spices from life.

GTD Workflow

My updated GTD Workflow for academic research in pdf format for printing can be found at my trac repository.

Here is the jpeg version of the same:


Note:
1. Most GTD systems have feedback loop for Delegated tasks. I do not maintain that because most of my tasks (research/coursework) do not involve lot of people interactions / delegations.