Search within Lanny's blog:


Leave me comments so I know people are actually reading my blogs! Thanks!

Thursday, February 05, 2009

My Research: BYU UAV Demo for Utah County Search and Rescue Team

On November 21, 2009, our research group, WiSAR (Wilderness Search and Rescue) demonstrated our UAV technologies to the Utah County Search and Rescue team representatives at Elberta, Utah. Three search and rescue personnel participated in the demo and one of them flew the UAV in a simulated search and rescue exercise.

In two previous blog postings I described BYU research on using UAV to support Wilderness Search and Rescue and UAV capabilities:

My Research: BYU UAV Demo Dry Run
Robot of the Day: UAVs at BYU

The demo was scheduled at 8:30-11:00 am at Elberta, Utah (in the middle of nowhere), which was about an hour's drive from BYU campus. That meant we had to get there by 8 to set up and test equipments. The previous day's weather forecast predicted snow shower, so I was assigned the task of picking up some hot chocolate from the BYU cafeteria so people don't freeze to death!

Despite the facts that I had to deal with my 10-month old son's high fever at 1:30am and not really fall asleep until 3:30am and unconsciously turned off my alarm clock, I actually made it to the cafeteria only 5 minutes late, then I waited another 25 minutes because they haven't made the hot chocolate yet. By the time I arrived at the demo site at 8:30am, turned out the trailer just got there also, so I didn't miss anything! Also, turned out the weather forecast was way off, there was no snow at all, and it was going to be a great day!


Left to right, top to bottom: 1. BYU Cafeteria 2. Beautiful Utah mountains at Dawn
3. The lonely freeway 4. Driving down the highway 5. Good morning, Cows!
6. Gravel road with the destination in view (the ridge in the far distance).


The pictures above were taken by me using an android phone running NASA's GeoCam mobile client. Therefore, all photos were geo-tagged with GPS locations and camera orientation. You can actually view them from Google Earth, where you'll see the exact route I took on the map. Just download the zip file, unzip, and then double click the kml file.

Viewing pictures from Google Earth

The goal of the demo is to show real search and rescue workers how easy and useful our UAV technologies are in support of search and rescue operations. A simulated search and rescue mission was set up, a member of the search and rescue team had to fly the UAV using our interface and locate the simulated missing person (a dummy placed in the wilderness). Students and professors from BYU also acted as aerial video analysts and ground searchers to assist the simulated search. The picture blow shows a ground searcher scouting around in the distance searching for the missing person. The ground searchers always wear bright-colored vests so they can be easily spotted by others (e.g. from the aerial videos) and don't get shot at by hunters. (I know, research is a dangerous profession!)


Ground searcher in a distance (click photo to enlarge)


After setting up everything, Ron Zeeman, a member of the Utah County Search and Rescue team, test flew the UAV, and completed a test drill (launch, manual control, fixed pattern flying, and landing).

Left to right: 1. People busy setting things up 2. UAV at dawn 3. Last minute exercise

After other Search and Rescue team members arrived, we explained how our UAV works, and then started the simulated search and rescue mission. This time I was quite lucky to catch the flying UAV with my camera.

Left to right: 1. Two more professional searchers arrived 2. Two retired UAVs in display 3. The show is on now!

Left to right: 1 and 2. UAV in the air 3. UAV loitering above area of interest (click to enlarge)

Left to right: 1. The kind of junk people would dump to the middle of nowhere 2. Debris of camp fire 3. Real-time video mosaicing (frame stitching)

Eventually, the missing person was located in the aerial video and confirmed by ground searchers. "Unfortunately", by the time we found "him", he was not breathing.


The "missing person" was found, breathless.

Technologies demonstrated include auto launch, auto land, various UAV control mode (carrot and stick, fixed pattern flying, etc.), integrated gimballed camera view in augmented virtuality, click and point gimballed camera control (separate from UAV path), real-time video mosaicing, real-time video annotation and video zooming/scrubbing, point of interest communication between video GUI and UAV control GUI.

Technologies not demonstrated but are work in progress include automatic missing person probability distribution generation, automatic path planning (based on distribution), see-ability metric to measure coverage quality, and automatic anomaly detection.

The demo was a great success! The professional searchers were pleasantly surprised by the ease of operating the UAV and the usefulness of the aerial video support. Their comments included, "That was so cool!" "This could be very helpful!"




Video of the Day:

If the UAV sitting in our lab had a mind of its own,
it would have been singing this all night long...

Wednesday, February 04, 2009

Paper Review: Distributional Clustering of Words for Text Classification

This paper was written by Baker from Carnegie Mellon and McCallum from Justsystem Pittsburgh Research Center, published at 21st annual international ACM SIGIR conference on Research and development in information retrieval, 1998.

This paper applies Distributional Clustering to document classification. Distributional Clustering can reduce even space by joining words that induce similar probability distributions among the target features that co-occur with the words in questions. Word similarity is measured by the distributions of class labels associated with the words in question.

The three benefits of using word clustering are: useful semantic word clusterings, higher classification accuracy, and smaller classification models.

Clustered Word Clouds by Jeff Clark, perfect in memory of Dr. King on this year's Martin Luther King Day!

The paper first went over the probabilistic framework and Naïve Bayes, and then suggests using weighted average of the individual distributions as the new distribution. Kullback-Leibler divergence, an information-theoretic measure that can be used to measure difference between two probability distributions is introduced, and then the paper uses “KL divergence to the mean”. Instead of compressing two distributions optimally with their own code, the paper uses the code that would be optimal for their mean. Assuming a uniform class prior, choosing the most probable class by naïve Bayes is identical to choosing the class that has the minimal cross entropy with the test document. Therefore, when words are clustered according to this similarity metric, increase in naïve Bayes error is minimized.

The algorithm works as the following: The clusters are initialized with the M words that have the highest mutual information with the class variable. The most similar two clusters are joined, then the next word is added as a singleton cluster to bring the total number of clusters back up to M. This repeats until all words have been put into one of the M clusters.

The paper uses three real-world text corpora: newswire stores, UseNet articles and Web pages. Results show that Distributional Clustering can reduce the feature dimensionality by three orders of magnitude, and lose only 2% accuracy.

Distributional Clustering performs better than feature selection because merging preserves information instead of discarding it. Some features that are infrequent, but useful when they do occur, get removed by the feature selector; feature merging keeps them.




I have a dream that one day when I get old, there will be intelligent robots to take care of people like me, so we can enjoy life freely, happily, and independently.






Tuesday, February 03, 2009

Joy of Life: Volume 1 Chapter 4

Volume One: The City by the Sea
-- written by Maoni

Chapter 4: Late Night Visitor

“Are you thinking about something?”
The little girl sitting by Fan Xian’s right hand side asked with pouted lips while the two servant girls were busy setting up the dinner table. The little girl was a bit skinny and had somewhat darkish skin. Sitting right next to Fan Xian, whose face was almost as pretty as a girl, the little girl appeared even more pitiful.
Fan Xian reached out and rubbed the yellowish hair on the little girl’s head.
“I am thinking about what kind of tasty food you get to eat every day in the Capital City,” he grinned.
The little girl was the daughter of the Count of Southernland, Fan Xian’s younger sister. They shared the same biological father but had different mothers. Her name was Ruo-Ruo.
She had always been feeble since birth. The Old Madam loved her granddaughter very much, so she sent for her a year ago and kept her in Danzhou for recuperation. A year had already gone by and there still wasn’t much of an improvement. The hair on her head still looked sparse. Born into the family of a government official, she never lacked warm clothing or good food. Her symptoms must have resulted from premature labor, not malnutrition.
Fan Xian found himself quite fond of the little girl. Even though he dealt with her using the attitude of an uncle, treating her as an adorable little kid, playing with her, telling her stories, in everyone else’s eyes, such an attitude became the clear proof of a loving brother-sister relationship.
Nevertheless, due to Fan Xian’s awkward status – a baseborn son, which is very different from a legitimate daughter – the servant girls intentionally avoided mentioning anything regarding the other Count’s Manor in the Capital City.
Since the brother asked, the little girl sincerely started counting with her fingers the tasty things she had enjoyed back in the Capital City. The memory of a three-year-old is surely quite limited, so all she did was to repeat candied haws[1] and dough figurines[2].
It was quite late when dinner was over. The setting sun was already half hidden by the other side of the continent, and the dense twilight began to envelop the entire manor.
“Alas! Ruo-Ruo, you are indeed a Weak-Weak[3]!”
“Brother is teasing again!”
“Alright, alright! What story would you like to hear today?”
“Snow White.”
A big grin suddenly appeared on Fan Xian’s face out of nowhere. Luckily there was no one else around; otherwise one would be shocked to spot such a queer grin only capable by grown-ups appearing on the face of a four year old boy.
“How about a ghost story?”
“No! I don’t want it.” Fan Ruo-Ruo was quite frightened, shaking her head vigorously. Tears quickly formed around her eyes and two streams of tears soon rolled down her darkish face. Evidently, she had been tormented by ghost stories many times in the past year.
Teasing this little girl was only one of Fan Xian’s many vulgar hobbies. What he was best at was bantering with those servant girls. He frequently told ghost stories to those youthful blossoming girls, who always ended up jostling tightly into each other’s embraces screaming and shivering on top of the bed.
Although it was out of the question for Fan Xian to flirt with the young girls vocally for the sake of concealing his true self, he always enjoyed the sweet and tender hugs at these times.
He would always reassure himself with the argument that as a young kid, he was still in a phase where touching was very desirable. So what he did was completely normal and warranted, not something shameful.
Every time the servant girls became curious as to how he could have known so many terrifying stories, Fan Xian would always make his teacher liable. The direct result was that all the servant girls now eyed the teacher with a disgruntled look. “The Count is paying a handsome salary for you to give lessons to the Young Master, yet you teach him ghost stories. It is already evil to scare a little kid, but it is even more evil to scare us, the blossoming flowers.”
After the usual evening ghost story telling was over, the two servant girls, still carrying a mixture of frightened yet satisfied looks, attended to the little guy’s evening hygiene routines and then shut the door to let him sleep.
It seemed to be just another ordinary night.
Fan Xian pushed the hard and uncomfortable porcelain headrest[4] to the side, and then took out a winter robe from the chest of drawers. Folding it into a nice rectangular shape, he made himself a “pillow”.
He rested his head against the “pillow”, but his two eyes remained open. They shined dimly in the dark night as he remained awake for a long time.
He had accepted the fact that he was reborn into this world, but he was still not used to the customs. It should have been around nine o’clock in the evening, and it was not a comfortable feeling to sleep so early. Besides, he had already slept too much on the sickbed in his previous life.
He stroked the surface of the bed board with his hand and felt better with the conclusion that no one could easily spot the secret casing he had made. As he became more relaxed, naturally, the inner energy inside him began to circulate gradually and he slowly approached the state of meditative trance.
“What kind of life should I live in this world? And how should I spend the next few decades? Maybe I’ll even have many wives and concubines like an ordinary noble man,” Fan Xian’s mind wandered.
Just on the edge of entering the emptiness of mind, Fan Xian was suddenly awoken by an unannounced visitor.
……
……
“Are you Fan Xian?”
A man appeared by his bed all of a sudden. With a grain of abnormal brown in the pupils, his eyes only showed the coldest apathy, clearly indicating his indifference to life.
The question was actually asked nicely. But if such a question was asked by someone who had sneaked into your bedroom at midnight, wearing a mask on his face, holding a dagger in his hand, with a few small bags pinned to his waist, the question could be very terrifying.
If Fan Xian had been a real four-year-old boy, he would surely have screamed on the top of his lungs at the first sight of this queer uncle.
Even if he did all his thinking with his toes Fan Xian could still comprehend that a night traveler capable of sneaking into the Count’s Manor without triggering any alarms had to be someone with high caliber Kung Fu and very possibly, a cruel mind. If he had made any attempt to scream, most likely the man would not hesitate to break his neck in a split second.
At that thought, Fan Xian couldn’t help but feel quite pleased with his calmness. Working hard to suppress the growing uneasiness, he cleared his throat gently. Then putting on the most lovely baby face he could manage, he threw himself forward!
……
……
“Daddy, you are finally home!”
The four-year-old boy dove into the assassin’s arms, tears streaming, and held onto his waist tightly. But the boy’s arms were too short and could not completely circle around the waist. So instead, he grabbed the man’s robe tightly as though he was afraid the man would just suddenly disappear.
Perhaps the boy used too much strength when grabbing the robe, with a tearing sound, a strip of the robe came off.
The man frowned. Without any obvious movement, he suddenly freed himself from Fan Xian’s hug, and then just stood there, dumbstruck, as if he was still trying to work on why this baseborn son of the Count of Southernland had called him Daddy.
Meanwhile, he was also very puzzled. His robe was the top of the line gear of the Bureau. Even a knife wouldn’t have easily cut through it. How was the young kid able to easily tear it apart?
Fan Xian was even more baffled, so much so that he felt as though his heart began to bleed – during times when he managed to be alone, he had always experimented with the power of the nameless inner energy inside him using rocks in the rockwork hill in the courtyard. When he found out that he could almost manage to crush those not-too-hard rocks into bits and pieces with his tender little fingers, he started building some confidence in his self-defense ability.
That wasn’t an easy task to lower the man’s guard with the tears of a four-year-old. Directing all the inner energy to his fingers, Fan Xian thought he had a pretty good chance to subdue his opponent. But who could have imaged that all he was able to achieve was to tear a few strips off the man’s robe.
Something big was bound to happen now.


[1] http://www.lannyland.com/jol/TangHuLu.jpg
[2] http://www.lannyland.com/jol/MianRenEr.jpg
[3] The Chinese character for “weak” has the same pronunciation as the character in the girl’s name.
[4] Typical in ancient China before pillow was invented.


Now support the author Maoni by clicking this link, and support the translator Lanny by following my blog! :)


Video of the Day: Matrix running on Windows XP

Click on the picture to view video on YouTube because video embedding was disabled.

Monday, February 02, 2009

Paper Review: A Comparative Study on Feature Selection in Text Categorization

This paper is written by Yiming Yang from Carnnegie Mellon University and Jan O. Pedersen from Verity, Inc. presented at ICML 97 (International Conference on Machine Learning). It has been cited 2742 times according to Google Scholar, another seminal paper indeed!

This paper evaluates and compares five feature selection methods: document frequency (DF), information gain (IG), mutual information (MI), a χ2-test (CHI), and term strength (TS).




A major difficulty of text categorization is the high dimensionality of the feature space. Automatic feature selection methods include the removal of non-informative terms according to corpus statistics, and the construction of new features which combine lower level features into higher-level orthogonal dimensions.


Document frequency is the number of documents in which a term occurs. Terms with low document frequency (less than a threshold) were removed from the feature space with the assumption that rare terms are either non-informative for category prediction or not influential in global performance. Information gain measures the number of bits of information obtained for category prediction by knowing the presence or absence of a term in a document. Terms whose information gain was less than threshold were removed from the feature space. Mutual information becomes zero if the term t and category c are independent. A weakness of mutual information is that the score is strongly influenced by the marginal probabilities of terms. The χ2 statistic measures the lack of independence between t and c, and it is known not to be reliable for low-frequency terms. Term strength method estimates term importance based on how commonly a term is likely to appear in “closely-related” documents and is based on document clustering. Average number of related documents per document is used in threshold tuning.


The paper used kNN and LLSF because: both are top-performing, state-of-the-art classifier, both scale to large classification problems, both are a m-ary classifier providing a global ranking of categories given a document, both are context sensitive, and the two classifiers differ statistically. The Reuters-22173 collection and the OHSUMED collection were used for the experiments and recall and precision are used as performance measures.


Experiments include using full vocabulary to removing 98% of the unique terms. Results show that IG and CHI are most effective in aggressive term removal. DF is comparable to IG and CHI with up to 90% term removal. TS is comparable with up to 50-60% term removal. MI has inferior performance due to a bias favoring rare terms and a strong sensitivity to probability estimation errors. Results also show strong correlation among DF, IG and CHI scores.




Video of the Day: Industrorious Clock


Credit: Yugo Nakamura

Sunday, February 01, 2009

Random Thoughts: My Philosophy for Scholarship in Computer Science

I actually wrote this article to meet the requirement of a take home exam, but I thought you'd still find something useful. So here it is:

My Philosophy for Scholarship in Computer Science


When I first started graduate school at BYU three years ago, I had no idea what research in Computer Science (CS) was all about. Three years later, after successfully defending my Master Thesis and publishing (presenting) multiple papers, I found myself much more comfortable at research work. I am not saying that research in Computer Science is easy. In fact, it is quite difficult and requires strong determination and much devotion. I do, however, believe that there are secrets to success in Computer Science scholarship. If we follow these guidelines, research can be fun and rewarding, and we can also make good contributions to the advancement of the field. In this document, I would like to share my “philosophy” for key elements of research in Computer Science.


(a) Reading and evaluating CS literature


Literature review is a critical element of CS research. It allows a researcher to see what others have done to solve the problem the researcher is interested in. One purpose of the exercise is to not repeat prior art; another equally important purpose is to learn from previous work, see other researchers’ insights, and identify possible places for improvement. A good place to start is to find a survey paper for your research problem, which can help you identify key researchers in the field. Your advisor can also provide useful information in this regard. Next, pick a few seminal papers from the key researchers. See what papers they reference and what papers cite them. We are blessed with the Internet, so take advantage of it and use research tools such as Google Scholar, CiteSeer, and DBLP in your search for papers. Give priority to papers published at top journals and conferences. An important skill in literature review is focused reading. There are too many papers out there and you cannot read them all. Quickly skim through the abstract and conclusions to determine if the paper is related to your research problem. If it is, then do focused reading with the goal of identifying the paper’s contributions and shortcomings. Finally, make literature review an ongoing process throughout your research because new research results continuously appear.


(b) Doing CS research


The first step of doing CS research is to define a research problem. The problem has to be important in the field. A problem no one cares about is useless. The problem also has to be well defined and scoped. Setting a clear target makes reaching the target possible. Restricting the problem to a reasonable scale provides focus and allows incremental advancement in the research field. The problem also needs to be interesting to the researcher because passion is the driving force that enables the researcher to endure the many difficulties during research and keeps the research going. The second step in CS research is to select the appropriate research pattern for conducting research investigation. Choosing the right research pattern helps the researcher identify directions to follow, strategies for validation, and fallacies to avoid. The next step is to create a testable hypothesis. The keyword here is “testable”, meaning other people can repeat the experiments and achieve similar results. This step also implicitly requires careful experiment design and meaningful metrics. Overlooked factors in experiments and badly selected metrics can skew experiment results or lead to erroneous conclusions.


(c) Writing-up CS research


A lot of people think that writing is important only because it leads to publication, which shows research achievements and also let others know what the researchers are doing, but writing is more than that. Writing should begin at the same time research begins, because writing shapes research and writing is an important research activity. Writing things down on paper forces one to formulate and clarify. It helps a researcher better understand what to say and also helps the researcher better organize thoughts and materials. When writing for publication, the most important thing is to choose the right set of keywords so your paper ends up in the right group of reviewers’ hands. A pithy title and a well-written abstract (including the four elements described in Secret #1 in class slides) are also important because they might be the only things the busy reviewers read. To make a reviewer’s job easier, it is a good idea to embed answers to review questions (such as contributions, new results, and validation) in the abstract, introduction, and conclusion sections. For the body of the paper, write precisely and concisely. Know the technical capabilities of your readers and then write accordingly, striking the right balance of detail. Use simple words and active verbs. Avoid using the “official style” writing because you will sound like a lawyer and really annoy your readers.


(d) Teaching CS topics


Teaching is not about showing off knowledge. A good teacher doesn’t focus on teaching facts (they can be looked up), but instead, focuses on teaching learning methods and problem solving skills. A great teacher not only teaches, but also inspires students to seek knowledge on their own. For CS topics, teaching should focus on algorithms (including complexity analysis) and how to apply them to solve real-world problems. An ideal CS course should have interesting problems for students to solve at the beginning of the course, and throughout the course, students can apply algorithms, techniques, and problem solving skills to these problems creatively. They are also encouraged to apply skills learned in the course to problems the students are interested in themselves. A successful teacher creates a stimulating environment that encourages students to participate and learn.


(e) Presenting CS research


Presenting your research is like advertising your ideas to peers. It promotes discussion and collaboration among researchers who are interested in the same research problem. The presentation should be self-contained to tell a complete story, however, it should not include all the technical details, because that makes the presentation tedious and chubby. If the audience wants more details about your research, they can always read your paper. Presentation slides should be simple and easy to follow, lively but not too fancy. Try to make your story interesting and impressive, and when necessary, use simple graphs to show trends in your data analysis. Speak clearly and it is okay to use an excited tone. Don’t be afraid to show your passion, but also don’t make your presentation into a political speech. Always back up your claims with facts or experimental results. Adding a bit of humor is always helpful. Just make sure your audience will understand your joke. Lastly, don’t perform live demos unless you are very sure the demos will work smoothly, otherwise, you will look like a fool on stage.


(f) Evaluating the research work of others


Reviewing papers of others is a great opportunity to learn, to teach, and to contribute to the research community. The reviewer can learn not only what mistakes to avoid in his or her own writing, but also good writing styles and techniques the reviewer can follow. The review process also allows the reviewer to provide insightful feedback to the authors in order to help them improve the quality of their research and writing. A review report normally contains the reviewer’s summary of the paper, comments about the solution described, experiments performed, metrics used, and conclusions drawn, and comments about the presentation. It is possible that a reviewer will reject a paper that has great ideas but does a poor job presenting them. Remember to always be respectful and use a positive tone rather than a negative tone. Realize that no papers are perfect. Use a simply rule of thumb when evaluating others’ work: review work of others the same way you would want others to review your work.


At the end of the document, I’d like to emphasize “passion” in all the elements of research. Passion is the best motivation for keeping the research going. Passion also leads to the best reward for research progresses ¾ feelings of self-fulfillment. I hope you find great passion in your research, which makes research more than work and turns it into a life style. With passion, we strive for excellence, and make the world a better place.



Picture of the Day:

Picture credit: Argyris Kaldiris