Monthly Archives: February 2016

Constructing matrix in TI Nspire for Markov chain with Poisson distribution

In calculation for Markov chain, matrix setup can be complicated evn with the user-friendly interface on the TI Nspire. The built-in function like identity(), constructMat() etc are useful on specific cases.

For Markov chain calculation, the model setup in terms of matrix sometimes get quite complicated and demanded a few exceptions from the built-in function mentioned above that are geared towards common linear algebra.

The example below attempts to simply the construction of the Markov model by use of piece-wise functions in building matrix. The problem to solve in Markov process is on a stock resupply problem, where an imaginary shop keeps stock of 1 to 3, and replenish on each day only when all stock is exhausted. Poisson distribution is assumed on the demand side.

Firstly a function called markov_prob is created, which takes the demand as variable and return the corresponding Poisson distribution. Note that how the function handle probability for demand greater than 3. A short-hand function mkp() is created afterwards to ease reading in the matrix.
markovstock1

When the function is defined, the Markov model can be formulated in a new 3 x 3 matrix created using the template. It is sometimes not easy to define state transition function as in this example problem. Therefore, the shorthand function just created will help in filling in the states as matrix elements. For example, P11 means the stock next day (Sx+1) equals stock today (Sx) which is 1, and that means the demand is zero, and thus mkp(0). There are some curve ball like P12, where Sx+1 > Sx which is not possible, since that means the shop has more stock the next day for any day with non-zero stock (i.e. negative demand), and thus the probability is zero.markovstock2

After setting up the Markov model, the equilibrium distribution can be deduced. The below is one of the methods using Nelder-Mead algorithm.
markovstock3

Based on this model, more figures can be deduced for decision making on fine tuning stock keeping strategy.

Analysis of traffic CCTV camera image from data.gov.hk with GPU deep learning on Amazon cloud

In this installment, modern computing technology including Internet, artificial intelligence, deep learning, GPU, and cloud technology are utilized to solve practical problem.

Traffic jam is very common in metropolitan cities. Authorities responsible for road traffic management often install CCTV for monitoring. Data available at data.gov.hk site published on the Internet for big data analysis is one such example. The followings are two sample images from the same camera with one showing heavy traffic and the other one with very light traffic.

Modern pattern recognition technology is a piece of cake to determine these two distinct conditions from reading images above. The frontier in this field is no doubt utilizing deep learning network in GPU processor. Amazon AWS provided GPU equipped computing resources for such task.

The first step is to fire up an GPU instance on Amazon AWS. The following AMI is selected. Note that HVM is required for GPU VM.
awsgpu1

The next step is to choose a GPU instance. As the problem is simple enough only g2.2xlarge is used.
awsgpu2

After logging in to the terminal, set up CUDA 7, cuDNN, caffe, and DIGITS. The steps can be referred from their respective official documentations. A device query test below confirmed successful installation of CUDA. The whole process may took an hour to complete if installed from scratch. There may be pre-built images out there.
awsgpu4

Note that an account from NVIDIA Accelerated Computing Developer Program may be required to download some of these packages. A make test below confirmed complete setup of caffe.awsgpu5

Finally, after installing DIGITS, the login page is default to port 5000. At AWS console network connection rule can easily be setup to open this port. Alternatively, for more secure connections, tunneling can be used instead, as shown below running at 8500.awsgpu6

Now it is time to start training. A new image classification dataset is to be created. As stated above the source image set is obtained from data.gov.hk. At this site, traffic cameras installed over strategic road network point feed JPG image on the web for public access. The images are refreshed every 2 minutes. A simple shell script is prepared to fetch the image to build the data set. Below is the screen where DIGITS configures the classification training.
awsgpu8

Since our sample data set size is small, the training completed in no time.
awsgpu9

awsgpu10

Next, a model is defined. GoogLeNet is selected in this example.
awsgpu12awsgpu13

Model training in progress. The charts update in real time.
awsgpu17

awsgpu15awsgpuB

When the model is completed, some tests can be carried out. In this example, the model is trained to determine whether the camera image taken indicates traffic jam or not.

A traffic jam sample. Prediction: free=-64.23%, jam=89.32%
awsgpuC

The opposite. Prediction: free=116.62%, jam=-133.61%
awsgpuE

With Amazon cloud, the ability to deploy cutting edge AI technology in GPU is no longer limited to researchers or those rich in resources. General public can now benefit from these easy to access computing resources to explore limitless possibilities in the era of big data.

Using Nelder-Mead to solve for Markov chain stationary distribution

Taking the same problem from previous installments, another approach using the Nelder-Mead algorithm is tried and successfully obtained the same answer. After formulating the equation for passing to the Nelder-Mead program in TI Nspire, which required the same algebraic manipulation as in the previous linsolve() approach, another more intuitive formula is tried. The second one directly calculates matrix in the minimization equation and therefore render the algebraic manipulation unnecessary.

The first setting is as below.
markov_stationarydist_NM1

While the second setting that directly calculates on the matrix is shown below.
markov_stationarydist_NM2

TI Nspire shortcuts for finding Markov chain stationary distribution

In previous installment, the stationary distribution of Markov chain is determined in TI Nspire using built-in linSolve function. Apart from the implementation used, there are some shortcuts in TI Nspire that will arrive the same result. The first one is kind of a one-liner that distill all steps for solving for the stationary distribution, which can easily be programmed in Nspire using TI-Basic, is exemplified below in self-explanatory notes:
markov_stationarydist_quick1

The full one-liner in TI Nspire is as below:

simult(colAugment((subMat(p,1,1,rowDim(p),rowDim(p)-1))T,augment(list>mat(seqn(1,rowDim(p)-1)),[2]))-identity(rowdim(p)),colAugment(newMat(rowDim(p)-1,1),[1]))

markov_stationarydist_quick2

The other one is based on the fact the stationary distribution converges itself after repeated multiplication. This is tedious before the advent of modern computation power, but a piece of cake today even with hand-held calculators 🙂

markov_stationarydist_quick3

Finding stationary distribution in Markov chain with TI Nspire

For Markov chain calculation with a transition matrix P:
markov_stationarydist1

attempt to find the stationary distribution using TI Nspire solve function apparently is not appropriate:
markov_stationarydist2

But no worry, the question can be solved using the linsolve function because this problem can be broken down into a series of linear equations by the properties of stationary distribution of Markov chain. In TI Nspire, a pop-up menu style wizard will guide through the linear solver:
markov_stationarydist3

When finished setting up the template, the equations can be entered directly in the Calculator screen.markov_stationarydist4

A shortcut to this in the TI Nspire can be referenced here as a one-liner making use of matrices operations.

Regression plotting and r-squared in TI Nspire

An experiment by Galileo in 1609 shown a parabola for an object falling with horizontal motion. In TI Nspire, graphing the scatter plot is done by using the “Data and Statistics” page, and then clicking on the X and Y caption for respective data dimension.

Adding regression line is also easy by selecting the Analyze > Regression menu and then apply the regression model.
galileoreg2

The regression line will then be plotted against the scatter plot.
galileoreg3

To decide which one fits better, the R2 can be deduced by running the Quadratic Regression and Cubic Regression in the List and Spreadsheet page.

galileoreg1

Observations on effect of initial parameter of Nelder-Mead to solve linear problem

Out of curiosity a test program is created to iterate the initial parameters for the Nelder-Mead program in TI Nspire to see if there is any effects or patterns to the outcome of the algorithm. The Nelder-Mead program is to solve the following inequalities:

nmsimplexparmest1

The test case will iterate test variables x and y from 1 to 10, resulting in 100 tests. Absolute error value of the Nelder-Mead program result to the known optimal value (33) is plotted in the below chart.

nmsimplexparmest2

nmsimplexparmest3