mns2012 (mns2012) wrote in biosemiotics,
mns2012
mns2012
biosemiotics

Закон сохранения информации

Компьютер не создаёт новой информации,
он лишь осуществляет полезную трасформацию уже имеющейся информации.

Леон Бриллюэн, Science and Information Theory, 1956.


Что такое информация и почему она в среднем не возрастает натуралистически (то есть за счёт комбинированного действия случайных и закономерных факторов)?

1. Неформальное введение: Eric Holloway: Why is Bell's theorem important for conservation of information?

2. William Dembski, Robert Marks: Conservation of Information in Search: Measuring the Cost of Success, IEEE Trans. on Systems, Man and Cybernetics, Part A, Vol.39(5), Sept.2009, 1051-1062.

Conservation of information theorems indicate that any search algorithm performs, on average, as well as random search without replacement unless it takes advantage of problem-specific information about the search target or the search-space structure. Combinatorics shows that even a mod-erately sized search requires problem-specific information to be successful. Computers, despite their speed in performing queries, are completely inadequate for resolving even moderately sized search problems without accurate information to guide them. We propose three measures to characterize the information requiredfor successful search: 1) endogenous information, which measuresthe difficulty of finding a target using random search; 2) exogenous information, which measures the difficulty that remainsin finding a target once a search takes advantage of problem-specific information; and 3) active information, which, as the difference between endogenous and exogenous information, measures the contribution of problem-specific information for successfully finding a target. This paper develops a methodology based on these information measures to gauge the effectiveness with which problem-specific information facilitates successful search. It then applies this methodology to various search tools widely used in evolutionary search.

3. William Dembski, Robert Marks: The search for a search: Measuring the Information Cost of Higher Level Search, Journal of Advanced Computational Intelligence and Intelligent Informatics (JACIII), Volume 14, 2010, 475-486.

Needle-in-the-haystack problems look for small targets in large spaces. In such cases, blind search stands no hope of success. Conservation of information dictates any search technique will work, on average, as well as blind search. Success requires an assisted search. But whence the assistance required for a search to be successful? To pose the question this way suggests that successful searches do not emerge spontaneously but need themselves to be discovered via a search. The question then naturally arises whether such a higher-level “search for a search” is any easier than the original search. We prove two results: (1) The Horizontal No Free Lunch Theorem, which shows that average relative performance of searches never exceeds unassisted or blind searches, and (2) The Vertical No Free Lunch Theorem, which shows that the difficulty of searching for a successful search increases exponentially with respect to the minimum allowable active information being sought.

Информация определяется прагматически как сведения, позволяющие более эффективно осуществлять поиск решения задачи.

Объясняем на пальцах.

Сложность задачи угадывания комбинации из 5 цифр, где каждая цифра принимает значения от 0 до 9, соответствует - log210-5 = 16.61 битам информации. Это так наз. эндогенная (внутренняя) информация, характеризующая степень сложности задачи и не зависящая от выбранного алгоритма. Для увеличения вероятности нахождения решения необходима дополнительная информация. Например, если известно дополнительно, что все цифры в отыскиваемой нами комбинации чётные, то количество информации, которую требуется отыскать (то есть получить правильный ответ) составляет: - log25-5 = 11.61 бит. Это так называемая экзогенная (сторонняя) информация. Разница между этими двумя  мерами называется активной информацией. В нашем примере эта разница составляет 5 бит. Активная информация -- это то, что необходимо сообщить алгоритму для эффективного поиска решения задачи. Активная информация характеризует распределение решений в пространстве поиска, а также структуру самого этого пространства.

Моих, как говорится, 5 копеек. Выводы о неувеличении в среднем информации в натуралистических сценариях (статья 2 вводит необходимый понятийный аппарат, статья 3 содержит доказательства формулируемых утверждений) находятся в полном соответствии с моим личным опытом решения задач комбинаторной сложности (который сводится к тому, что "халявы" не бывает), а также с основной гипотезой ID о существовании практического предела на производство функциональной информации неинтеллектуальными механизмами (комбинациями случайности и закономерности без участия внешнего интеллектуального управления).
Tags: no free lunch, активная информация, алгоритм, комбинаторный поиск, литература, номенклатура
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic
  • 0 comments