Viewing programming as constraint satisfaction

Programming could be viewed as solving a constraint satisfaction problem. We start with some empty disk space and the goal is have a program there. Only the goal state is important. We are not searching for a path. We are searching for a goal state that meets the constraints.

I could view my programming as an attempt to solve the problem efficiently. Modifying existing source code is like a mutation in a local search. Hitting an unexpected constraint and choosing a different path is like backtracking. And rewriting allows me to get rid of old constraints.

A super intelligent machine may laugh. It will see the inefficiency of my primitive attempts. I would seem like a 19 month old baby.

Ulimited "cd -" history

I use bash and I use "cd -" to go to the previous directory. To be able to go back more than one step, I had to replace the original cd command with a function:

# cd with automatic pushd
function cd() {
    if test "x$1" = "x-" ; then
        popd >/dev/null
    else
        pushd . >/dev/null
        builtin cd "$@"
    fi
}

Put that into your ~/.bashrc and start a new bash.

Example usage

/home$ cd /opt
/opt$ cd /var/log
/var/log$ cd -
/opt$ cd -
/home$

Learning from history

It is amazing to see that learning from historical data is theoretically solved. For example, we could calculate the probability that all crows are black when N black crows were seen previously:

P(all_crows_are_black|seen_N_black_crows)
    = P(seen_N_black_crows|all_crows_are_black) * P(all_crows_are_black)
      * 1/P(seen_N_black_crows)
    = 1 * P(all_crows_are_black) * 1/P(seen_N_black_crows)

A different model could predict that 90% of crows are black. Its probability after seeing N black crows would be:

P(90%_of_crows_are_black|seen_N_black_crows)
    = 0.9**N * P(90%_of_crows_are_black) * 1/P(seen_N_black_crows)

The 1/P(seen_N_black_crows) constant is not known. We could interpret it as a normalization constant. It ensures that the sum of probabilities of all possible models is 1. Or we could ignore it if just comparing the probabilities of different models.

Many models could have non-zero probability when given a small history. We should use them all when making a prediction. A prediction is just the probability of unseen data based on the seen data. That is calculated by:

P(data|old_data) 
    = sum(P(data|h,old_data) * P(h|old_data) for h in ALL_MODELS)

This approach is completely general. It could be used for non-independent samples, time series, everything. We would then work with models that predict such non-independent data or time series.

Additional Resources

• AI: A Modern Approach chapters 13, 14 and 20 give an introduction to probabilities and Bayesian learning.
• On Universal Prediction and Bayesian Confirmation by Marcus Hutter. It hints how to estimate the P(model|no_data_yet) probabilities. Simpler models are preferred.

Many layers are needed

I have read an interesting paper on limitations of machine learning models: Scaling Learning Algorithms towards AI. It mentions limitation of two-layer neural networks and other two-layer models (SVMs). These shallow models are unable to learn some functions without an exponential number of components. For example, to learn the parity function over N input bits, they would need 2^N hidden neurons.

On the other hand, a deep model with N layers could compute the parity with just N components.

Humane utility function

It will be hard to design a utility function for a strong AI. The utility function should express what the AI should maximize. Humans still cannot decide what weight to assign to lives. Especially if you have to decide between lives and the restoration of order in a society.

AI for real life: Understanding autonomy

There are talks about autonomy and other forms of motivations. But I realized the meaning of autonomy only after reading about it in an AI book.

Let's first define how we want an agent or an employee to behave. We want him to try his best to maximize our score assigned to him. When doing "his best", he can only use his prior knowledge or his senses. We should not blame a deaf person for not running in reaction to the sound "fire". We should also not blame a person without the prior knowledge of the English word "fire". They are acting rationally under the given conditions.

And autonomy is the ability to enhance or correct the prior knowledge. An autonomous agent does not need to follow the rules defined in the prior knowledge. He could override them if it makes sense to him. For example, he does not have to run immediately after hearing "fire". He can grab the deaf person's hand first.

Solving Problems by Searching

If you are new to AI, you will want to read this sample chapter: Solving Problems by Searching.
It explains the breadth-first search, A*, heuristic estimates, ...

It is from the newly updated AI: A Modern Approach 3rd Edition.