Thursday, December 6, 2018

Microsoft QuantumML tutorial

[this post was written for the 2018 Q# advent calendar]

Two colleagues recently went to Microsoft's internal Machine Learning and Data Science conference, and recommended a tutorial they did on-site, on Quantum Machine Learning. The materials for this lab have just been published on GitHub, and the following are my learnings while doing it.

The lab is implemented with Microsoft's Quantum SDK, using Q# for the Quantum code and C# for the driver code. The goal is to implement a Classifier, a discriminator able to classify a value into one of two classes -- just like a Logistic Regression classifier. Or in other words, a Quantum Perceptron. It is simple to implement if you know the core concepts of Quantum Computing, and most of it is very guided -- you just have to fill in the blanks with the right Quantum primitives, following the instructions in the comments.

Simplifying, what the algorithm does is as follows: imagine you have a pizza cut in two halves at a given angle 𝜃, and the angles higher than that are of class One, and Zero otherwise:



You also have a labeled training data set, specifying for a large number of angle values what the class/label is:


Note that the angles are represented in radians (i.e, the full circle is 0 to 2*PI) instead of 0-360º, but that is a detail. This is equivalent to having normalized data between 0 and 1.

The goal of the lab is first - to implement an algorithm that finds what the separation angle 𝜃, and second - classify new angle values as either class Zero or One. Finding the separation angle (which is equivalent to training a logistic regressor and finding its parameters) is achieved with a mixed of C# and Q# code, while doing the classification is purely Q# quantum code.

Some of the issues that confused me while doing the lab were the following:

Finding the angle - the underlying logic of Quantum Computing features a lof of linear algebra (matrixes) and trigonometry (angles). One important thing to keep in mind is that what the algorithm needs to find is not the separation angle at which the pizza was cut, but an angle perpendicular/90º to it. In the following code snippet, the separation angle is 2.0 (equivalent to 114.6º), but the angle that the algorithm needs to find is "correctAngle". By adding or subtracting PI/2 we get the perpendicular angle:

double separationAngle = 2.0; 
double correctAngle = separationAngle - Math.PI / 2;

The reason for this is related to the quantum transformations available to us. The slidedeck in the Github repo talks about this, but it wasn't immediately clear to me when I read it.

Success Rate - the Main() in the provided C# driver relies heavily on a Q# operator called QuantumClassifier_SuccessRate. What this does is find how well the quantum algorithm can classify the data points in the training data, for a given angle it is called with. The Q# operator returns this as a percentage.
The C# code then calls it multiple times with different angles using ternary search (imagine a binary tree search, but with 3 'halves'), until the error rate is low enough. This is the bulk of the training process, and when it ends it has found a good approximation of the "correctAngle" mentioned above (note that it's not looking for the separation angle 𝜃).

The QuantumClassifier_SuccessRate calls two other operators:
  • EncodeDataInQubits - as an analogy to "classical" machine learning, this can be seen as a sort of data preparation step, where you initialize the Qubits and generate a sort of "quantum feature", dataQubit. The output label is also encoded in a Qubit.
  • Validate - again as an analogy, this can be seen as applying the Hypothesis and check if we're doing the right prediction. It can be useful to think of the CNOT "truth table" to understand this code:

    CNOT(dataQubit, labelQubit);
    

     Remembering that the CNOT flips the second qubit if the first one is 1 ( |1> really), we have the following "truth table":

    CNOT(0,0) -> 0
    CNOT(1,0) -> 1
    CNOT(0,1) -> 1
    CNOT(1,1) -> 0


    Or, in other words: we have 0 as an output when the dataQubit == labelQubit, i.e., we have done the right prediction. 
Finally, the logic of the QuantumClassifier_SuccessRate itself includes two loops: one to iterate over all the values in the training dataset (0..N-1), and the second repeats each Validate operation several times (1..nSamples, where nSamples = 201 by default) to account for the probabilistic nature of Quantum Computing when you do a Measurement. Again note that nSamples is possibly a misleading name -- this doesn't refer to data samples, but to iterations of the algorithm. You can reduce this number to 100 for example, and you'll see the quality of the predictions will go down.
Doing predictions - as I mentioned in the beggining, a big part of the exercise is working on the training code, implementing the 3 operators mentioned above. For this second part, you have to implement:

a) C# code to generate a new dataset, the test dataset which you will ask your Quantum code to classify;

b) Q# code to actually do the classification. For both parts you can reuse/adapt code you have done before. This is what I ended up with:


operation QuantumClassifier (
    alpha : Double, 
    dataPoints : Double[]) : Int[] {
        
    let N = Length(dataPoints);
    mutable predictions = new Int[N];

    let nSamples = 201;

    // Allocate two qubits to be used in the classification
    using ((dataQubit, predictionQubit) = (Qubit(), Qubit())) {
            
        // Iterate over all points of the dataset
        for (i in 0 .. N - 1) {
                
            mutable zeroLabelCount = 0;
                
            // Classify i-th data point by running classification circuit nSamples times
            for (j in 1 .. nSamples) {

                // encode
                Reset(dataQubit);
                Reset(predictionQubit);
        
                Ry(dataPoints[i], dataQubit);
        
                // classify
                Ry(-alpha, dataQubit); 

                CNOT(dataQubit, predictionQubit);

                let result = M(predictionQubit) == Zero;
                if(result == true)
                { // count the number of zeros
                    set zeroLabelCount = zeroLabelCount + 1;
                }
            }

            if(zeroLabelCount > nSamples/2) {
                // if the majority of classifications are zero, we say it's a Zero
                set predictions[i] = 0;
            }
            else {
                set predictions[i] = 1;
            }
        }

        // Clean up both qubits before deallocating them using library operation Reset.
        Reset(dataQubit);
        Reset(predictionQubit);
    }
        
    return predictions;
}

This code then does the following correct predictions based on a new data set:


And that's it, your Quantum Perceptron is finished :). Now we only need hardware to run it!

While working on the lab I've gone and looked around on the web and found two articles that seem to be related to the approach followed here: "Quantum Perceptron Network" [paywall] and "Simulating a perceptron on a quantum computer", both possibly worth taking a look.

If you already have some basic knowledge of both Machine Learning and Q#, you should expect to spend maybe 2 hours on it.

Monday, December 3, 2018

Databricks/Spark Hands-on lab

This past week I organized a 4-day technical training for internal teams called LearnAI. I had some time to spare in the agenda in one of the days, so hacked together a simple challenge using Azure Databricks/Spark and Python.

Being a fan of Astronomy, I based this off a personal pet project of mine - explore ESA's Gaia satellite data using Spark. A few months back I completed Coursera's Data-driven Astronomy, and felt this was an amazing way of exploring big-data challenges while also learning some Astronomy along the way.

Anyway, I have put the resulting Notebooks and Word document with setup instructions on github. The exercises have the format of a Notebook where you fill in the missing Python code, and I've also included a solutions' notebook. The exercises are mostly introductory and should take max 3 hours to complete. You'll also need access to an Azure subscription, as I'm using Azure Blob Storage to store the data.

PS: it feels good to code once in a while ;-)

Saturday, December 1, 2018

Spark 2.4 - Avro vs Parquet

A few days ago Databricks posted this article announcing "Apache Avro as a Built-in Data Source in Apache Spark 2.4", and comparing the performance against the previous version of the Avro format support.

I was curious as to the performance of this new support against regular Parquet, so adapted the notebook Databricks supported to include a test versus this format, spun up my Azure Databricks cluster (running two Standard_DS3_v2 VMs with 14.0 GB Memory, 4 Cores, 0.75 DBUs each) using Databricks Runtime 5.0.

The notebook with the Scala code is available here, and the results I got were:

Test Avro Parquet Comparison
Read time (ms) 28061 18131 65%
Write time (ms) 41342 33904 82%
Disk space (mb) 2138 2037 95%

Parquet is the superior format in all three tests, but considering Avro is row-based and Parquet is columnar, I did expect - given the nature of the tests - for Avro to be most performant. Anyway, my goal was just to satisfy my curiosity about the performance differences at a high level, not compare the formats in general. For that, this deck is a couple of years old but has interesting information.