Batcher's odd-even merging network

Batcher's odd-even merge based sorting network node partner calculation.

I couldn't find a closed-form formula for odd-even network node partner calculation. The only available implementations were recursive and not very elegant. Here is the code that was provided on Wikipedia.

So I decided to work out a simpler and more intuitive solution to odd-even merge-based sorting network partner calculation, and here it is:

	object PartnerOddEven {
	/**
	*
	* Calculates partner in Batcher Odd-Even network.
	*
	* @param n node index: 0, 1, 2, 3, ... 2^d^-1
	* @param l merge stage: 1, 2, 3, ... d
	* @param p stage step: 1, 2, 3, ... l
	* @return Returns partner node, or self (n) if no partner for this step
	*/
	def partner(n: Int, l: Int, p: Int): Int = {
	assert(p <= l, "p should be at most l")
	assert(p > 0, "p should be at least 1")
	assert(l > 0, "l should be at least 1")
	if (p == 1)
	n ^ (1 << (l - 1))
	else {
	val (scale, box) = (1 << (l - p), 1 << p)
	val sn = n / scale - (n / scale / box) * box
	if (sn == 0 || sn == box - 1) n
	else if (sn % 2 == 0) n - scale else n + scale
	}
	}
	}

view raw OddEvenMerge.scala hosted with ❤ by GitHub

Also, here I put up a little interactive sorting network generator. Of course, I updated that Wikipedia article, to make it easier for learners :)

Here is the best performance analysis of this network that I could find.

Digit recognition with Multiclass SVM on Spark MLlib

Current version of Spark MLlib doesn't have multi-class classification with SVM, but it is possible to make multi-class classifiers out of binary classifiers. One easy way of doing it is with one-vs-all scheme. It is not as accurate as more sophisticated schemes, but it is relatively easy to implement and have decent results. Here is my implementation.

To test this multi-class classifier, we can try it on handwritten digit recognition problem. Get hand-written digits data from here.

	// using https://github.com/Bekbolatov/spark/commit/463d73323d5f08669d5ae85dc9791b036637c966
	import org.apache.spark.mllib.classification.SVMMultiClassWithSGD
	import org.apache.spark.mllib.regression.LabeledPoint
	import org.apache.spark.mllib.linalg.Vectors
	import breeze.linalg.DenseVector
	val digits_train = sc.textFile("/data/pendigits.tra").map(line => DenseVector(line.split(",").map(_.trim().toDouble))).map( v => LabeledPoint(v(-1),Vectors.dense(v(0 to 15).toArray))).cache()
	val digits_test = sc.textFile("/data/pendigits.tes").map(line => DenseVector(line.split(",").map(_.trim().toDouble))).map( v => LabeledPoint(v(-1),Vectors.dense(v(0 to 15).toArray)))
	val model = SVMMultiClassWithSGD.train(digits_train, 100)
	val predictionAndLabel = digits_test.map(p => (model.predict(p.features), p.label))
	val accuracy = 1.0 * predictionAndLabel.filter(x => x._1 == x._2).count() / digits_test.count()
	val scoreAndLabels = digits_test.map { point =>
	val score = model.predict(point.features)
	(score, point.label)
	}
	scoreAndLabels.take(5)

view raw DigitRecognition.scala hosted with ❤ by GitHub

Accuracy is only 74% with 100 iterations. Maybe it can't get much better with this construction. A different way of constructing multi-class classifiers from binary SVM is to use pairwise (one-vs-one) schemes with some adjustments as described here and also another method described here. Scikit-learn SVM classifier performs better out of the box (if used with RDF kernel accuracy is in high 90's), but the sklearn implementation is not scalable. Hopefully Spark MLlib will be able to beat this in future, when more sophisticated (high-level abstraction) ML pipeline API features comes online.

For comparison, here are some results with tree classifiers. With RandomForest (30 trees, Gini, depth 7) it goes up to 93%. Adding extra 2nd order interactions (Spark doesn't support kernels in classification yet, but here a simple feature transformation that adds second order feature interactions), and increasing allowed tree depth to 15, brings accuracy to 97%. So, there is a lot of room for improvement in multiclass to binary classifier reduction.