Paper Review: Detecting Spam Web Pages through Content Analysis

This paper was written by Ntoulas (UCLA) and et al. (Microsoft Research) and 15th international conference on World Wide Web, 2006.

This paper is continuing work following two other papers on detecting spam web pages by the same group of authors. It focuses on content analysis as apposed to links. The authors propose 10 heuristics and investigate how well these heuristics correlate with spam web pages using a dataset of 17,168 pages. These heuristics/metrics are then combined as features in addition to 28 others to build a training dataset, so machine learning classifiers can be used to classify spam web pages. Out of the several classifiers experimented, C4.5 decision tree algorithm performed the best, so bagging and boosting are used to improve the performance and the results are reported in terms of accuracy and the precision recall matrix.

The main contributions of this reference paper include detailed analysis of the 10 proposed heuristics and the idea of using machine learning classifiers to combine them in the specific spam web page detection application. Taking advantage of the large web page collection (over 105 million) and a good-sized labeled dataset (17,168 pages), the paper is able to show some nice statistical properties of web documents (spam or non-spam) and good performances of existing classifying methods when using these properties as features of a training set.
Not being an export in the IR field, I cannot tell which of the proposed 10 heuristics are novel ideas with respect to spam web page detection. However, fraction of visible content and compression ratio seem to be very creative ideas and look very promising. Using each heuristic by itself does not produce good performance, so the paper combined them into a multi-dimensional feature space. Note here that this method has been used in many research domains with various applications.

One common question IR researchers tend to ask is: how good is your dataset? In section 2, the paper did a good job acknowledging the biases of the document collection and then further provided good justifications. This makes the paper more sincere and convincing. The paper also did a good job explaining things clearly. For instance, in section 4.8, the example provided made it very easy to distinguish “Fraction of page drawn from globally popular words” from “Fraction of globally popular words”. Another example is in section 4.6 when the paper explained how some pages inflated during compression. I specifically liked how the authors explained the concepts of bagging and boosting briefly in this paper. They could have simply directed the readers to the references, but the brief introduction dramatically improves the experience for those readers who have not worked with such concepts (or are rusty on them such as in my case).
Although well-written, the paper still has some drawbacks and limitations. Firstly, section 6, related work, should really have been placed right after introduction. That way, readers can get a better picture of how this problem has been tackled in the IR community and also easily see how this paper differs. Also, this section gives a good definition of “content spam”, and it makes much more sense to talk about possible solutions after we have a clear definition.

Secondly, in section 3, the paper talks about 80% of all pages (as a result of uniform random sampling) being manually classified? I strongly suspect that is what the authors meant to say. 80% of over 105 million pages will take A LONG TIME to classify, period! Apparently this collection is not the same DS dataset mentioned in section 4 because the DS dataset only contained pages in English. So what is this collection? It apparently is a larger labeled dataset than the DS dataset. From Figures 6, 8, 10, and 11, we see the line graph touching the x-axis due to possibly not enough data. Using this larger labeled dataset (of the English portion) might have produced better graphs. Another thing I’d like to mention here is that spam web page is a “subjective classification” (at least for me it is). Naturally I’d think the large data collection was labeled under a divide-and-conquer approach, so each document is only looked at by one evaluator. If this were true, then the subjectivity of the evaluators plays an important role on the label. A better approach would have been having multiple evaluators working on the same set of web pages and label following the majority vote to minimize each evaluator’s subjectivity.

Thirdly, when building the training set, the proposed 10 heuristics are combined with 28 other features before applying the classifier. I think it would be better to compare results of using only these 10 features, using only those original 28 features, and using all features combined. That way, we can better evaluate how well these additional 10 heuristics contributed to the improvement of the classifiers.

Additionally, in section 4.1, the paper says “there is a clear correlation between word count and prevalence of spam” according to Figure 4. I failed to see the correlation.

Lastly, the experiment results are only for English web pages. Since the analysis in section 3 (Figure 3) clearly indicate that French and German web pages contained bigger portions of spam web pages, it would be great to see how proposed solution works with those languages. I understand the difficulty of working with other languages, but it would really improve the paper even if only some very initial experiments were performed and results reported.

There are other minor problems with the paper as well. For example, for each heuristic, the paper reported the mode, median, and mean. I think it is also necessary to provide variance (or standard deviation) because it is an important descriptor of a distribution. I would also suggest using a much lighter color so that the line graph is more readable for the portions where it overlaps with the bar graph. Dr. Snell once said that we should always print out your paper in black and white to make sure it looks okay, and I am strong believer of that! Also in section 4.3, the authors meant to say the horizontal axis represents the average “word length” within a page instead of “number of words”.

I think it’s worth mentioning that the authors did an awesome job in the conclusions and future work section. Detecting web spam is really like an “arms race” between the spam filter designers and spammers. As new technologies are developed to filter spam, spammers will always work hard to come up with ways to break the filtering technology. This is an ongoing battle and degradation of the classification performance over time is simply unavoidable.

This is a well-written paper that showed excellent performance, and I certainly enjoyed reading it. I’d like to end this report with a quote directly from the paper which is so well said:

“Victory does not require perfection, just a rate of detection that alters the economic balance for a would-be spammer. It is our hope that continued research on this front can make effective spam more expensive than genuine content.”

I just learned recently that Superman's father is the Godfather!

Robot of the Day: Wakamaru, the Robot Actor and Salesman

On the second day of the Human-Robot Interaction (HRI) 2010 conference, Dr. Ishiguro, one of the main organizers of this year's HRI conference, led us to a small traditional Japanese theater, and presented us a robotic play titled Hataraku Watashi (I, Worker), where I finally had the pleasure to meet the famous robot actor (and actress) in person. I have heard of them and their play from news media a long time ago.

The two robots stared in the theatrical production are the Wakamura robots made by Mitsubishi, named after the child name of a famous ancient Japanese general, although these yellow, 1 meter tall, and 30 kg robots were originally designed for companionship for elderly and disabled, selling at a hefty price of $14000 each.

The project was headed by Dr. Ishiguro at Osaka University, who sent his grad students to theater classes and also invited famous Japanese playwright, Oriza Hirata, to write a story. The result was a 20-minute piece named I, worker starring two Wakamura robots alongside two human actors. The robots played two depressed household servants who work for a young couple. Learning from the young couple's life experience, the robots grew tired of their mundane lifestyle and longed to break free and see the world.

Although the robots are not capable of facial expressions, their head and limb movements and the autonomous navigation capabilities successfully conveyed the depressing feeling to the audience. Most of the audience that day did not speak Japanese, but fortunately, Dillon, an American who works at ATR research institute in Osaka volunteered the translation on a big monitor, so we were able to follow the story. One interesting thing we noticed was that the robots apologized a lot, probably due to Japanese culture. The video below shows sections of the play in Japanese.

Since the robots were playing robots in the play, it is pretty hard to beat their performance with real human actors, but when asked about how they felt about the two robots in rehearsals and the real play, the human actor and actress actually almost thought of these robots as real human actors. So what if one day we have plays that comprise of robot actors only, when robots are becoming more sophisticated? What if one day we start to see robots sitting in the audience together with human? Don't think that would be interesting and entertaining by itself?

Other than acting, these Wakamaru robots are also acting as salesman in clothing stores now, and one found a job in a Uniqlo store in downtown New York. This robot is not only capable of conversations, it can also recommend promotions to customers, and best of all, it even asks customers to exercise with it, something that could be in great demand here in the US where obesity is a severe problem.

Video of the Day:

I also saw this at the HRI conference (yes, it's a chimpanzee, not a robot), and thought you'd all get a kick out of it!

Robot of the Day: Ishiguro and his "twin brother" Geminoid

Ever wished you could have a secret twin brother so he could go to classes for you while you sleep in or go out for a field trip? Well, maybe that dream could come true some day thanks to robotics and android technologies!

When Dr. Ishiguro decided to build an android robot for his research, he thought to himself, "why not build one that just looks like me?" And not long after, his new "twin brother", Genimoid, was born into this crazy human world!

Dr. Hiroshi Ishiguro of the Osaka University is the general co-chair of this years HRI conference. He was also one of the panelist in the panel discussion in the HRI Young Pioneers Workshop I was attending, so I finally met him in person, exccept for a fraction of a second, I wondered if it was really him, or his "twin brother" that was sitting at the front row of the room. :)

Dr. Ishiguro's ultimate goal in researching android and human-robot interaction is to really learn and understand about human race itself. His grad students had built behaviors resembling his behaviors into the robot, but Dr. Ishiguro didn't think he had actually behaved like that. I guess sometimes we don't really know ourselves, and looking at oneself as from an external viewing angle might be a very strange and suprising experience.

Geminoid had limited capabilities. He could move his head, his hands, and twich his legs. He blinks and moves his lips when he talks. He could also show some limited facial expressions. There are 50+ motors inside him, though he was not built to walk around, so should we say, he was born paralyzed? But he could hear, see, and speak, and one of his applications is for tele-presense, so Dr. Ishiguro could speak at a remote location, and the robot will lip sync with him through controls over the Internet.

Dr. Ishiguro's advice on career were very simple: 1) Do really good work, and 2) Work on new things. "If you do that," he said, "then good things will just happen to you!"

Picture of the Day:

If you have not seen this movie, I would recommend it. See what consequences you might have to face when you can just duplicate yourself.

Random Thourghts: Adventure in Japan -- Part 1

Hello everyone! Today is March 1st, 2010 (again, I am still living in this parallel universe), and this is Lanny blogging live from Osaka, Japan! :)

For those of you who already know, I'll be spending the next five days here with my adviser, Dr. Mike Goodrich, attending the Human-Robot Interaction Conference. This is the fist time I visit Japan. Thought I'd share with you some of the fun adventures and "culture shocks" during my trip, so you'll be prepared when you decide to visit Japan someday in the future.

=======================================================

Left home at exactly 4:00am on Sunday morning (February 28, 2010) and checked in at the City Plaza Osaka hotel downtown Osaka at approximately 8:00pm Monday evening (March 1, 2010). Does it really take this long? The truth is: yes, it does take a long time, but not this long. Osaka time is 14 hours ahead of Utah time (MST), so the trip "only" took 24 hours. What a long day!

The flight out of Salt Lake City to San Francisco was at 6:00am local time. Probably because our itinerary included international flights, we could not check in using the easy terminal, and had to stand in a long line to check in at the desk even though we only had carry on luggage. This only gave us 30 minutes to go through security check and rush to our gate, during which, I forgot to collect the little plastic bag containing my hand lotion and hair spray (probably because it didn't work well with the conveyor belt system and did not come out in time. Well, guess I'll just have dry hands and bad hair during the trip then! The good news was, we made the flight!!

The lay over at San Francisco was 4.5 hours. One waiting passenger at the International Terminal got so bored that he started exercising Tai-Chi, which successfully helped us kill about 20 minutes.

 

Tai-Chi in SFO International Terminal

The plane we flew in is a Boeing 777, big enough to have 2 seats on each side and 5 seats in the middle (where we sat at). The flight duration was 12 hours, and the distance between SF and Osaka is about 5800 miles.

 

Boeing 777 at SFO International Terminal

One thing nice about going to Japan from the US is that you don't need a visa. Going through the customs was quick and easy, but soon I had my first "culture shock" at the Osaka Airport restroom. While I was washing hands, a woman janitor just decided to walk in the men's restroom and began cleaning while others were still, you know, doing their business at the urinals. According to Mike, who lived in Japan before, this is a very common thing. Totally weird!

To get to the hotel downtown, we had to take a train first, and then transfer to a subway. We successfully bought our train tickets at at the station by showing the name of our destination in writing to the ticket agent. He gave us a warm reception and kept talking to us in Japanese as if we actually understood what he was saying. The ticket was a bit pricey: 1390 Yen, which is approximately $14 USD. Th exchange rate is 90 some Yen to 1 USD, so I simply calculate as if 1 USD is 100 Yen. The picture below shows a normal train at the station. We actually took a different one with a bullet-shape head.

 

Normal train at the underground train station.

 

Inside the Rapit Bullet Train

 

Looking out from the Rapit Bullet Train

The Rapit Bullet Train was quite empty, however, we did have to seat at our designated seats. Quite to my pleasant surprise, it had English anouncements for stations. Between stations, a train attendent lady would walk the entire six cabins to check tickets. The attendent lay was extremely polite -- she would bow every single time when she entered or left a cabin. Since she walked back and forth, I saw her bowing probably at least 10 times.

At a transfer station, we had to transfer from the train system to the city subway system. It took us a long time because we weren't sure what tickets to buy and which subway to get on -- there was no human agent to help us this time. Eventually we just boldly jumped on a subway and luckily, it was the right now. The subway fare is much cheaper: 230 Yen, which is about $2.5 USD. Another interesting thing I noticed was that the train and the subways would always play nice short melodies to indicate the arrival or leaving a station. Unlike the train, the subway didn't have English announcement, so we had to count number of stops.

When we exited the subway station in downtown, there was a slight shower. Immediately I saw a Starbucks Coffee shop, a 7-Eleven, and a McDonald (shown below, sorry, a bit blurry) around us. Man, it feels just like home! However, we didn't have any instructions to follow from the station to the hotel, and we didn't even know which direction we were going (really started to miss the nice grid street system in Utah). We had hoped to be able to just spot the hotel (since it is a big unique-looking building), but there are many big buildings downtown, and we failed. The shower also began to get worse.

 

McDonald at downtown Osaka

Desperate, we stopped a girl on the street and showed her a picture of the hotel without even attempt to talk to her. The girl then replied and gave us instructions with perfect English -- What a miracle! Turned out the hotel was only a few minutes walk from the subway station exit, we just didn't know which direction to go.

People in Japan drive on the left side of the street. I don't really know why. They weren't a British colony as far as I know. They also walk on the left side of the street. I kept forgetting about it and kept bump into people. How rude of me!

 

City Plaza Osaka hotel right at downtown Osaka

We were sure glad to finally found our hotel and checked in. It is a very nice hotel, and the twin-bed room was much more spacious than I had expected (given the fact that this is in Japan). Soon I found more differences between the American culture and the Japanese culture.

In Japanese bathrooms, shower and bath are two different things and therefore use different parts of the room. Toilet is actually in a different room on the other side, and man, what a FANCY toilet!! I won't go into more details about it, but you can see the picture below and judge yourself.

Japnese style bath room with seperate shower area

 

Fancy Toilet System

Well, that's enough for today. Look out for more updates directly from Osaka Japan in my blog soon!




You don't need to know Japanese to survive Osaka, and I am the living proof!

Paper Review: Finding Question-Answer Pairs from Online Forums

This paper was written by Cong (Aalborg University) et al. and presented at the 31st annual international ACM SIGIR conference on Research and development in information retrieval, 2008.

Question-Answer System is currently a very hot topic in the IR community and attracted many researchers. This 2004 paper (published in ACM SIGIR’08) is one among many in this area. The problem the paper tries to solve is how to mine knowledge in the form of question-answer pairs specifically from a forum setting. The knowledge can then be used for QA services, to improve forum management, or to augment the knowledge base of chatbot. This is a challenging paper to read because it touches many different concepts and ideas from many research disciplines besides IR such as machine learning (n-fold cross-validation), Information Theory (Entropy), NLP (KL-divergence), Bayesian statistics (Markov Chain Convergence), and Graph Theory (graph propagation).

The main contributions of this reference paper include: 1) a classification-based method for question detection by using sequential pattern features automatically extracted from both questions and non-questions in forums; 2) an unsupervised graph-based propagation approach, which can also be integrated with classification method when training data is available, for ranking candidate answers. The paper also presented a good amount of experimental results including a 2 (datasets) 4 (methods) 3 (measures) design for question detection, a 2 (w. w/o answers) 9 (methods) 3 (measures) design for answer detection, and a 2 (w. w/o answers) 2 (KL convergence or all three) 2 (propagate w. w/o initial score) 3 (measures) design for evaluating the graph-based method, and showed the performance superiority of the proposed algorithm compared to existing methods.

The paper proposed several novel ideas in solving the proposed problem. First, the paper defined support and confidence and also introduced minimum thresholds for both, which are additional constraints previous works did not have. “Minimum support threshold ensures that the discovered patters are general and minimum confidence threshold ensures that all discovered LSPs are discriminating and are cable of predicting question or non-question sentences.” (Quoted from the paper.)

Second, the paper introduced the idea of combining the distance between a candidate answer and the question, and the authority of an author, with KL convergence using a linear interpolation. Because of the specific forum setting, these additional factors improved the algorithm performance. However, note that these additional factors also poses limit to the applicability of the algorithm to other Question-Answer mining applications.

Third, the paper proposed a graph based propagation method that uses a graph to represent inter-relationships among nodes (answers) using generator and offspring ideas to generate edges (weights). With this graph, the paper suggests propagating authority through the graph. The authors argued (briefly) that because this can be treated as a Markov Chain, therefore, the propagation will converge. This idea of using a graph to propagate authority information is great because it takes into consideration of how inter-relationship between pair of nodes can be used to help ranking (following the PageRank idea). The idea of integrating classification (two ways) with graph propagation is another great idea. However, I find this Markovian argument weak. No rationality is given about why this can be treated as a Markovian process, and the transitional probability mentioned is not convincing.

The experiment design in this paper is extremely good. First, when using two annotators to annotate the dataset, the paper created two datasets, the Q-Tunion and Q-TInter and evaluated different algorithms using both datasets. This effectively shows that the algorithms performances showed same trends even with disagreeing annotators. The paper also showed detailed performance comparisons using multiple measures across different datasets and different algorithms/methods. This way, the superiority of the proposed algorithm is clear and convincing.

Additionally, the paper used many good examples in the first half of the paper explain complex concepts or to provide justifications. This is good writing! I wish the paper had done the same thing for the latter part of the algorithm description.

The paper also has some significant drawbacks. First, the paper certainly covered a great deal of information and ideas, especially because of the experiment design, a large amount of performance values are contrasted and analyzed. Even the authors used the phrase “due to space limitations” three times in the paper. It is truly a difficult task to cram everything into 8 pages, which is a constraint for a conference paper. And by doing so, lots of useful information are omitted (e.g. the section about how the Markov process can be justified) and some part of the paper just seemed difficult to understand (section 4.2.2). There are also places where proper references should be given, but are omitted probably due to space limitations (e.g. references for Ripper classification algorithm and power method algorithm). It is probably a better idea to either publish this as a journal paper where more space is available, or write a technical report on this subject and reference to it from this paper.

Second, it also seems that the authors were in a rush to meet the paper deadline. This is shown by the carelessness in many of the math notations used in the paper. For example, the Greek letter λ is used in equations (3), (5), (6), and (10) where they meant different things. The letter ‘a’ used to represent an answer sometimes is bolded and sometimes is italicized when all of them meant the same thing. Recursive updates are also represented using “=” instead of “”, such as in equation (10), and temporal indexes are not used. There are quite a few important spelling errors such as the sentence right after equation (3) where ‘w’ was written as “x”. My personal opinion is that if you are going to put your name on the paper, then better show some professionalism.

Third, the paper proposed a quite complex model with many parameters. Especially, the algorithm used many parameters that were set by empirical results. The author did mention that they did not evaluate different parameter values in one place and discussed the sensitivity of the empirical parameter in another; however, these empirical parameters make one wonder whether the algorithm will generalize well with other datasets or whether these parameters might be correlated in someway. A better approach would probably be either justify qualitatively or quantitively the sensitivity of these empirical parameters by discussing more intuitions behind them or showing experiment results using different values with several datasets of different domains and scale. The paper also proposed a few “magical” equations, such as author(i), equation (10), without rationalize how the formulas came about. (Again, publishing as a journal paper would have lessened such problems.)

There are other minor problems with the paper as well. For example, the paper mentioned several times that the improvements are statistically significant (p-value < 0.001), but without much more detail on how the statistical significances are calculated, I can only assume that they came from the 10-fold cross validation. In my opinion, statistical significance would not be a very good indicator of improvements in such set up. The paper also gave me the impression that they are ranking candidate answers by P(q|a). I would think ranking by P(a|q) would have been more appropriate.

Video of the Day:

Now here are some serious question asking and answering!

Full Moon Crescent Saber: Chapter 1 (1)

Chapter 1: The Outstanding Youngster

It was dawn, foggy, very thick fog.

Ding Peng pushed open the window of his small room. Milky, thick fog drifted in like willow catkins and stroked his face gently.

He had a very delicate face, and a healthy body. When he spoke, he looked vigorous, full of vitality. Yet when he smiled, his face often showed a childish and naïve look, as though he was just a big boy, a kid you had always watched as he grew.

But Ding Peng was no longer a kid.

In the last three months, he had already defeated in a row three famed swordsmen in the Martial World.

Sunshine and water make plants and trees grow bigger and stronger. Victory and success also make a boy mature and grow up.

Now he was not only a true man, but also calm, composed, and full of confidence.

He was born in March, and turned twenty this year. It was right on his birthday when he defeated the renowned swordsman Shi Ding of the Baoding City, using a move called “Shooting Star Beyond Skies.” Shi Ding was a sword master of the Northern Style Green Duckweed Sword Art. He used this victory as a birthday present for himself.

In April, he defeated “Wind-Chasing Sword” Ge Qi with the same move “Shooting Star Beyond Skies.” Ge Qi was the head apprentice of the Huashan Sword School. His sword art style was especially speedy and peculiar, and contained many ruthless moves.

Ge Qi was a very proud swordsman, but after that fight, he admitted his defeat sincerely. He actually acknowledged publicly, “Even if I train for another ten years, I would still have no way of fending off that sword move of his.”

In May, the Head Master of the Iron Sword Clan, “Songyang Swordsman” Guo Zhengping, also lost to his sword move “Shooting Star Beyond Skies.”

Guo Zhengping’s comment for this sword move and for him was, “The sword move rises above the mundane world, leaving absolutely no trace behind. Within one year, this young man will shine in the Martial World and have the world under his feet.”

The Iron Sword Clan was not a prominent school, but it had a long history and a reputation of honesty and decency. Naturally words from the Head Master of such a Martial Art school carried extra weight.

Every time when Ding Peng remembered that comment, he couldn’t help but feeling a great surge of excitement and thrill.

“Shine in the Martial World, and have the world under his feet!”

He had trained very hard in the past thirteen years, fourteen hours every single day, so hard that both his palms and soles bled many times from excessive rubbing.

Especially during those coldest, bitter nights of the winter, to maintain an upbeat spirit, he always held a snowball in his hand. If he saw any sign of sluggishness in himself, he would shove the snowball into his pants, a kind of experience not easily imaginable by others.

The reason why he tortured himself like that was because he was determined to excel and succeed, to earn respect for his father who accomplished nothing in his entire life.

His father was a nameless escort, and accidently got hold of an incomplete page of a sword art manuscript.

The entire sword art only contained one page. And on that one page, there was only one move, “Shooting Star Beyond Skies.”

A shooting star flying by from beyond skies and suddenly disappears. The instant of shine and swiftness are simply unstoppable. But his father was already too old with declined intellect and sluggish response. He could no longer master such speedy sword art. So he passed the page of sword art manuscript to his son.

The last words he left his son at his death bed were, “You must master this sword move. You must earn respect for your father so everyone knows that I have a son who has the world under his feet.”

Every time when Ding Peng thought of his father’s words, his blood would boil and he couldn’t hold his tears back.

But now he decided to never shed another drop of tear. Tears are for the weak. A true man only shed blood!

He took a deep breath of the early morning’s fresh air and drew his sword from under his pillow. Today he would once again fight for another victory using this same sword move.

If he wins today, it would be a real success.

Though Shi Ding, Ge Qi, and Guo Zhengping were also famed swordsmen in the Martial World, the three previous victories would be no match for today’s battle.

Because his rival today is Liu Ruosong.

A member of the “Three Friends of Winter^[1]”, the world-renowned “Pine Swordsman”, Liu Ruosong; the owner of the “Ten-Thousand Pines Villa”, Liu Ruosong; the only layman apprentice of the prominent Priest Tianyi of the Xuanzhen Taoist Temple on Mount Wudang, Liu Ruosong.

Many years ago had he heard of this name. At that stage of his life, this name had been as grave as Mount Taishan^[2], majestic, lofty, and untouchable. But that was no longer the case. Now he was confident that he could defeat this man. He followed the most appropriate manner when he sent in his invitation, requesting an opportunity to learn swordsmanship from an eminent senior sword master, to make sure Liu Ruosong could not refuse the fight, because he must defeat this man in order to advance and join the class of true Kung Fu masters in the Martial World. Both the time and place of the challenge were set by Liu Ruosong – June 15^th, noon, at the Ten-Thousand Pines Villa.

Today is June 15^th.

The fight today will shape his fortune for the rest of his life.

The clothes he had washed, straightened, and put up on bamboo poles by the window last night were almost dry now.

Although they were not completely dry, they would soon be once he put them on.

This was the only set of clothes he owned, hand-sewed by his old and sick mother right before his departure. It had been washed pale by now and had many frays. But as long as it was washed clean, he found no shame wearing it.

Poverty is not shameful; Laziness and dirtiness are.

He put on the clothes, and then retrieved from underneath the pillow a money bag also made of blue cloth.

There was only a small knob of silver inside.

This was his entire asset. After paying for the small inn room, there would probably be only a few dozens of copper pennies left.

Normally he slept at places that required no rent. Under the sacrifice altar in the shrine or on the small meadow inside the woods could all be his bed.

For the fight today, he gritted his teeth and booked a room at the small inn, because he needed plenty of sleep to make sure he had plenty of mental and physical strength to win the fight.

After taking care of the inn bill, he made the harsh choice of spending the rest of the money on half pound of halogen beef, ten pieces of dry bean curd, a big bag of peanuts, and five big steamed buns.

For him, this was not only extreme luxury, but also unforgivable waste. Usually he could easily get by a day with only three hard bread cakes.

But he decided to forgive himself today. Today he needed strength, and strength only comes with quality food.

Besides, things could be completely different after today.

Fame can bring not only glory and self-esteem, but also many things one would never dream of. Wealth and social status will also follow along.

He knew that very well, hence he always gritted his teeth to endure poverty and hunger.

He never let himself be tarnished by any indecency, for he was determined to rise up through the right way.

Since it was still four hours from noon, he decided to find a good spot to enjoy the wonderful food.

Somewhere by the foothills near the “Ten-Thousand Pines Villa”, he successfully found a spot that had a spring, a good size patch of grass, beautiful flowers and a nice view. The place was surrounded by flowery trees. The cloudless sky radiated with a beautiful shape of blue.

By then the thick fog had all cleared. The sun had just barely risen. Morning dews glittered on top of dark green leaves like beautiful pearls.

Ding Peng sat down on the soft grass and tore off a piece of beef. The beef tasted even better than what he had imagined.

He was extremely delighted.

Just at that moment, a girl ran into his secret little world like a little antelope chased by a hunter.

The girl was completely naked.

---

[1] “Three Friends of Winter” was created by Song Dynasty Poet Su Shi and refers to Pine, Bamboo, and Calyx canthus in Chinese culture because all three of them remain beautiful despite the severe cold of the winter. Here it is the name of a small trio of Kung Fu Masters whose nicknames contain these three things. The last character in Liu Ruosong’s name, “song”, also means pine.

[2] Mount Taishan is a famous mountain in Shandong Province, China. It is the first of the “Five Mountains” and is known for its majesty.

Now support the translator Lanny by following my blog and leaving comments! :)

Do not pretend to be something you are not, and I am not a plumber!

AI and Robots: Hybrid Video Display of Visible and Infrared Might Help Search and Rescue

A recent article in New Scientist discussed a research project performed at Brigham Young University where the effect of combining visible light and infrared on real-time video footage in Wilderness Search and Rescue was evaluated.

The research project was directed by Dr. Bryan Morse (who is also one of my committee members) and implemented by Nathan Rasmussen (a friend of mine, who successfully received his MS from this project and graduated in 2009). It is one of the many projects in the WiSAR research group at BYU that works on how to use mini-UAVs (Unmanned Aerial Vehicles) to support Wilderness Search and Rescue. The picture on the right shows Nathan throw-launching a UAV in a field trial at Elberta, Utah.

This research focuses on the human-robot interaction aspect and try to determine which method of display works better for human operators: displaying visible light video side by side with infrared video, or combine both in a hybrid display.

The UAV used in the experiments can already carry both a visual spectrum camera and an infrared camera (BTW: very expensive). Visible light video footage can be useful in spotting objects of unnatural/irregular shapes and colors (top view). Infrared light video footage, on the other hand, can be helpful in detecting objects with distinct heat signatures that are different from surrounding environments (especially early mornings, evenings, and nights, or in cold weathers where heat signatures are more distinct).

In order to align footage from both sensors, a calibration grid was created with black wires on a white background. To allow the infrared camera to "see" the grid, an electricity current was sent down the wires to heat them up. An algorithm is then used to align the vertices of the two grids to compensate for the slightly different viewing angle.
Once the hybrid view was possible, a user study was performed where students were used as test subjects to watch UAV videos in both methods and tried to identify suspicious objects while listening to audio signals (counting beeping sounds as a secondary task in order to measure mental workload). I happen to be one of the test subjects, and my hard work earned me some delicious chocolates.

Experiment results show that people who viewed the hybrid display performed much better in the secondary task of counting beeps. This suggests that the hybrid video is easier to interpret (requiring less mental work) and would allow the searcher to focus more on identifying objects from the fast moving video stream.

The research was presented at the Applications of Computer Vision conference in Snowbird, Utah, in December 2009. If you are interested in more details about this research, you can read Nathan's thesis　(warning: 22.4MB).

Picture of the Day:

Beautiful dusk sunshine mountain view from my house!

Robot of the Day: CubeStormer, the Rubik's Cube Solver

Ever played Rubik's Cube before? If you have, then you know how hard and how long it takes to solve a game of Rubik's Cube. The robot we talk about today, however, can solve it within seconds, and most impressively, the robot was built completely using Lego pieces from the Lego Mindstorms Kit, which means you could build a robot just like this yourself for only a couple hundred bucks!

The robot's name is CubeStormer, built by British engineer Mike Dobson using Lego Mindstorms parts hooked up to a laptop computer. The computer acts as the brain and performs tasks such as recognizing colors, solving the puzzle using algorithms, and sending motor commands.

As shown in the video below, the robot first quickly inspects all six sides of the cube using multiple cameras by first rotating it a few times to recognize the current state of the cube. The computer vision task is actually really simple because the cube is placed at a fixed position, so the recognition software only needs to sample a few points for each color piece and then simply detect the color of the pixels (one out of six possible choices). The state of the cube is then passed on to a solver software (such as this free online one) and sequences of moves are generated, which are translated into motor commands for the robot to perform.

What is impressive about this robot, though, is the engineering side of things, such as how parts are connected and how motors are used all with toy Lego pieces. A beautiful designed enabled the robot actuators to solve the game in such short period of time. If you look closely at the video, you'll also notice that two rows of the cube can be rotated at the same time to speed it up!

CubeStormer by Mike Dobson

The time it took the robot to solve a random game was about 12 seconds. This is very much comparable to the fastest human Rubik's Cube solvers such as the one shown below.

Rubik's cube official world record 7.08 Erik Akkersdijk

There are of course other Rubik's Cube solving robots in the wild, such as the one built by UC Berkeley shown in the video below, which solved a puzzle in 6 seconds. But apparently this robot would cost a lot more.

Rubik's cube solver by UC Berkeley

However, the Cubinator, aka RuBot II, by Pete Redmond from Dublin, Ireland gets extra point in my book of Human-Robot Interaction. Although much slower compared to the other two robots, it has a head and two arms. And after picking up the cube all by itself, it even played music and talked to the audience while solving the puzzle.

Cubinator by Pete Redmond

What if the Cubinator not only solves Rubik's Cube, but is also capable of playing board games or hide-and-seek with your kids, tell them jokes, read books for them, and help them with their homework? Would you want one for your kids? If so, for how much? If not, why?

Picture of the Day:

Leftover Valentine’s chocolate? Use it to measure the speed of light with your microwave. Click the picture to find out how!

Random Thoughts: Are you being watched?

It started as a great idea at the Lower Merion School District, outside Philadelphia, when school officials decided to loan laptop computers to students to encourage them to embrace newer technologies and to study better. However, the situation came to a dramatic turn when a suit was filed against the school district for spying students at students' homes through the web cam built into the laptop and a software that allowed the school officials to activate the camera remotely in order to view and take pictures of the students.

The interesting part was that a student named Blake Robbins was accused of selling drugs and taking pills by school officials (Blake claimed that he was eating candies), and the school official actually provided proof -- images of Blake eating things at home taken secretly through the web cam -- to back up their claim! The image on the left shows Blake's family and their lawyer appearing on "Early Show Saturday Edition" discussing the entire fiasco (photo credit CBS).

I am simply AMAZED at the intellectual capabilities of the school officials involved here!! The issue here is not whether the kid took pills or not. The issue is about a crude invasion of personal privacy at people's own homes without their knowledge and consent. A federal judge quickly ordered the school district to stop activating the cameras, and the school complied. The FBI has also opened a criminal investigation of the web cam use to see if the school district broke any federal wiretap or computer-intrusion laws.

Disturbing as the story is, what I want to emphasize here, though, is slightly different. Many people use web cams to do video conferences with friends and family. Some still use the old external web cams connected through USB ports (I am one of them). However, most people use the laptop built-in web cams these days because of the convenience and also because most laptops come with built-in web cams. So do you really know if you are being watched?

People these days take their laptops with them everywhere they go, including very private places such as their bedrooms and bathrooms. Many companies would also give their employees laptops so they can work from home or while they go on trips. Many large organizations DO put remote access software on company laptops for the ease of IT support, and I personally have used such software when I worked as an IT support staff in the past. The truth is, IT support staff can remotely watch your monitor screen when you have no idea they are doing so. And if the computer has a web cam, activating the web cam through such management tools is a piece of cake.

Also, many home computers are hacked and made into "zombie" computers for spamming or Denial Of Service attacks in large botnets controlled by hackers. These hackers can also easily control the web cams connected to these infected computers and the users would have no clue about such activities! If you think you are safe behind security firewalls you purchased from McAfee of Symantec, you'd better think twice.

So what lesson should we learn from this? That is, we should never naively believe that we have total control of web cams connected to our computers. The safest thing to do is to cover it up with tape of a piece of paper when we are not actively using it, because you never know who might be watching through the web cam. Especially for people have built-in web cams, it is so easy to forget about that special "eye" in the room, and it might be watching you actively at this very moment!

The commercial in the YouTube video below might seem funny, but it wouldn't be so funny if you weren't in a video conference yet someone is secretly watching you behind the web cam device. I think all built-in web cams should have a cover, so people only open it when they actively use it and can always close the cover when they are not.

This also poses an interesting question about future robots in people's homes. These robots will probably also have eyes, and eyelids will probably have to be mandatory so they don't peep on you when you don't want them to.

Video of the Day:

Sony laptop with built-in web cam ad!

Paper Review: Evaluation of evaluation in information retrieval

This paper was written by Saracevic from Rutgers University and published at the 18th annual international ACM SIGIR conference on Research and development in information retrieval, 1995.

Evaluation metrics are important components of scientific researches. Through evaluation metrics, performances of systems, algorithms, solution to problems can be measured and compared against baselines or among each other. However, what metrics should we use, at what level, and how good are these metrics? Questions like these must be carefully considered. This paper discussed such concerns about past and existing evaluation metrics used in Information Retrieval (IR) and raised many more questions. Please note that this paper was published in 1995 and evaluation metrics/methods in IR have progressed dramatically by now.

This paper is somewhat a survey paper that discussed evaluation metrics used in IR throughout the history and provided many literature references. The main contribution of the paper is that it suggests looking at the evaluation of IR from a much higher perspective, going back to the true purpose of IR, which is to resolve the problem of information explosion. When considering the evaluation of IR systems from this high point, the paper pointed out that there are a lot more to be evaluated besides common/popular evaluation metrics at simply the process level (e.g. Precision and Recall). It urged the IR community to break out of the isolation of single level narrow evaluations.

The author systematically defined six levels of objectives (engineering, input, processing, output, use and user, and social) that need to be addressed in IR systems together with five evaluation requirements (a system with a process, criteria, measures, measuring instruments, and methodology). Then he further discussed in details current practice, potential problems, and needs of evaluation metrics with respect to each of the requirement and how they can be categorized into the six objective levels. This is an excellent way of organizing contents and arguments, which allows the readers to easily see the big picture in a structured framework.

The paper made a strong statement that “both system- and user-centered evaluations are needed” and more efforts are required to allow cooperative efforts of the two orientations, in contrast to the widely proposed shifting from one to the other. This again highlights the author’s suggestion of treating the evaluation of IR as an overall approach.

The author identified many compelling problems and important issues with regard to the evaluation of IR and argued them well. To name a few: Laboratory collections are too removed from reality and TREC has highly unusual composition as to types and subjects of documents and should not be the sole vehicle for IR evaluation. Applying various criteria in some unified manner still poses a major challenge in IR. Assumption of one and only one relevant set as an answer to a request is not warranted. When using relevance as the criterion with precision and recall as the corresponding measures, someone has to judge or establish relevance; the assumption here is that the judgment is reasonable while we know relevance is a very subjective topic.

The paper repeatedly emphasized evaluation of interaction between users and IR systems as an integral part of the overall evaluation. In recent years, there’s also a strong trend showing more and more researchers in various areas interested in understanding how the human factors and the interaction between human and machines (robots) play an important role in the performance of systems. A good example is the emergence of Human Robot Interaction (HRI). Therefore, this topic deserves a separate discussion here. The ultimate goal of an IR system is to serve human. If information retrieved is not presented to the user correctly, then the IR system fails miserably. Also because of the subjectivity (with respect to an individual user) and ambiguity (such as query term meanings) of IR, multiple rounds of interaction between the user and the IR system can dramatically improve the performance of information retrieval. One example would be retrieving documents related to the query term “Python”. An interactive IR system can further allow the user to specify if he/she wants to retrieval information about the animal or the programming language. As stated in the paper, interactions in IR were extensive studied and modeled, however, interactivity plays no role in large evaluation projects (which I believe is still true even up to today). Granted that it is difficult to come up with sound evaluation metrics for interactivity, more discussion and research in this area is definitely very necessary.

This paper certainly has its shortcomings. First of all, the author could certainly have been more concise in the writing. Additionally I found the comparisons using expert systems and OPAC to be distracting from the main ideas and do not contribute much to the arguments. Eliminating them would have made the paper more focused.

Granted that precision and recall are used as the main evaluation metrics to measure relevance in the system and process level, many other evaluation metrics also existed but were not covered in this paper. Examples include (but not limited to) F-measure, Entropy, Variation of Information, Adjusted Rand Index, V-Measure, Q-2, Log likelihood of the data, etc. Besides quantitive evaluation metrics, qualitative analysis is also a common tool people use to evaluate performances of IR systems, and the paper didn’t touch this subject at all.

The paper argued that it is a problem that “every algorithm and every approach anywhere, IR included, is based on certain assumptions” and these assumptions could have potential negative effects. I found this argument weak and not well constructed. It is true that when researches design algorithms or model problems they make assumptions. Good researchers clearly identify these assumptions in their publications and analyze the potential effects these assumptions have on their algorithms or their models. Sometimes assumptions are made without sound reasons but are justified by good performances from real applications/data. It is almost unavoidable to make various assumptions when we do research. We should not be afraid of making assumptions, but be careful about our assumptions and justify for them.

Lastly, there is one more important drawback of this paper. It did a good job identifying many problems and issues regarding evaluations in IR. However, it did a poor job providing constructive ideas and suggestions to many of these problems. I am not suggesting the author should find solutions to many of these problems, but some initial ideas or thoughts (let it be throw-away or naïve ideas) would have improved the paper considerably.

In summary, the paper succeeded in bringing attentions to treating evaluation in IR from a much higher perspective and also provided good description, references, and discussion for the “current” state (up to 1995) of evaluation metrics in IR. I enjoyed reading this paper.

Video of the Day:

If you have a Toyota, take it in for a check, because it might be a matter of life and death for you and your family!