Wednesday, January 31, 2007

science research is not proof

Two days ago, we had a very nice discussion with Pat Langley.
Pat is more a cognitive scientist than a typical computer scientist, also very talkative:)

Basically, I question him why he recommend one paper saying that it took longer time for human beings to reason about difficult puzzles. The authors use a forward chaining scheme to build their model. Based on the similar performance of the model and human beings, it concludes that it took longer time for human beings to solve difficult puzzles.

OK. That paper is a little boring to me as the result is totally not surprising, or even too "obvious". Also, I really doubt human beings reasons like forward chaining or backward chaining. At the first sight, it seems the result of the paper is totally not convincing to me though the result is obvious.

So I asked him about the validality of this experiment set up. Then, I got his question, except this way, what can you do? Yep, I just post questions but forgot to think out of the box. What would I do if I am the researcher? You propose a model, then what you can do is to find "sufficient" evidence to support your claim. However, in most disciplines, this cannot be proved as mathematics. And even it's proved in someway, it might not work in reality. That's a common case in data mining, also in planning. The disadvantage of deduction is you have to trust your premise 100%, if one of your assumption is wrong, you mess up.

After reckon over that problem for a while, I have to sadly admit that's the only possible way or proper way to justify a new claim. So the problem is how to find "enough" evidence?

It seems that our science research is very weak. Or maybe that's exactly the process of doing research. You propose a model to solve a problem, explain some phenomenon. Then people use one counter example to disprove your model. (Disproof is always much easier than proof, but this seems not the case for refutation in logic proof). Then, a new model or theory is proposed.

You'll find that almost all science or engineering research are repeating the same cycle.

When going back to machine learning experiment, I think I've already put too much belief to 10-fold cross validation. But actually, most of tasks have no correct evaluation method. Like information retrieval, data analysis. these tasks requires a reasonable good answer but not an optimal solution.

Like the recent paper I coauthored with Payam for ICML, we found that two dramatically different feature selection evaluation methods turn out to be almost the same for comparing feature selection methods. There's actually no proof. But I believe it's an interesting research.

Science Research is pragmatic.

Thursday, January 25, 2007

Just finished the journal paper

I've just finished the journal paper for TKDD.
This paper really takes a while to fill in. I even got puke for rewriting it.

I guess I've looked through it at least 15 times. I really cannot bear to read it any more.

I am wondering, to do research, should I put more effort to polish a paper or to think about the idea?

I really hate spending so much time on writing the paper. i think it's not worthwhile.

The ridiculous thing about current stage of machine learning and data mining is that all these papers tend to foster UNNECESSARY formula to make paper more easy to accept.

That's not the goal for research. i would like more to motivate the problem well and present some simple, intuitive, sensible and working methods!!

Sunday, January 21, 2007

Some experiment result

I just finished some demo experiments. Originally, I wanted to find some toy example to show task selection's effect in transfer learning. Unfortunately, all the results I found are very disappointing.
Let me summarize the results a little bit:
(1) If the target task has very limited training data, transfer learning do help a lot compared with single task learning.
(2) The tasks selected make a very tiny difference (within 1% percent). Actually, it seems that combine all the tasks together is a very robust and reliable strategy for the data set I'm working on.
(3) Combine all the data together seems always better than transfer learning.


(1) is not surprising and has been approved by existing researchers.
(2) can not justify task selection.
(3) It seems that there's no difference between these tasks in the data set.

Maybe, one interesting problem is to determine whether the data extracted from multiple sources are actually the same. But I feel that's a more difficult problem than task selection.

Saturday, January 20, 2007

Flexing Muscle, China Destroys Satellite in Test

This is great news for Chinese!!

http://www.nytimes.com/2007/01/19/world/asia/19china.html?n=Top%2fNews%2fWorld%2fCountries%20and%20Territories%2fChina

Article Tools Sponsored By
By WILLIAM J. BROAD and DAVID E. SANGER
Published: January 19, 2007

China successfully carried out its first test of an antisatellite weapon last week, signaling its resolve to play a major role in military space activities and bringing expressions of concern from Washington and other capitals, the Bush administration said yesterday.

Only two nations — the Soviet Union and the United States — have previously destroyed spacecraft in antisatellite tests, most recently the United States in the mid-1980s.

Arms control experts called the test, in which the weapon destroyed an aging Chinese weather satellite, a troubling development that could foreshadow an antisatellite arms race. Alternatively, however, some experts speculated that it could precede a diplomatic effort by China to prod the Bush administration into negotiations on a weapons ban.

“This is the first real escalation in the weaponization of space that we’ve seen in 20 years,” said Jonathan McDowell, a Harvard astronomer who tracks rocket launchings and space activity. “It ends a long period of restraint.”

White House officials said the United States and other nations, which they did not identify, had “expressed our concern regarding this action to the Chinese.” Despite its protest, the Bush administration has long resisted a global treaty banning such tests because it says it needs freedom of action in space.

Jianhua Li, a spokesman at the Chinese Embassy in Washington, said that he had heard about the antisatellite story but that he had no statement or information.

At a time when China is modernizing its nuclear weapons, expanding the reach of its navy and sending astronauts into orbit for the first time, the test appears to mark a new sphere of technical and military competition. American officials complained yesterday that China had made no public or private announcements about its test, despite repeated requests by American officials for more openness about its actions.

The weather satellite hit by the weapon had circled the globe at an altitude of roughly 500 miles. In theory, the test means that China can now hit American spy satellites, which orbit closer to Earth. The satellites presumably in range of the Chinese missile include most of the imagery satellites used for basic military reconnaissance, which are essentially the eyes of the American intelligence community for military movements, potential nuclear tests and even some counterterrorism, and commercial satellites.

Experts said the weather satellite’s speeding remnants could pose a threat to other satellites for years or even decades.

In late August, President Bush authorized a new national space policy that ignored calls for a global prohibition on such tests. The policy said the United States would “preserve its rights, capabilities, and freedom of action in space” and “dissuade or deter others from either impeding those rights or developing capabilities intended to do so.” It declared the United States would “deny, if necessary, adversaries the use of space capabilities hostile to U.S. national interests.”

The Chinese test “could be a shot across the bow,” said Theresa Hitchens, director of the Center for Defense Information, a private group in Washington that tracks military programs. “For several years, the Russians and Chinese have been trying to push a treaty to ban space weapons. The concept of exhibiting a hard-power capability to bring somebody to the negotiating table is a classic cold war technique.”

Gary Samore, the director of studies at the Council on Foreign Relations, said in an interview: “I think it makes perfect sense for the Chinese to do this both for deterrence and to hedge their bets. It puts pressure on the U.S. to negotiate agreements not to weaponize space.”

Ms. Hitchens and other critics have accused the administration of conducting secret research on advanced antisatellite weapons using lasers, which are considered a far speedier and more powerful way of destroying satellites than the weapons of two decades ago.

The White House statement, issued by the National Security Council, said China’s “development and testing of such weapons is inconsistent with the spirit of cooperation that both countries aspire to in the civil space area.”

An administration official who had reviewed the intelligence about China’s test said the launching was detected by the United States in the early evening of Jan. 11, which would have been early morning on Jan. 12 in China. American satellites tracked the launching of the medium-range ballistic missile, and later space radars saw the debris.

The antisatellite test was first reported late Wednesday on the Web site of Aviation Week and Space Technology, an industry magazine. It said intelligence agencies had yet to “complete confirmation of the test.”

The test, the magazine said, appeared to employ a ground-based interceptor that used the sheer force of impact rather than an exploding warhead to shatter the satellite.

Dr. McDowell of Harvard said the satellite was known as Feng Yun, or “wind and cloud.” Launched in 1999, it was the third in a series. He said that it was a cube measuring 4.6 feet on each side, and that its solar panels extended about 28 feet. He added that it was due for retirement but that it still appeared to be electronically alive, making it an ideal target.

“If it stops working,” he said, “you know you have a successful hit.”

David C. Wright, a senior scientist at the Union of Concerned Scientists, a private group in Cambridge, Mass., said he calculated that the Chinese satellite had shattered into 800 fragments four inches wide or larger, and millions of smaller pieces.

The Soviet Union conducted roughly a dozen antisatellite tests from 1968 to 1982, Dr. McDowell said, adding that the Reagan administration carried out its experiments in 1985 and 1986.

The Bush administration has conducted research that critics say could produce a powerful ground-based laser weapon that would be used against enemy satellites.

The largely secret project, parts of which were made public through Air Force budget documents submitted to Congress last year, appears to be part of a wide-ranging administration effort to develop space weapons, both defensive and offensive.

The administration’s laser research is far more ambitious than a previous effort by the Clinton administration to develop an antisatellite laser, though the administration denies that it is an attempt to build a laser weapon.

The current research takes advantage of an optical technique that uses sensors, computers and flexible mirrors to counteract the atmospheric turbulence that seems to make stars twinkle. The weapon would essentially reverse that process, shooting focused beams of light upward with great clarity and force.

Michael Krepon, co-founder of the Henry L. Stimson Center, a group that studies national security, called the Chinese test very un-Chinese.

“There’s nothing subtle about this,” he said. “They’ve created a huge debris cloud that will last a quarter century or more. It’s at a higher elevation than the test we did in 1985, and for that one the last trackable debris took 17 years to clear out.”

Mr. Krepon added that the administration had long argued that the world needed no space-weapons treaty because no such arms existed and because the last tests were two decades ago. “It seems,” he said, “that argument is no longer operative.”

Mark Mazzetti contributed reporting.

Friday, January 19, 2007

Rejected by Google

I thought I could reject Google, but unfortunately Google rejected me!! :(



We would like to thank you for your interest in Google. After carefully reviewing your experience and qualifications, we have determined that we do not have a 'Software Engineering Intern' position available which is a strong match at this time.

Thanks again for considering Google. We wish you well in your endeavors
and hope you might consider us again in the future.

Thursday, January 18, 2007

Two TA work again!!!!

This semester, I have to work as TA for both AI and Data Mining Class again. So sad...
I am wondering why I am always so unlucky?

Just returned the new version of journal paper to boss. Feels really tired to make any change to that.

Wednesday, January 17, 2007

Google Phone Interview (1st round)

(1st round)

Why do you like google?
What's the difference between process and threads?
What's the difference between Java and C++?
Tell me the basic concepts of object-oriented programming?
How to implement mutiple inherience in Java? Why java use interface while C++ keeps feature of multiple inherience?

Have you ever involved into any team project? what did you do?
How do you handle the case that you have different opinions with manager?

Then discuss about my research topic.

How to find most common word in billions of documents?
1. If memory allowed (hashtable). what's the time complexity?
2. What if multiple machines? What's the bottleneck?
3. What if just one machine and hashtable can not be stored in the memory?

Then, I asked hime some general questions.
The last task, he asked me to send code to him in 30 mintues. The task is write a function to transform a string into an integer.

Google Phone Interview(2nd round)

Just finished my interview with Google. This time is an engineer, asking lots of detailed questions.

He knows a lot about lisp, so we just discuss about the issues about lisp. like
what's the difference of lisp and other languages?
which kind of lisp complier do you use? emacs lisp vs. clisp?

Then, some questions about operating system?
What's the difference between process and thread? What kind of information does thread maintain? its own stack? heap?
How and when to do a context switch? How do you handle an time slice interrupt?
What are the possible pitfalls for multi-thread programming?

How compiler works?
Can regular expression resolve the problem of nested structures?
Tell me something about grammar?
Is type check done before or after parsing?
(I did pretty bad in this session, so he finally stopped)

Familiar with TCP/IP, RPC, network programming? (NO, skipped)

Are you familiar with B-tree, red-black tree? (No, so we switch to binary search tree)
What's the time complexity of insertion or query in a binary search tree? O(lg n)
Worst case? (O (n))
How to transform a unbalanced tree into balanced tree?
Are you familiar with TreeMap in Java?

How hash table works? What if two object have the same key value? Show me one example of hash function.
What is the innate structure of a hashtable? (I said array) How do you map a key value to an index?

Finally, one technical question:
Given a source word, a target word, and a dictionary, how to transform the source word into target word by changing only one letter in each step. The word you get in each step must be in the dictionary.

Then, I asked him about some projects details.

Thursday, January 11, 2007

Wednesday, January 3, 2007

Desirable features of blog site

I just initiated two blogs, one in google blogspot, the other one in windows live space. Compare these two blog site is kind of interesting.

Windows Live:
1. Better handling photos
2. Template seems to be more beautiful.

Google blogspot:

1. Support group blog which is absent in windows live space.


Both sucks:
1. Can not set the permission for a specific post;
2. Can not change the layout and template freely, like change the background of template.

I am wondering how could these two blog sites to be so successful. Is there any other good ones?

Tuesday, January 2, 2007

Redundant Features useful or not?

I just browsed one interesting paper published in ICML'06:

nightmare at test time: robust learning by feature deletion

The motivation for the paper can be described as like buying stock.

Suppose you have several stocks with the same risk, and you have $1000. What would you do?

Of course, divide all the money evenly into these stocks should be more reliable than putting them into just one.

This is the same situation for feature selection. Suppose you select some relevant features from training data, but it could be wrong due to small samples or noise or any kind of noise.

In this process, you probably remove those redundant features as well. From this point of view, it seems more robust to keep those redundant features rather than remove them.

But from curse of dimensionality view, redundant features should be removed.

How to trade off redundancy and robustness?
I guess this is highly related to the definition of redundancy.

I'll comment on this issue more in future.

Monday, January 1, 2007

Some interesting search engines

Some interesting search engines: Hakia, powerset, snap
there's an article in nytimes talking about these search engines.

Will these be one of the future google?

I used to be a google fan. But I just found that google maps sucks. I tried different maps for LA trip, and mapquest seems to do a much better job. Google map finally and always got me lost. To be sure, this is not the first time.