авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 | 2 || 4 | 5 |

«БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ РАДИОФИЗИКИ И ЭЛЕКТРОНИКИ А. А. БЕЛЫЙ РАДИОЭЛЕКТРОННЫЕ СИСТЕМЫ МИНСК ...»

-- [ Страница 3 ] --

Gx ( f ) = x f 0, 0 f f1 f Рисунок 24 иллюстрирует связь между этими функциями. Рис. 24. Односторонняя и Именно эти величины измеряются двусторонняя спектральные на практике с помощью прямой фильт- плотности.

рации.

Односторонние спектральные плотности связаны со стационарными кор реляционными функциями соотношениями Gx ( f ) = 4 Rx ( ) cos 2 f d.

Обратные преобразования имеют вид Rx ( ) = S x ( f ) cos 2 f df ( 7.4 ) В частности, при = 0 получаем Rx ( 0 ) = M x ( t ) = = Gx ( f ) df 2 Последнее выражение очень полезно для выяснения физического смысла спектральной плотности. Спектральная плотность (спектр мощности) G ( f ) да ет скорость изменения среднего квадрата в зависимости от частоты (см. рис.

2 4 ) Общая площадь, лежащая под графиком спектральной плотности по все поло се частот, равна суммарному среднему квадрату реализации случайного про цесса. Часть этой площади, заключенная между частотами f1 и f 2, равна сред нему квадрату, сосредоточенному в этой полосе частот. Для оценивания спек тра вычисляется средний квадрат в узкой полосе частот при разных централь ных частотах, а затем полученное значение делится на ширину этой полосы.

Одностороння взаимная спектральная плотность Gxy ( f ), где f ( 0, ) оп ределяется как 2S xy ( f ), 0 f ;

Gxy ( f ) = ( 7.5) f 0.

0, Из формулы ( 7.1) имеем Gxy ( f ) = 2 Rxy ( ) exp ( j 2 f ) d = Cxy jQxy ( f ), ( 7.6 ) где C xy ( f ) — называется коспектральной плотностью (коспектром), а Qxy ( f ) ЧАСТЬ 3. ИНФОРМАЦИОННЫЕ АСПЕКТЫ ИЗУЧЕНИЯ СИСТЕМ — квадратурной спектральной плотностью (квадратурным спектром). Заметим, что C xy ( f ) и Qxy ( f ) выражаются через Gxy ( f ), а не через S yx ( f ). Отметим также, что при t = Rxy ( 0 ) = M x ( t ) y ( t ) = Cxy ( f ) df Величину R ( 0 ) можно определить, зная C xy ( f ) = Re Gxy ( f ).

Одностороннюю взаимную спектральную плотность можно представить в комплексной полярной форме, Gxy ( f ) = Gxy ( f ) exp j xy ( f ), 0 f, ( 7.7 ) где модуль и фазовый угол определяются формулами:

Gxy ( f ) = Cxy ( f ) + xy ( f ) 2 ( 7.8) xy ( f ) = arctg Qxy ( f ) Cxy ( f ) Знаки членов C xy ( f ) и Qxy ( f ) могут быть как положительными, так и от рицательными, а их сочетание определяет квадрант, в котором располагается фа зовый угол.

Определение спектров через финитное преобразование Фурье.

Второй способ определения спектральных плотностей по своему характеру тоже является математическим. Он основан на финитном ПФ реализаций ис ходного процесса. Именно этот способ в настоящее время чаще других исполь зуется для вычисления спектральных плотностей.

Рассмотрим пару реализаций xk ( t ) и yk ( t ) случайных стационарных про цессов x ( t ) и y ( t ). Определим на конечном интервале времени 0 t T функ цию S ( f, T, k ) = X k ( f, T ) Yk ( f, T ), ( 7.9 ) T где T X k ( f, T ) = xk ( t ) exp ( j 2 ft ) dt, ( 7.10 ) T Yk ( f, T ) = yk ( t ) exp ( j 2 ft ) dt.

Величины X k ( f, T ) и Yk ( f, T ) — это финитные ПФ реализаций xk ( t ) и yk ( t ) соответственно, а X k ( f, T ) — величина комплексно сопряженная X k ( f, T ).

Такие ПФ по конечному интервалу существуют для реализаций широкого клас са случайных процессов.

Распространенная ошибка состоит в том, что по аналогии с периодически ми процессами взаимную спектральную плотность определяют по формуле S xy ( f, k ) = lim S xy ( f, T, k ) T ЛЕКЦИЯ 7. СПЕКТРАЛЬНАЯ ПЛОТНОСТЬ МОЩНОСТИ СЛУЧАЙНОГО ПРОЦЕССА Это определение не годится в случае случайных стационарных процессов общего вида, поскольку при стремлении T оценка S xy ( f, T, k ) функции S xy ( f, T ) не становится лучше в статистическом смысле, т.е. она не состоятельна.

Обратим внимание, что левая часть соотношения, зависит еще и от индекса k. Правильное определение для спектральной плотности дает следующее вы ражение S xy ( f ) = lim M {S x ( f, T, k )}, ( 7.11) T где M {...} — математическое ожидание, взятое по множеству индексов k.

Спектральные плотности S x ( f ) или S y ( f ) — это частные случаи формулы ( 7.11) :

S x ( f ) = lim M {S x ( f, T, k )} ( 7.12 ) T S y ( f ) = lim M {S y ( f, T, k )} T Можно доказать эквивалентность формул ( 7.1) и ( 7.11), ( 7.12 ). Заметим, что замена двусторонних плотностей на односторонние приводит к следующим формулам:

lim M { X k ( f, T ) Yk ( f, T )} Gxy ( f ) = T T { } Gx ( f ) = lim M X k ( f, T ) T T { } G y ( f ) = lim M Yk ( f, T ) T T Для вычисления по этим формулам используются процедуры быстрого ПФ. На практике длина реализации T всегда конечна и математическое ожида ние M {...} также берется только по конечному ансамблю, поэтому получают оценки спектральных плотностей:

Gxy ( f ) = M { X k ( f, T ) Yk ( f, T )} % 2 T { } % Gx ( f ) = M X k ( f, T ) ( 7.13) T { } % G y ( f ) = M Yk ( f, T ) T На рисунке 2 алгоритм вычисления спектральных плотностей представлен графически.

Определение спектров с помощью фильтрации.

Третий способ вычисления спектральной плотности подразумевает применение аналоговых устройств и включает следующие операции:

ЧАСТЬ 3. ИНФОРМАЦИОННЫЕ АСПЕКТЫ ИЗУЧЕНИЯ СИСТЕМ 1) частотную фильтрацию сигнала x ( t ) с помощью узкополосного фильтра с полосой пропускания f и центральной частотой f 0, в результате этой опе рации получается величина x (t, f 0, f ) ;

2) возведение в квадрат мгновенного значения отфильтрованного сигнала;

3) усреднение квадрата мгновенного значения по реализации длины T. В результате этой операции образуется оценка среднего квадрата отфильтрован ного сигнала;

4) деление на ширину полосы пропускания фильтра, в результате чего по лучается оценка скорости изменения среднего квадрата в зависимости от цен тральной частоты f 0.

Следовательно, оценка спектральной плотности имеет вид T % ( f )= x ( t, f0, f ) dt ( 7.14 ) Gx f T Проводя фильтрацию совме- T % Gx ( f 0 ) ( ) dt стно с измерением средней мощ- ПФ ности для центральных частот f i, i = 1,2,..., N полосового фильтра Рис. 26. Спектральный анализатор на ПФ, получим N значений спек- основе метода фильтрации.

тральной плотности. Параллельные спектральные анализаторы содержат i = N представленных каналов, каждый из кото рых настроен на собственную частоту f i. Такие анализаторы обладают максимальным быстродействием и выполняют измерения в реальном масштабе времени, однако, их практическая реализация требует больших затрат оборудования.

Технические трудно- T сти, возникающие при соз- G ( fi ) ( ) dt ПС ПФ дании анализаторов с парал- лельными фильтрами, уда лось в некоторой степени Gsin преодолеть заменой всех фильтров одним с узкой Рис. 27. Гетеродинный анализатор спектра.

полосой пропускания, ко торую можно перемещать Gsin – генератор гармонического сигнала с по всему диапазону иссле- переменной частотой, ПС – перемножитель дуемых частот. Таким сигналов, ПФ – полосовой фильтр со средней фильтром является гетеро- частотой f sin и полосой пропускания f.

динная система, в которой частотная характеристика фильтра остается неизменной, а перемещение спектра достигается с помощью генератора гармонических колебаний с управляемой час тотой — гетеродина (рис. 27).

G ( f ) df дает полную мощность сигнала x ( t ), a интеграл Интеграл ЛЕКЦИЯ 7. СПЕКТРАЛЬНАЯ ПЛОТНОСТЬ МОЩНОСТИ СЛУЧАЙНОГО ПРОЦЕССА f G ( f ) df мощность сигнала в полосе частот ( f1, f 2 ).

f Определение спектральной плотности одного сигнала можно распростра нить на случай двух сигналов. Для вычисления взаимной спектральной плотно сти аналоговыми методами применяется прямое обобщение описанной проце дуры на случай двух сигналов x ( t ) и y ( t ), которое включает следующие опе рации:

1) раздельную частотную фильтрацию обоих сигналов с помощью узкопо лосных фильтров, имеющих одинаковые полосы пропускания и одну и ту же центральную частоту f 0. В результате получают x ( t, f 0, f ) и y ( t, f 0, f ) ;

2) перемножение мгновенных значений двух отфильтрованных сигналов при отсутствии сдвига фазы между ними с целью получения синфазных членов, необходимых для вычисления коспектра;

3) перемножение мгновенных значений двух отфильтрованных сигналов, причем y ( t, f 0, f ) сдвинутых по фазе на 90°по отношению к x ( t, f 0, f ) с це лью получения смещенных по фазе членов, что нужно для вычисления квадра турного спектра;

4) усреднение каждого из этих произведений по реализации длиной T с целью построения оценок средних произведений синфазных и смещенных по фазе членов;

5) деление каждого из средних произведений на ширину полосы пропуска % % ния f для получения оценок C xy ( f 0 ) и Qxy ( f 0 ) — оценка взаимной спектраль ной плотности имеет вид:

% % % Gxy ( f0 ) = Cxy ( f 0 ) jQxy ( f 0 ), T % C xy ( f 0 ) = x ( t, f 0, f ) y ( t0, f 0, f ) dt, f T ( 7.15) T % Qxy ( f 0 ) = x ( t, f0, f ) y ( t0, f0, f ) dt, где y ( t, f0, f ) 0 f T отфильтрованный сигнал y ( t, f 0, f ),сдвинутый по фазе на 90° Эквивалентность представленного аналогового способа определения спек тральных плотностей предыдущим двум математическим требует доказательства.

Рассмотрим определение спектральной плотности из формулы ( 7.13). Величина 2 T T X k ( f, T ) = xk ( t ) cos [ 2 ft ] dt + xk ( t ) sin [ 2 ft ] dt ( 7.16 ) 0 0 действует как фильтр, выделяющий значение среднего квадрата xk ( t ) в узкой полосе частот, окружающей центральную частоту f 0. Чтобы доказать это не очевидное утверждение, определим для любой реализации xk ( t ) величину ЧАСТЬ 3. ИНФОРМАЦИОННЫЕ АСПЕКТЫ ИЗУЧЕНИЯ СИСТЕМ xk ( t ), 0 t T, xk ( t, T ) = t [ 0, T ].

0, Тогда средний квадрат конкретной реализации X k ( t ) можно выразить формулой T 12 x ( k ) = lim xk ( t ) dt = lim xk ( t ) dt ( 7.17 ) 2 T T T T Если F ( f ) — это ПФ от f ( t ), то по теореме Парсеваля ( t ) dt = F ( f ) ( 7.18) f df Поскольку X k ( f, T ) — это ПФ от xk ( t, T ), т.е.

T X k ( f, T ) = xk ( t ) e x ( t,T ) e ( 7.19 ) j 2 ft j 2 ft dt = dt, то k 1 ( k ) = lim X k ( f, T ) df = 2 lim X k ( f, T ) df ( 7.20 ) 2 x T T T T Тогда взяв математическое ожидание от x ( k ) по всевозможным реализа циям xk ( t ), получим уже знакомую формулу ( k ) = Gx ( f ) df, ( 7.21) = M 2 x x где Gx ( f ) определено формулой ( 7.13).

Предположим теперь, xk ( t ) проходит через узкополосный фильтр с цен тральной частотой f 0 и полосой пропускания f, имеющий частотную харак теристику H ( f ) вида f f f f0, f0 + 1, ;

H( f )= ( 7.22 ) f f 0, f f0, f0 +.

Тогда ПФ процесса на выходе фильтра равно H ( f ) X k ( f, T ), где X k ( f, T ) — ПФ входного процесса. Поэтому вместо формулы ( 7.20 ) для сред него квадрата отдельной отфильтрованной реализации xk ( t ) получим выраже ние x ( f0, f, k ) = 2 lim H ( f ) X k ( f, T ) df ( 7.23) 2 T T Взяв математическое ожидание от обеих частей формулы ( 7.23), получим ЛЕКЦИЯ 7. СПЕКТРАЛЬНАЯ ПЛОТНОСТЬ МОЩНОСТИ СЛУЧАЙНОГО ПРОЦЕССА f f0 + x ( f 0, f ) = H ( f ) Gx ( f ) df = Gx ( f ) df ( 7.24 ) f 0 f Таким образом, формула ( 7.24 ) утверждает, что Gx ( f ) есть скорость из менения среднего квадрата в зависимости от частоты. Кроме того, оператор X k ( f, T ) действует на реализацию xk ( t ) как фильтр, который пропускает только те ее составляющие, которые лежат в узкой полосе частот, а затем воз водит в квадрат значения на выходе до выполнения соответствующих операций усреднения. Именно на этом принципе действуют аналоговые спектральные анализаторы.

Можно во мно X(f) x (t ) го раз повысить возможности анали затора с разверткой частоты, если заста вить его работать в f1 f f t f другом, более ко X ( kf ) масштабе x ( t k ) ротком времени. Достигает ся это тем, что сиг нал x ( t ) сжимается во времени при со kf1 k f хранении всех дру- t kf гих его параметров Рис. 28. Сжатие времени (отсюда выражение "сжатие времени"). При этом каждая из частот, составляющих сигнал, возраста ет в k раз, где k называют коэффициентом сжатия.

Отметим, что свойство подобия преобразования Фурье приводит к сле дующему соотношению между сжатым сигналом и его Фурье-образом x ( t k ) k X ( kf ).

Ширина полосы полосового фильтра ПФ становиться равной k f, допус тимая скорость развертки возрастает в k раз, и во столько же раз уменьшается продолжительность анализа F k F T= = ( k f ) k f Этот метод был предложен в 1956 году для анализа сигналов в гидро и ра диолокации. При этом использовался анализатор, в котором сжатие времени осуществлялось в цифровой форме, а перед модуляцией и кварцевым фильтром (непосредственно частотный анализ) сигнал вновь преобразовывался в аналого вую форму.

Низкочастотный фильтр на входе анализатора ограничивает полосу частот анализируемого сигнала в соответствии с выбранным частотным диапазоном.

ЧАСТЬ 3. ИНФОРМАЦИОННЫЕ АСПЕКТЫ ИЗУЧЕНИЯ СИСТЕМ Затем сигнал преобразуются в цифровую форму и записывается в циклическую память на основе сдвигового регистра емкостью N слов. Данные, записанные в память, считываются из нее с гораздо более высокой скоростью (1000 — 10 раз), что и приводит к сжатию масштаба времени исследуемого сигнала. Отно шение частоты считывания из входной памяти к частоте записи определяет ко эффициент сжатия.

Недостатки такого типа анализаторов связаны с работой аналоговых схем и касаются главным образом динамического диапазона амплитуд, который в данном случае ограничен 50 — 60 дБ.

T T dt X M Gsin Статистические оценки измеряемых характеристик.

Рассмотрим распространенную модель смешанного сигнала x ( t ) = s ( t ) + n ( t ) = a cos 0t + n ( t ), где n ( t ) — выборочная функция случайного процесса типа "белый шум", для которого спектральная плотность G ( f ) постоянна и равна N 0, а корреляцион ная функция K ( ) приближается к -функции. Как корректно измерить спек тральную плотность мощности представленного сигнала?

При процедуре спектрального оценивания, использующей метод периодо грамм, спектральная плотность мощности непрерывной части спектра опреде ляется следующим известным соотношением 2 T Gn ( ) = lim M x ( t ) e dt = lim M {Sn ( )} jt T T T 0 T 2 Функция Sn ( ) = x ( t ) e jt dt = X n ( ) называется оценкой СПМ.

T0 T Известно, что для случайного гауссовского процесса оценка СПМ является асимптотически несмещенной, т.е. lim M {Sn ( )} = S n ( ) и имеет относитель T ную дисперсию 2 =. Величина BeT = R определяет число степеней свобо BeT ды для спектральной оценки. Для частот в непосредственной близости от дис кретной компоненты сигнала, необходимо использовать оценку 2 Gs ( ) = lim M 2 X ( ) ( i ).

T T ЛЕКЦИЯ 7. СПЕКТРАЛЬНАЯ ПЛОТНОСТЬ МОЩНОСТИ СЛУЧАЙНОГО ПРОЦЕССА Функция Gs ( ), вычисляемая как периодограмма, не масштабирована как спектральная плотность мощности. Она определяет не площадь под кривой СПМ, а пики на этой кривой, величина которых равна мощности предполагае мых периодических компонент.

Относительная дисперсия сглаженной оценки для периодической компо ненты определяется соотношением 1 2 2 X ( ) ( i ) 2 = BeT T 1 + 2R 2 = BeT [1 + ] где = s2 n — отношение сигнал/шум на выходе устройства, формирующего оценку G ( ), т. е. отношение мощностей сигнальной и шумовой компонент, s присутствующих в полосе Be. На рис. 30 представлена зависимость нормиро ванной среднеквадратической ошибки 1 + 2R = B T [1 + R ] e от отношения сигнал/шум и числа степеней свободы.

R, % BeT = 1 2 10 50, дБ 40 20 0 20 Лекция 8. ЭНТРОПИЯ И КОЛИЧЕСТВО ИНФОРМАЦИИ Установив, что случайные процессы являются адекватной моделью сигна лов, мы можем воспользоваться результатами и мощным аппаратом теории случайных процессов. Это не означает, что теория вероятностей и теория слу чайных процессов дают готовые ответы на все вопросы о сигналах: подход с новых позиций выдвигает такие вопросы, которые просто не возникали. Так и родилась теория информации, специально рассматривающая сигнальную спе цифику случайных процессов. При этом были построены принципиально новые понятия и получены новые, неожиданные результаты, имеющие характер науч ных открытий.

Понятие неопределенности. Первым специфическим понятием теории ин формации является понятие неопределенности случайного объекта, для которо го удалось ввести количественную меру, названную энтропией. Начнем с про стейшего примера — со случайного события. Пусть, например, некоторое со бытие может произойти с вероятностью 0,99 и не произойти с вероятностью 0,01, а другое событие имеет вероятности соответственно 0,5 и 0,5. Очевидно, что в первом случае результатом опыта "почти наверняка" является наступле ние события, во втором же случае неопределенность исхода так велика, что от прогноза разумнее воздержаться.

Для характеристики размытости распределения широко используется вто рой центральный момент (дисперсия) или доверительный интервал. Однако эти величины имеют смысл лишь для случайных числовых величин и не могут применяться к случайным объектам, состояния которых различаются качест венно. Следовательно, мера неопределенности, связанной с распределением, должна быть некоторой его числовой характеристикой, функционалом от рас пределения, никак не связанным с тем, в какой шкале измеряются реализации случайного объекта.

Энтропия и ее свойства.

Примем (пока без обоснования) в качестве меры неопределенности слу чайного объекта A с конечным множеством возможных состояний A1,..., An с соответствующими вероятностями p1... pn величину n H ( A ) = H { pi } = pi log pi. ( 8.1) i Эту величину называют «энтропией случайного объекта A » (или распре деления { pi } ). Убедимся, что этот функционал обладает свойствами, которые вполне естественны для меры неопределенности.

1. H ( p1,..., pn ) = 0 в том и только в том случае, когда какое-нибудь одно из { pi } равно единице (а остальные — нули). Это соответствует случаю, когда ис ход опыта может быть предсказан с полной достоверностью, т.е. когда отсутст вует всякая неопределенность. Во всех других случаях энтропия положительна.

Это свойство проверяется непосредственно.

ЛЕКЦИЯ 8. ЭНТРОПИЯ И КОЛИЧЕСТВО ИНФОРМАЦИИ 2. H ( p1,..., pn ) достигает наибольшего значения при p1 = p2 =... = pn = n т.е. в случае максимальной неопределенности. Действительно, вариация H по pi при условии pi = 1 дает pi = const =.

n 3. Если A и B — независимые случайные объекты, то H ( A B ) = H ({ pi qk } ) = H ({ pi } ) + H ({qk } ) = H ( A ) + H ( B ) Это свойство проверяется непосредственно.

4. Если A и B В — зависимые случайные объекты, то H ( A B ) = H ( A) + H ( B A) = H ( B ) + H ( A B ), где условная энтропия H ( A B ) определяется как математическое ожидание эн тропии условного распределения. Это свойство проверяется непосредственно.

5. Имеет место неравенство H ( A) H ( A B ), что согласуется с интуитив ным предположением о том, что знание состояния объекта B может только уменьшить неопределенность объекта A, а если они независимы, то оставит ее неизменной.

Как видим, свойства функционала H позволяют использовать его в каче стве меры неопределенности.

Дифференциальная энтропия. Обобщение столь полезной меры неопре деленности на непрерывные случайные величины наталкивается на ряд слож ностей, которые, однако, преодолимы. Прямая аналогия ( 8.2 ) pk log pk p ( x ) log p ( x ) dx не приводит к нужному результату. Плотность p ( x ) является размерной вели чиной (размерность плотности p ( x ) обратно пропорциональна x ) а логарифм размерной величины не имеет смысла. Однако положение можно исправить, умножив p ( x ) под знаком логарифма на величину K, имеющую туже размер ность, что и величина x :

pk log pk p ( x ) log Kp ( x ) dx Теперь величину K можно принять равной единице измерения x, что приводит к функционалу ( 8.3) h ( X ) = p ( x ) log p ( x ) dx, который получил название «дифференциальной энтропии». Это аналог энтро пии дискретной величины, но аналог условный, относительный: ведь единица измерения произвольна. Запись ( 8.3) означает, что мы как бы сравниваем не определенность случайной величины, имеющей плотность p ( x ), с неопреде ленностью случайной величины, равномерно распределенной в единичном ин тервале. Поэтому величина h ( X ) в отличие от H ( X ) может быть не только положительной. Кроме того, h ( X ) изменяется при нелинейных преобразовани ях шкалы x, что в дискретном случае не играет роли. Остальные свойства ЧАСТЬ 3. ИНФОРМАЦИОННЫЕ АСПЕКТЫ ИЗУЧЕНИЯ СИСТЕМ h ( X ) аналогичны свойствам H ( X ), что делает дифференциальную энтропию очень полезной мерой.

Пусть, например, задача состоит в том, чтобы, зная лишь некоторые огра ничения на случайную величину (типа моментов, пределов области возможных значений и т.п.), задать для дальнейшего (каких-то расчетов или моделирова ния) конкретное распределение. Один из подходов к решению этой задачи дает «принцип максимума энтропии»: из всех распределений, отвечающих данным ограничениям, следует выбирать то, которое обладает максимальной диффе ренциальной энтропией. Смысл этого критерия состоит в том, что, выбирая максимальное по энтропии распределение, мы гарантируем наибольшую неоп ределенность, связанную с ним, т.е. имеем дело с наихудшим случаем при дан ных условиях.

Фундаментальное свойство энтропии случайного процесса. Особое значение энтропия приобретает в связи с тем, что она связана с очень глубоки ми, фундаментальными свойствами случайных процессов. Покажем это на примере процесса с дискретным временем и дискретным конечным множест вом возможных состояний.

Назовем каждое такое состояние «символом», множество возможных со стояний — «алфавитом», их число m — «объемом алфавита». Число возмож ных последовательностей длины n, очевидно, равно mn. Появление конкрет ной последовательности можно рассматривать как реализацию одного из mn возможных событий. Зная вероятности символов и условные вероятности появ ление следующего символа, если известен предыдущий (в случае их зависимо сти), можно вычислить вероятность P ( C ) для каждой последовательности C.

Тогда энтропия множества {C}, по определению, равна P ( C ) log P ( C ) ( 8.4 ) Hn = C{C} Определим энтропию процесса H (среднюю неопределенность, приходя щуюся на один символ) следующим образом:

( 8.5) H = lim [ H n n ] n На множестве {C} можно задать любую числовую функцию f n ( C ), кото рая, очевидно, является случайной величиной. Определим f n ( C ) c помощью соотношения f n ( C ) = log P ( C ).

n Математическое ожидание этой функции M { f n ( C )} = P ( C ) f n ( C ) = P ( C ) log P ( C ), n Mоткуда следует, что 1 H M log P ( C ) = n n n и ЛЕКЦИЯ 8. ЭНТРОПИЯ И КОЛИЧЕСТВО ИНФОРМАЦИИ 1 lim M log P ( C ) = H ( 8.6 ) n n Это соотношение является одним из проявлений более общего свойства дискретных эргодических процессов. Оказывается, что не только математиче ское ожидание величины f n ( C ) при n имеет своим пределом H, но и са ма эта величина f n ( C ) стремится к H при n. Другими словами, как бы малы ни были 0 и 0, при достаточно большом n справедливо неравен ство 1 P log P ( C ) + H, ( 8.7 ) n т.е. близость f n ( C ) к H при больших n является почти достоверным событи ем.

Для большей наглядности сформулированное фундаментальное свойство случайных процессов обычно излагают следующим образом. Для любых задан ных 0 и 0 можно найти такое n0, что реализация любой длины n n распадаются на два класса:

— группа реализаций, вероятность P ( C ) которых удовлетворяет неравен ству log P ( C ) + H ( 8.8 ) n — группа реализаций, вероятности которых этому неравенству не удовле творяют.

Так как согласно ( 8.7 ) суммарные вероятности этих групп равны соответ ственно 1 и, то первая группа называется «высоковероятной», а вторая — «маловероятной».

Это свойство эргодических процессов приводит к ряду важных следствий, из которых три заслуживают особого внимания.

1) независимо от того, каковы вероятности символов и каковы статистиче ские связи между ними, все реализации высоковероятной группы приблизи тельно равновероятны (см. ( 8.8 ) ).

Это следствие, в частности, означает, что при известной вероятности P ( C ) одной из реализаций высоковероятной группы можно оценить число N1 реали заций в этой группе:

N1 = 1 P ( C ) 2) Энтропия H n с высокой точностью равна логарифму числа реализаций в высоковероятной группе:

( 8.9 ) H n = n H = log N 3) При больших n высоковероятная группа обычно охватывает лишь ни чтожную долю всех возможных реализаций (за исключением случая равнове роятных и независимых символов, когда все реализации равновероятны и ЧАСТЬ 3. ИНФОРМАЦИОННЫЕ АСПЕКТЫ ИЗУЧЕНИЯ СИСТЕМ H = log m ).

Действительно, из соотношения ( 8.9 ) имеем N1 = nH, где — основание логарифма. Число N всех возможных реализаций есть N = mn = nlog m.

Доля реализаций высоковероятной группы в общем числе реализаций вы ражается формулой ( 8.10 ) N1 N = ( n log m H ) и при H log m эта доля неограниченно убывает с ростом n. Например, если = 2, n = 100, H = 2,75, m = 8, то ( N1 N ) = 225 = 1 3 107, т.е. к высоковероят ной группе относится лишь одна тридцати миллионная доля всех реализаций!

Строгое доказательство фундаментального свойства эргодических процес сов здесь не приводится. Однако следует отметить, что в простейшем случае независимости символов это свойство является следствием закона больших чи сел. Действительно, закон больших чисел утверждает, что с вероятностью, близкой к 1, в длиной реализации i-й символ, имеющий вероятность pi встре тится примерно npi раз. Следовательно вероятность реализации высоковероят ной группы есть P ( C ) { p }, откуда log P ( C ) = n p log p = n H, что и m m nPi i i i i = i = доказывает справедливость фундаментального свойства в этом случае.

Количество информации В основе всей теории информации лежит открытие, что «информация до пускает количественную оценку». В простейшей форме эта идея была выдвину та еще в 1928г. Хартли, но завершенный и общий вид придал ее Шэннон в 1948г. Не останавливаясь на том, как развивалось и обобщалось понятие коли чества информации, дадим сразу ее современное толкование.

Количество информации как мера снятой неопределенности. Процесс получения информации можно интерпретировать как «изменение неопределен ности в результате приема сигнала». Проиллюстрируем эту идею на примере достаточно простого случая, когда передача сигнала происходит при следую щих условиях:

- полезный (передаваемый) сигнал является последовательностью стати стически независимых символов с вероятностями p ( xi ), i = 1, m ;

- принимаемый сигнал является последовательностью символов yk того же алфавита;

- если шумы (искажения) отсутствуют, то принимаемый сигнал совпадает с отправленным yk = xk ;

- если шум имеется, то его действие приводит к тому, что данный символ либо остается прежним (i-м), либо подменен любым другим (k-м) с вероятно стью p ( yk / xi ) ;

- искажение данного символа является событием статистически независи мым от того, что произошло с предыдущим символом.

Итак, до получения очередного символа ситуация характеризуется неопре ЛЕКЦИЯ 8. ЭНТРОПИЯ И КОЛИЧЕСТВО ИНФОРМАЦИИ деленностью того, какой символ будет отправлен, т.е. априорной энтропией H ( X ). После получения символа yk неопределенность относительно того, ка кой символ был отправлен, меняется: в случае отсутствия шума она вообще ис чезает (апостериорная энтропия равна нулю, поскольку точно известно, что был передан символ yk = xi ). При наличии шума мы не можем быть уверены, что принятый символ и есть переданный, т.е. возникает неопределенность, характе ризуемая апостериорной энтропией:

( ) H ( X yk ) = H { p ( xi yk )} 0.

В среднем после получения очередного символа энтропия H ( X Y ) = M y { H ( X yk )}.

Определим теперь количество информации как меру снятой неопределен ности: числовое значение количества информации о некотором объекте равно разности априорной и апостериорной энтропии этого объекта, т.е.

I ( X,Y ) = H ( X ) H ( X Y ). ( 8.11) Используя свойство 2 энтропии, легко получить, что I ( X, Y ) = H ( Y ) H (Y X ) ( 8.12 ) В явной форме равенство ( 8.11) запишется так:

m I ( X, Y ) = H ( X ) H ( X Y ) = p ( xi ) log p ( xi ) + i = m m m + p ( yk ) p ( xi yk ) log p ( xi yk ) = p ( xi, yk ) log p ( xi ) + ( 8.13) k =1 i =1 k i m m m + p ( xi, yk ) log p ( xi yk ) = p ( xi, yk ) log { p ( xi yk ) p ( xi )} i =1 k = 1 k А для равенства ( 8.12 ) имеем m m I ( X, Y ) = p ( xi, yk ) log { p ( yk xi ) p ( yk )} ( 8.14 ) k = Количество информации как мера соответствия случайных процессов.

Представленным формулам легко придать полную симметричность: умножив и разделив логарифмируемое выражение в ( 8.13) на p ( yk ), а в ( 8.14 ) на p ( xi ) сразу получим, что m m I ( X, Y ) = p ( xi, yk ) log { p ( xi, yk ) p ( xi ) p ( yk )} ( 8.15 ) k = Эту симметрию можно интерпретировать так: «количество информации в объекте X об объекте Y равно количеству информации в объекте Y об объекте X. Таким образом, количество информации является не характеристикой одно го из объектов, а характеристикой их связи, соответствия между их состояния ми. Подчеркивая это, можно сформулировать еще одно определение: «среднее количество информации, вычисляемое по формуле (8.15), есть мера соот ветствия двух случайных объектов».

Это определение позволяет прояснить связь понятий информации и коли ЧАСТЬ 3. ИНФОРМАЦИОННЫЕ АСПЕКТЫ ИЗУЧЕНИЯ СИСТЕМ чества информации. Информация есть отражение одного объекта другим, про являющееся в соответствии их состояний. Один объект может быть отражен с помощью нескольких других, часто какими-то лучше, чем остальными. Сред нее количество информации и есть числовая характеристика степени отраже ния, степени соответствия. Подчеркнем, что при таком описании как отражае мый, так и отражающий объекты выступают совершенно равноправно. С одной стороны, это подчеркивает обоюдность отражения: каждый из них содержит информацию друг о друге. Это представляется естественным, поскольку отра жение есть результат взаимодействия, т.е. взаимного, обоюдного изменения со стояний. С другой стороны, фактически одно явление (или объект) всегда вы ступает как причина, другой — как следствие;

это никак не учитывается при введенном количественном описании информации.

Формула ( 8.15 ) обобщается на непрерывные случайные величины, если в отношении ( 8.11) и ( 8.12 ) вместо H подставить дифференциальную энтропию h ;

при этом исчезает зависимость от стандарта K и, значит, количество ин формации в непрерывном случае является столь же безотносительным к едини цам измерения, как и в дискретном:

I ( X, Y ) = p ( x, y ) log { p ( x, y ) p ( x ) p ( y )} dxdy, ( 8.16 ) XY где p ( x ), p ( y ) и p ( x, y ) — соответствующие плотности вероятностей.

Свойства количества информации. Отметим некоторые важные свойст ва количества информации.

1. Количество информации в случайном объекте X относительно объекта Y равно количеству информации в Y относительно X :

I ( X, Y ) = I (Y, X ) ( 8.17 ) 2. Количество информации неотрицательно:

I ( X,Y ) 0 ( 8.18 ) Это можно доказать по-разному. Например, варьированием p ( x, y ) при фиксиро ванных p ( x ) и p ( y ) можно показать, что минимум I, равный нулю, достига ется при p ( x, y ) = p ( x ) p ( y ).

3. Для дискретных X справедливо равенство I ( X, X ) = H ( X ).

4. Преобразование ( ) одной случайной величины не может увеличить содержа ние в ней информации о другой, связанной с ней, величине:

I ( X ), Y I ( X, Y ) ( 8.19 ) 5. Для независимых пар величин количество информации аддитивно:

( ) I { X i, Y }i = I ( X i, Yi ) ( 8.20 ) i Единицы измерения энтропии и количества информации. Рассмотрим те перь вопрос о единицах измерения количества информации и энтропии. Из оп ределений I и H следует их безразмерность, а из линейности их связи — оди наковость их единиц. Поэтому будем для определенности говорить об энтро пии. Начнем с дискретного случая. За единицу энтропии примем неопределен ЛЕКЦИЯ 8. ЭНТРОПИЯ И КОЛИЧЕСТВО ИНФОРМАЦИИ ность случайного объекта, такого, что m H ( X ) = pi log pi = 1 ( 8.21) i Легко установить, что для однозначного определения единицы измерения энтропии необходимо конкретизировать число m состояний объекта и основа ние логарифма. Возьмем для определенности наименьшее число возможных состояний, при котором объект еще остается случайным, т.е. m = 2, и в качест ве основания логарифма также возьмем число 2. Тогда из равенства p1 log 2 p2 p2 log 2 p2 = вытекает, что p1 = p2 = 1 2. Следовательно, единицей неопределенности служит энтропия объекта с двумя равновероятными состояниями. Эта единица получи ла название "бит". Бросание монеты дает количество информации в один бит.

Другая единица "нит" получается, если использовать натуральные логарифмы.

Обычно она употребляется для непрерывных величин.

Количество информации в индивидуальных событиях. Остановимся еще на одном важном моменте. До сих пор речь шла о «среднем» количестве информации, приходящемся на пару состояний ( xi, yk ) объектов X и Y. Эта характеристика естественна для рассмотрения особенностей стационарно функционирующих систем, когда в процессе функционирования принимают участие все возможные пары ( xi, yk ). Однако в ряде практических случаев ока зывается необходимым рассмотреть информационное описание конкретной па ры состояний, оценить содержание информации в конкретной реализации сиг нала. Тот факт, что некоторые сигналы несут информации намного больше, чем другие, виден на примере того, как отбираются новости средствами массовой информации (о рождении шестерых близнецов сообщают практически все газе ты мира, а о рождении двойни не пишут).

Допуская существование количественной меры информации i ( xi, yk ), в конкретной паре ( xi, yk ) естественно потребовать, чтобы индивидуальное и среднее количество информации удовлетворяли соотношению I ( X, Y ) = M {i ( xi, yk )} = p ( xi, yk ) i ( xi, yk ) ( 8.22 ) i,k Хотя равенство имеет место не только при равенстве всех слагаемых, сравнение формул ( 8.22 ) и, например, ( 8.4 ) наталкивает на мысль, что мерой индивидуальной информации в дискретном случае может служить величина i ( xi, yk ) = log { p ( xi yk ) p ( xi )} = ( 8.23) = log { p ( yk xi ) p ( yk )} = log { p ( xi, yk ) p ( xi ) p ( yk )} а в непрерывном — величина i ( x, y ) = ln { p ( x y ) p ( x )} = ln { p ( y x ) p ( y )} = ln { p ( x, y ) p ( x ) p ( y )}, ( 8.24 ) называемая «информационной плотностью». Свойства этих величин согласу ются с интуитивными представлениями и, кроме того, доказана единственность меры, обладающей указанными свойствами. Полезность введения понятия ин дивидуального количества информации проиллюстрируем на следующем при ЧАСТЬ 3. ИНФОРМАЦИОННЫЕ АСПЕКТЫ ИЗУЧЕНИЯ СИСТЕМ мере.

Пример. Пусть по выборке x (т.е. совокупности наблюдений x = x1,...xn ) требуется отдать предпочтение одной из конкурирующих гипотез ( H 1 или H 0 ), если известны распределения наблюдений при каждой из них, т.е. p ( x H 0 ) и p ( x H1 ). Как обработать выборку? Из теории известно, что никакая обработка не может увеличить количество информации, которое содержится в выборке x (см. формулу ( 8.19 ) ). Следовательно, выборке x следует поставить в соответ ствие число, содержащее всю полезную информацию, т.е. обработать выборку без потерь. Возникает мысль о том, чтобы вычислить индивидуальное количе ство информации в выборке x по каждой из гипотез и сравнить их:

i = i ( x, H1 ) i ( x, H 0 ) = ln { p ( x H1 ) p ( x )} ( 8.25 ) ln { p ( x H 0 ) p ( x )} = ln { p ( x H1 ) p ( x, H 0 )} Какой из гипотез отдать предпочтение зависит теперь от величины i и от того, какой порог сравнения мы назначим. Оказывается, что мы получили ста тистическую процедуру, оптимальность которой специально доказывается в математической статистике, — именно к этому сводится содержание фунда ментальной леммы Неймана-Пирсона. Данный пример иллюстрирует эвристи ческую силу теоретико-информационных представлений.

Подведем итог. Связав понятие неопределенности дискретной величины с распределением вероятности по возможным состояниям, и потребовав некото рых естественных свойств от количественной меры неопределенности, мы при ходим к выводу, что такой мерой может служить функционал ( 8.11), назван ный энтропией. С некоторыми трудностями энтропийный подход удалось обобщить на непрерывные случайные величины (введением дифференциальной энтропии) и на дискретные случайные процессы.

Для системного анализа теория информации имеет двоякое значение. Во первых, ее конкретные методы позволяют провести ряд количественных иссле дований информационных потоков в изучаемой или проектируемой системе.

Однако более важным является эвристическое значение основных понятий тео рии информации — неопределенности, энтропии, количество информации, из быточности, пропускной способности и пр. Их использование столь же важно для понимания системных процессов, как и использование понятий, связанных с временными, энергетическими процессами. Системный анализ неизбежно вы ходит на исследование ресурсов, которые потребуются для решения анализи руемой проблемы. Информационные ресурсы играют далеко не последнюю роль наряду с остальными ресурсами — материальными, энергетическими, временными, кадровыми.

Лекция 9. ОБ ОСНОВНЫХ РЕЗУЛЬТАТАХ ТЕОРИИ ИНФОРМАЦИИ Теория информации приводит к ряду новых понятий, описывающих ин формационные процессы, происходящие в системах, к введению новых количе ственных параметров, позволяющих производить измерения и расчеты. Однако главная ценность теории информации состоит в полученных новых результа тах, в открытии ранее неизвестных свойств систем. Чтобы познакомиться с ос новными из этих результатов, рассмотрим еще некоторые понятия и параметры информационных процессов и систем.

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

Пусть сигнал длиной n символов содержит количество информации I.

Если это представление информации обладает избыточностью, то такое же ко личество информации I может быть представлено с помощью меньшего числа символов. Обозначим через n0 наименьшее число символов, необходимое для представления I без потерь. На каждый символ в первом случае приходится I1 = I n бит информации, во втором I1max = I n0 бит. Очевидно, I = nI1 = n0 I1max.

В качестве «меры избыточности» R принимается относительное удлинение сигнала, соответствующее данной избыточности:

R = ( n n0 ) n = 1 n0 n = 1 I1 I1max ( 9.1) В дискретном случае имеются две причины избыточности: неравновероят ность символов и наличие статистической связи между символами. В непре рывном случае — это отклонение от распределений, обладающих максималь ной энтропией, т.е. неэкстремальность распределений.

Не следует думать, что избыточность — явление всегда отрицательное.

При наличии шумов, искажениях, выпадениях и вставках символов именно из быточность позволяет обнаружить и исправить ошибки.

Скорость передачи и пропускная способность. Следующим важнейшим понятием является скорость передачи информации. Так называется количество информации, передаваемое в единицу времени. Эта величина определяется по формуле R = H (X ) H (X Y ), ( 9.2 ) где указанные энтропии исчисляются на единицу времени.

В дискретном случае единицей времени удобно считать время передачи одного символа. Тогда в ( 9.2 ) фигурирует априорная и апостериорная энтропии на один символ. Для непрерывных каналов единицей времени может служить либо обычная единица (например, секунда), либо интервал между отсчетами.

ЧАСТЬ 3. ИНФОРМАЦИОННЫЕ АСПЕКТЫ ИЗУЧЕНИЯ СИСТЕМ Для непрерывных каналов в соотношение ( 9.2 ) вводят соответствующие диф ференциальные энтропии.

Скорость передачи информации по каналу связи зависит от многих факто ров — от энергии сигнала, числа символов в алфавите, избыточности, полосы частот, способа кодирования и декодирования. Если имеется возможность из менять некоторые из них, то, естественно, следует делать это так, чтобы макси мально увеличить скорость передачи. Оказывается, что существует предел, выше которого увеличение скорости невозможно. Этот предел называется «пропускной способностью канала»:

( 9.3) C = sup RA, { A} где RA — скорость передачи информации при условиях A, { A} — множество вариантов условий.

Так как множество { A} можно определить по-разному, то имеет смысл го ворить о нескольких типах пропускной способности. Наиболее важным являет ся случай, когда мощность сигнала (объем алфавита) фиксирована, а варьиро вать можно только способ кодирования. Именно таким образом пропускную способность определил К.Шеннон.

Для представления о порядках величины C пропускной способности кана ла приведем примеры. Прямыми измерениями установлено, что пропускная способность зрительного, слухового и тактильного каналов связи человека имеют порядок 50 бит/с (вопреки распространенному мнению о большем отли чие пропускной способности зрительного канала). Возможно, ограничивающим фактором являются не сами рецепторы, а нервные волокна, передающие возбу ждение. Если включить в канал и "исполнительные" органы человека (напри мер, предложить ему нажимать кнопку в темпе получения сигналов), то пропу скная способность близка к 10 бит/с. Для более наглядного представления о ве личине R укажем, что темп обычной речи соответствует скорости порядка бит/с. Муравьи обмениваются информацией путем касания усиками со скоро стью около 0,1 бит/с. Интересно отметить, что многие бытовые технические устройства слабо согласованы с органами чувств человека. Например, канал те левидения имеет пропускную способность в десятки миллионов бит/с.

Кодирование в отсутствии шумов.

С помощью введенных понятий можно рассмотреть многие информацион ные процессы. Начнем с дискретных систем без шумов. Здесь главное внима ние привлекает проблема эффективности. Важно, чтобы данная информация заняла в запоминающем устройстве как можно меньше ячеек, при передаче же лательно занимать канал связи на максимально короткий срок. В такой поста новке задачи легко распознается проблема устранения всякой избыточности и эта проблема далеко не тривиальна.

Пусть алфавит системы состоит из m символов. Средствами этого алфави та требуется представить любой из M возможных сигналов {uk }, k [1, M ], ве роятности которых { p ( uk )} заданы. Обычно M m, поэтому каждый из сигна лов, подлежащих передаче, невозможно обозначить только одним символом и ЛЕКЦИЯ 9. ОБ ОСНОВНЫХ РЕЗУЛЬТАТАХ ТЕОРИИ ИНФОРМАЦИИ приходится ставить им в соответствие некоторые последовательности симво лов, которые называют «кодовыми словами». Так как возможна последователь ная передачи разных кодовых слов, то они не только должны различаться для разных uk, но и не должны быть продолжением других, более коротких. Пусть сигналу uk соответствует кодовое слово длиной lk символов. При стационар ной передаче сигналов с вероятностями { p ( uk )} средняя длина кодового слова равна L = lk p ( uk ).

k Возникает вопрос о том, как выбрать L и {lk }. Вопрос не имеет смысла, пока не задан критерий выбора этих величин. Определим этот критерий так: L и {lk } должны быть минимальными величинами, такими, при которых еще не происходит потери информации. Напомним, что в отсутствие шумов среднее количество информации на один элемент uk ансамбля {uk } равно энтропии это го ансамбля, т.е.

M H (U ) = p ( uk ) log p ( uk ), k = а индивидуальное количество информации в uk есть i ( uk ) = log p ( uk ).

С другой стороны, на один символ придется максимальное количество ин формации i, если символы равновероятны и независимы;

при этом i = log m.

Поскольку кодирование должно вестись без потерь информации, сразу получа ем H (U ) log m L, ( 9.4 ) i ( uk ) log m lk i ( uk ) log m + 1 ( 9.5) Так из общих соображений находим нижние границы для L и lk. В теории информации доказываются теоремы об условиях достижимости этих границ.

Мы не будем приводить эти теоремы. Укажем лишь, что речь идет не только о принципиальной возможности: разработаны процедуры построения кодов, обеспечивающих безизбыточное кодирование (либо сколь угодно близкое к не му).

Кодирование при наличии шумов.

Наиболее интересные и важные результаты были получены при рассмот рении передачи информации по каналам связи с шумами. В этом случае безиз быточное кодирование приведет к безвозвратным потерям информации: иска женный символ нельзя ни обнаружить, ни исправить. Для борьбы с влиянием помех необходимо ввести избыточность в сигнал. Основываясь на интуитивных соображениях, легко прийти к выводу, что при неограниченном повышении требований к малости вероятности ошибки избыточность (при любом способе кодирования) должна неограниченно возрастать, а скорость передачи — стре миться к нулю. Здесь мы имеем яркий пример того, как интуиция может при вести к сильному заблуждению. К.Шеннон показал, что «существуют такие способы введения избыточности, при которых обеспечиваются одновременно ЧАСТЬ 3. ИНФОРМАЦИОННЫЕ АСПЕКТЫ ИЗУЧЕНИЯ СИСТЕМ и сколь угодно малая вероятность ошибки и конечная (отличная от нуля) ско рость передачи информации. Причем эта скорость может быть сколь угодно близкой к пропускной способности канала». Это замечательное открытие и привлекло столь большое внимание к теории информации. Воспроизведем уп рощенное доказательство указанного утверждения.

Рассмотрим схему передачи по Канал с каналу с шумом (рис. 31) Кодер X шумом Y Декодер U Будем считать, что на вход коде ра сигналы поступают закодирован ными безизбыточно. Кодер вносит в сигнал избыточность, увеличивая дли тельность кодовых слов. Число воз можных последовательностей сразу резко увеличивается. Но избыточность Задано:

P(X Y) и состоит в том, что к отправке пред- Вход кодера Вход Выход Выход назначаются не все из них, а лишь (источник) канала канала декодера «разрешенные» (на рис. отмечены Число всевозможных Число Каждой принятой последствий длиной разрешенных к последовательности черными кружками). Согласно фунда- соответствует 2 ( ) – n равно 2 ( ) nH X Y nH X отправке 2 nH ментальному свойству энтропии, чис- возможно отправленных Рис. 31. Схема передачи ло всевозможных последовательно по каналу с шумом стей длины n равно 2 ( ), а число nH X разрешенных к отправке равно 2nH 2 ( ) (считаем, что энтропия исчисляется nH X в битах). H — энтропия на символ во множестве разрешенных к отправке по следовательностей ("энтропия источника", или "скорость создания информа ции"), H ( X ) — энтропия на символ во множестве всевозможных последова тельностей.

В результате воздействия шумов какие-то из символов отправленной по следовательности подменяются другими и на приемный конец поступает дру гая, отличная от отправленной, последовательность. Поскольку P ( X Y ) счита ется известным, каждой принятой последовательности соответствует 2 ( ) nH X Y возможно отправленных. Декодирование, (т.е. принятие решения о том, какая последовательность была отправлена) можно выразить как разбиение всего множества Y принимаемых последовательностей на 2nH подмножеств, сопос тавляемых с разрешенными к отправке. Если, например, принят сигнал i-й группы, то считается, что был послан i-й разрешенный сигнал, который и вы дается в "чистом" виде получателю.

Итак, в построенной модели проблема выбора кода (способа передачи) со стоит в размещении разрешенных последовательностей среди множества все возможных на передающем конце и в разбиении этого множества из 2 ( ) по nH X следовательностей на 2nH подмножеств на приемном конце.

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

Рассмотрим класс всевозможных кодов, которые получаются, если разре ЛЕКЦИЯ 9. ОБ ОСНОВНЫХ РЕЗУЛЬТАТАХ ТЕОРИИ ИНФОРМАЦИИ шенные последовательности размещать среди всевозможных случайным обра зом, а в качестве декодирующего подмножества брать 2 ( ) последователь nH X Y ностей высоковероятной группы, соответствующей принятому сигналу. Веро ятность ошибки при этом равна вероятности того, что среди 2 ( ) последова nH X Y тельностей окажется более одной разрешенной. Так как код получается в ре зультате случайного (равновероятного) выбора 2nH последовательностей среди 2 ( ), то вероятность того, что данная последовательность окажется разрешен nH X n H H ( X ) ной, равна 2nH 2 ( ) = 2 nH X.

Средняя вероятность того, что в декодирующем подмножестве из 2 ( ) nH X Y последовательностей имеется только одна разрешенная, выразится соотноше нием { } nH ( X Y ) n H H ( X ) ( 9.6 ) P = 1 2 Это и есть вероятность безошибочного приема. Поскольку H C = H ( X ) H (X Y ), имеем H H ( X ) = H ( X Y ), где 0.

nH ( X Y ) Отсюда (пренебрегая единицей по сравнению с 2 ) находим P = {1 2 n[ H ( X /Y )+ ]} nH ( X / Y ) ( 9.7 ) Логарифмируя и применяя правило Лопиталя, легко показать, что lim P = n, т.е. при кодировании достаточно длинными блоками средняя вероятность ошибки может быть сделана сколь угодно малой. Доказательство завершается утверждением, что существуют коды с вероятностями ошибок меньше средней.

Пропускная способность гауссова канала связи Перейдем теперь к знакомству с основными результатами для систем с не прерывными сигналами. Наиболее известным выводом теории является форму ла для пропускной способности гауссова канала связи.


Гауссовым каналом называется канал связи, для которого выполняются следующие условия:

1) сигналы и шумы в нем непрерывны;

2) канал занимает ограниченную полосу частот шириной F ;

3) шум n ( t ) в канале распределен нормально ("гауссов шум");

4) спектр мощности шума равномерен в полосе частот канала и равен N единиц мощности на единицу полосы частот;

5) средняя мощность полезного сигнала фиксирована и равна P0 ;

6) сигнал и шум статистически независимы;

7) принимаемый сигнал y ( t ) есть сумма полезного сигнала и шума, т.е.

y ( t ) = x ( t ) + n ( t ) — «шум аддитивен».

Эти предположения позволяют вычислить пропускную способность гаус сова канала. Во-первых, ограниченность полосы частот позволяет применить ЧАСТЬ 3. ИНФОРМАЦИОННЫЕ АСПЕКТЫ ИЗУЧЕНИЯ СИСТЕМ теорему отсчетов и вести рассуждения для каждого отсчета в отдельности. Да лее, аддитивность шума и его независимость от X позволяют представить ко личество информации в Y об X в виде I ( X, Y ) = h (Y ) h (Y X ) = h (Y ) h ( X + N X ) = h (Y ) h ( N ), ( 9.8) где h ( N ) — дифференциальная энтропия шума. Следовательно, пропускная способность такова:

C = max h (Y ) h ( N ) { p( x )} Согласно условиям 3) и 4), имеем h ( N ) = F log ( 2 eNF ). ( 9.9 ) В силу условий 4)-7) мощность принимаемого сигнала есть M (Y 2 ) = P0 + nF ( 9.10 ) Максимум h (Y ) при условии ( 9.10 ) достигается в случае нормального распределения, т.е.

max h (Y ) = F log 2 e ( P0 + NF ) ( 9.11) { p( x )} Так как шум имеет равномерный спектр (условие 4) и спектр смеси y ( t ) также равномерен (вследствие независимости отсчетов), то и полезный сигнал должен иметь равномерный спектр. Вводя спектральную плотность P = P0 F и вычитая равенство ( 9.9 ) из ( 9.11), получаем известную формулу Шеннона Таллера C = F log (1 + P N ).

Таким образом, мы не только определили пропускную способность, но и заодно показали, что она реализуется, если полезный сигнал закодировать так, чтобы его спектр был равномерным в представленной полосе частот, а распре деление мгновенных значений — нормальным.

Дальнейшие обобщения связаны с рассмотрением "небелых" сигналов и шумов. Предполагается зависимость от частоты их спектральных мощностей P ( f ) и N ( f ), а также с допущением случайности величины P (например, в случае замирания радиосигналов). Решение возникающих при этом задач мож но найти в литературе по теории информации.

Подведем итог. Теоремы Шеннона о кодировании в каналах без шумов и при наличии шумов, приведенные в данном параграфе относятся к числу ос новных результатов теории информации. Практически самым важным откры тием в теории информации является установленная Шенноном возможность практически безошибочной передачи информации по каналу с шумом со скоро стью, близкой к пропускной способности.

Заключение Отметим, что наиболее важные результаты тории информации — теоремы о кодировании — являются теоремами о существовании и носят асимптотиче ский характер, т.е. не являются конструктивными. Однако уже само знание по тенциальных возможностей имеет огромное значение: сравнение характеристик реальных систем с теоретическими пределами позволяет судить о достигнутом ЛЕКЦИЯ 9. ОБ ОСНОВНЫХ РЕЗУЛЬТАТАХ ТЕОРИИ ИНФОРМАЦИИ уровне и о целесообразности затрат на его повышение. Прикладные же вопросы рассматриваются в специальном разделе теории информации — теории коди рования, которая изучает способы построения конкретных кодов и их свойства.

Для напоминания об основных понятиях теории информации приведем ва риант блок-схемы системы передачи информации (см.рис. 32). На этом рисунке приведено большинство введенных в данной главе понятий и обозначений.

Знание теории информации выходит далеко за рамки теории связи. Имен но ее появление привело к более глубокому пониманию открытых ранее зако номерностей природы, например, второго закона термодинамики. Вместе с тем некоторые специалисты различных отраслей науки некритически распростра няли методы и конкретные результаты теории информации на любые информа ционные процессы в реальном мире. Уже сам Шеннон заметил эту тенденцию и настоятельно предостерегал от того, чтобы ей безоглядно следовать. Дело в том, что шенноновское количество информации является характеристикой, лишь с одной стороны описывающей информационные отношения. Именно эта сторона — соответствие состояний — играет главную роль в технических уст ройствах. Однако в этом соответствии не проявляют себя такие свойства ин формации, как смысл, доброкачественность (степень истинности), ценность, полезность, временное старение, причинно-следственная направленность и т.д, — свойства, весьма существенные для информационных отношений с участием живых организмов, людей, коллективов. К развитию новых подходов в теории информации толкает сильное "внешнее" давление общественной практики.

Масштабы и значение информационных потоков в современном обществе так резко возросли в последние годы, что даже возникло образное выражение "ин формационный взрыв". Появилась новая отрасль — "индустрия обработки дан ных", затраты на которую в промышленно развитых странах превосходят затра ты на энергетику. Этой общественной потребности отвечает и возникновение новой отрасли науки — информатики.

Системный анализ неизбежно выходит на исследование ресурсов (налич ных и необходимых), которые потребуются для решения анализируемой про блемы. При этом информационные ресурсы играют первостепенную роль наря ду с ресурсами материальными, энергетическими, временными, кадровыми.

n (t ) I ( X,Y ) H X Y R C s (t ) y (t ) = s (t ) + n (t ) C = max R Часть 4. ПРИНЯТИЕ РЕШЕНИЙ (ВЫБОР).

Лекция 10. ЯЗЫКИ ОПИСАНИЯ ВЫБОРА Главная цель курса системного анализа — раскрытие системности любой целенаправленной деятельности. Для этого необходимо построить систему мо делей, с помощью которых можно обобщать, передавать и совершенствовать опыт такой деятельности. В предыдущих лекциях мы уже выделили некоторые из операций, входящие во всякую целенаправленную деятельность: моделиро вание, перенос информации во времени и в пространстве, получение новой ин формации. В данном разделе рассмотрим еще одну операцию, обязательно вхо дящую в целенаправленные процессы — выбор.

Выбор как реализация цели. Выбор является действием, придающим всей деятельности целенаправленность. Именно выбор реализует подчинен ность всей деятельности определенной цели или совокупности целей. Рано или поздно наступает момент, когда дальнейшие действия могут быть различными, приводящие к разным результатам, а реализовать можно только одно действие, причем вернуться к ситуации, имевшей место в этот момент времени уже (как правило) нельзя.

Способность сделать правильный выбор в таких условиях — очень ценное качество, которое присуще людям в разной степени. Великие полководцы, вы дающиеся политики, гениальные инженеры и ученые, талантливые админист раторы отличались и отличаются от своих коллег или конкурентов прежде все го умением принимать лучшие решения, делать лучший выбор.

Естественно стремление понять, что такое "хороший выбор", как прибли зиться к наилучшему решению, возможно ли предложить алгоритм получения такого решения. Работа многих исследователей в этом направлении выявила характерную ситуацию: полная формализация нахождения наилучшего реше ния возможна, но лишь для хорошо изученных (хорошо структурированных) задач. Для решения слабо структурированных задач полностью формальных алгоритмов не существует. Современная тенденция практики выбора в естест венных ситуациях состоит в сочетании способности человека решать неформа лизованные задачи с возможностями формальных методов и компьютерного моделирования (например, диалоговые методы поддержки решений, эксперт ные системы, информационно-поисковые системы, системы управления базами данных, автоматизированные системы управления и т.д.).

Задачи выбора чрезвычайно многообразны, различны и методы их реше ния. Прежде всего, введем понятия, общие для всех задач выбора.

Будем представлять принятие решения как действие над множеством аль тернатив, в результате которого получается подмножество выбранных альтер натив. Сужение множества альтернатив возможно, если имеется способ сравне ния альтернатив и определение наиболее предпочтительных. Каждый такой способ называют «критерием предпочтения». Обратим внимание на то, что при таком описании выбора считают сами собой разумеющимися, уже пройденны ми, два чрезвычайно важных этапа системного анализа:

1) порождение множества альтернатив, на котором предстоит осуществ ЛЕКЦИЯ 10. ЯЗЫКИ ОПИСАНИЯ ВЫБОРА лять выбор;

2) определение целей, ради достижения которых производится выбор.

Будем считать, что исходное множество альтернатив уже задано и пресле дуемые нами цели определены настолько детально, что уже имеются критерии оценки и сравнения любых альтернатив.

Множественность задач выбора. Отметим сразу, что проблема выбора далеко нетривиальна и допускает существенно различающиеся математические постановки задач. Дело в том, что каждая компонента ситуации выбора может реализовываться в качественно различных вариантах. Отметим основные их этих вариантов:

• множество альтернатив может быть конечным, счетным или континуальным;

• оценка альтернативы может осуществляться по одному или по нескольким критериям, которые в свою очередь могут иметь как количественный, так и ка чественный характер;

• режим выбора может быть однократным (разовым) или повторяющимся, до пускающим обучение на опыте;

• последствия выбора могут быть точно известны (выбор в условиях определен ности), иметь вероятностный характер, когда известны вероятности возможных исходов после сделанного выбора (выбор в условиях риска), или иметь неодно значный исход, не допускающий введение вероятностей (выбор в условиях не определенности);


• ответственность за выбор может быть односторонней (индивидуальной) или многосторонней. Собственно различают индивидуальный и групповой выбор;

• степень согласованности целей при многостороннем выборе может варьиро ваться от полного совпадения интересов сторон (кооперативный выбор) до их противоположности (выбор в конфликтной ситуации). Возможны также про межуточные случаи, например, компромиссный выбор, коалиционный выбор, выбор в условиях нарастающего конфликта и т.д.

Различные сочетания перечисленных вариантов и приводят к многообраз ным задачам выбора, которые изучены не в одинаковой степени. В данном раз деле лекций дадим краткий обзор состояния теории выбора в настоящее время.

При этом главное внимание будем уделять постановке задач и важным резуль татам и лишь упоминать, какие именно теории дают методы решения.

На примере описания выбора видно, как об одном и том же явлении можно говорить на языках различной общности. К настоящему моменту сложились три основных языка описания выбора. Самым простым и наиболее развитым (и, быть может, поэтому чаще употребляемым) является критериальный язык.

Критериальный язык описания выбора Такое название языка связано с основным предположением, состоящим в том, что каждую отдельно взятую альтернативу можно оценить конкретным числом (значением критерия), и сравнение альтернатив сводится к сравнению соответствующих им чисел.

Пусть x — некоторая альтернатива из множества X. Считается, что для всех x X может быть задана функция q ( x ), которая называется критерием ЧАСТЬ 4. ПРИНЯТИЕ РЕШЕНИЙ (ВЫБОР) (критерием качества, целевой функцией, функцией предпочтения, функцией полезности) и обладает тем свойством, что если альтернатива x1 предпочти тельнее x2 (будем обозначать это x1 x2 ), то q ( x1 ) q ( x2 ) и обратно. Если те перь сделать еще одно важное предположение, что выбор любой альтернативы приводит к однозначно известным последствиям (т.е. считать, что выбор осу ществляется в условиях определенности) и заданный критерий q ( x ) численно выражает оценку этих последствий, то наилучшей альтернативой x* является, естественно, та, которая обладает наибольшим значением критерия:

x* = arg max q ( x ) (10.1) xX Задача отыскания x, простая по постановке, часто оказывается сложной * для решения, поскольку метод ее решения определяется как характером множе ства X, так и характером критерия q ( x ).

Чаще всего на практике оценивание любого варианта единственным чис лом оказывается неприемлемым упрощением. Более полное рассмотрение аль тернатив приводит к необходимости оценивать их не по одному, а по несколь ким критериям, качественно различающимся между собой. Например, при вы боре конструкции самолета проектировщикам следует учитывать множество критериев: технических, технологических, экономических, социальных, эрго номических и пр. Даже в обычной жизни при выборе мы почти никогда не ис пользуем единственный критерий: вспомним хотя бы затруднения при выборе подарка ко дню рождения или при выборе места стоянки в турпоходе.

Сведение многокритериальной задачи к однокритериальной. Итак, пусть для оценивания альтернатив используется несколько критериев qi ( x ), i = 1,..., p. Как же тогда осуществлять выбор? Рассмотрим наиболее употреби тельные способы решения многокритериальных задач. Первый способ состоит в том, чтобы многокритериальную задачу свести к однокритериальной. Это оз начает введение суперкритерия, т.е. скалярной функции векторного аргумента:

q0 ( x ) = q0 q1 ( x ), q2 ( x ),..., q p ( x ) (10.2 ) Суперкритерий позволяет упорядочить альтернативы по величине q0, вы делив тем самым наилучшую (в смысле этого критерия). Вид функции q0 опре деляется тем, как мы представляем себе вклад каждого критерия в суперкрите рий. Обычно используют аддитивные или мультипликативные функции:

p q0 = { i qi si } (10.3) i = p 1 q0 = {1 i qi si } (10.4 ) i = Коэффициенты si обеспечивают, во-первых, безразмерность числа qi si (частные критерии могут иметь разную размерность) и, во-вторых, в необходи мых случаях (как в формуле (10.4 ) ) выполнения условия i qi si 1. Коэффици енты i и i отражают относительный вклад частных критериев в суперкрите ЛЕКЦИЯ 10. ЯЗЫКИ ОПИСАНИЯ ВЫБОРА рий.

Итак, при данном способе задача сводится к максимизации суперкритерия:

x* = arg max q0 q1 ( x ),...,q p ( x ) (10.5 ) xX Очевидные достоинства объединения нескольких критериев в один супер критерий сопровождаются рядом трудностей и недостатков, которые необхо димо учитывать при использовании этого метода. Оставив в стороне трудности построения самой функции и вычислительные трудности ее максимизации, об ратим внимание на следующий очень важный момент. Упорядочение точек в многомерном пространстве в принципе не может быть однозначным и полно стью определяется видом упорядочивающей функции. Суперкритерий играет роль этой упорядочивающей функции, и его даже "небольшое" изменение мо жет привести к тому, что оптимальная в новом смысле альтернатива окажется очень сильно отличающейся от старой.

Условная максимизация. Недостатки свертывания нескольких критериев заставляют искать другие подходы к решению задач многокритериального вы бора. Рассмотрим второй способ решения таких задач. Он заключается в ис пользовании того факта, что частные критерии обычно неравнозначны между собой. Наиболее явное выражение этой идеи состоит в выделении основного, главного критерия и рассмотрении остальных как дополнительных, сопутст вующих. Такое различие критериев позволяет сформулировать задачу выбора как задачу нахождения условного экстремума основного критерия:

x* = arg max q1 ( x ) qi ( x ) = Ci,i = 2,3,..., p (10.6 ) xX при условии, что дополнительные критерии остаются на заданных им уровнях.

В некоторых задачах оказывается возможным или даже необходимым за давать ограничения на сопутствующие критерии не столь жестко, как в задаче (10.6 ). Например, если сопутствующий критерий характеризует стоимость за трат, то вместо фиксации затрат разумнее задавать их верхний уровень, т.е.

формулировать задачу с ограничениями типа неравенств:

x* = arg max q1 ( x ) qi ( x ) Ci,i = 2,3,..., p (10.7 ) xX Отметим, что такое, казалось бы, незначительное изменение постановки задачи требует принципиально иных методов ее решения.

Поиск альтернативы с заданными свойствами. Третий способ много критериального выбора относится к случаю, когда заранее могут быть указаны значения частных критериев (или их границы). Задача состоит в том, чтобы найти альтернативу, удовлетворяющую этим требованиям, либо, установив, что такая альтернатива во множестве X отсутствует, найти в X альтернативу, ко торая подходит к поставленным целям ближе всего.

Удобным свойством является возможность задавать желательные значения qi критериев так точно, как и в виде верхних или нижних границ. Назначаемые * значения величин qi* иногда называют уровнями притяжения, а точки их пере сечения в p-мерном пространстве критериев — целью или опорной точкой.

Теперь идея оптимизации состоит в том, чтобы, начав с любой альтернати ЧАСТЬ 4. ПРИНЯТИЕ РЕШЕНИЙ (ВЫБОР) вы, приближаться к x* по некоторой траектории в пространстве X.

Это достигается введением числовой меры близости между очередной аль тернативой x и целью x*, т.е. между векторами q ( x ) = [ q1 ( x),..., q p ( x )] и q* ( x) = [q1* ( x ),..., q p* ( x)]. Можно по-разному количественно писать эту близость, что и определяет методы решения задачи.

Нахождение паретовского множества. Четвертый полностью формали зуемый способ многокритериального выбора состоит в отказе от выделения единственной "наилучшей" альтернативы и соглашении о том, что предпочте ние одной альтернативе перед другой можно отдавать, только если первая по всем критериям лучше второй. Если же предпочтение хотя бы по одному кри терию расходится с предпочтением по другому, то такие альтернативы призна ются несравнимыми. В результате попарного сравнения альтернатив все худ шие по всем критериям альтернативы отбрасываются, а все оставшиеся несрав нимые между собой принимаются. Если все максимально достижимые значе ния частных критериев не относятся к одной и той же альтернативе, то приня тые альтернативы образуют множество Парето и выбор на этом заканчивается.

При необходимости же выбора единственной альтернативы следует привлекать дополнительные соображения: вводить новые добавочные критерии и ограни чения, бросить жребий, либо прибегать к услугам экспертов.

Мы обсудили наиболее употребительные способы описания выбора в тер минах критериального языка. Возможны и другие постановки задач на этом языке;

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

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

Описание выбора на языке бинарных отношений Второй, более общий язык, на котором описывается выбор, — это язык бинарных отношений. Его большая, нежели у критериального языка, общность основана на учете того факта, что в реальности дать оценку отдельно взятой альтернативе часто затруднительно или невозможно. Однако, если рассматри вать альтернативу не в отдельности, а в паре с другой, то находятся основания сказать, какая из них более предпочтительна. Таким образом, основные пред положения этого языка сводятся к следующему:

1) отдельная альтернатива не оценивается, т.е. критериальная функция не вводится;

2) для каждой пары альтернатив ( x, y ) некоторым образом можно устано вить, что одна из них предпочтительнее другой либо они равноценны или не сравнимы (чаще всего последние два понятия отождествляются);

ЛЕКЦИЯ 10. ЯЗЫКИ ОПИСАНИЯ ВЫБОРА 3) отношение предпочтения внутри любой пары альтернатив не зависит от остальных альтернатив, предъявленных к выбору.

Математически бинарное отношение R на множестве X определяется как определенное подмножество упорядоченных пар ( x, y ). Удобно использовать обозначение xRy, если x находится в отношении R c y, и xRy в противном случае. Множество всех пар {( x, y ), x, y X } называется полным ("универсаль ным") бинарным отношением. Поскольку в общем случае не все возможные пары ( x, y ) удовлетворяют условиям, накладываемым отношением R, бинар ное отношение является некоторым подмножеством полного бинарного отно шения, т.е. R X X.

Задать отношение — это значит тем или иным способом указать все пары ( x, y ), для которых выполнено отношение R.

Способы задания бинарных отношений. Существует четыре разных спо соба задания отношений, а преимущества каждого проявляются при разных ха рактеристиках множества X.

Первый, очевидный, способ состоит в непосредственном перечислении та ких пар. Ясно, что он приемлем лишь в случае конечного множества R. Второй удобный способ задания отношения R на конечном множестве — матричный.

Все элементы нумеруются, и матрица отношения R определяется своими эле { } ментами rij ( R ) = 1: xi Rx j ;

0 : xi Rx j для всех i и j. Известным примером такого задания отношений являются турнирные таблицы (если ничьи обозначить ну лями, как и проигрыш, то матрица изобразит отношение " xi - победитель x j ").

Третий способ — задание отношения графом. Вершинам графа G ( R) ста вят в соответствия (пронумерованные) элементы множества X, и если xi Ry j, то от вершины xi проводят направленную дугу к вершине x j ;

если же xi Ry j, то дуга отсутствует.

Для определения отношений на бесконечных множествах альтернатив ис пользуется четвертый способ — задание отношения R — сечениями. Множе ство R + ( x ) = { y X ( y, x ) R} называется верхним сечением отношения R, а множество R ( x ) = { y X ( y, x ) R} — нижним сечением. Иначе говоря, верх нее сечение — это множество всех y X, которые находятся в отношении xRy с заданным элементом x X, а нижнее сечение — множество всех y X, с ко торыми заданный элемент x находится в отношении R. Отношение однознач но определяется одним из своих сечений.

Подведем итог. В ряде практических случаев критериальная функция не существует, т.е. оценку данной альтернативе можно дать только в результате ее сравнения с другой альтернативой. Это потребовало более общего описания выбора. Первым таким обобщением и является язык бинарных отношений.

Некоторые особенности выбора привели к построению третьего, еще более общего языка его описания — «языка функций выбора». Во-первых, нередко приходится сталкиваться с ситуациями, когда предпочтение между двумя аль ЧАСТЬ 4. ПРИНЯТИЕ РЕШЕНИЙ (ВЫБОР) тернативами зависит от остальных альтернатив. Например, предпочтение поку пателя между чайником и кофеваркой может зависеть от наличия в продаже кофемолки. Во-вторых, возможны такие ситуации выбора, когда понятие пред почтения вообще лишено смысла. Например, по отношению к множеству аль тернатив довольно обычными являются правила выбора «типичного», выбора «среднего», выбора «наиболее отличного, оригинального», теряющие смысл в случае двух альтернатив. Язык функций выбора является весьма общим и по тенциально может описывать любой выбор. Однако его теория находится в на чальной стадии развития и пока еще занимается описанием преимущественно старых ситуаций в новых терминах. Знакомство с языком функций выбора вы ходит за рамки настоящего курса лекций.

Лекция 11. ВЫБОР В УСЛОВИЯХ СТАТИСТИЧЕСКОЙ НЕОПРЕДЕЛЕННО СТИ Существует класс задач выбора, особенностью которых является наличие неопределенности даже после того, как проведена серия наблюдений, измере ний. Дело в том, что данные, полученные в результате эксперимента, связаны с интересующим нас аспектом явления не непосредственно, не однозначно, а в совокупности с другими, неконтролируемыми факторами.

Статистические решения как выбор. Пусть, например, требуется знать высокоточное значение веса некоторого предмета. Неоднократное его взвеши вание на аналитических весах дает хотя и близкие, но разные значения. На по казания весов оказывают внимание не только вес самого предмета, но и трение, не идеальность геометрической формы опорной призмы, воздушная турбулент ность, тепловой режим и пр. При радиолокационном зондировании Луны мы будем так же за каждым разом получать различные расстояния до нее, чему имеется множество причин.

Аналогичная ситуация — выбор в условиях статистической неопределен ности — имеет место не только при оценке некоторой величины, но и при клас сификации объектов, при необходимости подобрать математическую модель явления, или обнаружить некую закономерность и пр.

Во всех таких задачах есть общее — необходимость выбора на основании косвенных или прямых, но обязательно "зашумленных" данных. Основным, центральным, самым важным предположением для формализации решения та ких задач является предположение о статистичности экспериментальных дан ных. Оно состоит в том, что связь между истинной, но неизвестной искомой альтернативой w и наблюдаемыми данными x1, x2,..., xn адекватно описывается распределением вероятностей F ( x1, x2,..., xN w ) или плотностью вероятностей f ( x1, x2,..., xN w ). Считается, что любая закономерность w, отыскиваемая в протоколе наблюдений, принадлежит множеству W возможных закономерно стей, на котором и надо сделать выбор. Другими словами, считается, что во-первых, выборка наблюдений принадлежит статистическому ансамблю всевозможных выборок, на котором задано распределение вероятностей, и, во-вторых, это распределение различно для разных w, что и обеспечивает наличие информации о w в выборке x1, x2,..., xN.

Вопрос состоит в том, как извлечь эту информацию, т.е. как сделать выбор на множестве W или как принять статистическое решение.

Общая схема принятия статистических решений. Рассмотрим общие черты для задач выбора в условиях статистической неопределенности. Обстоя тельства принятия статистических решений иллюстрирует схема, приведенная на рисунке 33.

На этой схеме точкой w W изображено то, что нам неизвестно, но необ ходимо определить;

W — множество всех предполагаемых возможностей от носительно w.

x X Точкой изображена выборка наблюдений) (протокол ЧАСТЬ 4. ПРИНЯТИЕ РЕШЕНИЙ (ВЫБОР) x = ( x1, x2,..., xN ) ;

X — множество всех возможных выборок.

Тот факт, что на реализовавшееся значение выборки оказывает влияние не только искомая закономерность w, но и совокупность случайных факторов, изображен на схеме как результат совместного отображения w и некоторого случайного воздействия n в пространство X с помощью некоторого оператора µ : x = µ ( w, n ).

w x µ ( w, n ) ( x, i ) X W Зная x, мы должны теперь сделать выбор относительно w, принять реше ние, какую из множества альтернатив W мы примем за истинную. Чтобы не путать принимаемое решение и "истинное" состояние w, обозначим простран ство, на котором производится выбор, через. Очевидно, что в входят все элементы множества W, но могут быть и дополнительные решения (типа отка за от выбора, увеличить число наблюдений и др.).

Процедура выбора изображена как действие некоторого оператора над выборкой x : каждой выборке x этот оператор, называемый решающей функ цией, ставит в соответствие решение = ( x, i ). Здесь аргумент i введен, - во-первых, для того, чтобы подчеркнуть, что одну и ту же выборку мож но обрабатывать по-разному, получая решения различного качества, и, - во-вторых, чтобы сделать акцент на том, что качество решения зависит не только от того, какой протокол обрабатывается, но и от того, какие априорные предположения вошли в структуру алгоритма.

Проблема синтеза статистических процедур (построения решающих функ ций) и проблема анализа их качества (оценивание степени близости между и w ) тесно связаны с ролью априорной информации.

Определим конкретнее, что именно в статистике понимается под априор ной информацией. В нее включают любые сведения, имеющиеся до того, как мы приступили к синтезу новой процедуры, в том числе и любую информа цию о природе наблюдений (но не саму выборку x, считающуюся информаци ей апостериорной). Конкретнее априорные сведения характеризуют:

1) пространство ситуаций W ;

2) природу случайных факторов n ;

3) оператор µ, определяющий характер взаимодействия w и n ;

4) пространство наблюдений X ;

5) требования потребителя к качеству решений. Нумерация та же, что и на рисунке.

Понятие об основных направлениях математической статистики.

ЛЕКЦИЯ 11. ВЫБОР В УСЛОВИЯХ СТАТИСТИЧЕСКОЙ НЕОПРЕДЕЛЕННОСТИ Априорная информация может быть более или менее полной;

в зависимо сти от этого по-разному ставятся и решаются статистические задачи выбора.

Можно даже утверждать, что разным уровням априорной информации соответ ствуют различные специфические ветви математической статистики.

Самое полное описание случайного объекта состоит в задании распределе ния вероятностей на множестве возможных состояний этого объекта. Поэтому наиболее подробное и полное задание априорной информации состоит в том, что считаются известными:

1) распределение P ( w ), w W ;

2) условное распределение выборочных значений F ( x w ), x X, w W ;

3) функция потерь L (, w ), выражающая отношение потребителя решений к расхождению между, т.е. тем, что он должен использовать вместо истинно го w, и действительным состоянием w.



Pages:     | 1 | 2 || 4 | 5 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.