Fortunately, Kolmogorov complexity approximately equals Shannon entropy H, if the sequence is chosen at random from a distribution having the entropy H. We consider Kolmogorov complexity to be more fundamental than Shannon entropy. It is the limit of data compression and leads us to a logical consistent inference procedure.

A pleasant complementary relationship between algorithmic complexity and computational complexity exists here. We can see computational complexity (time complexity) and Kolmogorov complexity (the length of the program or descriptive complexity) as two axes corresponding to the running time of the program and the length of the program. Kolmogorov complexity focuses on minimizing along the second axis and computational complexity focuses on minimizing along the first axis. Few attempts have been made to minimize simultaneous along both axes.

Physics (thermodynamics). Statistical mechanics is the place of birth for entropy and the second law of thermodynamics. Entropy always grows.

Mathematics (Theory of probability and statistics). Fundamental measures of information theory – relative entropy and mutual information – describe the behavior of long sequences of random variables and allow us to estimate the probability of rare events and to find the best error estimator in hypothesis testing.

Philosophy of Science (Occam Razor). William of Occam said: “Causes shall not be multiplied beyond necessity” or, paraphrasing him, “The simplest explanation is the best”. Solomonoff, and later Chaitin, stated that we can obtain a universal good prediction procedure if we take a weighted combination of all the programs that explains the data and still look at what they print afterwards. Furthermore, this inference procedure will work in many problems that cannot be solved by statistics. When it is applied on stock market is has to find stock market rules and to extrapolate them optimally. Basically, such a procedure would have found Newton law in physics. Certainly, such inference is not applicable, because eliminating all the programs that do not manage to generate the data takes too much time.

Economy. Repeating investments in a stationary market leads to an exponential growth of welfare. Welfare growing rate is dual to the market entropy. There is an obvious link between the theory of optimal investment in stock market and information theory. To explore this duality, a theory of investments can be developed.

Computation versus Communication: As we build bigger and bigger computers made by smaller and smaller components we reach both a computing limit and a communication limit. Computing is limited by communication and communication is limited by computing. These become interdependent and, therefore, all the developments in communication theory based on information theory should have a direct impact on computation theory.

References:

1. http://finereader.abbyy.com/
2. Banciu, D., e-Romania – A Citizens’ Gateway towards Public Information, Journal of Studies In Informatics and Control, Vol. 18, No. 3, 2009.
3. Cover, T. M., T. A. Joy, Elements of Information Theory, John Wiley & Sons Interscience Publication, 1991.
4. Forman, G., A Pitfall and Solution in Multi-Class Feature Selection for Text Classification, Proceedings of the 21st International Conference on Machine Learning, Banff, Canada, 2004.
5. Guerra-Salcedo, C., S. Chen, D. Whitley, S. Smith, Fast and Accurate Feature Selection Using Hybrid Genetic Strategies, CEC00, Proc. of the Congress on Evolutionary Computation, CEC00, July 2000.
6. http://alice.ulbsibiu.ro:8080/scribe/
7. Sifaoui, A., A. Abdelkrim, S. Alouane, M. Benrejeb, On New RBF Neural Network Construction Algorithm for Classification, Journal of Studies In Informatics and Control, Vol. 18, No. 2, 2009.