Autodart

Autodart library introduced at dartwatch.

Advertisements

Sweet spot for buying a used Honda Civic!

Sweet spot for buying a used Honda Civic!

Sweet spot for buying a used Honda Civic! Buy 2009, sell in 2 years! Would depreciate only $30/month.

Hidden Markov Models, Bayesian Statistics, and Quantum Computing together can estimate inventories

In production systems, organisations that produce things, like mines, factories, refineries, etc. a whole system exists dubbed inventory. The inventory is a graph of materials and objects moving through the systems and changing face. For example, in a coal mine, dirt is digged out of pits in units called lots. The lot moves around the mine, gets merged, crushed, dried, and cleaned. The lot moves from the ground to trucks and process points, ports, railways, etc. where most likely it changes shape and characteristics. Same thing happens in manufacturing, chemicals, water procurements, and many other industries.

It is crucial and critical for the business to know their inventory at each stage. They usually have manual or automatic processes to measure characteristics of every part of the inventory. For example weightometers are fitted all over the system which generate data, and they may manually keep record of what happens on the ground. The data generated is almost always limited, of low quality and is not directly a reflection of the reality. In fact, computer science should come in and start filling the gaps, improve data quality and estimate inventories much better than the most skilled human can do by looking at the inventories and excel sheets. In this post I want to reflect on how three techniques, two from AI, and one from Quantum Computing can provide a set of tools to just do that.

Hidden Markov Models (HMM) are used to extract state machine in temporal data. For example, if we track Joe movements, the fact that Joe  usually gets out of the kitchen, go to the Mary’s desk for five minutes and come back to his own desk, is a Markov chain of states hidden in the data. In inventories HMM can be very well used to extract sate machines. I refer to this paper for a good tutorial on HMMs. In the inventory settings, HMMs can be used to extract movements of materials and objects and the change in their characteristics. For example coal goes to the process point A and becomes dry and the dry coal goes to the crusher and becomes grained, and then goes to another process points and becomes pure by loosing ash. Or again coal goes into a process point and ash comes out. Such MMs can be extracted by looking at the data.

Bayesian statistics is simply the implications of the Bayes theorem: P(A|B) = P(B|A)P(A)/P(B). In computer science a mixture of Bayesian statistics and HMM is used for improving data quality in time series (read a good paper here). It is mainly done by forming correlation tables. For example, Joe always goes from Mary’s office to his own, so the correlation of Joe location between Mary’s office and Joe’s office is high, but he never goes from Mary’s office to the Jack’s office, so the correlation of Joe’s location between Mary’s and Jack’s office is zero. Using this knowledge, if we are in doubt if Joe is currently in his own office or in Jack’s office, we can check to see where has he been before. If he has been in mary’s office beforehand, we can estimate that Joe is probably in his own office. In literature this is called probabilistic easing. The probabilistic easing, however, does not produce an exact value of the location and characteristics of objects, instead it creates a set of probable location with their probability. For example in a coal mine, we may estimate that the lot X is out of the crusher with 20% probability and it is merged with lot Y with 80% probability. This dramatically extends our knowledge of the inventory, however, it is probabilistic, which is ok, because life and reality are probabilistic.

Quantum mechanics may seem irrelevant to a coal mine. However, Quantum mechanics is extremely beautiful, and I love to find a use for some of the formulas and methods coming out of Quantum computing in unrelated fields. There is one specific method in Quantum computing that might be relevant to our settings. It can become very useful to improve our estimations for eased data generated from the previous steps.

The problem of the eased data is of course that it is probabilistic (its both curse and blessing). In reality, inventories get measured occasionally and this measurements infer valuable information that are ignored in the easing approaches. For example, the easing method reports a specific inventory of coal to be with 60% probability high in Ash. The engineers on the ground sample some of the coal in this inventory and send it to lab, and the result comes that the coal has exactly 20% ash. The easing approach uses this fact merely to improve the easing from this point forward. However, quantum algorithms tell us that this fact contains much more information.

In quantum mechanics there is a state which is called entanglement. Entanglement is a very unintuitive phenomenon but we know that it happens. It means once two atoms are entangled, their electron are in the same superpositions, no matter how far apart those atoms are from each other. By the way, superposition is nothing new in this post. Remember we said that easing method says that Joe is with 10% probability in Jack’s office and 90% probability in his own office, this is called super position in quantum mechanics. Just replace Joe with your favorite electron. Now that we figure out the similarity with eased state of inventory and quantum state of matter, we can utilize the work in quantum computing to improve our knowledge of the state of inventory.

In quantum computing, once entangled atoms pass through quantum gates, their state changes, and we can compute their superpositions, which is something similar to Bayesian easing. However, in quantum computing, once we measure the sate of one of the atoms, we break the engagement, and the atom collapses to the new state which we measured. This is very similar to when we send the coal samples to lab and realize the exact state of our coal. In fact, the eased probabilistic state collapses to one value that has come out of lab. In quantum computing however, we use this data to calculate new superposition for all other atoms. For example, if the measurement of the output of the first quantum gate comes out as 001, we know that other gates can not be in an state which is inconsistent with the first gate being in 001. We can re-estimate the superposition of other atoms with some linear algebra. We can do exactly the same in inventory. For example, we can apply this new knowledge to back track and re-estimate the eased sate of all other bits of coal in the system but limit easing only to states that are consistent with the new knowledge out of lab.

This may sound a bit superficial and hard to implement, but remember that the Bayesian easing based on HMM is not my invention and people have been using it successfully. Adding the quantum flavour is not hard even because it is also implemented and used by many others in the computer science field. I don’t see a feasibility problem here. There might be a marketing problem but if you are interesting in implementing above, and you are research student, feel free to drop me an email.

Cost of war in Electric Cars unit

Cost of Iraq and Afghanistan war in about a decade? $1.4E12

Cost of an average electric car today? $4E4

Considering 50% discount reduction when ordered in tens of millions!

Cost of war ~ 70M electric cars. (Half of the U.S. fleet)

Note: 98% of oil is burned in vehicles.

 

Conclusion:

If the money spent on war was spent on electric cars, U.S. would be independent from oil import.

Electric cars would have been affordable already. Therefore, rest of the world would reduce oil consumption.

Therefore, funding for terrorist would have gone. Saudi arabia, Iran, Qatar, etc. wouldn’t have enough surplus to fund terrorism.

And world would have been a much nicer place to live.

Cofee shop closing down.

Based on a recent law, every cofee shop operating in Tehran has to install cameras monitored by government. These emotional photos depict the last day at Cafe Perague, which did not accept to install cameras and had to close down.

Algorithm to find two repeated numbers in an array, without sorting

I saw this question in Stack Overflow which I found interesting.

This is the link to the actual question on StackOverflow.com.

There is an array of size n (numbers are between 0 and n – 3) and only 2 numbers are repeated. Elements are placed randomly in the array.

E.g. in {2, 3, 6, 1, 5, 4, 0, 3, 5} n=9, and repeated numbers are 3 and 5.

What is the best way to find the repeated numbers? Space complexity should not be more than O(1) and time complexity should not exceed O(n). Note thatn O(1) means constant amount of memory where memory consumption is not relative to the size of n and O(n) means you can look into the array only a constant number of times.

HINT: Sorting, or using a hash table is not the answer.

One solution is to sum the numbers and also sum the squares then solve the problem by solving the following math equation: A+B=cte and A^2+B^2=anotherCte.

I would suggest a different solution:

As the numbers are integers, they have constant bit size (i.e. 32). Let us assume we are working with 4 bit integers right now. We look for A and B which are the duplicate numbers.

We need 4 buckets, each for one bit. Each bucket contains numbers which its specific bit is 1. For example bucket 1 gets 2, 3, 4, 7, …:

Bucket 0 : Sum ( x where: x & 2 power 0 == 0 )
...
Bucket i : Sum ( x where: x & 2 power i == 0 )

We know what would be the sum of each bucket if there was no duplicate. I consider this as prior knowledge.
Once above buckets are generated, a bunch of them would have values more than expected. By constructing the number from buckets we will have (A OR B for your information).

We can calculate (A XOR B) as follows:

A XOR B = Array[i] XOR Array[i-1] XOR … 0, XOR n-3 XOR n-2 … XOR 0
Now going back to buckets, we know exactly which buckets have both our numbers and which ones have only one (from the XOR bit).

For the buckets that have only one number we can extract the number num = (sum – expected sum of bucket). However, we should be good only if we can find one of the duplicate numbers so if we have at least one bit in A XOR B, we’ve got the answer.

But what if A XOR B is zero? Well this case is only possible if both duplicate numbers are the same number, which then our number is the answer of A OR B.

Example:

Given array of numbers:

0, 1, 2, 3, 4, 5, 2, 3

Let’s write them in Binary format:

 0 => 0 0 0
 1 => 0 0 1
 2 => 0 1 0
 3 => 0 1 1
 4 => 1 0 0
 5 => 1 0 1
 2 => 0 1 0
 3 => 0 1 1

Let us calculate the XOR (^) first: (number xor index)

0^0 ^ 1^1 ^ 2^2 ^ 3^3 ^ 4^4 ^ 2 ^ 3 => 0 0 1

Then we create 3 bit buckets by summing all number where bucket bit is 1:

Expected bucket values:
 B3(2) B2(5) B1(9)
Actual bucket values:
 B3(2) B2(10) B1(12)

From the buckets we can say A|B = 0 1 1 which is correct 0 1 0 | 0 1 1 = 0 1 1.
Using the result of XOR, we know that bucket B1 contains only one of the extra numbers. This is because when A|B is 1, and A^B=1, then one of the numbers should be 0 and the other should be 1.
So we can calculate one number : 12 – 9 = 3. The other number is 10-3-5 = 2.

WordPress reminded me of Iran today

I opened the wordpress home page this morning and suddenly I felt like I am using internet in Iran. No image was visible and all the images were censored.

This might be a weird concept for you but it is the most common internet page for Iranians. Iranian regime blocks inappropriate material, and you know how governments work, level of inappropriateness grows throughout the time and once a black censored box appeared in your browser, it would be just a matter of time for them to fill up your screen.

Please protest against SOPA http://sopastrike.com/strike. Even if you are not American you will be affected with american government’s decision on internet, so let our voice be heard.

To realize how dangerous this bill is, please check this good article.