1
00:00:00,370 --> 00:00:01,850
My name is David Thompson, and this

2
00:00:01,850 --> 00:00:05,070
presentation is Local Methods for Pattern
Recognition.

3
00:00:05,070 --> 00:00:08,480
It's the first of several modules that
will involve, or talk about

4
00:00:08,480 --> 00:00:14,430
dimensionality reduction in the context of
this Caltech Big Data Summer School.

5
00:00:14,430 --> 00:00:18,160
And so, the first of these lectures is
intended to provide just

6
00:00:18,160 --> 00:00:23,320
a common reference some basic skill set
that we'll refer to later.

7
00:00:23,320 --> 00:00:24,660
I'm going to review some basic

8
00:00:24,660 --> 00:00:27,820
pattern recognition strategies, such as
classification regression

9
00:00:27,820 --> 00:00:30,640
that you will have been exposed to
previously, but I think it's, it's

10
00:00:30,640 --> 00:00:33,950
worth talking about them again, because it
really is foundational for some of

11
00:00:33,950 --> 00:00:35,760
the things that we'll describe later

12
00:00:35,760 --> 00:00:37,570
as far as dimensionality reduction is
concerned.

13
00:00:37,570 --> 00:00:39,080
So it's an important background to have.

14
00:00:40,340 --> 00:00:42,540
Okay, so this first talk will, as I

15
00:00:42,540 --> 00:00:47,070
said, review basic pattern recognition
problems, classification, and regression.

16
00:00:47,070 --> 00:00:50,830
And in particular on the context of local
pattern recognition strategies.

17
00:00:50,830 --> 00:00:54,629
These are non-parametric pattern
recognition strategies, as opposed

18
00:00:54,629 --> 00:00:58,420
to say parametric methods that we have
seen earlier.

19
00:00:58,420 --> 00:01:01,760
A lot of these fall into the general
category of nearest neighbor methods.

20
00:01:01,760 --> 00:01:04,020
So I'll describe the nearest-neighbor
methodology, and why that might be a

21
00:01:04,020 --> 00:01:08,730
good thing, and then a couple variants of
that, including local linear regression.

22
00:01:08,730 --> 00:01:10,980
Which is a flexible regression strategy
that

23
00:01:10,980 --> 00:01:13,940
is based on a local non-KerMetric
approach.

24
00:01:13,940 --> 00:01:15,980
And then kernel density estimation, which

25
00:01:15,980 --> 00:01:19,160
is a probabilistic method for pattern
recognition.

26
00:01:21,910 --> 00:01:26,020
Okay, so let's start off with a simple
pattern recognition task.

27
00:01:26,020 --> 00:01:28,000
Here I've got a, a data set with a couple
of

28
00:01:28,000 --> 00:01:32,100
attributes on it, and is pattern
recognition folks I want to do.

29
00:01:32,100 --> 00:01:35,430
I just plotted these giving each its own
coordinates.

30
00:01:35,430 --> 00:01:38,120
So here, this is a two-dimensional
attribute space where

31
00:01:38,120 --> 00:01:40,750
every data point may have associated with
it some

32
00:01:40,750 --> 00:01:44,710
class value or some real valued ordinate
that we're

33
00:01:44,710 --> 00:01:46,884
regressing against, some value that we'd
want to predict.

34
00:01:46,884 --> 00:01:51,600
[INAUDIBLE] were just interesting in
intrinsic properties of the data set how

35
00:01:51,600 --> 00:01:54,510
the data is distributed to try to infer
something about the process that

36
00:01:54,510 --> 00:01:58,720
generated that data, so that is more akin
to say a density estimation

37
00:01:58,720 --> 00:02:00,690
task where we are estimating probability

38
00:02:00,690 --> 00:02:02,420
density in this two dimensional attribute
space.

39
00:02:02,420 --> 00:02:06,030
So there are lots of different kinds of
pattern recognition questions that

40
00:02:06,030 --> 00:02:09,230
we can ask of this data set even this very
simple one here.

41
00:02:10,390 --> 00:02:15,690
So, I've plotted here on this, this slide
a red question mark to indicate

42
00:02:15,690 --> 00:02:17,190
some query point where we'd like to

43
00:02:17,190 --> 00:02:20,300
describe or predict behavior of this
process.

44
00:02:20,300 --> 00:02:22,601
Again, this could be a, a prediction of
the

45
00:02:22,601 --> 00:02:25,463
real valued function at that location in
the input

46
00:02:25,463 --> 00:02:27,265
space, or it could be that we have a

47
00:02:27,265 --> 00:02:30,352
new point there, who's class we're tying
to infer.

48
00:02:30,352 --> 00:02:32,858
Regardless we've got a, a query point and
we want to be

49
00:02:32,858 --> 00:02:35,985
able to infer something about what the
process is doing at that location.

50
00:02:35,985 --> 00:02:39,170
All right, a little bit of notation
background.

51
00:02:39,170 --> 00:02:42,280
So I'm going to treat these data points as
column vectors, so

52
00:02:42,280 --> 00:02:45,340
we're going to say X is, er, X sub I is
our data point.

53
00:02:45,340 --> 00:02:47,450
And it has from one to n attributes.

54
00:02:47,450 --> 00:02:49,548
Again, that's example, a simple example
only has

55
00:02:49,548 --> 00:02:52,280
two, but you can imagine having
arbitrarily many.

56
00:02:52,280 --> 00:02:53,850
And because this is dimensionality

57
00:02:53,850 --> 00:02:55,440
reduction, we're eventually going to be
talking

58
00:02:55,440 --> 00:03:00,070
about data points that have hundreds or
even thousands of attributes.

59
00:03:00,070 --> 00:03:03,430
And we can represent the entire data set
as

60
00:03:03,430 --> 00:03:06,390
a matrix where we stack these column
vectors together

61
00:03:06,390 --> 00:03:11,260
in rows so we have an N by d matrix, where
D is the number of data points.

62
00:03:11,260 --> 00:03:13,650
For now without much loss of generality,
I'm just going

63
00:03:13,650 --> 00:03:18,200
to assume that all of these attributes are
real valued.

64
00:03:18,200 --> 00:03:21,530
Continuous attributes so, I'm not going to

65
00:03:21,530 --> 00:03:24,050
deal much with, for example, categorical
attributes,

66
00:03:24,050 --> 00:03:25,300
but many of the same principles that

67
00:03:25,300 --> 00:03:28,490
I'll discuss apply to categorical
attributes as well.

68
00:03:28,490 --> 00:03:31,410
And you may be familiar with encoding
strategies that

69
00:03:31,410 --> 00:03:34,950
you can use to turn categorical attributes
into continuous.

70
00:03:34,950 --> 00:03:39,349
So really we'll just focus on the, the the
continuous case here.

71
00:03:40,510 --> 00:03:42,560
Okay, so, or one reasonable way to do

72
00:03:42,560 --> 00:03:44,390
pattern recognition on this data set is to
just

73
00:03:44,390 --> 00:03:46,470
look at the local behavior in the vicinity

74
00:03:46,470 --> 00:03:49,570
of the query point that we're interested
in inferring.

75
00:03:49,570 --> 00:03:53,380
So here we can, this goes under the
assumption that whatever

76
00:03:53,380 --> 00:03:57,010
process generated the data is locally
smooth in the input space.

77
00:03:57,010 --> 00:03:58,750
So maybe we can disregard a bunch of the

78
00:03:58,750 --> 00:04:00,880
points that are really far away from our
query, right.

79
00:04:00,880 --> 00:04:03,260
We don't have to look at the function
values.

80
00:04:03,260 --> 00:04:06,180
it, it, at the extreme lower left side of
a plot.

81
00:04:06,180 --> 00:04:08,070
We can just look at the, the values on

82
00:04:08,070 --> 00:04:10,200
the upper right near the, the red question
mark.

83
00:04:10,200 --> 00:04:10,380
Right?

84
00:04:10,380 --> 00:04:12,500
So, maybe to look at its, its closest
neighbors

85
00:04:12,500 --> 00:04:14,860
to see what the function is doing in that
vicinity.

86
00:04:14,860 --> 00:04:16,090
And you can do this for each

87
00:04:16,090 --> 00:04:17,930
of the pattern recognition strategies that
I mentioned.

88
00:04:18,990 --> 00:04:19,280
All right.

89
00:04:19,280 --> 00:04:22,620
So the canonical example is, of course,
nearest neighbor classification.

90
00:04:22,620 --> 00:04:26,114
To infer the class of the query, just look
to its nearest neighbor in our

91
00:04:26,114 --> 00:04:29,803
data set, and assume that it has the same
class as that one neighbor point.

92
00:04:29,803 --> 00:04:33,546
So, in this case I've indicated, with a
red arrow, the nearest neighbor of the

93
00:04:33,546 --> 00:04:36,809
query and so we just assume that that is
the class of our, of our query.

94
00:04:36,809 --> 00:04:39,261
Now this amounts to a [UNKNOWN]
partitioning of

95
00:04:39,261 --> 00:04:41,455
the input space so here in two dimensions

96
00:04:41,455 --> 00:04:44,554
I've drawn, I've partitioned the space
drawing areas

97
00:04:44,554 --> 00:04:47,341
for which every input point is responsible
right?

98
00:04:47,341 --> 00:04:49,681
So you can see that the nearest neighbor
points

99
00:04:49,681 --> 00:04:53,110
are actually responsible for a polygon,
within this input space.

100
00:04:53,110 --> 00:04:56,790
And any query within that polygon is going
to get its class now this has kind of

101
00:04:56,790 --> 00:05:00,190
nice property, because the data that is
where

102
00:05:00,190 --> 00:05:03,100
we have denser data right in the center.

103
00:05:03,100 --> 00:05:05,780
it, where we, it, have more information

104
00:05:05,780 --> 00:05:07,920
that the Voronio partitions are smaller,
right?

105
00:05:07,920 --> 00:05:10,290
And we permit the function to vary a
little bit more.

106
00:05:10,290 --> 00:05:13,000
Far from the data cloud these, these

107
00:05:13,000 --> 00:05:15,440
partitions get a lot larger and, again,
we,

108
00:05:15,440 --> 00:05:19,000
we don't have as much to say about that
corner of, of the input space.

109
00:05:19,000 --> 00:05:21,640
So our inference there is going to be
smoother.

110
00:05:21,640 --> 00:05:24,280
Right, so this is a basic example of
nearest

111
00:05:24,280 --> 00:05:27,240
neighbor classification, and the decision
boundary looks like this.

112
00:05:27,240 --> 00:05:28,880
This is he resulting decision boundary.

113
00:05:28,880 --> 00:05:32,960
I've applied here some, some labels to the
data set, red and, and blue.

114
00:05:32,960 --> 00:05:36,220
And you can see that the decision boundary
here drawn in black is sort

115
00:05:36,220 --> 00:05:41,140
of a wiggly shape through this input space
that bends around all of these inputs.

116
00:05:41,140 --> 00:05:43,980
Now the, the query's actually been paired
with a blue point.

117
00:05:43,980 --> 00:05:46,880
This is kind of interesting, though
because

118
00:05:46,880 --> 00:05:48,340
if you look carefully you'll note that

119
00:05:48,340 --> 00:05:53,370
the query is actually also fairly close to
a bunch of red points as well.

120
00:05:53,370 --> 00:05:53,770
Right?

121
00:05:53,770 --> 00:05:57,530
To it's immediate left there are clusters
of red points and it's almost as close

122
00:05:57,530 --> 00:05:59,980
to those, but it's just sort of
happenstance

123
00:05:59,980 --> 00:06:02,170
that it got paired with a blue point.

124
00:06:02,170 --> 00:06:04,740
So another way of saying this is that the

125
00:06:04,740 --> 00:06:08,310
one nearest neighbor approach to
classification is rather sensitive noise.

126
00:06:08,310 --> 00:06:13,248
It has high variance, in the language of
pattern recognition.

127
00:06:13,248 --> 00:06:18,010
Variance-bias tradeoff, is definitely well
it's definitely

128
00:06:18,010 --> 00:06:20,000
more variance than bias in this case.

129
00:06:20,000 --> 00:06:23,960
So this also manifests as a fairly wiggly
decision boundary.

130
00:06:23,960 --> 00:06:27,630
So if you see in the center of the cloud
there, maybe our decision boundary wiggles

131
00:06:27,630 --> 00:06:29,410
a little bit more than is appropriate
given,

132
00:06:29,410 --> 00:06:31,810
given the, the amount of data that we
have.

133
00:06:31,810 --> 00:06:34,570
So what this really needs is some way to
smooth that decision

134
00:06:34,570 --> 00:06:38,990
boundary or regularize it so we're less
sensitive to those single point outliers.

135
00:06:38,990 --> 00:06:42,310
And the way that's typically done is by
introducing more nearest neighbors.

136
00:06:42,310 --> 00:06:44,850
So here I'm looking at the five nearest
neighbors and taking

137
00:06:44,850 --> 00:06:49,640
a majority vote of which which class to
call the query.

138
00:06:49,640 --> 00:06:53,050
And you can see the decision boundary
straighten out quite a bit as a result.

139
00:06:53,050 --> 00:06:54,830
This has the effect of regularizing

140
00:06:54,830 --> 00:06:56,960
or smoothing our classification, and we're
now

141
00:06:56,960 --> 00:07:01,790
paired correctly with the, the red points
as opposed to that single blue outlier.

142
00:07:03,010 --> 00:07:04,620
Alright, so this is just one example

143
00:07:04,620 --> 00:07:06,970
of regularization in the context of
pattern recognition.

144
00:07:08,370 --> 00:07:11,860
So, I alluded to other kinds of pattern
recognition tasks

145
00:07:11,860 --> 00:07:15,060
that one might want to perform using this
sort of local estimation.

146
00:07:15,060 --> 00:07:17,220
And another one is regression, right?

147
00:07:17,220 --> 00:07:20,520
So, a really simple regression strategy
that sort of.

148
00:07:20,520 --> 00:07:24,430
The regression analog to K's nearest
neighbor is kernel smoothing.

149
00:07:24,430 --> 00:07:28,530
And that is to, if I have some real value
function that I want to estimate, I can

150
00:07:28,530 --> 00:07:31,480
just perform a weighted average of the
local, of

151
00:07:31,480 --> 00:07:35,380
that function where the weights are
weighted by local neighbors.

152
00:07:35,380 --> 00:07:38,180
Right, so locality to the, the query
point.

153
00:07:38,180 --> 00:07:41,740
Which amounts to convolving a kernel
function over the training data.

154
00:07:41,740 --> 00:07:44,400
So here the kernel function, which I've
represented

155
00:07:44,400 --> 00:07:48,500
as K can be any decreasing function of
distance.

156
00:07:48,500 --> 00:07:51,270
So it's quite common to use a Gaussian
bump for that.

157
00:07:51,270 --> 00:07:55,720
There you see on the lower right the, the
formula for a Gaussian kernel function.

158
00:07:55,720 --> 00:07:58,930
Which is a perfectly good kernel, and it's
actually what I'd recommend you start

159
00:07:58,930 --> 00:08:04,536
off with as sort of a first cut for all
your your kernel smoothing problems.

160
00:08:04,536 --> 00:08:08,379
It's got a free parameter which is the
width which is here represented as H.

161
00:08:08,379 --> 00:08:13,147
So if the width is wide it's sort of akin
to many nearest neighbor classification.

162
00:08:13,147 --> 00:08:16,430
We're taking into account a large
neighborhood around our query point right.

163
00:08:16,430 --> 00:08:19,050
And most of the the nearest neighbors in
that

164
00:08:19,050 --> 00:08:21,340
point vicinity will get more or less equal
weighting.

165
00:08:21,340 --> 00:08:23,460
Right, so that's a lot of smoothing.

166
00:08:23,460 --> 00:08:26,260
If our width is very narrow, or then what

167
00:08:26,260 --> 00:08:27,990
that means is that we're, just look, it's
a

168
00:08:27,990 --> 00:08:30,640
very skinny Gaussian bump function, and
we're only looking

169
00:08:30,640 --> 00:08:33,640
at the points very, very close to the
query points.

170
00:08:33,640 --> 00:08:35,250
So it's akin to a one nearest neighbor
where

171
00:08:35,250 --> 00:08:37,640
our variance is a little bit higher, which
might be

172
00:08:37,640 --> 00:08:40,280
more appropriate if we have more data for
instance

173
00:08:40,280 --> 00:08:42,170
or over a dense region of the, the input
space.

174
00:08:43,230 --> 00:08:45,577
Note also that we're normalizing by all of

175
00:08:45,577 --> 00:08:48,191
the kernel outputs over all of the data
points.

176
00:08:48,191 --> 00:08:51,490
So we, we do this calculation over all the
training

177
00:08:51,490 --> 00:08:55,110
data for any query whose value we want to
estimate.

178
00:08:55,110 --> 00:08:57,432
So here's an example for just a 1D
classification

179
00:08:57,432 --> 00:09:00,080
problem of what kernel smoothing looks
like in practice.

180
00:09:00,080 --> 00:09:02,430
So we've got a process, which is green
here.

181
00:09:02,430 --> 00:09:03,880
It's Y of X.

182
00:09:03,880 --> 00:09:07,470
Which is a, just a simple periodic
function in this case.

183
00:09:07,470 --> 00:09:11,530
And it generates a bunch of data points
that are here noted in blue.

184
00:09:11,530 --> 00:09:14,270
And we're trying to infer what this, what
this function looks like.

185
00:09:14,270 --> 00:09:17,540
And I've applied a, a kernel smoothing
algorithm to the data.

186
00:09:17,540 --> 00:09:20,170
So you, we can see that for X sub naught.

187
00:09:20,170 --> 00:09:23,130
There, where we've inferred a value, Y of
X

188
00:09:23,130 --> 00:09:25,960
sub naught, or Y hat because it's an
estimate.

189
00:09:25,960 --> 00:09:27,990
And you can see we're looking at, at
points in the, the

190
00:09:27,990 --> 00:09:32,230
vicinity of X sub naught to determine what
that, what that real function

191
00:09:32,230 --> 00:09:36,430
value would be; and that those points,
which are red in this diagram,

192
00:09:36,430 --> 00:09:39,670
are weighted by a kernel function, which
is centered on X sub naught.

193
00:09:39,670 --> 00:09:42,820
So points near X sub naught are going to
get high weighting.

194
00:09:42,820 --> 00:09:45,990
In our local average and points far from,
from X sub naught are going to

195
00:09:45,990 --> 00:09:48,200
get low weighting and that's what the,

196
00:09:48,200 --> 00:09:50,970
what the yellow Gaussian function there
represents.

197
00:09:50,970 --> 00:09:53,150
So you can see that this is without very

198
00:09:53,150 --> 00:09:56,060
many assumptions at all, just using the
intrinsic properties

199
00:09:56,060 --> 00:09:57,990
of the data, this method's already done a
pretty

200
00:09:57,990 --> 00:10:01,268
good job of modeling the, the periodic
sine function.

201
00:10:01,268 --> 00:10:05,410
Right, so this is quite a powerful method
for regression, simply

202
00:10:05,410 --> 00:10:08,840
because it makes so few assumptions about
the intrinsic structure of

203
00:10:08,840 --> 00:10:11,190
the data, the parametric form of the data
and can be

204
00:10:11,190 --> 00:10:14,200
used, just out of the box on a wide range
of problems.

205
00:10:14,200 --> 00:10:15,020
But it's not perfect.

206
00:10:15,020 --> 00:10:17,410
And in particular you'll note challenges
at the

207
00:10:17,410 --> 00:10:19,500
edges, right, where there's a little bit
of bias.

208
00:10:19,500 --> 00:10:22,910
The function sags a little bit at the
edges instead of.

209
00:10:22,910 --> 00:10:25,390
Modeling the data precisely there and
that's because we're

210
00:10:25,390 --> 00:10:27,930
being unduly weighted by that data points
on one

211
00:10:27,930 --> 00:10:31,650
side of that, that function of the very
extreme

212
00:10:31,650 --> 00:10:35,270
side X values, on the extreme left and
extreme right.

213
00:10:35,270 --> 00:10:39,660
So we aren't doing as good a job of
modeling our underlying function there.

214
00:10:39,660 --> 00:10:43,740
And there are ways to address this one, a
common way to do that is

215
00:10:43,740 --> 00:10:49,270
by adding a little bit of, of parametric
inference into this by, by building in.

216
00:10:49,270 --> 00:10:50,590
Into our local, instead of using a

217
00:10:50,590 --> 00:10:54,710
local average, actually using a local,
linear regression,

218
00:10:54,710 --> 00:10:56,600
that takes into account the linear
structure

219
00:10:56,600 --> 00:10:58,970
of the data set at those edge points.

220
00:10:58,970 --> 00:11:00,880
And this is what local linear regression
looks like.

221
00:11:00,880 --> 00:11:03,950
It's actually very similar to kernel
smoothing in a lot of ways.

222
00:11:03,950 --> 00:11:07,130
But it builds off of standards lee's
square linear regression.

223
00:11:07,130 --> 00:11:11,950
So you may be familiar with the hatmey
tricks and standard linear lee's squares.

224
00:11:11,950 --> 00:11:16,310
Here's an example of a, a liner lee's
estimate of x sub not.

225
00:11:16,310 --> 00:11:22,270
Where we've defined the data matrix B and
our predictor is Y.

226
00:11:22,270 --> 00:11:22,450
Right.

227
00:11:22,450 --> 00:11:26,090
So this projects the the data onto the
column space

228
00:11:26,090 --> 00:11:29,230
of the design matrix B is the basic
premise here.

229
00:11:29,230 --> 00:11:33,480
Now, if we add kernel weights to this,
right, so that we weight our nearest

230
00:11:33,480 --> 00:11:35,020
neighbors more highly in this regression,
we

231
00:11:35,020 --> 00:11:36,680
get an expression that looks something
like this.

232
00:11:36,680 --> 00:11:43,860
So we've added matrices W of X sub note /
g which represents the kernel evaluation.

233
00:11:43,860 --> 00:11:47,840
Of all of the data points to the location
X sub not.

234
00:11:47,840 --> 00:11:48,210
Right?

235
00:11:48,210 --> 00:11:51,740
So that's a diagonal matrix with all the
colonel weights on the diagonal.

236
00:11:51,740 --> 00:11:53,430
So just by making this simple change,

237
00:11:53,430 --> 00:11:55,220
we've actually created a local linear
regression

238
00:11:55,220 --> 00:11:58,880
problem that will let us predict the value
of this function at X sub not.

239
00:12:00,340 --> 00:12:01,250
And this is what it looks like.

240
00:12:01,250 --> 00:12:04,750
And you can see it does a very good job of
modeling our, our sine function.

241
00:12:04,750 --> 00:12:09,410
And in particular it's removed the bias at
the extremes the extreme left

242
00:12:09,410 --> 00:12:11,190
and extreme right, so we're actually
modelling

243
00:12:11,190 --> 00:12:14,180
the local linear structure there quite
accurately.

244
00:12:14,180 --> 00:12:16,340
But otherwise it's very similar to, to
kernal smoothing.

245
00:12:18,120 --> 00:12:20,660
Okay, there's one more local method for

246
00:12:20,660 --> 00:12:22,170
pattern recognition that I'd like to talk
about.

247
00:12:22,170 --> 00:12:24,250
And this is kernel density estimation.

248
00:12:24,250 --> 00:12:29,100
So this is the, this is meant to address
the density estimation problem.

249
00:12:29,100 --> 00:12:31,260
So if we want to estimate a probability
density

250
00:12:31,260 --> 00:12:35,070
or a conditional probability density in
this input space.

251
00:12:35,070 --> 00:12:40,390
One way to do that is simply assume that
each input point is responsible

252
00:12:40,390 --> 00:12:43,050
for a local kernel, right, a local

253
00:12:43,050 --> 00:12:47,050
probability density function in its
immediate neighborhood.

254
00:12:47,050 --> 00:12:51,370
So we can take the density to be the sum
of all, or the density of

255
00:12:51,370 --> 00:12:52,610
any new point to be the sum of

256
00:12:52,610 --> 00:12:55,440
all the kernel evaluations of all our
training data.

257
00:12:55,440 --> 00:12:58,290
So this, this image here right show an
example of that.

258
00:12:58,290 --> 00:13:04,090
We got just one real valued input here on
the X-axis and we convulsed our kernel

259
00:13:04,090 --> 00:13:09,700
across that and summed up the response of
the kernel over all those data points.

260
00:13:09,700 --> 00:13:11,660
To provide some estimates of the density.

261
00:13:11,660 --> 00:13:13,650
Here are the true density is given by the

262
00:13:13,650 --> 00:13:17,190
grey curve and the estimated densities are
given bu the

263
00:13:17,190 --> 00:13:20,010
various color curves as we change our
current bandwidth, you

264
00:13:20,010 --> 00:13:22,890
can see that the density estimate becomes
smoother or more

265
00:13:22,890 --> 00:13:26,440
wiggly right which is [UNKNOWN] to the
regularization that we

266
00:13:26,440 --> 00:13:31,945
saw before both with the increase in the
number of

267
00:13:31,945 --> 00:13:35,070
[INAUDIBLE] we can do exactly the same
thing here note

268
00:13:35,070 --> 00:13:37,580
that the blue might even be a bit over
smooth.

269
00:13:37,580 --> 00:13:40,010
Looks right, so we're doing a pretty good
job of modeling the underlying

270
00:13:40,010 --> 00:13:44,260
galaxy influction, but we've started to
truncate its peak a little bit, right?

271
00:13:44,260 --> 00:13:48,540
So maybe a width of point three is a
little bit too much.

272
00:13:48,540 --> 00:13:51,790
One thing to note about this expression,
note that it's normalized to provide

273
00:13:51,790 --> 00:13:54,220
a true probability density estimate, so
it's

274
00:13:54,220 --> 00:13:57,020
a valid PDF so that the normalization.

275
00:13:57,020 --> 00:14:00,420
Factor Z, zed normalizes our kernel
function so

276
00:14:00,420 --> 00:14:03,130
that all the kernel evaluations have a
volume

277
00:14:03,130 --> 00:14:08,220
one or area one and we're also dividing by
the total number of data points that

278
00:14:08,220 --> 00:14:10,380
enter into this kernel density estimate
that's the

279
00:14:10,380 --> 00:14:12,230
n score so our density you were to

280
00:14:12,230 --> 00:14:14,360
evaluate the density everywhere in this
space and

281
00:14:14,360 --> 00:14:17,080
integrate that we get an area of one.

282
00:14:18,390 --> 00:14:18,600
Okay.

283
00:14:18,600 --> 00:14:23,710
So, how would you go about setting all of
these these regularization terms?

284
00:14:23,710 --> 00:14:26,990
Well, typically you'd simply use cross
validation.

285
00:14:26,990 --> 00:14:29,810
You could use you can leave one point out

286
00:14:29,810 --> 00:14:32,890
and look at your performance estimating at
that point

287
00:14:32,890 --> 00:14:35,440
for either regression or classification
and you use that

288
00:14:35,440 --> 00:14:37,780
to adjust the kernel bandwidths so the
number [UNKNOWN].

289
00:14:37,780 --> 00:14:40,070
That's probably the most common way.

290
00:14:40,070 --> 00:14:43,750
I guess the anag the the analogous method
for density estimation would

291
00:14:43,750 --> 00:14:46,460
be look at the, the, likelihood of held
out data points, right?

292
00:14:46,460 --> 00:14:49,070
So, the, the cross validation is the, the

293
00:14:49,070 --> 00:14:51,670
typical way that one would estimate these,
these parameters.

294
00:14:51,670 --> 00:14:53,880
But, fortunately there's really only one
parameter

295
00:14:53,880 --> 00:14:55,910
to estimate which is the, in this case.

296
00:14:55,910 --> 00:14:56,570
The kernel width.

297
00:14:56,570 --> 00:14:58,440
So we get a wide range of very

298
00:14:58,440 --> 00:15:02,030
flexible functions out of very few input
parameters.

299
00:15:02,030 --> 00:15:05,300
We're letting the data speak for itself
unlike a parametric method.

300
00:15:06,320 --> 00:15:10,920
And this is the, the real power of these
local methods for pattern recognition.

301
00:15:10,920 --> 00:15:11,140
Okay.

302
00:15:11,140 --> 00:15:14,010
So, in summary I've described some

303
00:15:14,010 --> 00:15:16,880
local nonparametric methods for pattern
recognition.

304
00:15:16,880 --> 00:15:21,300
This is in contrary to parametric methods
that imply some

305
00:15:21,300 --> 00:15:25,420
global functional form for the process
that generates the data here.

306
00:15:25,420 --> 00:15:29,580
We're just looking at local patches of
data to infer the

307
00:15:29,580 --> 00:15:33,990
values of the underlying function or
process at some query point.

308
00:15:33,990 --> 00:15:36,710
And there are 3 different examples of

309
00:15:36,710 --> 00:15:40,475
this local pattern recognition that I
demonstrated.

310
00:15:40,475 --> 00:15:42,920
K-nearest neighbor for classification.

311
00:15:44,140 --> 00:15:47,370
Kernel smoothing and local linear
regression for regression problems

312
00:15:47,370 --> 00:15:51,840
and then kernel density estimation for
probability density estimation tasks.

313
00:15:51,840 --> 00:15:54,870
In order, the main parameter is
regularization and

314
00:15:54,870 --> 00:15:56,980
you can set this using a cross validation
strategy.