1
00:00:00,000 --> 00:00:04,921
In this video, I'd like to tell you about
the idea of vectorization. So whether

2
00:00:04,921 --> 00:00:09,743
you're using Octive, or a similar language
like Mad Lab, or whether you're using

3
00:00:09,743 --> 00:00:14,565
[inaudible], Java, [cough]++, all of these
languages have either built into them or

4
00:00:14,565 --> 00:00:19,021
have redily and easily accessible
difference in numerical linear algebra

5
00:00:19,021 --> 00:00:23,783
libraries that will usually be very well
written, highly optimized often so as

6
00:00:23,783 --> 00:00:28,544
developed by people that, you know, have
PhDs in numerical computing, or they're

7
00:00:28,544 --> 00:00:33,366
really specialized in numerical computing.
And when you're implementing machine

8
00:00:33,366 --> 00:00:38,250
learning algorithms, if you're able to
take advantage of these linear algorithms.

9
00:00:38,250 --> 00:00:43,052
Picture of libraries or these numerical
linearchal libraries and make some routine

10
00:00:43,052 --> 00:00:47,566
calls to them rather than sort of write
code yourself to do things that these

11
00:00:47,566 --> 00:00:52,368
libraries could be doing if you do that
then often you get code that is first more

12
00:00:52,368 --> 00:00:56,824
efficient so just run more quickly and
take better advantage of any parallel

13
00:00:56,824 --> 00:01:01,511
hardware that your computer may have and
so on and second it also means that you

14
00:01:01,511 --> 00:01:06,140
end up with less code that you need to
write so the simpler implementation that

15
00:01:06,140 --> 00:01:11,116
it's therefore may be also more likely to
be [inaudible] and as a concrete example

16
00:01:11,290 --> 00:01:16,340
Rather than writing code yourself to
multiply matrices, if you let Otter do it

17
00:01:16,340 --> 00:01:21,066
by typing AxB, that will use a very
efficient routine to multiply the two

18
00:01:21,066 --> 00:01:26,440
matrices. And there's a bunch of examples
like these where if you use a [inaudible]

19
00:01:26,440 --> 00:01:31,749
implementations you get much simpler code
and much more efficient code. Let's look

20
00:01:31,749 --> 00:01:37,039
at some examples. Here's our usual
hypothesis of linear progression, and if

21
00:01:37,039 --> 00:01:43,360
you want to compute H of X notice this sum
on the right and so one thing you could do

22
00:01:43,360 --> 00:01:48,810
is compute the sum from J=0 to J=N
yourself. Another way to think of this is

23
00:01:48,810 --> 00:01:55,480
to think of [inaudible] as theta transpose
X. And, what you can do is think of this

24
00:01:55,480 --> 00:02:01,992
as, you know, computing this inner product
between two vectors, where, theta is, you

25
00:02:01,992 --> 00:02:07,955
know, your vector [inaudible] theta zero,
theta one, theta two. If you have two

26
00:02:07,955 --> 00:02:13,882
features, if N=2. And if you think of X as
is vector XO, X1, X2. And. These two views

27
00:02:13,882 --> 00:02:18,001
can give you two different
implementations. Here's what I mean.

28
00:02:18,001 --> 00:02:23,383
Here's an unauthorized implementation for
[inaudible]. And by unauthorized, I mean

29
00:02:23,383 --> 00:02:27,900
without vectorization. We might first
initialize, you know, prediction,

30
00:02:27,900 --> 00:02:32,883
[inaudible] to be 0.0. This is going to
eventually be, prediction's gonna

31
00:02:32,883 --> 00:02:37,666
eventually be, be [inaudible]. And then
agree to have a [inaudible] for J=1

32
00:02:37,666 --> 00:02:42,914
through N=1, prediction gets incremented
by theta J times XJ. So it's kind of this

33
00:02:42,914 --> 00:02:48,476
expression over here. By the way, I should
mention. In D sectors like [inaudible]

34
00:02:48,476 --> 00:02:54,279
over here I have these vectors being zero
index I have data zero data one data two

35
00:02:54,279 --> 00:03:00,151
but because mat lab is one index beta zero
in that map we might end up representing

36
00:03:00,151 --> 00:03:05,662
as data one. And the second element ends
up as theta two, and this third element

37
00:03:05,662 --> 00:03:11,241
might end up as theta three, just because,
vectors and [inaudible] are indexed

38
00:03:11,241 --> 00:03:17,030
starting from one, even though, you know,
I wrote theta a X here starting, indexing

39
00:03:17,030 --> 00:03:22,260
from zero. Which is why, here, I have a
[inaudible]. J goes from one through N+1,

40
00:03:22,260 --> 00:03:27,225
rather than J goes through zero up to N.
Right so this is an unvectorized

41
00:03:27,225 --> 00:03:32,896
implementation in that we have a full view
of that you know summing up the N elements

42
00:03:32,896 --> 00:03:38,040
of the sum. In contrast here's how you
would write a vectorized implementation.

43
00:03:38,040 --> 00:03:43,456
Which is that you would think of. X and
eta as vectors, and you just set

44
00:03:43,456 --> 00:03:49,102
prediction equals theta [inaudible] times
x. Just computing like so. So you, instead

45
00:03:49,102 --> 00:03:54,680
of [inaudible] all these line of code for
you there just is one line of code and

46
00:03:54,680 --> 00:03:59,775
what this, what, what this code on the
right will do is it will use octaves,

47
00:03:59,775 --> 00:04:05,077
highly atomized numerical [inaudible]
routines to compute this inter-product

48
00:04:05,077 --> 00:04:10,723
routine the two vectors theta and x and
not only is the vectorized implementation

49
00:04:10,723 --> 00:04:16,960
simpler it will also run much more
efficiently. [sound] So that was octave

50
00:04:16,960 --> 00:04:22,780
like the issue of vectorization applies to
other programming languages as well. Let's

51
00:04:22,780 --> 00:04:28,188
look at the example in C++ here's what an
unvectorized implementation might look

52
00:04:28,188 --> 00:04:34,323
like, we again initialize. Your prediction
to 0.0 and then we now have a full loop

53
00:04:34,323 --> 00:04:40,563
for J=0 up to n. Prediction plus = theta J
times XJ where J you have this explicit

54
00:04:40,563 --> 00:04:46,329
folder that you write yourself. In
contrast, using a good numerical linear

55
00:04:46,329 --> 00:04:53,740
algebra library in C++ you could use,
write the function like or rather. [cough]

56
00:04:54,160 --> 00:04:58,990
In contrast, using a good numerical linear
algebra [inaudible] in C++, you can,

57
00:04:58,990 --> 00:05:04,207
instead, write code that might look like
this. So depending on the details of your

58
00:05:04,207 --> 00:05:09,360
numerical linear algebra [inaudible], you
[inaudible] have an object. This is a C++

59
00:05:09,360 --> 00:05:14,255
object, which is vector theta, and the C++
object, which is, in fact, an X. And you

60
00:05:14,255 --> 00:05:19,441
just take a theta [inaudible] transpose
times X, [inaudible]. This times becomes a

61
00:05:19,441 --> 00:05:24,415
C++ to overload the operator so you can
just multiply these two vectors in C++ and

62
00:05:24,415 --> 00:05:29,765
depending on you know the details of your
numerical algebra library you might end up

63
00:05:29,765 --> 00:05:34,802
using a slightly different syntax but by
relying on the library to do this in a

64
00:05:34,802 --> 00:05:39,838
product you can get a much more simpler
piece of code and a much more efficient

65
00:05:39,838 --> 00:05:44,830
one. Let's now look at a more
sophisticated example. Just to remind you,

66
00:05:44,830 --> 00:05:50,648
here's an update rule for [inaudible], for
linear regression. And, so we updated

67
00:05:50,648 --> 00:05:56,251
theta J using this rule for all values of
J=0, one, two, and so on. And [inaudible]

68
00:05:56,251 --> 00:06:02,531
write out. These equations data zero data
one data two assuming we have two features

69
00:06:02,531 --> 00:06:08,093
so N=2 then these are the updates we
perform to theta zero theta one theta two

70
00:06:08,093 --> 00:06:13,582
where you might remember my saying in an
earlier video that these should be

71
00:06:13,582 --> 00:06:18,638
simultaneous updates, so let's see if we
can come up with a vectorized

72
00:06:18,638 --> 00:06:23,735
implementation of this. Here my same three
equations written in a slightly smaller

73
00:06:23,735 --> 00:06:28,569
form and you can imagine that one way to
implement these three lines of code is to

74
00:06:28,569 --> 00:06:33,461
have a for-loop that says you know for J =
zero one through two to update near the J

75
00:06:33,461 --> 00:06:38,178
or something like that but instead lets
come up with a vectorized implementation

76
00:06:38,178 --> 00:06:42,837
and see [inaudible] we can have a simpler
way to basically suppress these three

77
00:06:42,837 --> 00:06:47,844
lines of code or for-loop [inaudible]. You
know the fact of the does these three sets

78
00:06:47,844 --> 00:06:52,719
one set at a time lets see if we can take
these three sets and compress them into

79
00:06:52,719 --> 00:06:57,654
one line of a vectorized code. Here's the
idea, what I'm going to do is I'm going to

80
00:06:57,654 --> 00:07:05,687
think of. Theta as a vector and I'm going
to update theta as theta. Minus Alpha

81
00:07:05,687 --> 00:07:17,337
times some other vector, Delta. Where
Delta is going to be equal to one over M,

82
00:07:17,337 --> 00:07:27,989
sum from I=1 through M. And then this
term. Over on the right. Okay, so let me

83
00:07:27,989 --> 00:07:35,546
explain what's going on here. Here I'm
going to treat theta as a vector so

84
00:07:35,546 --> 00:07:43,614
there's an n+1 dimensional vector. I'm
saying that theta gets updated as that's a

85
00:07:43,614 --> 00:07:50,375
vector or n+1. Alpha is a real number and
delta here. Is a vector. So this

86
00:07:50,375 --> 00:07:56,996
subtraction operation, that's a vector
subtraction, okay? Cuz, Alpha times Delta

87
00:07:56,996 --> 00:08:03,286
is a vector, and so I'm saying theta,
gets, you know, this vector, Alpha X Delta

88
00:08:03,286 --> 00:08:10,321
subtracted from it. So, what is the vector
Delta? Well, this vector Delta. Looks like

89
00:08:10,321 --> 00:08:16,809
this. And what it's meant to be is really
meant to be. This thing over here. Briefly

90
00:08:16,809 --> 00:08:23,876
delta would be a m plus one dimensional
vector and the very first element of the

91
00:08:23,876 --> 00:08:30,767
vector delta was going to be hold you
that. So if we have the delta you have to

92
00:08:30,767 --> 00:08:37,833
in taxiii from zero was delta zero, delta
one, delta two. What I want is that delta

93
00:08:37,833 --> 00:08:46,515
zero. Is equal to you know this first box
in green up above and in D you might be

94
00:08:46,515 --> 00:08:55,299
[inaudible] that Delta Zero is one of the
N sum of you know H of X, X I - Y I. Times

95
00:08:55,299 --> 00:09:02,945
XIO. So, let's just make sure that, we're
on the same page about how Delta really is

96
00:09:02,945 --> 00:09:10,051
computed. Delta is one over M times the
sum over here. And, you know, what is this

97
00:09:10,051 --> 00:09:20,100
sum? Well, this term over here. That's her
real number. And, the second term over

98
00:09:20,100 --> 00:09:28,161
here, XI. This term over there is a
vector, right?'Cause XI, you know, may be

99
00:09:28,161 --> 00:09:37,200
a vector, that would be, say, XI0, XI1,
XI2, right? And what is the summation?

100
00:09:37,200 --> 00:09:48,825
Well, what the summation's saying is that
this term. That is this term over here, it

101
00:09:48,825 --> 00:10:03,750
is equal to H of X1. Minus y one times x
one. Plus H of X2 minus Y2. Times x two.

102
00:10:03,750 --> 00:10:09,843
Plus. You know, and so on. Okay, because
the summation of an i. So as I ranges from

103
00:10:09,843 --> 00:10:16,458
I equals one to m. These different terms,
I'm summing up these terms here. And the

104
00:10:16,458 --> 00:10:22,990
meaning of each and these terms, this is a
lot like, if you remember, from the

105
00:10:22,990 --> 00:10:29,192
earlier quiz right? You solved this
equation we said that in order to

106
00:10:29,192 --> 00:10:35,559
[inaudible] this code. We said that u
equals two times the factor v plus five

107
00:10:35,559 --> 00:10:41,689
times the factor w. This is the example of
how to add different factors. The

108
00:10:41,689 --> 00:10:47,398
summation is the same thing. Saying that.
This summation over here. Is just some

109
00:10:47,398 --> 00:10:53,070
rule number right that's kinda like the
number two and some other number times the

110
00:10:53,070 --> 00:10:58,537
vector X1 this is kinda like you know two
times V [inaudible] some other number

111
00:10:58,537 --> 00:11:03,936
times X1 and then plus instead of five
times W we instead have some other rule

112
00:11:03,936 --> 00:11:09,539
number plus some other vector and then you
add on other vectors you know plus dot,

113
00:11:09,539 --> 00:11:15,381
dot, dot, dot, dot, plus the other
vectors, which is why overall. This thing

114
00:11:15,381 --> 00:11:23,596
over here that whole quantity that deltar
is just some vector. And concretely the

115
00:11:23,596 --> 00:11:30,048
three elements of delta correspond if E =
two. The three elements of delta

116
00:11:30,048 --> 00:11:35,959
correspond exactly to this thing. To the
second thing and this third thing which is

117
00:11:35,959 --> 00:11:41,705
why when you update theta according to
theta minus alpha delta we end up carrying

118
00:11:41,705 --> 00:11:47,501
exactly the same simultaneous updates as
the update rules that we have up top. So I

119
00:11:47,501 --> 00:11:52,704
know that there was a lot that happens on
the slides. But, again, [inaudible] to

120
00:11:52,704 --> 00:11:58,035
pause the video, and I'd, encourage you to
sort of step through the difference. If

121
00:11:58,035 --> 00:12:03,303
you're not sure what just happened, I'd
encourage you to, step through the slide

122
00:12:03,303 --> 00:12:08,506
to make sure you understand. Why is it
that this update here with this definition

123
00:12:08,506 --> 00:12:13,709
of Delta, right? Why is it that that's
equal to this update on top? And if still

124
00:12:13,709 --> 00:12:18,688
not clear, one, one, one insight is that,
you know, this. Thing over here. That's

125
00:12:18,688 --> 00:12:23,959
exactly the vector X. And so we're just
taking, you know, all three of these

126
00:12:23,959 --> 00:12:29,800
computations, and compressing them into
one step, which is, vector delta, which is

127
00:12:29,800 --> 00:12:35,428
why we can come up with a vectorized
implementation of this, of this step of

128
00:12:35,428 --> 00:12:40,525
the linear regression this way. So. I hope
this, step makes sense. And, do, do look

129
00:12:40,525 --> 00:12:44,859
at the video, and make sure, and see if
you can understand it. In case you don't

130
00:12:44,859 --> 00:12:49,246
understand quite the equivalance of this
math, if you implement this, this turn out

131
00:12:49,246 --> 00:12:53,473
to be the right answer anyways. So even,
even if you didn't quite understand the

132
00:12:53,473 --> 00:12:57,700
equivalence. If you just implement it this
way, you, you, you'll be able to get

133
00:12:57,700 --> 00:13:02,302
linear regression to work. But, if you're,
if you're able to figure out why these two

134
00:13:02,302 --> 00:13:06,582
steps are equivlant, then hopefully, that
will give you a better understanding of

135
00:13:06,582 --> 00:13:13,142
vectorization as well. And finally. If,
you. Are implementing linear regression

136
00:13:13,142 --> 00:13:17,345
using more than one or two features. So
sometimes, we use linear regression with

137
00:13:17,345 --> 00:13:21,175
tens, or hundreds, or thousands of
features. But if you use the vectorized

138
00:13:21,175 --> 00:13:25,272
implementation of linear regression,
[inaudible] will run much faster than if

139
00:13:25,272 --> 00:13:29,368
you had, say, your old folder, that was,
you know, updating theta zero, then theta

140
00:13:29,368 --> 00:13:33,571
one, then theta two yourself. So using a
vectorized implementation, you should be

141
00:13:33,571 --> 00:13:37,508
able to get a much more efficient
implementation of linear regression. And,

142
00:13:37,668 --> 00:13:41,977
when you vectorize later algorithms that
we'll see in this class is a good trick.

143
00:13:42,137 --> 00:13:46,825
Whether an octave or some [inaudible]. C
plus as driver for getting your code to

144
00:13:46,825 --> 00:13:48,159
run more efficiently.