Custom Quicksort vs Library Sort in C#

Last night I was thinking about the performance of a custom, program-defined sorting routine versus the performance of a built-in, library-defined sorting routine. (Yes, my life is pretty sad).

I had two hypotheses. First, a custom sort routine would be slightly faster than a library routine because the custom version could avoid unnecessary error-checking. Second, a library sort routine would be slightly faster because it can do all kinds of low-level optimizations.

customsortvslibrarysort

Years ago I worked on analyzing the performance of Internet Explorer. It turns out that the only way to know about performance is to run experiments. So, I coded up a custom quicksort routine using the C# language. Then I measured the time to sort an array with 100,000 random values using my custom quicksort and also using the built-in library Array.Sort() routine.

The library sort routine took about 26 milliseconds and the custom sort routine took about 13 milliseconds. My conclusion is that the library sort routine is better except in situations where you need some kind of custom sorting behavior, or if you intend for the program that uses the sort routine to be implemented in several different languages.

Posted in Machine Learning | Leave a comment

Generative Adversarial Networks

I listened to a super interesting talk about deep learning a few days ago. The talk was mostly an overview of deep learning but also presented current and future trends. According to the speaker, the hottest topic in deep learning is something called “generative adversarial networks” (GANs).

GANs are very difficult to explain succinctly. Regular deep neural networks require training data that has known input and output values. Then the network is trained which really means learning a very complex math equation that can be used to make predictions for new data that has unknown output values. For example, a deep neural network can predict if an image represents a ‘0’ or a ‘1’ or a ‘2’ or . . . or a ‘9’.

At a high level, GANs try to create input data and output data. Put another way, a GAN tries to generate a complex math equation that yields both input and output values.

A GAN has two main components. A common analogy is that a GAN has a “forger” / “generator” component that attempts to create data (a counterfeit bill that is indistinguishable from a real bill). The “investigator” / “discriminator” component looks at real training data and the forged data, and attempts to determine which is the real data (is a bill counterfeit or not).

This is a rather difficult concept to grasp. The classic example of a GAN is one that learns how to generate images of a cat or something similar). The idea here is that if a GAN can create very realistic images of a cat, then the GAN “discriminator” component can predict if any image is one of a cat. The images below are “Starry Night” by van Gogh and a fake image generated by a GAN. In theory the GAN can distinguish between real and fake van Gogh paintings.

gan_real_vs_generated

GANs are very new (first introduced in 2014) and it’s not clear if GANs can be used for tasks other than image processing and pattern recognition. At any rate, GANs are the subject of intense research efforts. Maybe GANs will turn out to be a major new deep learning technique, or maybe GANs will fade to obscurity in a few years. Or maybe they’ll be just another tool in the general bag of machine learning tools.

Posted in Machine Learning | Leave a comment

A Brief Look at CNTK v2.0

CNTK is the Microsoft Cognitive Toolkit. CNTK is a collection of software that can do classification prediction using regular feed-forward neural networks, deep neural networks, and convolutional neural networks.

The tool itself is very complex. A few months ago, I took a first look at CNTK v1.6. I noticed that a beta of v2.0 had been released on GitHub so I thought I’d revisit CNTK to see what was new.

The first thing I noticed was that the documentation for CNTK is very weak. The organization is bad, much published information is out of date, and a lot of important information doesn’t exist. I suspect the CNTK team is just releasing too fast, without taking into account the fact that potential end users will be utterly frustrated by inconsistent and out-of-date information.

cntk_v2_demo

Another thing that irks me is the name of CNTK itself. CNTK originally stood for “Computational Network Toolkit”. OK, but “toolkit” is one word so why wasn’t the acronym “CNT”? And what possible advantage is there to changing the name to Microsoft Cognitive Toolkit? And why is the acronym for Microsoft Cognitive Toolkit still CNTK? Why not MCT?

Now naming isn’t all that important, but it suggests a lack of attention to detail by the CNTK team (or perhaps that the team is just over-extended).

The CNTK installation instructions were pretty awful. I had to follow link, after link, after link, and I never really did find clear instructions. How hard could it be to create a simple end-to-end install and run-a-demo Quick Start? In the end I just downloaded a zip file and extracted it. On my first attempt to run a CNTK script, I got a “msmpi.dll is missing from your computer” error in a popup window. After a bit a googling I found an installation page for that dependency and was able to get an example running.

CNTK has great potential, but the documentation needs lots of work. I’ve talked to quite a few of my colleagues who attempted to use CNTK but gave up because of the lack of clear documentation. When the CNTK people get their documentation act together, I suspect CNTK could become my neural network tool of choice.

Posted in Machine Learning | Leave a comment

A Document-Based Automated Answering System

I was sitting in on a meeting of some of my colleagues recently. They were discussing how you might go about creating an automated answering system that is based on a document of some sort. For example, the base document might be the rule book for a complicated game like American football, or perhaps a Wikipedia page. Users could query the base document in natural language, for example, “What is a 1-point safety?”

My first thought was that the creation of such a system absolutely has to be 100% automated — any system that has a manual component is obviously doomed.

fortuneteller

So, later in the day I gave the problem a little bit of thought and came up with a possible architecture for an automated, document-based answering system. First you’d programmatically analyze the base document. For each sentence, you’d generate possible questions. For example, if one base document sentence reads “the penalty for defensive holding is loss of five yards and automatic first down” then one question might be “what is the penalty for defensive holding?”

After the document has been analyzed and the questions created, the system would work by accepting a user’s question then doing a sentence-similarity search for the auto-generated questions. The closest question maps to an answer, which is returned to the user. For example, a user might ask “Is the penalty for holding five yards?” which would map to the system question “what is the penalty for defensive holding?” which maps to the answer “the penalty for defensive holding is loss of five yards and automatic first down”.

This would be a difficult system to create. But it seems possible.

Posted in Machine Learning | Leave a comment

NFL 2016 Week 13 Predictions – Zoltar has Nine Suggestions

Zoltar is my NFL prediction computer program. Here are Zoltar’s predictions for week 13 of the 2016 NFL season:


Zoltar:     cowboys  by    0  dog =     vikings    Vegas:     cowboys  by  3.5
Zoltar:       bears  by    6  dog = fortyniners    Vegas:       bears  by  2.5
Zoltar:     packers  by    2  dog =      texans    Vegas:     packers  by    6
Zoltar:    dolphins  by    0  dog =      ravens    Vegas:      ravens  by  3.5
Zoltar:     broncos  by    9  dog =     jaguars    Vegas:     broncos  by    5
Zoltar:      chiefs  by    0  dog =     falcons    Vegas:     falcons  by  3.5
Zoltar:    patriots  by   11  dog =        rams    Vegas:    patriots  by 13.5
Zoltar:     bengals  by    6  dog =      eagles    Vegas:      eagles  by    2
Zoltar:       lions  by    0  dog =      saints    Vegas:      saints  by    5
Zoltar:     raiders  by    6  dog =       bills    Vegas:     raiders  by    3
Zoltar:  buccaneers  by    0  dog =    chargers    Vegas:    chargers  by    4
Zoltar:    steelers  by    4  dog =      giants    Vegas:    steelers  by    6
Zoltar:   cardinals  by    2  dog =    redskins    Vegas:   cardinals  by  2.5
Zoltar:    seahawks  by    5  dog =    panthers    Vegas:    seahawks  by    7
Zoltar:       colts  by    0  dog =        jets    Vegas:       colts  by    1

Zoltar theoretically suggests betting when the Vegas line is more than 3.0 points different from Zoltar’s prediction. For week 13 Zoltar has nine suggestions, which is the most suggestions he’s had for a week in the last five years

1. Zoltar likes the Vegas underdog Vikings against the Cowboys. Zoltar thinks the teams are evenly matched by Vegas has the Cowboys winning by 3.5 points.

2. Zoltar likes the Vegas favorite Bears against the 49ers. Zoltar thinks the Bears are 6.0 points better than the 49ers but Vegas has the Bears wining by only 2.5 points.

3. Zoltar likes the Vegas underdog Texans against the Packers. Zoltar thinks the Packers are only 2.0 points better than the Texans but Vegas has the Packers as a 6.0 point favorite.

4. Zoltar likes the Vegas underdog Dolphins against the Ravens. Zoltar thinks the two teams are evenly matched but Vegas has the Ravens to win by 3.5 points.

5. Zoltar likes the Vegas favorite Broncos against the Jaguars. Zoltar thinks the Broncos are 9.0 points better than the Jaguars but Vegas says the Broncos will win only by 5.0 points.

6. Zoltar likes the Vegas underdog Chiefs against the Falcons. Zoltar thinks the teams are evenly matched but Vegas says the Falcons will win by 3.5 points.

7. Zoltar likes the Vegas underdog Bengals against the Eagles. Zoltar thinks the Bengals are 6.0 points better than the Eagles but Vegas says the Eagles will win by 2.0 points.

8. Zoltar likes the Vegas underdog Lions against the Saints. Zoltar says the two teams are evenly matched but Vegas says the Saints will win by 5.0 points.

9. Zoltar likes the Vegas underdog Buccaneers against the Chargers. Zoltar thinks the two teams are evenly matched but Vegas says the Chargers will win by 4.0 points.

In week 12, Zoltar went a poor 1-2 against the Vegas point spread. Note: on my original predictions I had some bad data and so I didn’t count two games. Also, I have a super-secret version of Zoltar that correctly figured the Seahawks would lose to the Bills because the Seahawks starting Strong Safety was out due to injury but I didn’t count this — Zoltar believes that there are three positions that have an enormous 6.0 point effect.

For the season so far, Zoltar is 22-16 against the Vegas spread, for 58% accuracy. Historically, Zoltar is usually between 62% and 72% accuracy against the Vegas spread over the course of an entire season.

Theoretically, if you must bet $110 to win $100 (typical) then you’ll make money if you predict at 53% accuracy or better. But realistically, you need to predict at 60% accuracy or better.

Just for fun, I track how well Zoltar and Cortana/Bing Predictions do when just trying to predict just which team will win a game. This isn’t useful except for parlay betting.

In week 12, just predicting winners, Zoltar was 10-6. Cortana/Bing was a very good 12-4 for the week.

For the season, just predicting winners, Zoltar is 114-61 (65% accuracy). Cortana/Bing is 103-72 (59% accuracy). There have been two ties, which I don’t include.

Note: Zoltar sometimes predicts a 0-point margin of victory. In those situations, to pick a winner so I can compare against Cortana/Bing, in the first four weeks of the season, Zoltar picks the home team to win. After week 4, Zoltar uses historical data for the current season (which usually ends up in a prediction that the home team will win).

zoltarweek13run

Posted in Machine Learning | 2 Comments

Sorting Parallel Arrays using Quicksort

I was thinking about coding up a demo of the k-nn (“k nearest neighbors) classifier algorithm. The k-nn algorithm is almost too simple. The goal is to predict the class of something, for example, the political leaning (conservative, moderate, liberal) of a person based on age, income, and number dependents. You get a bunch of data that has known class labels, then set k (suppose k = 3), then find the k closest data items to your unknown data, then “take a vote” to determine the predicted class.

Well I was thinking about the part of the algorithm where you find the k nearest neighbors. The simplest approach is to calculate the distances from the item-to-predict and all known data items, then sort from nearest to farthest, then use the k nearest.

Anyway, there are a lot of implementation details. One approach would be to create an object that holds data values plus an index that IDs each item. For languages like C# this is a good approach because you can automatically (well, almost) sort objects.

An older approach is to set up two parallel arrays where one of the arrays holds distance values and the other array holds index IDs. Then you can sort on the distance array but every time two cells are exchanged, you also exchange the corresponding IDs in the other array.

parallelarrayquicksortdemo

For example, suppose you have just five data items and item [0] is 4.0 units away from the item to classify, and items [1] thru [4] have distances of 0.0, 2.0, 3.0, 1.0 respectively. The distance array would be { 4.0, 0.0, 2.0, 3.0, 1.0 } and the IDs array would be { 0, 1, 2, 3, 4 }. After sorting you’d have:

0.0  1.0  2.0  3.0  4.0  
1    4    2    3    0

Item [1] is closest, item [4] is second closet and so on. Just for fun, I coded up a little demo that implements the quicksort algorithm, but on two arrays. Good fun!

Posted in Machine Learning | Leave a comment

Strong vs. Weak Artificial Intelligence

I was chatting with a couple of work colleagues recently, about strong AI vs. weak AI. Strong AI loosely means trying to create a system or a robot that can do pretty much whatever a human can do. Weak AI (also called narrow AI) loosely means creating a system that can do just one task that is normally associated with human abilities.

One of the oldest examples of weak AI is computer chess. (Note: there is a world chess championship match going on right now between current champ Magnus Carlsen and challenger Sergei Karjakin). Other examples of weak AI might be Apple’s Siri, Microsoft’s Cortana, and Amazon’s Alexa.

strongartificialintelligence

Most of my colleagues think that research should focus on strong AI. I hold the minority view that we are decades away from having enough raw computing power to get anywhere close to strong AI. My view is that work on strong AI may lead to a few unexpected breakthroughs, but a more efficient approach is to focus on weak AI problems and let strong AI more or less take care of itself.

Put slightly differently, I enjoy working on a specific problem, such as predicting NFL football scores (as in my Zoltar system) rather than general problems or pure research.

Posted in Machine Learning | Leave a comment