Understanding Relationships Through Data

This session on the Large Scale Computing track called "Understanding Relationships Through Data" was presented by Ming Hua, one of my lab-mates from grad school!   Ming now works at Facebook so it was great to see her again.  Of course, I knew from being a student with her that her talk would be excellent. :-)

Ming began the talk with some data - there are ~350 million users on facebook with 80 million photos uploaded.  Billions of pieces of content are shared every week, with people listening to music, checking in with friends, and posting photos and videos and sharing those updates with their friends.  The average user has 130 friends and is connected to 80 pages, groups, locations, etc.  This can be organized as a giant social graph.

The key point Ming makes is that there is a 'data generation loop', with reciprocal relationships between shared content, social context, and social connections.  Each node in this loop brings up different questions:

• What do people share about?
• What do people do together?
• What do people connect with?

To explore these questions, Ming presented several aspects of her research.  First, she spoke about her investigations into 'happiness analysis', in which she tried to predict if people (Facebook users) are happy.  She stressed that they conducted a voluntary study where they received feedback from users and analyzed their facebook updates.  An ideal measure of happiness requires:

• a reperesetnative of sample population
• should be based on naturalistic behaviour
• is computational (no human raters)
• is efficient (must process millions of updates per hour)

She conducted sentiment analysis on FB status updates:

• there are billions of status updates are shared monthly
• these updates are used for self-expression
• the identified updates are then published to friends and the public

The words in Facebook statuses can be mapped to emotion:

• there are word categories to represent psychological content
• this is well validated in many corpa
• i.e. "Fred hates passive aggressive Facebook updates, but loves irony" - "hate" and "aggress" are negative emotional terms, "updates" is a neutral term, and "love" is positive.

The hypothesis is that happier people use more positive and/or fewer negative words
Facebook recruited 1341 English speakers to complete the study.  They looked at the percentage  of positive and negative words in updates and graphed the gross national happiness in US as a result.  It was interesting to see that the happiest days of the year according to the data are Thanksgiving, Christmas, New Years' Eve, Valentine's Day, Easter, and Halloween (however Ming stressed the need to normalize for phrases like 'Happy Halloween' in Facebook status updates).

People also like many pages (owned, authentic pages, sourced pages like wikipedia, community pages), so Ming asked, what if we represent all entities in the world by facebook pages, thus turning them into connections in the graph?  We might be better able to provide page recommendations, insights, ad targeting, and de-duplication of existing pages and pages provided in results.

Another interesting application of this kind of data analysis is to predict hours of business based on user check-ins using the words and data provided in their status updates.  There are other applications as well, given by the demographic and temporal data mapped geographically.  For example, check-ins could be predicted.  A study was done by holding out check-ins and trying to predict them by feeding the features into a logistic regression, works well for check-ins.  It doesn't work as well for predicting comments or 'likes' on a given check-in.

Responses to check-ins could also be predicted: Ming found that responses are more likely when the person checks in far from their usual location.  For example, when Ming checks in in Portland, she gets more responses than her check-ins in SF, which are much more common for her.  Also, if you check-in close to a commenter/liker, then you will are more likely to get a response.

Ming showed us several prototypes; for example, one that suggests better content for you based on the people you tag.  Or, instead of searching for pages when you type in #ghc11, you would get events, pages, friends statuses, etc.  The goal is to rank things that best match your original purpose.  There are new features based on geolocation, and real-time search of friends status updates.  Ming ended by reminding us that the ultimate goal is to stress the loop to make the world more open and connected.

There were many questions including one of my own: what are the concerns/implications around being able to identify people's moods?  Do happier people have more happy friends?  What are the future directions for Facebook along these lines?  Ming said that happier friends may have more interactions with their friends, so that can help identify them.

Public Table Extraction Dataset

I am posting a copy of the table extraction dataset I created for my thesis here.

The dataset has three parts:

• PublicTableExtractionDataset, a SQL database to keep track of the html pages and tables and which contains the manual labels of 'data table' or 'layout table'
• JavaCrawlerTestDump, a folder containing all the crawled html pages
• TableDump, a folder containing all the extracted tables from each crawled html page

Practical Information

Schema: PublicTableExtractionDataset consists of two tables, HTMLPages and Table_Contents. HTMLPages contains information on where html pages are located and how to identify them, while Table_Contents contains information on each table extracted from each HTMLPage, as well as the type of table it is (a value of '1' indicates a layout table, while a value of '2' indicates a data table).

The schema for the two tables is as follows:

HTMLPages:

• File_ID (int, not null)
• File_Name (varchar(200), not null)
• Page_Domain (varchar(200), not null)
• URL (varchar(1000), not null)
• Page_Type(int, not null)

Table_Contents:

• File_ID (int, not null)
• Table_ID (int, not null)
• Table_File_Location (varchar(200), not null)
• Table_Type (int, null)

Format: This database is a backup of the original SQL database I used. You will need to import it to a new database using the 'import database' wizard provided with SQL Server. I have tested this with the express and full versions of SQL Server 2000 and 2008, so please let me know if you have any questions.

Accessing html pages and tables: I have removed the folder locations from the database, but you can easily add your own. For example, to update the HTMLPages SQL table to add the locations, you could use the following query:

update HTMLPages

set File_Name = 'new location' + File_Name

from HTMLPages

The same query could be used to update the Table_Contents table, just remember to change HTMLPages to Table_Contents.

Dataset Statistics

I collected 9,365 HTML pages which contain the <table> tag from 512 random domains. These pages contain a minimum of 1 and a maximum of 1,539 table pages. 6,620 table pages consist only of non-data tables, while 2,745 pages consist of at least one data table.

The total number of tables collected was 78,438, with 74,202 (94.6%) of these being non-data tables, and 4,236 (5.4%) being data tables.

More Details

You can read more about this data set and the experiments I used it for in my thesis.

Funny Biproducts of Research

I've recently begun working full-throttle on my Master's thesis. The first stage requires crawling a number of pages looking for certain HTML features within them. Unfortunately, the feature I am interested in can be used in multiple ways, and I need to make sure manually that each page contains the one I need. Luckily I was able to make an interface that significantly speeds up this process, but the whole process still requires several hours of clicking 'keep' or 'reject' buttons. On the bright side, I got to see first-hand what an eclectic collection of pages I've crawled:

• several pages of sumo wrestler bios and statistics
• lots of pages about the odds on horse races
• many pages in Estonian
• a lot of pages about finances, weather, and distaster information

It's a fun project and hopefully I'll be able to blog more about it as I progress with each stage of it.

So many things, So little time.

My poor blog! I've been so busy I haven't had any time to update...so here's a recap from the past week.

On Thursday I attended Burnaby Mountain College's "Dialogue with William Gibson". I had no idea that a Burnaby Mountain College even existed, let alone that they had dialogues with such cool guests. William Gibson is a slow and deliberate speaker; you hang off every word he says and know he's carefully chosen them. The ideas we discussed ranged from the Cold War, to Japan, to the privacy of the future, to the rapid development of Vancouver. Memorable ideas from the talk: "Japan is the windshield of humanity" (with reference to Japan's unique history from the rapid industrialization of Japan right up until the end of the Second World War); secrets may not exist in the future; politicians can use complete lack of secrets/total transparency such that they would be harder to attach than politicians with secrets; the main problem with Vancouver's development is that we are destroying cheap, ground-level retail rental space. I realized that I completely missed the release of his latest book, "Spook Country", which I should get around to reading sometime.

Apart from doing research and working on my internship, I've been busy with WICS as usual, helping students apply for funding within the school (Yes! Grad students can apply!), and for the Grace Hopper Conference Scholarship. We had a Technical Interview event last week that was really eye-opening for me at least; I've seen some of the problems before but learned a lot about how to approach them in an interview situation; a fun and valuable experience overall.

Speaking of WICS, a while back I met three other students on a Facebook forum where we were discussing our women's technical groups. We ended up making a proposal to GHC for a Birds of a Feather session, which was accepted! I'm just thrilled to be able to play a [slightly] larger role in GHC this year and show off the work we've been doing with WICS@SFU. :D

In other news: will be attending the SIGMOD conference next week, my first data mining conference. Should be great!

Official Google Blog: Searching for the Wisconsin primaries

This is a neat idea, and it's nice that we get to see some concrete examples of how Googlers spend their 20% time. Mash-ups have some really practical applications and if I ever get the time, I'd really like to try making some of my own.

Here's an example from the blog of the map with the queries for Democratic candidates plotted on it:

End of Semester Updates

It's been a long, difficult semester for me, but it is finally coming to a close. There were many challenges along the way, and I gained many new skills and learned many new things, from python, to robotics hardware and programming strategy, to the fundamentals of Complexity Theory. I also worked on my first real research project, wrote a paper, attended two conferences, competed in my very first robotics competition, as well as the Google Games. Still, I'm very glad it's all over and am only waiting to hear about the results of one last course.

I have many plans for the winter break. From now until January I will be working on completing the coding for my research project, PLEDS, which I will probably talk more about at a later date. I have submitted a demo paper to a conference and have high hopes for it! I am also working on a new NSERC proposal for an Industrial Postgraduate Scholarship. I also think I should really take a crack at brushing up on C++ and becoming proficient with it. I plan to reread Cormen and improve my skills in the theory and algorithm area. I know this is not my strongest area and I want to do my best to improve. Finally, I would like to work on improving my French - it's been a long-abandoned language for me, but it may be useful in the coming year.

This marks the end of my undergraduate career! I feel that it is somewhat of a milestone and am looking forward to starting my Master's in January.

Robots!

We are now in the hardware phase of building our robot. Yesterday we were able to get linux installed on a CF card! No luck booting from it when connecting to the robot, however. We'll continue the work this weekend and hopefully have something usable by the start of next week. In the meantime, work continues on my data mining project, which I am now implementing, and I am also trying to keep up with my other two courses. In the picture above I don't look nearly as sleep-deprived as I actually am.

Nexus 6 Robotics Team @ SFU and Other Work

I realize I haven't updated for a while. I've been busy preparing for a robotics competition at the Richard Tapia conference - I am a member of a four-person undergraduate team from SFU called Nexus 6. The qualification deadline is next week so there is a bit of a crunch right now.

I'm learning to use linux, program in python, and am studying automated classification and other data mining techniques such as Support Vector Machines. I'm also working on an interesting project in the Data Mining lab. Finally, I'm getting a chance to use my physics background while working with robots, which is pretty neat.