Кандаминимум 010109 - ответы доп.специальности (Дедус) — различия между версиями
Материал из YourcmcWiki
м |
|||
| (не показано 13 промежуточных версий этого же участника) | |||
| Строка 2: | Строка 2: | ||
== Метод наименьших квадратов == | == Метод наименьших квадратов == | ||
| + | |||
| + | * Также см. [[machinelearning:Метод наименьших квадратов]]. | ||
| + | * Задача — построение регрессий / аналитических описаний каких-то измерений. МНК — минимизация квадрата отклонения значений, вычисленных аналитически, от экспериментальных значений. | ||
| + | * Приходит к решению <m>A^TAw=A^Ty</m>, то есть <m>w=(A^TA)^{-1}(A^Ty)</m>. | ||
| + | * Есть проблемы в случае плохой обусловленности матрицы, нужно юзать [[machinelearning:Сингулярное разложение]]. | ||
| + | * И, что важно (!) Если просто <m>x^k</m>, то при увеличении точности нужно пересчитывать все коэффициенты. | ||
== Спектральная реализация метода наименьших квадратов == | == Спектральная реализация метода наименьших квадратов == | ||
| + | |||
| + | * Чебышев решил использовать при разложении системы ортогональных функций — тогда коэффициенты пересчитывать не нужно, это будут просто коэф. ряда Фурье (скалярные произведения на функции базиса). | ||
| + | * '''Опр.''' L<sub>2</sub>, скалярное произведение, ортогональные функции, полная система, замкнутая система, ряд Фурье. | ||
| + | * '''Т.''' (Фурье) конечный отрезок ряда Фурье осуществляет наилучшее приближение. | ||
== Равенство Ляпунова-Стеклова. Равенство Парсеваля. Свойство жёсткости разложения == | == Равенство Ляпунова-Стеклова. Равенство Парсеваля. Свойство жёсткости разложения == | ||
| + | |||
| + | * Неравенство Бесселя: <br /> <m>\sum_{n=1}^{N}|c_n|² \le \|f\|²</m>. <br /> В пределе при <m>N \to \infty</m> для полных систем переходит в <br />равенство Парсеваля: <m>\sum_{n=1}^{\infty}|c_n|² \le \|f\|²</m>, где c<sub>n</sub> — коэффициенты ряда Фурье функции f. | ||
| + | * Равенство Ляпунова-Стеклова = равенство Парсеваля в пространстве функций. | ||
| + | * Свойство жёсткости разложения — как раз то, что пересчитывать коэффициенты при увеличении точности не нужно. | ||
== Классические ортогональные базисы. Их основные свойства == | == Классические ортогональные базисы. Их основные свойства == | ||
| + | |||
| + | * Определяются одним из 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>. | ||
| + | #* Гегенбауэра: α = β = λ — 0.5. | ||
| + | #** Чебышева I рода: λ = 0. | ||
| + | #** Чебышева II рода: λ = 1. | ||
| + | #** Лежандра: λ = 0.5 (весовая функция = 1). | ||
| + | # (0; +∞) Сонина-Лагерра: <m>\rho(x) = x^\alpha e^{-x}</m> | ||
| + | #* Лагерра: α = 0. | ||
| + | # (-∞; +∞) Эрмита: <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 МБ).
Содержание
- 1 Метод наименьших квадратов
- 2 Спектральная реализация метода наименьших квадратов
- 3 Равенство Ляпунова-Стеклова. Равенство Парсеваля. Свойство жёсткости разложения
- 4 Классические ортогональные базисы. Их основные свойства
- 5 Вычисление коэффициентов разложения. Роль квадратурных формул Гаусса
- 6 Оператор умножения на функцию. Деление сигналов
- 7 Алгебра спектральных преобразований. Использование рекуррентных соотношений
- 8 Использование соотношений в пространстве коэффициентов разложения для распознавания образов и анализа сцен
- 9 Интегральные оценки сигналов. Коэффициент формы сигнала
- 10 Интегральное преобразование Фурье. Собственные функции
Метод наименьших квадратов
- Также см. machinelearning:Метод наименьших квадратов.
- Задача — построение регрессий / аналитических описаний каких-то измерений. МНК — минимизация квадрата отклонения значений, вычисленных аналитически, от экспериментальных значений.
- Приходит к решению , то есть .
- Есть проблемы в случае плохой обусловленности матрицы, нужно юзать machinelearning:Сингулярное разложение.
- И, что важно (!) Если просто , то при увеличении точности нужно пересчитывать все коэффициенты.
Спектральная реализация метода наименьших квадратов
- Чебышев решил использовать при разложении системы ортогональных функций — тогда коэффициенты пересчитывать не нужно, это будут просто коэф. ряда Фурье (скалярные произведения на функции базиса).
- Опр. L2, скалярное произведение, ортогональные функции, полная система, замкнутая система, ряд Фурье.
- Т. (Фурье) конечный отрезок ряда Фурье осуществляет наилучшее приближение.
Равенство Ляпунова-Стеклова. Равенство Парсеваля. Свойство жёсткости разложения
- Неравенство Бесселя:
.
В пределе при для полных систем переходит в
равенство Парсеваля: , где cn — коэффициенты ряда Фурье функции f. - Равенство Ляпунова-Стеклова = равенство Парсеваля в пространстве функций.
- Свойство жёсткости разложения — как раз то, что пересчитывать коэффициенты при увеличении точности не нужно.
Классические ортогональные базисы. Их основные свойства
- Определяются одним из 3-х свойств:
- Их производные также образуют ортогональную систему.
- Удовлетворяют гипергеометрическому дифуру.
- Обобщённая формула Родрига: .
- Также для них есть рекуррентные соотношения, связывающие 3 любые последовательных функции.
- Базисы:
- [-1; 1]. Якоби — с весовой функцией .
- Гегенбауэра: α = β = λ — 0.5.
- Чебышева I рода: λ = 0.
- Чебышева II рода: λ = 1.
- Лежандра: λ = 0.5 (весовая функция = 1).
- Гегенбауэра: α = β = λ — 0.5.
- (0; +∞) Сонина-Лагерра:
- Лагерра: α = 0.
- (-∞; +∞) Эрмита:
Вычисление коэффициентов разложения. Роль квадратурных формул Гаусса
- Можно почитать 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(предыдущих базисных функций) и относительно самих базисных функций.
Использование соотношений в пространстве коэффициентов разложения для распознавания образов и анализа сцен
- Тоже можно почитать Руслануса.
- Контуры, векторизация, инварианты — площадь ограниченная контуром, периметр контура, аффинная длина дуги кривой.
- Короче, генерация признаков.
Интегральные оценки сигналов. Коэффициент формы сигнала
- Фактически идея — величина проекции функции на некоторую другую, то есть скалярное произведение.
- Коэффициент формы — интегральная инвариантная к длительности оценка.
- Можно напридумывать много:
- Степенной: .
- Параболический: .
- Экспоненциальный: .
Интегральное преобразование Фурье. Собственные функции
- Можно почитать rupedia:Преобразование Фурье и ещё лучше — wikipedia:Fourier transform.
- Собственные функции преобразования Фурье образуют ортонормированную систему функций Эрмита — см. wikipedia:Fourier transform#Eigenfunctions, а собственные значения равны (-i)n.
