Кандаминимум 010109 - ответы доп.специальности (Дедус) — различия между версиями

Материал из YourcmcWiki
Перейти к: навигация, поиск
(Равенство Ляпунова-Стеклова. Равенство Парсеваля. Свойство жёсткости разложения)
м
 
(не показано 9 промежуточных версий этого же участника)
Строка 3: Строка 3:
 
== Метод наименьших квадратов ==
 
== Метод наименьших квадратов ==
  
* Также см. [[mlwiki:Метод наименьших квадратов]].
+
* Также см. [[machinelearning:Метод наименьших квадратов]].
 
* Задача — построение регрессий / аналитических описаний каких-то измерений. МНК — минимизация квадрата отклонения значений, вычисленных аналитически, от экспериментальных значений.
 
* Задача — построение регрессий / аналитических описаний каких-то измерений. МНК — минимизация квадрата отклонения значений, вычисленных аналитически, от экспериментальных значений.
 
* Приходит к решению <m>A^TAw=A^Ty</m>, то есть <m>w=(A^TA)^{-1}(A^Ty)</m>.
 
* Приходит к решению <m>A^TAw=A^Ty</m>, то есть <m>w=(A^TA)^{-1}(A^Ty)</m>.
* Есть проблемы в случае плохой обусловленности матрицы, нужно юзать [[mlwiki:Сингулярное разложение]].
+
* Есть проблемы в случае плохой обусловленности матрицы, нужно юзать [[machinelearning:Сингулярное разложение]].
 
* И, что важно (!) Если просто <m>x^k</m>, то при увеличении точности нужно пересчитывать все коэффициенты.
 
* И, что важно (!) Если просто <m>x^k</m>, то при увеличении точности нужно пересчитывать все коэффициенты.
  
Строка 22: Строка 22:
  
 
== Классические ортогональные базисы. Их основные свойства ==
 
== Классические ортогональные базисы. Их основные свойства ==
 +
 +
* Определяются одним из 3-х свойств:
 +
** Их производные также образуют ортогональную систему.
 +
** Удовлетворяют гипергеометрическому дифуру.
 +
** Обобщённая формула Родрига: <m>\phi_n(x) = \frac{1}{K_n \rho(x)}\frac{d^n(\rho(x)X^n)}{dx^n}</m>.
 +
* Также для них есть рекуррентные соотношения, связывающие 3 любые последовательных функции.
 +
* Базисы:
 +
# [-1; 1]. Якоби — с весовой функцией <m>\rho(x) = (1-x)^\alpha (1+x)^\beta</m>.
 +
#* Гегенбауэра: &alpha; = &beta; = &lambda; — 0.5.
 +
#** Чебышева I рода: &lambda; = 0.
 +
#** Чебышева II рода: &lambda; = 1.
 +
#** Лежандра: &lambda; = 0.5 (весовая функция = 1).
 +
# (0; +&infin;) Сонина-Лагерра: <m>\rho(x) = x^\alpha e^{-x}</m>
 +
#* Лагерра: &alpha; = 0.
 +
# (-&infin;; +&infin;) Эрмита: <m>\rho(x) = e^{-x²}</m>
  
 
== Вычисление коэффициентов разложения. Роль квадратурных формул Гаусса ==
 
== Вычисление коэффициентов разложения. Роль квадратурных формул Гаусса ==
 +
 +
* Можно почитать [[rupedia:Численное интегрирование#Метод Гаусса]].
 +
* В книжке Дедуса стр. 59.
 +
* Квадратуры Гаусса по k точкам точны для полиномов степени не выше 2k-1.
 +
* Узлы = корням полинома p<sub>k</sub>(x), соответствующего заданной весовой функции.
 +
* Веса находятся по формулам…
 +
* Роль: позволяют классической ОНС непрерывного аргумента сопоставить ОНС дискретного аргумента.
  
 
== Оператор умножения на функцию. Деление сигналов ==
 
== Оператор умножения на функцию. Деление сигналов ==
 +
 +
* Идея — вычислить коэффициенты ряда произведения функций, не вычисляя само произведение: <br /> <m>c_k = \sum_{0}^{N-1} \sum_{0}^{N-1} \delta_{ijk} a_i b_j</m>, где <m>\delta_{ijk} = \int \psi_i(x)\psi_j(x)\psi_k(x)\rho(x)dx</m>
 +
* В матричной форме c = Ba, B — оператор умножения на b.
 +
* Деление: a = B<sup>-1</sup>c(x) — обратная задача.
 +
* '''Утв.''' Матрица оператора умножения симметрична.
 +
* '''Утв.''' Матрица оператора положительно определена, если функция b положительна.
 +
* '''Утв.''' Макс. и мин. с.з. оператора ограничены по модулю макс. и мин. функции b.
  
 
== Алгебра спектральных преобразований. Использование рекуррентных соотношений ==
 
== Алгебра спектральных преобразований. Использование рекуррентных соотношений ==
 +
 +
* По ходу, имеется ввиду диссер Руслануса: {{Скачать|Тетуев Р.К. - Алгебра спектральных преобразований в задачах обработки данных.pdf}}.
 +
* '''Т.''' Если A — линейный оператор и существуют рекуррентные соотношения для A(всех базисных функций) относительно A(предыдущих базисных функций) и самих базисных функций, существует алгоритм линейной сложности для вычисления A(f).
 +
* Рассматриваются операторы интегрирования, дифференцирования, умножения на x, деления на x.
 +
* Плюс метод «каскада и диффузии» — рекуррентное соотношение разделяется на два — относительно A(предыдущих базисных функций) и относительно самих базисных функций.
  
 
== Использование соотношений в пространстве коэффициентов разложения для распознавания образов и анализа сцен ==
 
== Использование соотношений в пространстве коэффициентов разложения для распознавания образов и анализа сцен ==
 +
 +
* Тоже можно почитать Руслануса.
 +
* Контуры, векторизация, инварианты — площадь ограниченная контуром, периметр контура, аффинная длина дуги кривой.
 +
* Короче, ''генерация признаков''.
  
 
== Интегральные оценки сигналов. Коэффициент формы сигнала ==
 
== Интегральные оценки сигналов. Коэффициент формы сигнала ==
 +
 +
* Фактически идея — величина проекции функции на некоторую другую, то есть скалярное произведение.
 +
* Коэффициент формы — интегральная инвариантная к длительности оценка.<br /><m>K_i = \frac{\int_{0}^{T}x(t)h(t)dt}{\int_{0}^{T}x(t)g(t)dt}</m>
 +
* Можно напридумывать много:
 +
* Степенной: <m>h(t) = (T-t)^i, g(t) = t^i</m>.
 +
* Параболический: <m>h(t)=(2t-T)^{2}, g(t)=4t(T-t)</m>.
 +
* Экспоненциальный: <m>h(t)=e^{-at}, g(t)=e^{-a(T-t)}</m>.
  
 
== Интегральное преобразование Фурье. Собственные функции ==
 
== Интегральное преобразование Фурье. Собственные функции ==
 +
 +
* Можно почитать [[rupedia:Преобразование Фурье]] и ещё лучше — [[wikipedia:Fourier transform]]. <br /> <m>\hat{f}(\omega)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}f(x)e^{-ix\omega}\,dx</m>
 +
* Собственные функции преобразования Фурье образуют ортонормированную систему функций Эрмита — см. [[wikipedia:Fourier transform#Eigenfunctions]], а собственные значения равны (-i)<sup>n</sup>.
  
 
[[Категория:Кандаминимум]]
 
[[Категория:Кандаминимум]]

Текущая версия на 00:35, 3 апреля 2011

Берётся в основном из книжки Дедуса Дедус - Классические ортогональные базисы в задачах аналитического описания и обработки информационных сигналов.pdf (application/pdf, 1,9 МБ).

Метод наименьших квадратов

  • Также см. machinelearning:Метод наименьших квадратов.
  • Задача — построение регрессий / аналитических описаний каких-то измерений. МНК — минимизация квадрата отклонения значений, вычисленных аналитически, от экспериментальных значений.
  • Приходит к решению , то есть .
  • Есть проблемы в случае плохой обусловленности матрицы, нужно юзать machinelearning:Сингулярное разложение.
  • И, что важно (!) Если просто , то при увеличении точности нужно пересчитывать все коэффициенты.

Спектральная реализация метода наименьших квадратов

  • Чебышев решил использовать при разложении системы ортогональных функций — тогда коэффициенты пересчитывать не нужно, это будут просто коэф. ряда Фурье (скалярные произведения на функции базиса).
  • Опр. L2, скалярное произведение, ортогональные функции, полная система, замкнутая система, ряд Фурье.
  • Т. (Фурье) конечный отрезок ряда Фурье осуществляет наилучшее приближение.

Равенство Ляпунова-Стеклова. Равенство Парсеваля. Свойство жёсткости разложения

  • Неравенство Бесселя:
    .
    В пределе при для полных систем переходит в
    равенство Парсеваля: , где cn — коэффициенты ряда Фурье функции f.
  • Равенство Ляпунова-Стеклова = равенство Парсеваля в пространстве функций.
  • Свойство жёсткости разложения — как раз то, что пересчитывать коэффициенты при увеличении точности не нужно.

Классические ортогональные базисы. Их основные свойства

  • Определяются одним из 3-х свойств:
    • Их производные также образуют ортогональную систему.
    • Удовлетворяют гипергеометрическому дифуру.
    • Обобщённая формула Родрига: .
  • Также для них есть рекуррентные соотношения, связывающие 3 любые последовательных функции.
  • Базисы:
  1. [-1; 1]. Якоби — с весовой функцией .
    • Гегенбауэра: α = β = λ — 0.5.
      • Чебышева I рода: λ = 0.
      • Чебышева II рода: λ = 1.
      • Лежандра: λ = 0.5 (весовая функция = 1).
  2. (0; +∞) Сонина-Лагерра:
    • Лагерра: α = 0.
  3. (-∞; +∞) Эрмита:

Вычисление коэффициентов разложения. Роль квадратурных формул Гаусса

  • Можно почитать rupedia:Численное интегрирование#Метод Гаусса.
  • В книжке Дедуса стр. 59.
  • Квадратуры Гаусса по k точкам точны для полиномов степени не выше 2k-1.
  • Узлы = корням полинома pk(x), соответствующего заданной весовой функции.
  • Веса находятся по формулам…
  • Роль: позволяют классической ОНС непрерывного аргумента сопоставить ОНС дискретного аргумента.

Оператор умножения на функцию. Деление сигналов

  • Идея — вычислить коэффициенты ряда произведения функций, не вычисляя само произведение:
    , где
  • В матричной форме c = Ba, B — оператор умножения на b.
  • Деление: a = B-1c(x) — обратная задача.
  • Утв. Матрица оператора умножения симметрична.
  • Утв. Матрица оператора положительно определена, если функция b положительна.
  • Утв. Макс. и мин. с.з. оператора ограничены по модулю макс. и мин. функции b.

Алгебра спектральных преобразований. Использование рекуррентных соотношений

  • По ходу, имеется ввиду диссер Руслануса: Тетуев Р.К. - Алгебра спектральных преобразований в задачах обработки данных.pdf (application/pdf, 2,19 МБ).
  • Т. Если A — линейный оператор и существуют рекуррентные соотношения для A(всех базисных функций) относительно A(предыдущих базисных функций) и самих базисных функций, существует алгоритм линейной сложности для вычисления A(f).
  • Рассматриваются операторы интегрирования, дифференцирования, умножения на x, деления на x.
  • Плюс метод «каскада и диффузии» — рекуррентное соотношение разделяется на два — относительно A(предыдущих базисных функций) и относительно самих базисных функций.

Использование соотношений в пространстве коэффициентов разложения для распознавания образов и анализа сцен

  • Тоже можно почитать Руслануса.
  • Контуры, векторизация, инварианты — площадь ограниченная контуром, периметр контура, аффинная длина дуги кривой.
  • Короче, генерация признаков.

Интегральные оценки сигналов. Коэффициент формы сигнала

  • Фактически идея — величина проекции функции на некоторую другую, то есть скалярное произведение.
  • Коэффициент формы — интегральная инвариантная к длительности оценка.
  • Можно напридумывать много:
  • Степенной: .
  • Параболический: .
  • Экспоненциальный: .

Интегральное преобразование Фурье. Собственные функции