![\"\"](\"https:\/\/www.forinvest.com\/insights\/wp-content\/uploads\/2017\/04\/image35_65-300x185.png\")
<\/center><\/p>\nIn this post, I am going to demonstrate a two-step Scala implementation of Radial Basis Function Neural Network (RBFNetwork): (unsupervised) k-means clustering first, and (supervised) gradient descent second. This two-step implementation is fast and efficient compared to Multilayer Perceptron while providing good predictive performance. This is because unsupervised learning at the first step provides information about data distribution so that the second step can have an intuition about the data and fine-tune the model.<\/p>\n
For us, most of the Machine Learning models that we use today are just black box approaches that we take from some library. It is good to have this ability for faster development; however, it would be nicer to know internal dynamics of their implementations. Therefore, I am hoping that this post will be simple enough to provide you that information.<\/p>\n
<\/p>\n
Implementation<\/strong><\/h2>\nLet’s start with introducing the abstractions that we are going to use for the rest of the code.<\/p>\n
Function Aliases<\/h3>\n
Since the most granular abstraction is a function, here below we are going to name them based on their actual job in this implementation:<\/p>\n
\n\n\n\n\n<\/p>\ntype Features = IndexedSeq[Double]\ntype DistanceFunc = ((IndexedSeq[Double], IndexedSeq[Double]) => Double)\ntype RadialBasisFunction = (IndexedSeq[Double] => Double)\ntype Clustering = () => IndexedSeq[(Features, IndexedSeq[Features])]<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\nThis definition is useful since it lets us write more readable code. Remember:\u00a0we write code for humans to understand, assuming that the computer somehow is going to understand it anyway. For example, you can read the above code like this:<\/p>\n
Distance is a function that takes two points from n<\/em>-dimensional space specified with\u00a0IndexedSeq<\/code>‘s size\u00a0and produces an output metric of type double.<\/p>\nLet’s move forward with introducing higher-level abstractions like traits.<\/p>\n
Traits<\/h3>\n
You can think of a trait as a recipe for doing something; however, it is not something by itself. It is preferable over abstract classes when you want to take advantage of mixing classes, but the end goal is the same: you want to have a resuable set of behaviors somewhere in your code that you can use anytime to add any class that conforms to the protocol that you declare within the trait. An example of this would be gradient descent. It can actually optimize a lot of Machine Learning algorithms, not just neural networks or something else. Therefore, we can think of it as a recipe for optimizing a neural network algorithm. Down below, we define this set of behaviors.<\/p>\n
import Math.{exp,pow,sqrt}\nimport scala.annotation.tailrec\nimport scala.util.Random\ntrait Optimizer {\n def fit(dataSet: Iterable[(IndexedSeq[Double], IndexedSeq[Double])], learningRate: Double)\n}\ntrait NeuralNetworkModel extends (IndexedSeq[Double] => IndexedSeq[Double]) {\n def getH(input: (IndexedSeq[Double], IndexedSeq[Double])):IndexedSeq[Double]\n}\ntrait EuclideanDistance extends DistanceFunc {\n override def apply(position1: IndexedSeq[Double], position2: IndexedSeq[Double]): Double = {\n val sum = position1.zip(position2).map {\n case (p1, p2) => \n val d = p1 - p2\n pow(d,2)\n }.sum\n sqrt(sum)\n }\n}\ntrait GradientDescent extends Optimizer with NeuralNetworkModel {\n val nHidden: Int\n val weights: Array[Double]\n def fit(trainingData: Iterable[(IndexedSeq[Double], IndexedSeq[Double])], learningRate: Double = 0.1): Unit = {\n for(pair <- trainingData){\n val actual = this(pair._1)\n val X = getH(pair)\n val desired = pair._2\n for( outputIndex <- desired.indices) {\n val error = desired(outputIndex) - actual(outputIndex)\n val update = X.indices.map(i => learningRate * X(i) * error)\n X.indices.foreach { i =>\n val weightIndex = (nHidden * outputIndex) + i\n weights(weightIndex) = update(i) + weights(weightIndex)\n }\n \/\/bias term\n val weightIndex = (nHidden * outputIndex) + X.length\n weights(weightIndex) = learningRate * error + weights(weightIndex)\n }\n }\n }\n}<\/pre>\n<\/div>\nWe can even think of k<\/em>-means as a trait and change its distance function that it uses for its internal clustering calculation according to the same convention. Down below, we move forward with this.<\/p>\n\n\n\n\n\n\n\n\n<\/p>\ntrait RadialBasisFunctionNetworkTrait extends NeuralNetworkModel {\n val nIn: Int\n val nOut: Int\n val rbfs: IndexedSeq[RadialBasisFunction]\n val nHidden: Int = rbfs.length + 1\n val weights: Array[Double] = Array.fill(nHidden * nOut)(scala.math.random)\n override def getH(input: (IndexedSeq[Double], IndexedSeq[Double])):IndexedSeq[Double] = {\n rbfs.indices.map { i => rbfs(i)(input._1) }\n }\n override def apply(input: IndexedSeq[Double]): IndexedSeq[Double] = {\n for (outputIndex <- 0 until nOut) yield {\n val linearCombination = rbfs.indices.map { i => rbfs(i)(input) * weights((nHidden * outputIndex) + i)}\n val bias = weights((nHidden * outputIndex) + rbfs.length)\n linearCombination.sum + bias\n }\n }\n}\nabstract class KMeans(val seed: Int, val k: Int, val eta: Double, val data: Vector[Features]) extends DistanceFunc with Clustering {\n val rand = new Random(seed)\n val _data = data\n val means: Vector[Features] = (0 until k).map(_ => data(rand.nextInt(data.length))).toVector\n def apply(): IndexedSeq[(Features, IndexedSeq[Features])] = {\n @tailrec\n def _kmeans(means: IndexedSeq[Features]): IndexedSeq[(Features, IndexedSeq[Features])] = {\n val newMeans: IndexedSeq[(Features, IndexedSeq[Features])] =\n means.map(mean => {\n _data.groupBy(p => means.minBy(m => this (m, p))).get(mean) match {\n case Some(c) => (c.transpose.map(_.sum).map(x => x \/ c.length), c)\n case _ => (mean, Vector(mean))\n }\n })\n val converged = (means zip newMeans.map(_._1)).forall {\n case (oldMean, newMean) => this (oldMean, newMean) <= eta\n }\n if (!converged) _kmeans(newMeans.map(_._1)) else newMeans\n }\n _kmeans(means)\n }\n}\ntype ErrorFunc = (NeuralNetworkModel, Iterable[(IndexedSeq[Double], IndexedSeq[Double])]) => Double<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\nLet’s read above code like this: We have a NeuralNetworkModel<\/code>\u00a0that takes an input that consists of features like\u00a0IndexedSeq<\/code>\u00a0and produces target values as again IndexedSeq, this is because neural networks may produce multi outputs like in the case of mutliclass classification. We define this behavior by extending Function[IndexedSeq[Double],IndexedSeq[Double]]<\/code>. It also declares getH<\/code>\u00a0in its protocol, which means that any class that implements this needs to tell how to get hidden values from the pair of input and target values. In the case of RBFNetwork<\/code>\u00a0it applies a Gaussian Function to its inputs in its hidden layer. Therefore, when we call getH<\/code>,<\/span>\u00a0RBFNetwork<\/code> may want to return these values. Now, let’s create a K-means implementation that uses Euclidean Distance as a distance function and RBFNetwork<\/code>\u00a0with\u00a0the Gradient Descent optimizer.<\/p>\n\n\n\n\n\n\n\n\n\u00a0<\/p>\ncase class KMeansImpl(override val seed: Int,override val k: Int,override val eta: Double,override val data: Vector[Features]) extends KMeans(seed, k, eta , data)\n with EuclideanDistance\ncase class RadialBasisFunctionNetwork(nIn: Int, nOut: Int, rbfs: IndexedSeq[RadialBasisFunction]) \n extends RadialBasisFunctionNetworkTrait\n with GradientDescent<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\nThat is it. Let’s analyze an example of the dataset using this code.<\/p>\n
Inference<\/h2>\n
In this example, we have two by 50 training data and two by 100 validation data. The end goal is to construct a regression model. The first column is an input and the second column is a target or in the other words respondent variable. We are going to use Gaussian Function as a Radial Basis Function component for the neural network and use Gradient Descent as an optimizer. To initialize Gaussian Functions’ center and width, we are going to run the K-means algorithm and take means as a center for the Gaussian Function and the maximum distance between cluster elements and its mean as a width for the same function. We are going to run this pipeline with a different amount of Gaussian Experts in the other words with different hidden layer sizes and evaluate their performance so that we can observe one underfitting model, one overfitting model, and one good fit model.<\/p>\n
\n\n\n\n\n<\/p>\ndef trainAndGetModel(rbfCount: Int, training:Vector[(Vector[Double], Vector[Double])]) = {\n val kmeansImpl = KMeansImpl(seed = 1990, k = rbfCount, eta = 1E-5, data = training.map(_._1))\n val clusters = kmeansImpl()\n val radialBasisFunctions = clusters.map { case (means, cluster) => GaussianFunction(width = cluster.map(it => kmeansImpl(it, means)).max, center = means) }\n val net = new RadialBasisFunctionNetwork(nIn = 1,rbfs = radialBasisFunctions,nOut = 1)\n for (i <- 0 to 500)\n net.fit(training,0.1)\n net\n}\nval models = \n (for{i <- 1 to 10} yield { \n ( i -> trainAndGetModel(rbfCount=i,trainingData))\n })<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\nVisualization<\/h3>\n
type Features = IndexedSeq[Double]\ntype DistanceFunc = ((IndexedSeq[Double], IndexedSeq[Double]) => Double)\ntype RadialBasisFunction = (IndexedSeq[Double] => Double)\ntype Clustering = () => IndexedSeq[(Features, IndexedSeq[Features])]<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\nThis definition is useful since it lets us write more readable code. Remember:\u00a0we write code for humans to understand, assuming that the computer somehow is going to understand it anyway. For example, you can read the above code like this:<\/p>\n
Distance is a function that takes two points from n<\/em>-dimensional space specified with\u00a0
IndexedSeq<\/code>‘s size\u00a0and produces an output metric of type double.<\/p>\nLet’s move forward with introducing higher-level abstractions like traits.<\/p>\n
Traits<\/h3>\n
You can think of a trait as a recipe for doing something; however, it is not something by itself. It is preferable over abstract classes when you want to take advantage of mixing classes, but the end goal is the same: you want to have a resuable set of behaviors somewhere in your code that you can use anytime to add any class that conforms to the protocol that you declare within the trait. An example of this would be gradient descent. It can actually optimize a lot of Machine Learning algorithms, not just neural networks or something else. Therefore, we can think of it as a recipe for optimizing a neural network algorithm. Down below, we define this set of behaviors.<\/p>\n
import Math.{exp,pow,sqrt}\nimport scala.annotation.tailrec\nimport scala.util.Random\ntrait Optimizer {\n def fit(dataSet: Iterable[(IndexedSeq[Double], IndexedSeq[Double])], learningRate: Double)\n}\ntrait NeuralNetworkModel extends (IndexedSeq[Double] => IndexedSeq[Double]) {\n def getH(input: (IndexedSeq[Double], IndexedSeq[Double])):IndexedSeq[Double]\n}\ntrait EuclideanDistance extends DistanceFunc {\n override def apply(position1: IndexedSeq[Double], position2: IndexedSeq[Double]): Double = {\n val sum = position1.zip(position2).map {\n case (p1, p2) => \n val d = p1 - p2\n pow(d,2)\n }.sum\n sqrt(sum)\n }\n}\ntrait GradientDescent extends Optimizer with NeuralNetworkModel {\n val nHidden: Int\n val weights: Array[Double]\n def fit(trainingData: Iterable[(IndexedSeq[Double], IndexedSeq[Double])], learningRate: Double = 0.1): Unit = {\n for(pair <- trainingData){\n val actual = this(pair._1)\n val X = getH(pair)\n val desired = pair._2\n for( outputIndex <- desired.indices) {\n val error = desired(outputIndex) - actual(outputIndex)\n val update = X.indices.map(i => learningRate * X(i) * error)\n X.indices.foreach { i =>\n val weightIndex = (nHidden * outputIndex) + i\n weights(weightIndex) = update(i) + weights(weightIndex)\n }\n \/\/bias term\n val weightIndex = (nHidden * outputIndex) + X.length\n weights(weightIndex) = learningRate * error + weights(weightIndex)\n }\n }\n }\n}<\/pre>\n<\/div>\nWe can even think of k<\/em>-means as a trait and change its distance function that it uses for its internal clustering calculation according to the same convention. Down below, we move forward with this.<\/p>\n
\n\n\n\n\n\n\n\n<\/p>\ntrait RadialBasisFunctionNetworkTrait extends NeuralNetworkModel {\n val nIn: Int\n val nOut: Int\n val rbfs: IndexedSeq[RadialBasisFunction]\n val nHidden: Int = rbfs.length + 1\n val weights: Array[Double] = Array.fill(nHidden * nOut)(scala.math.random)\n override def getH(input: (IndexedSeq[Double], IndexedSeq[Double])):IndexedSeq[Double] = {\n rbfs.indices.map { i => rbfs(i)(input._1) }\n }\n override def apply(input: IndexedSeq[Double]): IndexedSeq[Double] = {\n for (outputIndex <- 0 until nOut) yield {\n val linearCombination = rbfs.indices.map { i => rbfs(i)(input) * weights((nHidden * outputIndex) + i)}\n val bias = weights((nHidden * outputIndex) + rbfs.length)\n linearCombination.sum + bias\n }\n }\n}\nabstract class KMeans(val seed: Int, val k: Int, val eta: Double, val data: Vector[Features]) extends DistanceFunc with Clustering {\n val rand = new Random(seed)\n val _data = data\n val means: Vector[Features] = (0 until k).map(_ => data(rand.nextInt(data.length))).toVector\n def apply(): IndexedSeq[(Features, IndexedSeq[Features])] = {\n @tailrec\n def _kmeans(means: IndexedSeq[Features]): IndexedSeq[(Features, IndexedSeq[Features])] = {\n val newMeans: IndexedSeq[(Features, IndexedSeq[Features])] =\n means.map(mean => {\n _data.groupBy(p => means.minBy(m => this (m, p))).get(mean) match {\n case Some(c) => (c.transpose.map(_.sum).map(x => x \/ c.length), c)\n case _ => (mean, Vector(mean))\n }\n })\n val converged = (means zip newMeans.map(_._1)).forall {\n case (oldMean, newMean) => this (oldMean, newMean) <= eta\n }\n if (!converged) _kmeans(newMeans.map(_._1)) else newMeans\n }\n _kmeans(means)\n }\n}\ntype ErrorFunc = (NeuralNetworkModel, Iterable[(IndexedSeq[Double], IndexedSeq[Double])]) => Double<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\nLet’s read above code like this: We have a
NeuralNetworkModel<\/code>\u00a0that takes an input that consists of features like\u00a0IndexedSeq<\/code>\u00a0and produces target values as again IndexedSeq, this is because neural networks may produce multi outputs like in the case of mutliclass classification. We define this behavior by extendingFunction[IndexedSeq[Double],IndexedSeq[Double]]<\/code>. It also declaresgetH<\/code>\u00a0in its protocol, which means that any class that implements this needs to tell how to get hidden values from the pair of input and target values. In the case ofRBFNetwork<\/code>\u00a0it applies a Gaussian Function to its inputs in its hidden layer. Therefore, when we callgetH<\/code>,<\/span>\u00a0RBFNetwork<\/code> may want to return these values. Now, let’s create a K-means implementation that uses Euclidean Distance as a distance function andRBFNetwork<\/code>\u00a0with\u00a0the Gradient Descent optimizer.<\/p>\n\n\n\n\n\n\n\n\n\u00a0<\/p>\ncase class KMeansImpl(override val seed: Int,override val k: Int,override val eta: Double,override val data: Vector[Features]) extends KMeans(seed, k, eta , data)\n with EuclideanDistance\ncase class RadialBasisFunctionNetwork(nIn: Int, nOut: Int, rbfs: IndexedSeq[RadialBasisFunction]) \n extends RadialBasisFunctionNetworkTrait\n with GradientDescent<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\nThat is it. Let’s analyze an example of the dataset using this code.<\/p>\n
Inference<\/h2>\n
In this example, we have two by 50 training data and two by 100 validation data. The end goal is to construct a regression model. The first column is an input and the second column is a target or in the other words respondent variable. We are going to use Gaussian Function as a Radial Basis Function component for the neural network and use Gradient Descent as an optimizer. To initialize Gaussian Functions’ center and width, we are going to run the K-means algorithm and take means as a center for the Gaussian Function and the maximum distance between cluster elements and its mean as a width for the same function. We are going to run this pipeline with a different amount of Gaussian Experts in the other words with different hidden layer sizes and evaluate their performance so that we can observe one underfitting model, one overfitting model, and one good fit model.<\/p>\n
\n\n\n\n\n<\/p>\ndef trainAndGetModel(rbfCount: Int, training:Vector[(Vector[Double], Vector[Double])]) = {\n val kmeansImpl = KMeansImpl(seed = 1990, k = rbfCount, eta = 1E-5, data = training.map(_._1))\n val clusters = kmeansImpl()\n val radialBasisFunctions = clusters.map { case (means, cluster) => GaussianFunction(width = cluster.map(it => kmeansImpl(it, means)).max, center = means) }\n val net = new RadialBasisFunctionNetwork(nIn = 1,rbfs = radialBasisFunctions,nOut = 1)\n for (i <- 0 to 500)\n net.fit(training,0.1)\n net\n}\nval models = \n (for{i <- 1 to 10} yield { \n ( i -> trainAndGetModel(rbfCount=i,trainingData))\n })<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\nVisualization<\/h3>\n
![\"Image](\"https:\/\/dzone.com\/storage\/temp\/5136202-trainingrmse.png\")
<\/p>\n![\"Image](\"https:\/\/dzone.com\/storage\/temp\/5136211-testrmse.png\")
<\/p>\n![\"Image](\"https:\/\/dzone.com\/storage\/temp\/5136271-underfit.png\")
<\/p>\n![\"Image](\"https:\/\/dzone.com\/storage\/temp\/5136280-overfit.png\")
<\/p>\n![\"Image](\"https:\/\/dzone.com\/storage\/temp\/5136295-goodfit.png\")
<\/p>\n