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.

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.

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 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 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.

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

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.

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 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.

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


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

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


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%

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

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.

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

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:

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



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 🙂


Finding stationary distribution in Markov chain with TI Nspire

For Markov chain calculation with a transition matrix P:

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

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:

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.

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

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.


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:


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.



Solving linear programming problem with Nelder-Mead method

For solving linear programming problem, the simplex method is often applied to search for solution. On the other hand, the Nelder-Mead method is mostly applied as a non-linear searching technique. It would be interesting to see how well it is applied to a linear programming problem previously solved using the Simple Method in TI-84.

The Nelder-Mead method is ran under the TI Nspire CX CAS with NM program written in the TI Basic program. The program accepts arguments including the name of the function to maximize as a string and a list of initial parameters to execute the Nelder-Mead algorithm. The function itself is declared using piece-wise function to bound the return value to the function to maximize while giving penalty to values that violate any constraints (as in the inequalities of the standard simplex method).

Previous program in the TI-84 using the simplex method obtained {200,400} as the solution. The Nelder-Mead returned a solution very close to it.


TI Nspire CX program to generate initial tableau for Simplex Algorithm

The simplex algorithm can be easily performed in TI Nspire CX and also in the TI-84 series. A program is created to provide an intuitive means to construct the initial tableau.

The function prototype takes two arguments, one for a list of expression consisting the constraint inequalities plus the function to maximize (assumed to be the last in the list), and another argument to specify the number of variables. The variables in the inequalities must be named as x[n] where n is a number starting from one.


Example of the usage of this program showing how the inequalities are set up.simplextableau1a

The program makes use of some string functions, the expr and polyCoeffs functions and also indirection to extract the coefficients in the inequalities and to build the initial tableau matrix.


Graphical representation of the example above.