743.68K

Категория: $Математика$ Математика

Похожие презентации:

Численные методы линейной алгебры (Е.И. Коновалова, Л.В. Яблокова)

Классификация и основные способы математического описания СУ

Теория матричных игр

Степени свободы. Четвертая задача динамики

Интерполирование и смежные вопросы. Приближение функций

Формирование и первичная обработка видеосигналов

Алгоритмы биоинформатики

Устойчивость узла нагрузки

Графы

Устойчивость пластин

Лекция2

1.

Событие
• Элементарное событие.
• Событие как множество.
• Невозможное событие.
• Достоверное событие.
• Несовместные события.
• Полная группа событий.
1

Операции над событиями
А
А B
А B
Для любых событий Aи B:
• Отрицание события: ¬A – событие Aнепроизошло.
• Объединение событий: A∪B– произошло хотя бы одно из событий.
• Пересечение событий: A∩B– произошли оба события.
2

3.

Вероятность
• Мера возможности наступления события.
• Для достоверного события вероятность 1.
• Для невозможного события вероятность 0.
• Вероятность события Aобозначим P(A).
3

4.

Вероятность отрицания события
«A или ¬A» – всегда достоверное событие.
• Следовательно, P(A)+P(¬A)=1
• Следовательно,
P(¬A)=1 −P(A)
4

5.

Вероятность пересечения событий
• Для независимых событий:
P(A∩B)=P(A)•P(B)
• В общем случае:
P(A∩ B) =P(A)•P(B|A)
P(A∩ B) =P(B)•P(A|B)
5

6.

Условная вероятность
• P(B|A)– вероятность наступления событияB
при условии A:
P(A
∩B
)
P(B|A)=
P(A)
• Для независимых событий:
P(A)•P(B)
P(B|A)=
=P(B)
P(А)
6

7.

Вероятность объединения событий
• Для несовместных событий:
P(A∪B)=P(A)+P(B)
• Для полной группы событий:
P(A1)+P(A2)+… +P(An)=1
• В общем случае:
P(A∪B)=P(A)+P(B)−P(A∩B)
7

8.

Принцип включения-исключения для вероятностей
Формула вероятности объединения для произвольного числа событий:
n
n
n
(⋃A)=∑P(A) − ∑ P(A ∩A ) + ∑ P(A ∩A ∩A ) + ... + (−1) ∙ P(⋂A)
P
i
i =1
8
i
i =1
i
1 ≤i <j≤n
i
j
1≤i <j <k≤n
j
k
n−1
i
i =1

9.

Формула полной вероятности
Для полной группы событий A1, A2, ..., Anи события B:
n
1=
n
∑ P(A|B)= ∑
i =1
i
P(Ai∩B)
P(B)
i =1
n
=
P(B|Ai)∙ P(A)
i
∑
P(B)
i =1
Формула полной вероятности:
n
∑P(A)∙P(B|A)
P(B)=
i
i =1
9
i

10.

Формула Байеса
Используем равенства P(A⋂B) =P(A) ∙P(B|A) и P(A⋂B)=P(B)∙P(A|B)
• Формула Байеса:
P(A)∙P(B|A)
P(A|B)=
P(B)
• С учетом формулы полной вероятности для полной группы событий {Ai }:
P(Aj|B)=
10
∑
P(Aj)∙P(B|Aj)
n
P(Ai)∙P(B|Ai)
i =1

11.

Классическое
определение вероятности
P(A)=
благоприятные исходы
равновероятные события
• Опирается на комбинаторные методы.
• Подходит для идеальных условий.
11

12.

Геометрическая вероятность
P(A)=
Мера (A)
Мера (Ω)
• Когда невозможно вычислить количество
элементарных событий.
12

13.

Статистическая вероятность
P(A)=
благоприятные исходы
проведенные эксперименты
• Приближается к реальной вероятости
при росте числа экспериментов.
13

14.

Байесовская вероятность
P(Aj|B)=
∑
P(Aj)∙P(B|Aj)
n
P(Ai)∙P(B|Ai)
i =1
• Степень уверенности.
• Пересчет при поступлении дополнительной информации.
14

15.

Пример: условия
• Коллекция документов:
– 95% документов типа R;
– 5% документов типа Q.
• Алгоритм клас ификации ошибается в 1% случаев.
• Какова вероятность, что ответ Q окажется верным?
15

16.

17.

Вероятностное пространство
• Множество элементарных событий.
• σ-алгебра событий.
• Вероятностная мера на множестве
элементарных событий.
17

18.

Случайная величина
• Неизвестное числовое значение –
результат случайного эксперимента.
• Отображение из множества элементарных
событий в вещественные числа:
X: Ω →
• Для количественных и качественных
характеристик события.
18

19.

Дискретные и непрерывные
• Дискретные: изолированные значения.
Конечное или счетное множество значений.
• Непрерывные: произвольные значения
из некоторого интервала.
Несчетное множество значений.
19

20.

Независимые случайные величины
События независимы, если P(A∩B)=P(A)•P(B)
Случайные величины X1и X2независимы, если
• независимы события «X1=a»и «X2=b»
• то есть, ∀a, b∈
:
P((X1=a)∩(X2=b))=P(X1=a)•P(X2=b)
20

21.

Характеристики случайной величины
• Распределение вероятностей.
• Математическое ожидание.
• Дисперсия.
• Среднеквадратичное отклонение.
21

22.

Распределение
• Вероятность P(X=a)– общая вероятность всех ω:
X(ω)=a
• Функция распределения:
FX(a)=P(X≤a)
Свойства:
• 0≤FX(x)≤1,
• FX– неубывающая,
• P(a<X≤b)=FX(b)−FX(a)
22

23.

Плотность распределения
• Скорость изменения вероятности.
• Для непрерывной случайной величины, производная функции распределения:
f (x) =F’(x)
Свойства:
a
• P(a<X<b)=∫ f(x)dx
b
• f(x)≥0
+∞
−∞
• ∫ f(x)=1
a
−∞
• F(a) =∫ f(x)dx
23

24.

Математическое ожидание
Обозначают E[X],M[X],µ
• Для дискретной случайной величины:
n
∑x ∙p
E[X]=
i
i
или
i =1
∞
∑x ∙p
E[X]=
i =1
• Для непрерывной случайной величины:
+∞
∫−∞x∙ f(x)∙ dx
E[X]=
24
i
i

25.

Свойства математического ожидания
• E[C]=C
• E[C•X]=C •E[X]
• E[X+Y]=E[X]+E[Y]
• Для независимых Xи Y:
E[X∙ Y]=E[X]∙E[Y]
25

26.

Дисперсия
Математческое ожидание квадрата отклонения, обозначают Var(X),D[X],σ2
Var(X)=E[(X −E[X])2]
• Для дискретной случайной величины:
∞
n
∑
Var(X)=
pi∙ (xi−E[X])2
∑
или Var(X)=
i =1
i =1
• Для непрерывной случайной величины:
+∞
∫−∞(x−E[X]) ∙f(x)dx
Var(X)=
26
pi∙ (xi−E[X])2
2

27.

Свойства дисперсии
• Var(X)=E[X2]−E[X]2
• Var(X)≥0
• Var(C)=0
• Var(C•X)=C2•Var(X)
• Var(X±Y)=Var(X)+Var(Y)
27

28.

Среднеквадратичное отклонение
• Var(X)=σ2,
• σ =√Var(X)=√E[(X−E[X])2]
Единицы измерения случайной величины.
28

29.

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

30.

Примеры распределений
случайных величин
• Распределения дискретных случайных величин.
• Распределения непрерывных случайных величин.
30

31.

Биномиальное распределение
Испытания с двумя исходами.
Вероятность успеха p и неудачи q =1−p.
• X=k – ровно k удач из n испытаний.
• Формула Бернулли:
Pn(k)=Cnk •pk•qn−k
• Математическое ожидание: E[X]=n•p
• Дисперсия: Var(X)=n •p •q
31

32.

Геометрическое распределение
Испытания с двумя исходами.
Вероятность успеха p и неудачи q =1−p.
• X=k – первая удача в k-том испытании.
P(X=k)=qk−1∙p
• P(1),P(2),P(3),... – геометрическая прогрессия.
1
• Математическое ожидание: E[X]= p
q
• Дисперсия: Var(X)= 2
p
32

33.

Гипергеометрическое распределение
Kиз Nпредметов особенные, выбираем n преметов из N.
• X=k – выбрано ровно k особенных предметов.
−k
CKk ∙ CNn−K
P(X=k)=
CNn
• Математическое ожидание: E[X]=n ∙K
N
• Дисперсия: Var(X)=n ∙ K∙ (1− K)∙ N−n
N
N
N−1
33

34.

Равномерное распределение
• X– постоянна на отрезке [a,b]
• Распределение:
{
f(x)=
0,
x<a
1
, a ≤x≤b
b −a
0,
b <x
{
F(x)=
b −a
• Математическое ожидание: E[X]=
2
2
(
b
−a)
• Дисперсия: Var(X)=
12
34
0,
x<a
x−a , a ≤x≤b
b −a
1,
b <x

35.

Показательное распределение
• Xхарактеризует время между повторяющимися случайными событиями.
• Является непрерывным аналогом геометрического распределения.
• Распределение:
f(x)=
{
0,
F(x)=
λ•e−λx, x≥0
1
• Математическое ожидание: E[X]=
1
• Дисперсия: Var(X)= 2
λ
35
{
x<0
λ
0,
x<0
1−e−λx, x≥0

36.

Распределение Гаусса
• Относится ко многим физическим
и социальным величинам.
• Нормальное распределение:
1
f(x)=
e
σ√2∏
(x−µ)2
2σ2
x
1
F(x)=
∫−∞e
σ√2∏
• Математическое ожидание: E[X]=µ
• Дисперсия: Var(X)=σ2
36
(t−µ)2
2σ2
dt

37.

Стандартное нормальное
распределение
• Нормальное распределение при µ=0, σ =1
x2
1
φ(x)=
e 2
√2∏
1
x
−
μ
φ
• f(x)=
σ
σ
x
−
μ
• F(x)=Φ
σ
(
(
t2
x
1
Φ(x)=
∫−∞ e 2dt
√2∏
)
)
µ– коэффициент смещения,
σ – коэффициент масштабирования.
37

38.

Правило трех сигм
34,1% 34,1%
0,1% 2,1%13,6%
−3σ
−2σ
−1σ
13,6%
0
1σ
2,1% 0,1%
2σ
3σ
• Около 68% площади лежит в пределах [µ−σ, µ+σ];
• Около 95% – в [µ−2σ, µ+2σ];
• Более 99% – в [µ−3σ, µ+3σ].
38

39.

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

40.

Задачи статистики
Имеется случайная величина доступная через наблюдения.
• Собирать данные.
• Структурировать.
• Представлять.
• Анализировать параметры.
• Предсказывать будущее поведение.
40

41.

Генеральная совокупность и выборка
• Генеральная совокупность – точное поведение
в прошлом и будущем.
• Выборка – отдельная группа наблюдений
Пример:
• Поведение покупателей в магазине.
• Выборка – статистика посещений и покупок
группы людей за определенный период.
41

42.

Выборка как случайная величина
• Каждое наблюдение как случайная величина.
• Выборка – набор случайных величин заданной длины.
• Среднее по выборке.
42

43.

Точечная оценка
и доверительный интервал
• Точечная оценка.
• Доверительный интервал для оценивания величины X
и вероятности p:
[a,b]: P(a≤X≤b)=p
• Искомая величина лежит в интервале [a,b]
с заданной вероятностью.
43

44.

Квантиль
• α-квантиль – это такое xα, что
P(X ≤xα)≥α и P(X≥xα)≥1−α
• Пропорциональная α доля выборки лежит не выше xα,
• k-тая q-вантиль – это kq-квантиль.
Например, перцентиль –
1 -квантиль,
100
95-тая перцентиль – 0.95-квантиль.
44

45.

Квартили и медиана
1
• Медиана –
-квантиль
2
Среднее значение.
• Квартиль – 1-квантиль
4
Вторая квартиль – медиана.
• Интерквартильный размах.
• Боксплот.
45
Боксплот
−5
0
5
10
15
20

46.

Корреляция
• Свойство быть зависимыми.
• Закономерная зависимость между изменениями
нескольких случайных величин.
• Причина и следствие?
• Отсутствие корреляции и зависимость.
46

47.

Ковариация
• Мера линейной зависимости.
• Математическое ожидание произведения отклонений:
cov(X, Y)=E[(X−E[X])•(Y−E[Y])]
• Положительная и отрицательная корреляция.
47

48.

Свойства ковариации
• cov(X, Y)=E[X•Y]−E[X]•E[Y]
• cov(X, X)=Var(X)
• |cov(X,Y)|≤√Var(X)•Var(Y)
• Для независимых случайных величин: cov(X,Y)=0,
обратное неверно.
• Единицы измерения.
48

49.

Коэффициент корреляции
Коэффициент корреляции Пирсона:
ρX,Y =
cov(X,Y)
σX∙σY
=
E[(X−E[X])∙ (Y−E[Y])]
√E[(X−E[X])2]∙ E[(Y−E[Y])2]
• −1≤ρX,Y≤1
• Единицы измерения.
• 0для независимых величин.
• Положительная и отрицательная корреляция.
49

50.

Выбросы
• Наблюдение, которое сильно выбивается.
• Влияние на оценки.
• Робастные методы.
50

51.

Ресемплинг
• Генерация псевдовыборок –
создание дополнительных наборов
из имеющихся наблюдений.
• Имитация тестирования на генеральной совокупности.
51

52.

Метод складного ножа
• Оценка статистических характеристик.
• Генерация выборок исключением одного элемента.
• n выборок размера n −1.
52

53.

Метод перекрестной проверки
• Выборка делится на k частей.
• k −1часть используется для обучения.
• Одна часть – дляпроверки.
53

54.

Бутстрэп
• Случайная генерация из имеющейся выборки:
выборки с повторениями.
• Не уменьшает число наблюдений на выборку.
54

55.

Используемые обозначения
• det – определитель,
• rank – ранг,
• ||A||– евклидованорма:
=√∑[элементывектора (матрицы)]2
• .Т– транспонирование,
• .−1– обращение,
• E– единичная матрица,
• A[j]– j-й столбец матрицы A.
55

56.

Собственные числа и собственные векторы матрицы
A: =
a11 a12 … a1n
a21 a22 … a2n
… …
…
an1 an2 … ann
Вектор-столбец X=[x1,x2, … , xn]Т– собственный вектор матрицы,
принадлежащий собственному числу λ если AX=λXи ∃xj≠0.
56

57.

58.

Характеристический полином
det(A −λE)=0
58

59.

Характеристический полином
det(A −λE) =0
Не обязательно собственные числа будут вещественными.
59

60.

Характеристический полином
det(A −λE)=0
Не обязательно собственные числа будут вещественными.
Но для симметричной матрицы A =AТбудут!
60
собственны
е числа
λ1
λ2
…
λn вещественны
собственны
е векторы
Ӿ1
Ӿ2
…
Ӿn попарно ортогональны

61.

Ортогональная матрица
Ӿj=[x1,x2, …, xn]Т, Ӿk=[y1, y2, …, yn]Т
(Ӿj, Ӿk): =x1y1+x2y2 +… +xnyn=0
61
при j ≠ k

62.

Ортогональная матрица
Ӿj=[x1,x2, …, xn]Т, Ӿk=[y1, y2, …, yn]Т
(Ӿj, Ӿk): =x1y1+x2y2 +… +xnyn=0
при j ≠ k
А можно еще и нормировать:
||Ӿ|j|:2=(Ӿ, Ӿj )=jx
62
2
1
+x22 +… +x2n =1

63.

Ортогональная матрица
Ӿj=[x1,x2, …, xn]Т, Ӿk=[y1, y2, …, yn]Т
(Ӿj, Ӿk): =x1y1+x2y2 +… +xnyn=0
при j ≠ k
А можно еще и нормировать:
||Ӿ|j|:2=(Ӿ, Ӿj )=jx
2
1
+x22 +… +x2n =1
AӾ1=λ1Ӿ1, AӾ2=λ2Ӿ2, …, AӾn=λnӾn
A[Ӿ1|Ӿ2|…| Ӿn]=[Ӿ1|Ӿ2|…| Ӿn]
63
λ1
0
0
λ2
0
0
0
0
λn

64.

Симметричная
и ортогональная матрицы
Ортогональная матрица P:=[P[1]|P[2]|… |P[n]]:
P • P Т= P Т• P = E
P −1 = P Т
64

65.

Симметричная
и ортогональная матрицы
Ортогональная матрица P:=[P[1]|P[2]|… |P[n]]:
P • P Т= P Т• P = E
P −1 = P Т
симметричная
матрица
65
=P
диагональная
матрица
• PТ

66.

Симметричная
и ортогональная матрицы
Ортогональная матрица P:=[P[1]|P[2]|… |P[n]]:
P • P Т= P Т• P = E
P −1 = P Т
симметричная
матрица
=P
диагональная
матрица
Т +… +λ P
Т
+
λ
P
•P
•P
A=λ1P[1] •P
[n]
2 [2]
[2]
n [n]
Т
[1]
66
• PТ

67.

Экстремальное свойство собственныхчисел
67
A: =
3 2 0
2 4 −2
0 −2 5
1⁄3
7∙ 2⁄3
-2⁄3
1 2 2
, ,−
3 3 3
=
2⁄3
+4∙
1⁄
3
2⁄3
2 1 2
, ,
3 33
-2⁄3
+1∙ 2⁄3
1⁄3
2 1 2
− , ,
3 3 3

68.

Экстремальное свойство собственныхчисел
A: =
3 2 0
2 4 −2
0 −2 5
1⁄3
7∙ 2⁄3
-2⁄3
1 2 2
, ,−
3 3 3
=
2⁄3
-2⁄3
2 1 2
2 1 2
+1∙ 2⁄3 − , ,
+4∙
, ,
3 3 3
3 33
1⁄3
1⁄
3
2⁄3
Можно ли поместить поверхность [x, y , z]A[x, y , z]Т=1
внутрь посылочного ящика?
68

69.

70.

Экстремальное свойство собственныхчисел
(x;y;z)A
7
70
x
y
z
=1
1 1 2
x+ y − z
3
3
3
2
+4
2 1 2
x+ y + z
3
3
3
2
+1
2 2 1
− x+ y− z
3
3
3
2
=1

71.

Экстремальное свойство собственныхчисел
(x;y;z)A
7
x
y
z
=1
1 1 2
x+ y − z
3
3
3
7X 2+4Y2+1Z 2=1
71
2
+4
2 1 2
x+ y + z
3
3
3
2
+1
2 2 1
− x+ y− z
3
3
3
2
=1

72.

Экстремальное свойство собственныхчисел
(x;y;z)A
7
x
y
z
=1
1 1 2
x+ y − z
3
3
3
2
+4
2 1 2
x+ y + z
3
3
3
2
+1
2 2 1
− x+ y− z
3
3
3
2
=1
7X 2+4Y2+1Z 2 =1
… и переход к новым переменным не меняет расстояний между точками!
72

73.

Экстремальное свойство собственныхчисел
Эллипсоид в
n
XТAX =1
«шире всего» в направлении его оси, соответствующей
минимальному собственному числу матрицы A,
73

74.

Экстремальное свойство собственныхчисел
Эллипсоид в
n
XТAX =1
«шире всего» в направлении его оси, соответствующей
минимальному собственному числу матрицы A,
размеры минимального ящика (длина, ширина, высота …) –
2
2
2
,
, …,
,
√λ1 √λ2
√λn
74

75.

76.

Неквадратные матрицы
симметр.
матрица
=
ортогон.
матрица
ди
аг.
ортогон.
матрица
Т
Можно ли построить аналогичное представление для любой матрицы A ∈
76
m×n
?

77.

Неквадратные матрицы
симметр.
матрица
=
ортогон.
матрица
ди
аг.
ортогон.
матрица
Т
Можно ли построить аналогичное представление для любой матрицы A ∈
A=V •Σ •WТ
77
m×n
?

78.

Неквадратные матрицы
симметр.
матрица
ортогон.
матрица
=
ди
аг.
ортогон.
матрица
Т
Можно ли построить аналогичное представление для любой матрицы A ∈
A=V •Σ •WТ
Матрицы V ∈
и W∈
m×m
n ×n
– ортогональные.
Элементы Σ =[σij]все равны 0если i ≠j.
78
m×n
?

79.

Сингулярное разложение (SVD)
A=V •Σ •WТ
m×n
A
m×m
=
V
σ1
σ2
m×n
σm
∑
79
n ×n
WT

80.

Сингулярное разложение (SVD)
A=V •Σ •WТ
m×n
A
m×m
=
V
σ1
σ2
m×n
σm
∑
Сингулярные числа матрицы A:
{σj}=√собственные числа матрицы A•A Т
80
n ×n
WT

81.

Сингулярное разложение (SVD)
A=V •Σ •WТ
m×n
A
m×m
=
V
σ1
σ2
m×n
σm
∑
Сингулярные числа матрицы A:
{σj}=√собственные числа матрицы A•A Т
det(A •AТ−σ2jE)=0
81
n ×n
WT

82.

Сингулярные числа и векторы
σ1>0, σ2>0, . . . , σr>0при r: =rank(A)
Сингулярные векторы матрицы A
82
V[j ]– левый
A•AТV[j ]=σ 2V[j]
W[j ]– правый
AТ AW[j ]=σ 2W[j]
j
j

83.

Сингулярные числа и векторы
σ1>0, σ2>0, . . . , σr>0при r: =rank(A)
Сингулярные векторы матрицы A
V[j ]– левый
A•AТV[j ]=σ 2V[j]
W[j ]– правый
AТ AW[j ]=σ 2W[j]
j
j
A•W[j ]=σjV[j ], AТV[j ]=σjW[j]
83

84.

Сингулярное разложение: приближение матрицы
Пусть σ1≥σ2≥… ≥σr>0,
Т
Т
Т
+…
+σV
W
,
A=σV
W
+σ
V
W
1 [1] [1]
2 [2] [2]
r [r] [r]
84

85.

86.

Сингулярное разложение: приближение матрицы
Пусть σ1≥σ2≥… ≥σr>0,
Т
Т
Т
+…
+σV
W
,
A=σV
W
+σ
V
W
1 [1] [1]
2 [2] [2]
r [r] [r]
Т r
Все матрицы {V[j]W[j]
}j =1 не очень большие: |элемент| ≤1,
Основной «взнос» в сумму производится за счет множителей σj.
большие
σ1,…, σk, σk+1, …, σr
малые
86

87.

88.

Сингулярное разложение:
приближение матрицы
A≈Ak: =σ1V[1]W [Т1] +… +σkV[k]W[Тk]
Ошибка приближения (норма – евклидова):
||A−A|k|=√σ
88
2
k +1
+… +σ2r

89.

Сингулярное разложение:
приближение матрицы
A≈Ak: =σ1V[1]W [Т1] +… +σkV[k]W[Тk]
Ошибка приближения (норма – евклидова):
||A−A|k|=√σ
2
k +1
+… +σ2r
Матрица Ak– наилучшее приближение матрицы A
во множестве матриц ранга k.
89

90.

Сингулярное разложение:
основная идея
При больших размерах матрицы Aзаменять ее
приближением Akдля малых величин k.
90

91.

Сингулярное разложение:
основная идея
При больших размерах матрицы Aзаменять ее
приближением Akдля малых величин k.
• Почему это работает?
91

92.

Сингулярное разложение:
основная идея
При больших размерах матрицы Aзаменять ее
приближением Akдля малых величин k.
• Почему это работает?
• Всегда ли это работает?
92

93.

Сингулярное разложение:
основная идея
При больших размерах матрицы Aзаменять ее
приближением Akдля малых величин k.
• Почему это работает?
• Всегда ли это работает?
• Откуда взялась матрица A •AТ?!
93

94.

Диаграмма
рассеяния
Рост взрослых детей
Пример (Ф. Гальтон, 1886): n =2, m=898
75
70
65
60
58 60 62 64 66 68 70 72 74
Усредненный рост родителей
94

95.

Диаграмма
рассеяния
Рост взрослых детей
Пример (Ф. Гальтон, 1886): n =2, m=898
75
70
65
60
58 60 62 64 66 68 70 72 74
Усредненный рост родителей
95
Напоминает эллипс?

96.

Ковариационная матрица
К. Пирсон, 1901: эллипс рассеяния
[x−x, y −y]S
−1
75
70
65
60
58 60 62 64 66 68 70 72 74
96
x−x
y −y
=4

97.

Оптимизационная задача Пирсона
Найти прямую, дающую min(δ2+δ 2+δ 2+…).
1
5
δ1
4
δ2
δ3
3
2
1
0
97
1
2
3
4
5
6
7
8
9
2
3

98.

Оптимизационная задача Пирсона
Найти прямую, дающую min(δ2+δ 2+δ 2+…).
1
5
δ1
4
δ2
δ3
3
2
1
0
1
2
3
4
5
6
7
8
9
≠метод наименьших квадратов!
98
2
3

99.

Ковариационная матрица
Центрируем данные:
F :=
99
x1−x
y1−y
x2−x
y2−y
… xm−x
… ym−y
Т

100.

Ковариационная матрица
Центрируем данные:
F :=
x1−x
y1−y
x2−x
y2−y
Ковариационная матрица
1 Т
S: = F F
m
100
… xm−x
… ym−y
Т

101.

Ковариационная матрица
Центрируем данные:
F :=
x1−x
y1−y
x2−x
y2−y
… xm−x
… ym−y
Т
Ковариационная матрица
1 Т
S: = F F
m
Вдоль какого направления эллипс шире всего?
101

102.

Ковариационная матрица: геометрия
Эллипс рассеяния
102
Главные оси
= собственные векторы матрицы S
Длины осей
= const × √собственные числа матрицы S

103.

104.

Ковариационная матрица: геометрия
Эллипс рассеяния
Главные оси
= собственные векторы матрицы S
Длины осей
= const × √собственные числа матрицы S
А что, если λ2<<λ2?Эллипс →отрезок прямой.
Гипотеза: закон связи между xи y – линейный,
а рассеяние вызвано ошибками наблюдений.
104

105.

106.

Метод главных компонент
Данные в
n
:
Т +… +λ P
Т
+
λ
P
•P
•P
S =λ P •P
1 [1]
Т
[1]
2 [2]
[2]
n [n]
Т n
}j =1 – главныекомпоненты; λ1≥λ2≥… ≥λn.
{P[j]•P[j]
106
[n]

107.

Метод главных компонент
Данные в
n
:
Т +… +λ P
Т
+
λ
P
•P
•P
S =λ P •P
1 [1]
Т
[1]
2 [2]
[2]
n [n]
Т n
}j =1 – главныекомпоненты; λ1≥λ2≥… ≥λn.
{P[j]•P[j]
большие
λ1, …, λk, λk+1, …,λn
малые
107
[n]

108.

Метод главных компонент
Данные в
n
:
Т +… +λ P
Т
+
λ
P
•P
•P
S =λ P •P
1 [1]
Т
[1]
2 [2]
[2]
n [n]
Т n
}j =1 – главныекомпоненты; λ1≥λ2≥… ≥λn.
{P[j]•P[j]
большие
λ1, …, λk, λk+1, …,λn
k
S≈S=
k
108
малые
∑
j =1
λjP[j] ∙P[Тj]
[n]

109.

Метод главных компонент
Данные в
n
:
Т +… +λ P
Т
+
λ
P
•P
•P
S =λ P •P
1 [1]
Т
[1]
2 [2]
[2]
n [n]
[n]
Т n
}j =1 – главныекомпоненты; λ1≥λ2≥… ≥λn.
{P[j]•P[j]
большие
λ1, …, λk, λk+1, …,λn
малые
k
S≈S=
k
∑
λj P[j ]∙P [Тj]
j =1
Эллипсоид рассеяния адекватно оценивается своей «тенью»,
т.е. проекцией на плоскость с направляющими векторами {P[j]}jk=1.
109

110.

Сингулярное разложение: распознавание фотографий
Облако данных может состоять из нескольких «эллипсоидов».
110

111.

Сингулярное разложение: распознавание фотографий
Облако данных может состоять из нескольких «эллипсоидов».
Сингулярное разложение часто срабатывает.
Пример: 10 человек, 80 оцифрованных и векторизованных фотографий,
10 000 пикселей каждая. Сингулярное разложение матрицы данных F∈ 80×10000
80
∑
F=
j =1
σj V[j ]WТ]
[j
Что произойдет, если оставим только 9 первых слагаемых?
F[Тj] ≈αj 1W[1]+αj2WТ[2] +… +αj 9W[Т9]
111

112.

«Собственные» лица
W[1],W[2],… – тоже векторизованные фотографии, Eigenfaces.
112
1
2
3
4
5
6
7
8
9

113.

«Собственные» лица
Фотография из коллекции = сумма масок,
домноженных на координаты:
113

114.

«Собственные» лица
Фотография из коллекции = сумма масок,
домноженных на координаты:
114

115.

«Собственные» лица
Тестовая фотография = сумма «масок»,
домноженных на координаты.
115

116.

«Собственные» лица
Тестовая фотография = сумма «масок»,
домноженных на координаты.
Чья фотография? – Сравните векторы координат.
116

117.

Вычислительные аспекты сингулярного разложения
Сингулярные числа – корни уравнения
det(A •AТ−λE)=0
Нереально вычислить ВСЕ при больших размерах матриц.
117

118.

119.

Вычислительные аспекты сингулярного разложения
Сингулярные числа – корни уравнения
det(A •AТ−λE)=0
Нереально вычислить ВСЕ при больших размерах матриц.
Но можно ограничиться только самыми большими!
Существуют методы, позволяющие строить сингулярное разложение
матрицы A последовательным вычислением первого слагаемого
Т
σV
W
,
1 [1] [1]
119

120.

English Русский Правила