Задача

Даны два вектора a = (a0, a1, ..., an1) и b = (b0, b1, ..., bn1). Существует много стан- дартных способов их объединения: например, вычисление суммы с получением вектора a + b = (a0 + b0, a1 + b1, ..., an1 + bn1) или вычисление скалярного произве- дения в форме вещественного числа a · b = a0b0 + a1b1 + ...
+ an1bn1. (По причинам, которые вскоре станут ясны, векторы в этом разделе удобнее записывать с коор- динатами, которые индексируются с 0, а не с 1.)

Один из способов объединения векторов, находящий очень важные практиче- ские применения (хотя и не всегда упоминаемый во вводном курсе линейной алге- бры), — свертка a * b. Свертка двух векторов длины n (таких, как a и b) представляет собой вектор с 2n - 1 координатами, в котором координата k равна

Другими словами,




Координаты вектора свертки вычисляются суммированием по диагоналям.

Стоит отметить, что, в отличие от векторной суммы и скалярного произведения, свертка легко обобщается на векторы разной длины a = (a0, av ..., am1) и b = (b0, bv ..., bn1). В этом более общем случае a * b определяется как вектор с m + n - 1 координатами, в котором координата к равна


И снова можно представить происходящее с помощью матрицы произведений ab; матрица стала прямоугольной, но координаты по-прежнему могут вычисляться суммированием по диагоналям. (В дальнейшем условие i < m, j < n в сверточном суммировании явно упоминаться не будут, посколько из контекста понятно, что сумма может вычисляться только по определенным элементам.)

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

♦ Первый пример (который также доказывает, что свертка уже встречалась нам в старших классах школы, хотя и неявно) — умножение многочленов. Любой многочлен A(x) = a0 + a1x + a2x2 + ... am1xm-1 может быть естественно представлен в виде вектора коэффициентов a = (a0, a1, ..., am1). Теперь для двух многочленов A(x) = a0 + a1x + a2x2 + ... am1xm-1 и B(x) = b0 + b1x + b2x2 + ... bn1xn-1 рассмотрим многочлен С(x) = А(x)В(x), равный их произведению. В многочлене С(x) коэф- фициент при члене xк равен

Иначе говоря, вектор коэффициентов С(x) вычисляется как свертка векторов коэффициентов A(x) и B(x).

♦ Пожалуй, самое важное практическое применение сверток лежит в области обработки сигналов. Эта тема сама по себе заслуживает отдельного учебного

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


Допустим, имеется вектор a = (a0, av ..., am1), который представляет серию изме- рений (температура, данные биржевых котировок и т. д.), зафиксированных в m последовательных временных точках. Такие серии часто содержат высокий уро- вень шума из-за ошибок измерения или случайных отклонений, поэтому к ним часто применяется операция «сглаживания»: каждое значение a усредняется со взвешенной суммой соседей на к позиций слева и справа в последовательности; весовые коэффициенты быстро убывают при увеличении расстояния от a. На- пример, при гауссовом сглаживании ai заменяется на

с некоторым параметром «ширины» к и значением Z, выбранным просто для нормализации суммы весов в среднем до 1. Существуют некоторые проблемы с граничными условиями (например, что делать, если i - к < 0 или i + к > m?), но они могут решаться игнорированием первых и последних к элементов из сглаженного сигнала или масштабированием по другой схеме, компенсирую- щей недостающие элементы.


Чтобы понять, как это связано с операцией свертки, можно рассматривать опе- рацию сглаживания следующим образом. Сначала определяется «маска»

гауссова сглаживания). Затем маска последовательно позиционируется так, чтобы она была совмещена по центру с каждой возможной точкой в серии a; для каждого варианта позиционирования вычисляется взвешенное среднее. Иначе говоря, а заменяется на

Последнее выражение фактически является сверткой; чтобы это стало оче- видно, нужно лишь немного изменить запись. Определим b = (bQ, b{, ..., й), где ⅛ = . Нетрудно убедиться в том, что с этим определением сглаженное

значение вычисляется в виде


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

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

цией о ежегодном доходе всех мужчин и женщин в выборке. Нужно построить новую гистограмму, где для каждого к будет отображаться количество пар (M, W), для которых у мужчины M и женщины W суммарный доход составляет к. Задача представляет собой свертку. Первую гистограмму можно записать в виде вектора а = (a0, ..., am1), который показывает, что существуют а мужчин с ежегодным доходом, равным i. Аналогичным образом вторая гистограмма за- писывается в виде вектора b = (b0, ..., bn1). Введем обозначение ck для количества пар (m, w) с суммарным доходом k; это количество способов, которыми можно выбрать мужчину с доходом а. и женщину с доходом b. для любой пары (i, j) с i + j = к. Другими словами,

так что объединенная гистограмма c = (c0, ..., cm+n_2) представляет собой про- стую свертку а и b. (С использованием вероятностной терминологии, которая будет раскрыта в главе 13, этот пример может рассматриваться как применение свертки в качестве способа вычисления распределения суммы двух независимых случайных переменных.)

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ