2D Heat Equation Solver

My least weekend project. A javascript simulation of 2D heat diffusion. Vanilla JS. Source code is here

 

Principle Component Analysis for Stock Markets

PCA application sample for analysis of stock markets using python

Click Here For GitHub Page

PCA is a mathematical method for compressing multidimensional data into a less dimensional version. That data reduction helps to make analysis more simpler. More information about principle component analysis and its math is  here. With this project I tried to analyse stock market data with PCA decomposition.

# Data

I used "Borsa Istanbul 100" a.k.a. "Bist100"  stock market index symbols. It is an index of Turkey stocks that covers top 100 biggest components. Gathered 5 basic financial ratios  for each symbol around internet and here is the raw result (ticks.raw.csv):

 

These are some common financial indicators to measure fair price of a company. I picked 5 of many indicators which i wanted in my sample analyse. Different choices made among the indicators will change the whole result.Therefore, it is important to make the right choices.  Raw data columns has various ranges. For instance price to earning range is 1.43 to 244.74 and price to book value range is 0.29 to 30.51. Too much numerical difference between columns affects their impact on the result which is not wanted. Thats why applied following steps to balance them:

• Normalize each ratio indicator in its own column to fit 0 to 1
• Crop extreme high/lows fixed limit
• After normaliztion 1 should be the best and 0 should be the worst value for each column but for some ratios lower value is better. For price to book value,dept to equality,price to book, price to 52W range lower is better. Therfore subtracted their normalized value from 1 for these columns

 

Here is the result (ticks.norm.csv):

 

Afer data fetch and normalization I pushed an other single row to final data. It is "Referance"  point. An imaginary stock with perfect ratios. All the indicators equals to 1. That point will help me to figure out better stocks after PCA decomposition.

 

# PCA

Raw data contains one label dimension (symbol column) and 5 feature dimensions. With PCA calculation, reduced that information to 2 component dimentions. These dimentions contains primary characteristic information of whole 6 dimention data. Sklearn liblary has built in PCA tools to make that happened. Pandas and matplotlib will help to visualize reduced data in scatter plot. These steps in pca.py file. Here is the result plot:

 

Closer to Referrance point means  better results:

 

Javascript Lightning Effect

My recent javascript experiment that i build for fun. It generates lightning effect on canvas. Full source code available at github.

Tensorflow Gender Detector

Here is my last Tensorflow experiment. A convolutional neural network implementation sample that detect human genders via Tensorflow and Keras.

Souce code
https://github.com/diwsi/Tensorflow-Gender-Detector

Training Data
I used https://www.kaggle.com/playlist/men-women-classification for training data. Removed useless pictures, cropped from center as square shape and resized to 128x128 pixels.

Network Model
Tensorflow keras network contains 4 convolutional layers with 3 by 3 filters. Has somoe dropout between dense layers to prevent overfitting. (trainer.py)



Training
"Sparse Categorical Crossentropy" for loss funtion with adam optimizer over 50 epochs. (trainer.py)




Prediction
After training completed here is the result of test images (predictor.py)



f1.jpg Woman:99% Man:0%
f2.jpg Woman:99% Man:0%
f3.jpg Woman:99% Man:0%
f4.jpg Woman:99% Man:0%
f5.jpg Woman:99% Man:0%
f6.jpg Woman:100% Man:0%
m1.jpg Woman:43% Man:56%
m2.jpg Woman:0% Man:99%
m3.jpg Woman:0% Man:99%
m4.jpg Woman:28% Man:71%
m5.jpg Woman:2% Man:97%
m6.jpg Woman:99% Man:0%
m7.jpg Woman:0% Man:99%
m8.jpg Woman:0% Man:99%
m9.jpg Woman:0% Man:100%

A* Pathfinding Implementation With GO Web Assembly

I recently completed an "A* Pathfinding Alghoritm" project to get some web assembly and GO skills.

Source Code:
https://github.com/diwsi/A-Pathfinding-Implementation-With-GO-Web-Assembly


To Run Online:
https://diwsi.github.io/index.html

H-Break

Here is my android game that I made for fun. I used Unity3D for development.

https://play.google.com/store/apps/details?id=com.diwsi.hbreak

Genetic Algorithm vs Travelling Salesman Problem

 Download demo source code HERE.

Travelling salesman problem (TSP) a NP-hard problem. A salesman must visit a certain number of cities only for once and return to start position. What is the shortest route? It is a popular problem on mathematical optimisations and computer science. Genetic algorithm is a metaheuristic method to resolve problems that inspired by biological evolution process. I tried to resolve TSP by genetic algorithm. I used pure javascript and html. Here its steps and how I applied them to the TSP.

1.Initialization
First, we need to create population. Each individual of the population is random route. To mimic biological processes, each individual must have a gene. Chromosome base on solution of problem and on TSP situation a gene is an array of city list.

2.Selection

Nature has an elimination system called 'Natural Selection'. Stronger members of the population survive and breed. Genetic algorithm uses a function called 'Fitness Function' to find out strongest individuals. The fitness function is not a generic function. It is determined by the developer based on the problem. In TSP case my fitness function measures the length of the route. Individuals with lower length route are stronger. I select top individuals, keep and breed them and replace with weaker ones. 

Here is my fitness function.

3.Genetic Operations
Chromosomal crossover is an exchange of genetic material. Nature creates better genes by using stronger parts of two different chromosomes.

 In the genetic algorithm approach I sorted population by fitness (length of the route) and apply crossover to create shorter route:

1. Select a pair of solution (route). Each solution is an index  array of city points.
   Mate 1:
   
   Mate 2: 
   
2.  Select a random point and slice Mate 1:
   
3. Fill rest of the sliced Mate 1 array by using Mate 2:
   
4. Here is the new solution (child):
   

New children populeted this way probably will have better finess result.

4.Mutation
Some mutations create crippled creatures, but some mutations are next jump in evaluation tree. Mutation adds dynamism to the population and breaks, repeating crossover loops. I added mutation if genes in pair of solution are same. Just swapped two random indices.

Mutates to

The working implemantation is down below. Also here is he github page.

Point Count:

Population Count:

---

3D Procedural Dungeon Generation

 Download demo project HERE.

I am working on a hobby project which is an Unity 3D game. I needed to crate 3D procedural map and stumbled upon this post. I decided to implement my own solution based on that approach. First created some module prefabs with an input and multiple outputs. (Yeah they are just boxes. Replace them with your fancy models.)

Here is the script of module prefab:

using System.Collections.Generic;
using System.Linq;
using UnityEngine;

namespace Assets.Scripts
{
    public class Module : MonoBehaviour
    {

        System.Random rnd;
        public GameObject[] Outputs;
        public List<GameObject> AvailableOutputs { get; set; }
     
        public GameObject GetOutput()
        {
            //Get an output and seal
            var op = AvailableOutputs.ElementAt(rnd.Next(AvailableOutputs.Count));            
            AvailableOutputs.Remove(op);
            return op;

        }


        public void Init(int seed)
        {
            rnd = new System.Random(seed);
            AvailableOutputs = Outputs.ToList();
        }

    }
}

These are my test modules:

In dungeon generator script I followed this steps:

1. Select random module
2. Place selected module on some random free output transform position
3. Rotate selected module by using output objects local transform vector.
4. Check if there is any overlap problem. If current module overlaps destroy it and try an other random module on same output.

Dungeon creator script:

using System.Collections.Generic;
using System.Linq;
using UnityEngine;

namespace Assets.Scripts
{
    public class WorldBuilder : MonoBehaviour
    {
        public GameObject[] Modules;        
        public int Iterations;
        /// <summary>
        /// Random seed for debugging. 
        /// </summary>
        public int Seed;    
        System.Random rnd;

        List<GameObject> createdModules, availableModules;
        void Start()
        {
            rnd = new System.Random(Seed);
            
            BuildWorld();
        }

        void BuildWorld()
        {

            createdModules = new List<GameObject>();            
            var initialModule = GameObject.Instantiate(Modules.ElementAt(rnd.Next(Modules.Count())));
            initialModule.GetComponent<Module>().Init(Seed);            
            createdModules.Add(initialModule);
            availableModules = createdModules;

            for (int i = 0; i < Iterations; i++)
            {
                var module = availableModules.ElementAt(rnd.Next(availableModules.Count));
                var targetPoint = module.GetComponent<Module>().GetOutput();

                //Shuffle and try every blocks to fit 
                var shuffledBlocks = Modules.OrderBy(d => rnd.Next()).ToArray();
                foreach (var sBlock in shuffledBlocks)
                {
                    var candidate = GameObject.Instantiate(sBlock);  
                    candidate.GetComponent<Module>().Init(Seed);
                    candidate.gameObject.transform.position = targetPoint.transform.position;
                    candidate.transform.LookAt(targetPoint.transform.position + targetPoint.transform.forward);


                    //Check if there is an any overlapping
                    var bound = candidate.GetComponent<BoxCollider>().bounds;
                    var isSafe = true;
                    foreach (var item in createdModules)
                    {
                        if (bound.Intersects(item.GetComponent<BoxCollider>().bounds))
                        {
                            //Try another module
                            GameObject.Destroy(candidate);
                            isSafe = false;
                            break;
                        }
                    }

                    if (isSafe)
                    {
                        //Module connected safely
                        createdModules.Add(candidate);
                        break;
                    }
                }

                availableModules = createdModules.Where(d => d.GetComponent<Module>().AvailableOutputs.Any()).ToList();
                if (!availableModules.Any())
                {
                    //No availabel output on any modules. Stop the proccess
                    break;
                }
            }

            foreach (var item in createdModules)
            {
            
                //Disable overlap test colliders
                item.GetComponent<BoxCollider>().enabled = false;
            }

        }
                
    }


}

Results in different steps:

And here how it works in my game:

 Download demo project HERE.

Building An Artifical Neurol Network With .Net and C#

 Download demo source code HERE.

Terminator, matrix, i robot were all great movies because artifical intelligance is so cool concept. That's why humanity working hard to build a real skynet. Artifical neurol networks is a step forward  on this purpose. It is a mathematical model of biological neurol networks. Unlike many humans, they can learn by experiance. Neurol network models can be trained by samples. A network is made of following structures.

1. Input neurons: An input data for nerurol network to think about it.
2. Neuron: A math function  node that calculates inputs and genrates an output for other neurons. Output value is always must be a decimal between 0 and 1. Thats why functions like logistic or softmax usally prefered. Name of function that choosen for nerurons called "Activation Function". 
3. Hidden layers: Contains neurons that process input data. Mathematical magic happens here.
4. Weights: Connections between neurons. They are just simple decimal numbers that sets characteristics of neurol network.
5. Bias:  Some  value between 0 to 1 that added to neurons output. That prevents 0 valued outputs from neurons and keep neurons alive. Most boring thing in neurol networks.
6. Output neurons: Final output and conclusion of your network.

Here is a visual represantation of ANN:

 

Artificial neural network is an application of mathematics so MATH IS THE MOST IMPORTANT PART! Let's take look at it step by step using graphic above. For each neuron in the hidden layers and output layer calculate output signals by following formula:

K is logistic sigmoid activation function of our neurons

g_i is a vector of  other connected neuron outputs and w_i is vector of weight connections. Output signal function for each neuron is:

Every input data must be normalized to floating point between 0 to 1. That will also generate every neural  signal in  range of 0 to 1. This is the scaling equalization for input data:

  Here is an example of output signal calculation for a neuron called N1:

Output signal for N1=K(g1*w1+g2*w2+g3*w3)

Another example for output neuron called O1:

Output signal for O1=K(N1*w1+N2*2w+N3*w3+N4*w4)

We will get back to math later. That is enough for now. On this blog I will try to build an artificial neural network with .net and c#  because there are enough python examples already. Also, I will try to do it on object oriented approach. It is simple to write it just using matrix calculations but I think this way is more easy to understand and maintain. Here is my object structure:

 Layer class is a collection of neurons.

 public class Layer
        {
            public Neuron[] Neurons { get; set; }
        }

Here is neuron class. We will breakdown all the details later.

public enum NeuronTypes
    {
        Input,
        Hidden,
        Output
    }

    public class Neuron
    {
        public List<Synapse> Inputs { get; set; }
        public List<Synapse> Outputs { get; set; }
        public double Output { get; set; }
        public double TargetOutput { get; set; }
        public double Delta { get; set; }
        public double Bias { get; set; }
        int? maxInput { get; set; }
        public NeuronTypes NeuronType { get; set; }

        public Neuron(NeuronTypes neuronType, int? maxInput)
        {
            this.NeuronType = neuronType;
            this.maxInput = maxInput;
            this.Inputs = new List<Synapse>();
            this.Outputs = new List<Synapse>();
        }

        public bool AcceptConnection
        {
            get
            {
                return !(NeuronType == NeuronTypes.Hidden && maxInput.HasValue && Inputs.Count > maxInput);

            }
        }

        public double InputSignal
        {
            get
            {
                return Inputs.Sum(d => d.Weight * (d.Source.Output + Bias));
            }
        }

        public double BackwardSignal()
        {
            if (Outputs.Any())
            {
                Delta = Outputs.Sum(d => d.Target.Delta * d.Weight) * activatePrime(Output);
            }
            else
            {
                Delta = (Output - TargetOutput) * activatePrime(Output);
            }

            return Delta + Bias;
        }

        public void AdjustWeights(double learnRate, double momentum)
        {
            if (Inputs.Any())
            {
                foreach (var synp in Inputs)
                {

                    var adjustDelta = Delta * synp.Source.Output;
                    synp.Weight -= learnRate * adjustDelta + synp.PreDelta * momentum;
                    synp.PreDelta = adjustDelta;

                }
            }
        }

        public double ForwardSignal()
        {
            Output = activate(InputSignal);
            return Output;
        }

        double activatePrime(double x)
        {
            return x * (1 - x);
        }

        double activate(double x)
        {
            return 1 / (1 + Math.Pow(Math.E, -x));
        }
    }

Synapse class for connections between neurons.

public class Synapse
    {
        public double Weight { get; set; }
        public Neuron Target { get; set; }
        public Neuron Source { get; set; }
        public double PreDelta { get; set; }
        public double Gradient { get; set; }
        public Synapse(double weight, Neuron target, Neuron source)
        {
            Weight = weight;
            Target = target;
            Source = source;
        }

    }

And the NeuralNetwork class, the maestro that pulls them together.

public class NeuralNetwork
    {
        public double LearnRate = .5;
        public double Momentum = .3;
        public List<Layer> Layers { get; private set; }
        int? maxNeuronConnection;
        public int? Seed { get; set; }
        public NeuralNetwork(int inputs, int[] hiddenLayers, int outputs, int? maxNeuronConnection = null, int? seed = null)
        {
            this.Seed = seed;
            this.maxNeuronConnection = maxNeuronConnection;
            this.Layers = new List<Layer>();
            buildLayer(inputs, NeuronTypes.Input);
            for (int i = 0; i < hiddenLayers.Length; i++)
            {
                buildLayer(hiddenLayers[i], NeuronTypes.Hidden);
            }
            buildLayer(outputs, NeuronTypes.Output);
            InitSnypes();

        }

        void buildLayer(int nodeSize, NeuronTypes neuronType)
        {
            var layer = new Layer();
            var nodeBuilder = new List<Neuron>();
            for (int i = 0; i < nodeSize; i++)
            {
                nodeBuilder.Add(new Neuron(neuronType, maxNeuronConnection));
            }
            layer.Neurons = nodeBuilder.ToArray();
            Layers.Add(layer);
        }

        private void InitSnypes()
        {
            var rnd = Seed.HasValue ? new Random(Seed.Value) : new Random();

            for (int i = 0; i < Layers.Count - 1; i++)
            {
                var layer = Layers[i];
                var nextLayer = Layers[i + 1];
                foreach (var node in layer.Neurons)
                {
                    node.Bias = 0.1 * rnd.NextDouble();
                    foreach (var nNode in nextLayer.Neurons)
                    {
                        if (!nNode.AcceptConnection) continue;
                        var snypse = new Synapse(rnd.NextDouble(), nNode, node);
                        node.Outputs.Add(snypse);
                        nNode.Inputs.Add(snypse);
                    }
                }
            }

        }

        public double GlobalError
        {
            get
            {
                return Math.Round(Layers.Last().Neurons.Sum(d => Math.Pow(d.TargetOutput - d.Output, 2) / 2), 4);
            }
        }

        public void BackPropagation()
        {
            for (int i = Layers.Count - 1; i > 0; i--)
            {
                var layer = Layers[i];
                foreach (var node in layer.Neurons)
                {
                    node.BackwardSignal();
                }
            }
            for (int i = Layers.Count - 1; i >= 1; i--)
            {
                var layer = Layers[i];
                foreach (var node in layer.Neurons)
                {
                    node.AdjustWeights(LearnRate, Momentum);
                }
            }
        }

        public double[] Train(double[] _input, double[] _outputs)
        {
            if (_outputs.Count() != Layers.Last().Neurons.Count() || _input.Any(d => d < 0 || d > 1) || _outputs.Any(d => d < 0 || d > 1))
                throw new ArgumentException();

            var outputs = Layers.Last().Neurons;
            for (int i = 0; i < _outputs.Length; i++)
            {
                outputs[i].TargetOutput = _outputs[i];
            }

            var result = FeedForward(_input);

            BackPropagation();
            return result;
        }

        public double[] FeedForward(double[] _input)
        {
            if (_input.Count() != Layers.First().Neurons.Count())
                throw new ArgumentException();


            var InputLayer = Layers.First().Neurons;
            for (int i = 0; i < _input.Length; i++)
            {
                InputLayer[i].Output = _input[i];
            }

            for (int i = 1; i < Layers.Count; i++)
            {
                var layer = Layers[i];
                foreach (var node in layer.Neurons)
                {
                    node.ForwardSignal();
                }
            }

            return Layers.Last().Neurons.Select(d => d.Output).ToArray();
        }
    }

Now lets take a look how this thing works. My simple goal is to give my network 2 inputs and expect average of them as output result. As I said before input data must be scaled to 0 to1 range. Of course I can simply calculate it like x=(a+b)/2. The point is a neural network can learn (almost) ANY function. It can LEARN any pattern. An ANN can be trained. For many cases this way is more effective than traditional methods. This approch works very well in vast area of applications like image recognition and processing, data classification, data prediction and of course artificial intelligence. Here is a console application sample:

class ANN
    {        
        static void Main(string[] args)
        {
            var network = new NeuralNetwork(2, new int[] { 4 }, 1);
            var inputData = new double[] { .3, .5 };
            var output = network.FeedForward(inputData);
            Console.Write("Inputs: {0} {1}  Output:{2} ", inputData[0], inputData[1],output[0]);
            Console.ReadLine();
        }
    }

 new NeuralNetwork(2, new int[] { 4 }, 1);  this means build neural network with 2 input neurons, 1 hidden layer with 4 neurons and 1 output neuron. .3 and .5 values sent towards network to generate an output signal by using FeedForward function. The result is:

Different values on every run:

What does it mean? We gave 0.3 and 0.5 as input data. Shouldn't we get 0.4 as an average of them? Yes computer science is modern sorcery but it is not that easy. We need to train our little ANN. We must teach what "average"  means by showing samples over and over again.  Before the learning part lets take a look at our artificial neural network deeper. What happened to data in ANN. On constructor method, layers built and neurons created in buildLayer. After that InitSnypes method created synapse connection layer by layer with some random value. That's why output result is different on each run. Every different structure generates a different output with same input. FeedForward calculates output signal using that connection values. What if there is an exact synapse connection build that generate average of my inputs as output. There are countless random combinations of these synapse weight values. How can we find the correct one? There is a mathe-magical spell to do this. It is called backpropagation. It is a common "supervised learning method" to train  ANN's. An application of "Machine (deep) Learning". After output signal generated, if desired output is known we can calculate an error value and adjust the neural connection weights by backpropogation technique. Next time error should be smaller and smaller. After enough training error value will be ignorable. Let's train! Here is a windows form example.

public partial class Form1 : Form
    {
        public NeuralNetwork network;
        public List<double[]> trainingData;
        Random rnd;
        int trainedTimes;
        public Form1()
        {
            InitializeComponent();

            //For debugging
            int Seed = 1923;

            // 2 input neurons 2 hidden layers with 3 and 2 neurons and 1 outpu neuron
            network = new NeuralNetwork(2, new int[] { 3, 3 }, 1, null, Seed);

            //Generate Random Training Data 
            trainingData = new List<double[]>();
            rnd = new Random(Seed);

            var trainingDataSize = 75;
            for (int i = 0; i < trainingDataSize; i++)
            {
                var input1 = Math.Round(rnd.NextDouble(), 2); //input 1
                var input2 = Math.Round(rnd.NextDouble(), 2); // input 2
                var output = (input1+input2)/2 ; // output as avarage of inputs
                trainingData.Add(new double[] { input1, input2, output });// Training data set                
                chart1.Series[0].Points.AddXY(i, output);                
            }            
        }

        public void Train(int times)
        {
            //Train network x0 times  
            for (int i = 0; i < times; i++)
            {
                //shuffle list for better training
                var  shuffledTrainingData = trainingData.OrderBy(d => rnd.Next()).ToList();               
                List<double> errors = new List<double>();
                foreach (var item in shuffledTrainingData)
                {
                    var inputs = new double[] { item[0], item[1] };
                    var output = new double[] { item[2] };

                    //Train current set
                    network.Train(inputs, output);

                    errors.Add(network.GlobalError);
                }                

            }
            chart1.Series[1].Points.Clear();
            for (int i = 0; i < trainingData.Count; i++)
            {
                var set = trainingData[i];

                chart1.Series[1].Points.AddXY(i, network.FeedForward(new double[] { set[0], set[1] })[0]);
            }
            trainedTimes += times;
            TrainCounterlbl.Text = string.Format("Trained {0} times", trainedTimes);
        }

        private void Trainx1_Click(object sender, EventArgs e)
        {
            Train(1);
        } 

        private void Trainx50_Click(object sender, EventArgs e)
        {
            Train(50);
        }

        private void Trainx500_Click(object sender, EventArgs e)
        {
            Train(500);
        }

        private void TestBtn_Click(object sender, EventArgs e)
        {
            var testData = new double[] { rnd.NextDouble(), rnd.NextDouble() };
            var result = network.FeedForward(testData)[0];
            MessageBox.Show(string.Format("Input 1:{0} {4} Input 2:{1} {4} Expected:{3}  Result:{2} {4}",
                format(testData[0]),
                format(testData[1]), 
                format(result),
                format((testData[0]+ testData[1])/2), 
                Environment.NewLine));
        }
        string format(double val)
        {
            return val.ToString("0.000");
        }
    }

Neural network has multiple hidden layers with 3 neurons each. 75 samples of random values generated at form constructor and stored in "trainingData".  Here is the output chart of  "trainingData".

When I press test data my untrained ANN thinks average of 0.316 and 0.339 is equals to 0.781

Press "Train X1" button to study every samples for one time and here is the result:

It is still too far from expected result. Yellow "ANN" line of chart is actual response of our network for each input set in the training data. They are all almost same ~0.5. We must train more but Let's take a look what happened when we hit train button. Train method of network applies backpropagation algorithm. First FeedForward function generates an output signal. BackPropagation method calculates error value by using expected output and actual signal output. Feeds these error values back to input neurons using derivative of activation functions. That process helps to find which weight connections are most responsible of the error. That method is called "Gradient Descent". Let's take a look at math of the process. Gradient descent method needs an error calculation function. Squared error function is most common:

For each synapse connected to output neuron, backward signal can be calculated with following formula:

Net backward error signal for previous neuron can be calculated with following partial derivative respect to a weight.

Now let's inspect calculation of each term. The last term is error signal output of through a synapse connection.

For output neuron next term is simply actual output - expected output . (Yes that is why there is a 1/2 )

For other neurons that calculation depends on derivative of activation function. 

After all backward signals calculated we need to adjust synapse weights for better results. α here is called momentum. It is an adjustment value for faster learning that represents previous value

In my code BackwardSignal  applies partial derivative chain:

public double BackwardSignal()
        {
            if (Outputs.Any())
            {
                Delta = Outputs.Sum(d => d.Target.Delta * d.Weight) * activatePrime(Output);
            }
            else
            {
                Delta = (Output - TargetOutput) * activatePrime(Output);
            }

            return Delta + Bias;
        }

Then adjustment of weights at

public void AdjustWeights(double learnRate, double momentum)
        {
            if (Inputs.Any())
            {
                foreach (var synp in Inputs)
                {

                    var adjustDelta = Delta * synp.Source.Output;
                    synp.Weight -= learnRate * adjustDelta + synp.PreDelta * momentum;
                    synp.PreDelta = adjustDelta;

                }
            }
        }

Back to demo application. Remember our application tries to find average of two input values. More we train better results we get. After training 50 times over artificial neural network, results begins to fit expected values.

100 training times later ANN fits far better.

15200 times later that thing knows what its doing.

 Download demo source code HERE.