Rogue Wolves

Pac-Man is NP-Hard

2012-01-29T00:00:00-05:00

If you were never good at the 80’s classic video game Pac-Man don’t feel too bad. Giovanni Viglietta from the University of Pisa has published a research paper entitled ”Gaming is a hard job, but someone has to do it!” that provides an existence proof of a polynomial time reduction of Pac-Man to the famous Traveling Salesman Problem. For those not up on their theory of computation, this result means Pac-Man is in the complexity class NP-Hard, which means it is at least as hard to solve as the hardest problems in the class NP. In short, it is very hard to solve these problems with a computer in a reasonable amount of time.

Viglietta classifies a large number of classic video games by proving common game mechanics (features) reduce into particular complexity classes. This novel meta approach makes it easy to determine the complexity of particular video game by proving it exhibits a meta-feature, which maps it to a complexity class. Using this approach Viglietta shows the complexity class of several classic games such as:

Boulder Dash (First Star Software, 1984) is NP-hard.
Doom (id Software, 1993) is PSPACE-hard.
Lemmings (DMA Design, 1991) is NP-hard.
Lode Runner (Brderbund, 1983) is NP-hard.
Pac-Man (Namco, 1980) is NP-hard.
Prince of Persia (Broderbund, 1989) is PSPACE-complete.
Tron (Bally Midway, 1982) is NP-hard.

(via Technology Review)

Octopress

2012-01-28T00:00:00-05:00

Looking to switch to a static site generator for your blog or website? I came across Octopress, which is based on the same static site generator I used for this site: Jekyll. Octopress provides a nice modern HTML5 blog-style template, and comes pre-configured with 3rd party support for Twitter, Google Plus, Disquis, Google Analytics and more. It even has support for easy deployment using rsync or git. Essentially, most of the configuration and tweaks I did for my own Jekyll setup, Octopress comes with out of the box. If you are considering using Jekyll, you’d be crazy to not take a look at Octopress. I’m happy with my current setup, but I would have used it had I found it sooner.

(via @bmann)

Plex Media Center

2012-01-22T00:00:00-05:00

I’ve recently switched from using Boxee to power my home media center. I was excited for the Boxee Box version of the software to be ported to PCs. Unfortunately, the new version of the PC software, while looking more polished, is actually a downgrade in terms of reliability and features. It’s a disappointment, and Boxee has stated their desire to abandon the PC version going forward so don’t expect a lot of polish to go into this version:

This 1.5 release will be the last version of Boxee for PC/Mac/Ubuntu. It will be available on Boxee.tv through the end of January.

I understand their desire to focus their business on the Boxee Box and I wish them success. However, I needed to find a more reliable solution that fits my setup. My brother recommended I look at Plex as a replacement. First off, this application is gorgeous. It’s well designed and easy to use. Plex integrates with iTunes and iPhoto, allowing you to stream your music, videos and photos. Also, it supports extensibility via plugins such as adding new videos sources. It’s a free download, so I thought I’d give it a try.

The software is split into two major components: 1) streaming media server; and 2) media clients. The server manages your media library, downloads meta-data and streams to the client software. There are media clients for Mac, iOS and Android devices. You can pretty much watch your media wherever you want.

I’m impressed with the software so far. It’s technically still preview release, but it’s been pretty reliable so far. It’s freely available so give it a try if you are looking for media center software.

Natural Language Processing with Python

2012-01-17T00:00:00-05:00

Freely available text book on using the Python Natural Language Toolkit. I’ve used nltk for several projects. It’s a fantastic toolkit and definitely worth a look if you have some NLP work. I have not read this text. It appears to be a more hands on introduction rather than a deep dive into NLP theory and nltk.

From the preface:

This book is a practical introduction to NLP. You will learn by example, write real programs, and grasp the value of being able to test an idea through implementation. If you haven’t learnt already, this book will teach you programming. Unlike other programming books, we provide extensive illustrations and exercises from NLP. The approach we have taken is also principled, in that we cover the theoretical underpinnings and don’t shy away from careful linguistic and computational analysis. We have tried to be pragmatic in striking a balance between theory and application, identifying the connections and the tensions. Finally, we recognize that you won’t get through this unless it is also pleasurable, so we have tried to include many applications and examples that are interesting and entertaining, sometimes whimsical.

Rise of the Machine-oriented Web

2012-01-15T00:00:00-05:00

Stephen Wolfram proposes a Top Level Domain (TLD) to form a data web:

But wouldn’t it be nice if there was some standard way to get access to whatever structured data any organization wants to expose? […] My concept for the .data domain is to use it to create the “data web”-in a sense a parallel construct to the ordinary web, but oriented toward structured data intended for computational use. The notion is that alongside a website like wolfram.com (http://www.wolfram.com/), there’d be wolfram.data.

Why have a top level domain (TLD) over say a sub-domain like: data.roguewolves.com or sitemap-like construct?

Now of course one could just start a convention that organizations should have a “/datamap.xml” file (or somesuch) in the root of their web domains, just like a sitemap-rather than having a whole separate .data site. But I think introducing a new .data top-level domain would give much more prominence to the creation of the data web-and would provide the kind of momentum that’d be needed to get good, widespread, standards for the various kinds of data. […] If a human went to wolfram.data, there’d be a structured summary of what data the organization behind it wanted to expose. And if a computational system went there, it’d find just what it needs to ingest the data, and begin computing with it

This is an interesting idea. Creating a TLD could help promote organizing the web into a human-oriented web and data web. This would be a good first step in making data available, but to support machine computation we need standards to describe the data. Semantic web standards are complex, hampering their adoption. Recent proposals such as RDFa and Microformats have taken a different approach to the data web. Rather than having separate human/machine representations of web data, instead the data is semantically marked up inline with human readable content. The same data can be presented to humans and machines for consumption. This is a nice approach, but mostly appropriate for document oriented data that is intended for human consumption. Large data-bases of data are highly valuable but rarely exposed as human consumable data. There is a need for a machine oriented data web.

It’s been interesting for me in the past few years to be involved in the emergence of the modern data community. And from what I have seen, I think we’re now just reaching a critical point, where a wide range of organizations are ready to engage in delivering large-scale structured data in standardized forms.

The rise of the machine-oriented web has tremendous potential for data mining, search, automated inferencing and computation. The advanced reasoning capabilities that can be built on top of the machine-oriented web could transform our society. IBM’s Watson, Apple’s Siri and Wolfram Alpha are examples of advanced capabilities that can be built from availability of large structured data.

Citeology visualizing paper genealogy

2012-01-02T00:00:00-05:00

Autodesk Research has an interesting interactive visualization project, Citeology which visualizes citations in research publications.

From the Citeology website :

Citeology looks at the relationship between research publications through their use of citations. The names of each of the 3,502 papers published at the CHI and UIST Human Computer Interaction (HCI) conferences between 1982 and 2010 are listed by year and sorted with the most cited papers in the middle. In total, 11,699 citations were made from one article to another within this collection. These citations are represented by the curved lines in the graphic, linking each paper to those that it referenced.

The application runs as a Java Applet in the browser, where you can select a paper and see the papers referenced (blue arcs) and papers that reference it (red arcs). This would be a very useful tool for navigating through related work.

(via flowingdata)

Perspective

2011-12-31T00:00:00-05:00

This info graphic puts our place in the known Universe into perspective. A thought to contemplate while we are celebrating the beginning of 2012.

(via Techvert)

Also, check out this great video of the known Universe.

I’m always humbled when I try and wrap my head around the sheer scale of the Universe.

Graph Theory with Applications

2011-12-31T00:00:00-05:00

Freely available pdf of textbook on graph theory, Graph Theory with Applications by Bondy and Murty.

(via @phelo)

Productive Holiday Season

2011-12-30T00:00:00-05:00

Over the Christmas / New Years holidays I’ve gotten around to a few projects of mine:

I finally got around to completing two journal articles I have been working on for several months. It feels good to have them completed. Fingers crossed they are accepted for publication. I’ll refrain from mentioning where they were submitted, but the topics of the papers relate to my dissertation work on probabilistic multi-agent systems.
I bought a Mac Mini and built a new media hub for our home. With iCloud, iTunes Match and Boxee, all of our content is stored on the mini and hooked into our TV and stereo. I also bought a Bluetooth keyboard + Magic Tackpad and that setup is working great. I was skeptical of the Magic Trackpad, but it is awesome. I may have to get one of these for the office. I also hooked up a webcam and I built a makeshift nanny cam using Skype with auto-answer enabled. I can remotely call my home Skype account via my iPhone and check on our dog…and potentially yell at them if they are being bad. I call this the “voice of god” mode.
I wrote a few scripts to automate posting to this site. I use Gmail IMAP support + email filters to allow me to email posts (similar to posterious). A script running on my Mac Mini will login periodically to Gmail via IMAP, look for an unread email in a posts folder, download it and create a Markdown file, then rebuild my site via jekyll and rsync it to my web host. I’ll get around to writing more about my setup for those that might be interested.
Since I was playing around with automating posting to my website, I figured I’d also play around with auto posting the blog update to Twitter. Previously, I wrote a short url service so I turn the new post url into a short url and then generate a new tweet in my Twitter timeline. It seems to be working well.
I have been lax on backing up our computers lately. I have been thinking about buying a NAS such as an Apple Time Machine. I have an Apple AirPort and I noticed it has USB ports on the back. I decided to try plugging in an external hard drive and sure enough it mounts the volume and makes it available over the network! I have turned it into a Time Machine backup drive.
Recently, we have had a death in the family. It was unexpected and very sad. The experience made us realize how important it is to have a will and ensure all your assets are jointly owned with your spouse. My wife and I spent a few days adding each other to all our accounts. If you haven’t done this, trust me and go do it. In the unfortunately event, one of you passes, it will make everything much easier for your spouse.

Well that’s it in a nut, aside from the typical holiday events. Fairly productive. Last night we went to see the Trans-Siberian Orchestra. Wow. If you haven’t seen them before and you get the chance, I highly recommend it. Rock ‘n’ Rock + Classical + Pyro-technics = Awesome.

Mining of Massive Datasets

2011-12-27T00:00:00-05:00

Rajaraman and Ullman’s textbook Mining of Massive Datasets is available as a free download. Summary of the book’s contents from the preface:

At the highest level of description, this book is about data mining. However, it focuses on data mining of very large amounts of data, that is, data so large it does not fit in main memory. Because of the emphasis on size, many of our examples are about the Web or data derived from the Web. Further, the book takes an algorithmic point of view: data mining is about applying algorithms to data, rather than using data to “train” a machine-learning engine of some sort.

Links for 2011-07-25 [del.icio.us]

2011-07-26T00:00:00-07:00

Program for Large Network Analysis
Pajek is a program, for Windows, for analysis and visualization of large networks.

Links for 2011-07-13 [del.icio.us]

2011-07-14T00:00:00-07:00

Edward Tufte’s “Slopegraphs”

Links for 2011-07-10 [del.icio.us]

2011-07-11T00:00:00-07:00

My new bike
Recently, I've gotten into road cycling. Mostly because I can commute to work along the beautiful Lake Ontario shoreline into downtown Toronto. It's about a 19 km ride one way mostly along an aweso ...

Links for 2011-06-24 [del.icio.us]

2011-06-25T00:00:00-07:00

Eclipse Color Themes
Eclipse extension that makes it easy to change syntax coloring themes

Links for 2011-05-11 [del.icio.us]

2011-05-12T00:00:00-07:00

Tuffy: A Scalable MLN Inference Engine
Tuffy is an open-source Markov Logic Network inference engine
Gephi, an open source graph visualization and manipulation software
Gephi is an interactive visualization and exploration platform for all kinds of networks and complex systems, dynamic and hierarchical graphs.

Links for 2011-04-19 [del.icio.us]

2011-04-20T00:00:00-07:00

TrueCrypt
Free Open-Source On-The-Fly Disk Encryption Software for Windows 7/Vista/XP, Mac OS X and Linux

Links for 2011-04-05 [del.icio.us]

2011-04-06T00:00:00-07:00

Bayes OWL
Probabilistic extension to OWL
PR-OWL
A Bayesian Framework for Probabilistic Ontologies