Lecture 10.1: Gradient-Free Numerical Optimization

Recording. Download the text transcript.

Automatic transcript; technical terms and equations may contain recognition errors.

00:00:00 Okay, let's get started. Howdy.

00:00:03 So any remaining questions before I start about the homework or previous contents?

00:00:14 Okay, so previously we talked about the formulation of numerical optimization

00:00:22 because it's non-convex gradient-based, right?

00:00:26 For protein structure prediction in the midnight zone.

00:00:32 And we actually quite much enjoyed the art of starting with simple algorithms

00:00:40 and then trying to bring in the algorithm innovation.

00:00:45 And that was under the guideline of theoretical concepts like complexity and convergence rate, right?

00:00:52 We saw that the steepest descent is simple but slow, yet the Newton's method is complicated but faster.

00:01:06 So the question is, can you get a little bit better in both worlds?

00:01:10 Can you improve one from the extreme of that spectrum a little bit toward the sweet spot in between?

00:01:18 So we very much enjoyed how these theoretical concepts guided our algorithmic innovation, right?

00:01:26 In the meantime, we also knew that these gradient-based algorithms are only useful probably just for local minimization

00:01:34 because they are too expensive to get, yet not that informative for the global search.

00:01:43 So you can locally remove some clashes and that's probably what gradients are good at.

00:01:49 So very often we have to count on the derivative-free optimization, and that's why we talked about Markov-Chen Monte Carlo.

00:01:58 Okay?

00:01:59 So last time we started with the motivation of this Markov-Chen Monte Carlo.

00:02:07 The motivation is to sample a distribution, a probability distribution, because now the atomic coordinates,

00:02:16 or however you parameterize the search space or conformational state, can be regarded as an X that is a random variable.

00:02:24 And we know theoretically what's the distribution of the random variable, right?

00:02:30 It's following the Boltzmann distribution, exponential, right?

00:02:34 To the negative proportional to the Gibbs free energy, right?

00:02:41 And in this case, we're going to sample the distribution instead for the purpose of optimization.

00:02:48 Now we had a flavor of it, right?

00:02:51 It only depends on the sampling, and every time you just decide whether you accept the new samples or not based on what probability.

00:03:03 And the new samples are perturbations of the previous sample.

00:03:08 Again, iterative update rules, right?

00:03:12 So it's iterative algorithm.

00:03:13 So we said that we wanted to understand, right, where is this coming from?

00:03:19 This seems very simple.

00:03:21 So that's why we said that, well, actually, the gist of the story is we were actually constructing a proper Markov-Chen

00:03:30 so that the sampling could follow the desired distribution.

00:03:35 So that's the story behind it.

00:03:37 So we're going to try to understand this in this lecture.

00:03:42 So again, we have, for those of you who haven't taken stochastic processes, you could consider these electronic copies for the concepts, okay?

00:03:55 So, as we said, the Markov chain, what is a Markov chain, right?

00:04:01 It's a stochastic process.

00:04:03 The stochastic process means that a random variable that is time-dependent.

00:04:09 In our case, this random variable is x, and then n is a discrete time, okay?

00:04:16 And the state space of this stochastic process means the variables that this random variable stochastic process can take.

00:04:26 That is also discrete in this case, okay?

00:04:29 So that's why you have a chain, right?

00:04:32 The chain is connecting different state spaces.

00:04:37 I'm sorry, different values in the state space, okay?

00:04:41 Different states, in other words.

00:04:43 So a Markov chain is basically saying that if in the previous, in the previous, you have this whole history of the states,

00:04:53 and you are asking about the next state being j, right?

00:04:59 n plus 1, meaning the next, you will find that this probability is actually only dependent on the present, not the past.

00:05:08 So in other words, it's memoryless. It's Markovian, okay?

00:05:13 So in this sense, we are looking at this chain connecting the states from the previous time point to the current time point, okay?

00:05:27 And this conditional probability is also called a transition probability, right?

00:05:33 The probability that the present state is i and the next state is j.

00:05:37 If you put all this together, you have a matrix called a transition matrix.

00:05:43 Okay, so we are all familiar with the Markov chain.

00:05:48 I think most of you are, so I'm just going to say it very quickly.

00:05:52 Let's say this is one example.

00:05:54 This is the springtime weather in New York City.

00:05:57 This is a stochastic process because you have a random variable who's taking three possible values,

00:06:08 nice, rainy, snowy, on every day.

00:06:13 So, right?

00:06:14 The day, every day is a time point.

00:06:17 So let's say if it's nice today, then tomorrow will be rainy with 75% of the chance,

00:06:24 and it will be snowy for 25% of the time, okay?

00:06:28 So in this sense, we can continue doing that if it's raining today.

00:06:34 So in other words, we are given the conditional probabilities or the transition probabilities, right?

00:06:40 Because the conditions were conditioned on the past and calculating the conditional probability over the present, okay?

00:06:49 And we can keep doing this, okay?

00:06:51 So now we can represent this as a Markov chain, right?

00:06:56 With how many nodes?

00:06:59 That's how many states you have, so three states, right?

00:07:04 So we can represent it as a kind of graph, right?

00:07:08 N, S, R, like for the three different states.

00:07:11 And we can sort of represent this Markov chain using these nodes connected by the arcs.

00:07:23 So the arcs indicate the transition probability, okay?

00:07:27 So for instance, 0.75 here means pi ij where i equal to n and j equal to r.

00:07:35 In other words, the present state is n, nice, and the next day is rain.

00:07:41 So that percentage is 75%.

00:07:44 So this is the transition state.

00:07:46 This is an example of Markov chain, okay?

00:07:49 If you imagine that you are starting from some state and you can keep sampling following the Markov chain,

00:07:56 you may wonder what would happen in the end, right?

00:08:01 Okay, so much for the concept and we need to talk a little bit more about the Markov chain, okay?

00:08:10 So there are different kind of Markov chains.

00:08:12 I want you to be aware of these three concepts.

00:08:17 Irreducible, apyriotic, and recurrent, okay?

00:08:21 So a Markov chain is irreducible if it is possible to access any state from any state, okay?

00:08:30 So in other words, starting from any node on that graph, you can reach any other node.

00:08:35 So that's irreducible.

00:08:38 Aperiodic means that it takes irregular time to return to any state instead of like multiples of certain number, okay?

00:08:48 So in other words, if you have a cycle, then it wouldn't be regular time to return, right?

00:08:55 Right?

00:08:56 Because you can take, if the cycle consists of three states on the cycle, then you can return to that point on the cycle

00:09:03 after three time periods or six or three times n in general.

00:09:10 So in that case, it will be periodic, okay?

00:09:13 So in that case, Markov chain is recurrent if it's not transient.

00:09:19 In other words, the probability that we start at a state and at some time, and we will return to that state eventually, is one.

00:09:32 Okay?

00:09:33 So it's not transient.

00:09:34 So there is a chance to return to the state, okay?

00:09:38 So positive recurrent means that not only that you expect to return to the state with non-zero probability,

00:09:48 you are also expected to return first time in finite time, okay?

00:09:54 So it's possible that the probability is one to return, but the expected time to return for the first time is infinite.

00:10:03 So in that case, it's not positive recurrent, it's just recurrent, okay?

00:10:08 All right, so is it clear what these concepts are?

00:10:12 You have learned these concepts, right, before, right?

00:10:15 So this is a little bit of a reminder.

00:10:18 Now, let's talk about two kinds of distributions.

00:10:24 So stationary distribution and the limiting distribution, two kinds of distributions, okay?

00:10:31 So I think we understand why we are talking about the distribution, because we are talking about stochastic processes, right?

00:10:39 So the distribution is about the states, okay?

00:10:42 So let's use a notation, for instance, rho, right?

00:10:46 In this case, because of the expression, let's treat it as a rho vector, and pi is what we have seen before, the transition matrix, okay?

00:10:59 So a stationary distribution says the following.

00:11:04 First of all, we understand that the dimensionality of rho is the size of the state space, right?

00:11:08 It's a probability being at any state, right?

00:11:12 So that's a distribution over the state space, okay?

00:11:16 So apparently, the sum of all the elements should be one because of normalization, right?

00:11:24 You have to be at some state.

00:11:27 But the equilibrium that defines the stationary distribution says that rho equal to rho pi.

00:11:37 What does it mean?

00:11:41 If you look at, for instance, the i-th element of rho, on the left, you have the i-th element of rho, rho i, right?

00:11:53 On the right, you have a weighted sum, right?

00:11:58 rho 1 times pi 1, 1 plus rho 2 times pi 2, 1 plus rho 3 times pi 3, 1 and so on.

00:12:10 What is this thing?

00:12:13 What's on the right?

00:12:14 Rho 1 times pi 1, 1 plus rho 2 times pi 2, 1 plus rho 3 times pi 3, 1 plus all the way to rho n, let's say if there are n states, times pi n, 1.

00:12:34 What is this expression in probability?

00:12:49 It's a total probability, isn't it?

00:12:52 Rho 1 is the probability that you are being at state 1 and times pi 1, 1, which is the probability that the next state is 1,

00:13:03 given that the present state is 1, right?

00:13:06 And you have rho 2 times pi 2, 1 and so on, right?

00:13:10 So in other words, what you found is the following, right?

00:13:15 If I take the total probability and calculate the distribution of the state space, in the state space,

00:13:24 after one step of transition, I find myself being at the same distribution rho, isn't it?

00:13:31 It's still rho on the left, right?

00:13:35 On the right, it says that let's start with the rho distribution.

00:13:38 Let's say at this current time point, we don't know which state it belongs to, but I know the distribution, okay?

00:13:45 The chance that the current state is at state 1 is rho 1.

00:13:52 The chance that the current variable is taking the value of state 2 is rho 2 and so on, right?

00:13:59 So it's a total probability right here.

00:14:01 So if it equals to rho, it means what?

00:14:04 It means after one step of transition, you still end up having this distribution rho, isn't it?

00:14:13 This means once you reach the distribution rho, you will stop there forever.

00:14:23 Because one step of transition, two step of transition, you will still end up having rho, right?

00:14:30 So that's why we say it's equilibrium.

00:14:32 So this is a stationary distribution, meaning that once you're there, you're going to stay there, okay?

00:14:39 So that's what stationary distribution means, okay?

00:14:44 There's a second concept for the distribution called the limiting distribution, right?

00:14:48 Based on the name, you can guess what the limiting means.

00:14:51 The limiting means the limiting in the time, okay?

00:14:54 Or the number of transitions.

00:14:57 So to explain that concept, we first have to remind ourselves the Chapman-Korma-Gorov equation, right?

00:15:06 So which is actually kind of intuitive and can be also explained by something I said before, okay?

00:15:14 So the question is the following.

00:15:17 If we think about pi, right, and pi ij as a one step transition probability, okay?

00:15:25 So the probability that next day is at j given that the present day is i, right?

00:15:32 What about the n step probability in general, right?

00:15:37 What's the probability that n days later the state is j given that today's state is i?

00:15:45 What about that?

00:15:47 What about that?

00:15:48 How do we calculate that probability?

00:15:50 Or in general, what's the probability that after n plus n steps, right?

00:16:00 What's the probability that the transition after n plus n steps end up being at j if it started at i?

00:16:10 How do we calculate that probability?

00:16:14 Again, total probability, isn't it?

00:16:18 Right?

00:16:19 You can say that, well, let's start from i and take n steps and reach a k like the intermediate state, okay?

00:16:31 K days later.

00:16:32 I don't know what k equals to exactly.

00:16:35 I don't know what is the state, okay?

00:16:38 But if n days later the state is k, then what's the chance that n more days later the state is j?

00:16:50 It's just simply pi k j m, right?

00:16:53 Then because I don't know exactly which state I will end up being at k days later, then I can just sum over all the states of k.

00:17:08 Here is zero from infinity if the state space is infinity, right?

00:17:12 So in other words, this is what?

00:17:15 Total probability.

00:17:16 Again, isn't it?

00:17:17 Right?

00:17:18 So in this sense, if we rewrite it in the matrix, then we can find out that the n plus n step transition matrix is indeed the product of the n step transition matrix and n step transition matrix.

00:17:33 Isn't it?

00:17:34 Right?

00:17:35 So in other words, pi 2 equal to the square of pi, right?

00:17:40 Pi times pi.

00:17:41 Okay?

00:17:42 So now that we understand this one, then we know that, oh, okay, the n step transition matrix is simply pi to the power of n.

00:17:51 Okay?

00:17:52 So now we can talk about the limiting distribution after we have learned the Chapman-Gromov equation and its special case.

00:18:00 Okay?

00:18:01 So the limiting distribution basically says that what if, you know, you're going to the limit, that means n goes to infinity.

00:18:10 Okay?

00:18:11 So what if n goes to infinity?

00:18:14 What if n goes to infinity?

00:18:16 Okay?

00:18:17 If when n goes to infinity, you find that this pi ij to the power of n, right, becomes a value that's not dependent on i.

00:18:30 Which is only dependent on j.

00:18:33 In other words, it says that no matter where you start at i, okay, sorry, no matter where you start, okay, which is written as i here, as long as you sample enough as n goes to infinity, you will be ending up at state j with this probability j.

00:18:55 That's what the limiting distribution says, okay?

00:19:00 This happens when we have a godic Markov chain that can converge to the limiting distribution, okay?

00:19:07 This is exactly why we can do the Markov chain Monte Carlo by thinking that in the limit, it converges to the distribution we desire because of this limiting distribution, okay?

00:19:20 But why did I talk about the stationary distribution?

00:19:23 Again, stationary distribution says that once you reach there, you will stay there.

00:19:29 And the limiting distribution says that no matter where you start, as long as you run long enough, you will end up there.

00:19:38 So there are different concepts, okay?

00:19:41 But, but these can be equal to each other, which is very useful for us, okay?

00:19:49 Okay?

00:19:50 If the limiting distribution exists, okay, then, you know, they are stationary distributions, okay?

00:20:01 But stationary distributions are not necessarily limiting distributions all the time.

00:20:06 So there is, there is a difference.

00:20:08 So we need to consider this ergodicity, okay?

00:20:12 Ergodicity, right?

00:20:14 Because when we have the ergodic Markov chain, meaning that all states are irreducible, right?

00:20:20 In other words, aperiodic and positive recurrent, then the limiting distribution exists, and it will be equal to the stationary distribution, okay?

00:20:32 Okay?

00:20:33 So, in the end, you want to construct a Markov chain with the desired stationary distribution, and you also want this Markov chain to be ergodic so that when you sample it long enough,

00:20:47 the limiting distribution you observe empirically will be equal to the stationary distribution you designed, okay?

00:20:55 So that is the gist of the story.

00:20:59 Any questions so far about these two distributions?

00:21:03 Okay, we'll talk a little bit more about the last statement I just said.

00:21:08 Okay, let's come back to this example, right?

00:21:12 So we have already seen this one-step transition matrix, right?

00:21:17 And its graph representation.

00:21:19 And this is the transition probabilities, right?

00:21:25 The size is m plus n, where n is the size of the state space, okay?

00:21:31 And this is one-step transition probability, right?

00:21:37 And we can read this, and then we can talk about two-step transition probabilities, right?

00:21:46 Which is simply pi squared, and then the n-step is pi to the n, okay?

00:21:52 So for any given present time t, if you are asking that what's the probability that in n-steps it's reaching a state j,

00:22:00 given that the current time t is at state i,

00:22:03 you just look at the ij element of this n-step transition matrix, okay?

00:22:08 That's what we have learned from the slide several, two or three slides back, right?

00:22:19 Okay, Chapman-Kromagorff equations, okay?

00:22:25 Now, if we ask what's the weather like in 20 days, right?

00:22:31 This is, if you notice that, actually in this case, if you run pi to the power of 20, what did you notice?

00:22:38 The rows are all the same.

00:22:41 What does it say?

00:22:43 What does it mean?

00:22:45 Again, each row is the state at time t, or the current state, right?

00:22:54 Each column is the state in 20 days, right?

00:22:59 What does this pi to the 20 tell you?

00:23:05 Using one of the concepts that you have just learned.

00:23:21 Bless you.

00:23:24 What does it say?

00:23:29 What does it say?

00:23:30 Limiting.

00:23:31 This is a limiting distribution.

00:23:33 Each row is, the identical rows are limiting distributions, because no matter what's the state today,

00:23:40 if you run this simulation or do this transition long enough, in this case only 20 steps, or 20 days,

00:23:47 you observe that, right?

00:23:49 No matter where you start with, no matter which row on this day, you will find out that in 20 days or longer, you will have the same distribution for over the state space, right?

00:24:02 And this is the limiting distribution as Nani was saying correctly, okay?

00:24:07 This is one example of the limiting distribution.

00:24:10 Okay, so in other words, it's almost completely independent of the weather today.

00:24:17 Right?

00:24:18 That's what we said earlier, that this limiting distribution is regardless of i, right?

00:24:24 Right?

00:24:25 It's just pi j, rho j, okay?

00:24:30 All right, so now let's wrap them up and go back to the motivation, why we want to construct a Markov chain for the Markov chain Monte Carlo, right?

00:24:44 You understand the Monte Carlo part, but why Markov chain, right?

00:24:49 So this is, now, again, we said earlier, right?

00:24:57 If we said that, you know, the limiting distribution and the stationary distribution, right, what's their relationships?

00:25:04 Now let's summarize them again in one slide and learn a little bit more, okay?

00:25:11 So if you need the stationary distribution to exist, what you need is a so-called detailed balance, which says that rho i times pi ij equal to rho j times pi ji.

00:25:28 What is it telling us?

00:25:30 It's saying that if you look at two states, i and j, like two nodes on the graph, right?

00:25:41 Right?

00:25:42 And then if you start with i, the state, the probability is rho i, and then if you transition to j in one step, the probability is pi ij.

00:25:53 So that's the probability that you will reach j from i, right?

00:25:59 And what's on the right is the probability that you will reach i from j, right?

00:26:04 So this says that the probability of reaching i to j is the same as reaching j from i, right?

00:26:11 Right?

00:26:12 Right?

00:26:13 So we need this limiting distribution to follow this detailed balance, okay?

00:26:20 So this is, in other words, it's reversible, okay?

00:26:25 So this is just for the existence of the stationary distribution, right?

00:26:30 What about the uniqueness?

00:26:32 You know, it's possible that the stationary distributions may not be just the one, but maybe multiple choices, okay?

00:26:39 If you want this stationary distribution also to be unique, then you need the mark of chain to be ergodic, okay?

00:26:48 Ergodic already said that one condition is that needs to be irreducible and positive recurrent, right?

00:26:55 So, another, not the definition of ergodicity, but the property of the ergodicity basically says that, you know, the time ensemble is the same as the state ensemble, okay?

00:27:07 So, for instance, it's saying that if n is large enough, the time average is the same as the ensemble average, okay?

00:27:16 Which is following the stationary distribution.

00:27:18 The time, the time average is when you run n large enough, and this is essentially the limiting distribution, and the ensemble average is essentially the stationary distribution.

00:27:32 So this is another way of saying that the limiting distribution is equal to the stationary distribution when the Markov chain is ergodic, okay?

00:27:43 So you often do that, actually, in your sampling sometimes, right?

00:27:47 You don't know what's the distribution in the state, but then you think that I'm going to just run this Markov chain simulation long enough, then I believe that this time ensemble is the same as the state ensemble, right?

00:28:00 You're using that property.

00:28:02 But the assumption you don't often check is the Markov chain needs to be ergodic first, okay?

00:28:12 Any questions so far?

00:28:15 Okay, knowing that, then let's try to figure this out, okay?

00:28:21 How we use a Markov chain so that we can sample a desired distribution, okay?

00:28:28 So let's call it a row.

00:28:29 It's not a coincidence that I'm using row to denote the desired probability distribution over the sample space.

00:28:37 Oh, sorry, the state space, okay?

00:28:40 It's not a coincidence, okay?

00:28:43 Be careful that the samples you are collecting are correlated.

00:28:49 They are not IAD, okay?

00:28:51 So that's something you have to pay attention to.

00:28:54 So there is a more complicated version called Metropolis Hastings algorithm, and then there is a simplified version called Metropolis algorithm.

00:29:06 I will explain that to you, okay?

00:29:08 So the Metropolis Hastings algorithm is basically telling us, right, how you can make the detailed balance to be satisfied.

00:29:21 Remember, we need this stationary distribution to be existing and unique.

00:29:27 So for the existence, we need a detailed balance.

00:29:30 And for the uniqueness, we need the ergodicity, okay?

00:29:36 So the detailed balance, if we think about it, is basically saying that a row i times pi ij equal to row j times pi ji, right?

00:29:46 Row is already known because that's the desired distribution, right?

00:29:51 So the key for this Markov chain construction is constructing the transition probability pi ij, isn't it?

00:30:04 That's your key, right?

00:30:06 That also determines whether this Markov chain is recurrent or positive recurrent and so on, right?

00:30:12 So what Metropolis Hastings algorithm says that let's construct this transition probabilities pi ij to be q ij times pi ij.

00:30:20 Okay?

00:30:21 Okay?

00:30:22 Okay?

00:30:23 Okay?

00:30:24 So what this q ij is like a proposal, okay?

00:30:29 Probability.

00:30:30 The chance that I will propose j given that current, I'm sorry, the chance that I will propose j for the next time point given that the current time point of state is i.

00:30:41 So it's a conditional probability to propose that trial sample, okay?

00:30:47 And aij is a conditional probability to accept that trial sample, okay?

00:30:54 So if we write down this expression of the transition probability into the detailed balance, and we'll find out that this alpha ij, which are the elements of aij, right?

00:31:10 Needs to be minimum between these two values.

00:31:16 It's very easy to figure out, okay?

00:31:18 So I didn't put into details what is q ij and what is q ji, but this is the idea of our Metropolis Hastings algorithm, okay?

00:31:29 So there is a design of the q ij into the Metropolis Hastings algorithm, okay?

00:31:36 So the Metropolis algorithm is simple.

00:31:38 It's simpler.

00:31:39 It's saying that q ij and q ji are symmetric.

00:31:43 q ij equal to q ji.

00:31:46 If that is the case, you look at this alpha ij, the numerator and denominator have this q ij and q ji canceling each other.

00:31:55 Then you end up having minimum between one and rho j divided by rho i.

00:32:01 So is this something you have seen before?

00:32:04 Is this something you have seen before?

00:32:08 Well, let's go back to the very beginning when we talk about what is the Metropolis algorithm.

00:32:24 Did you see that alpha ij?

00:32:31 The minimum between the exponential of the minus pi times the function difference.

00:32:37 So that's exactly rho i divided by rho j.

00:32:42 Because rho i and rho j are exponential, isn't it?

00:32:45 Right?

00:32:46 Exponential minus beta e1 divided by exponential, ei divided by exponential minus beta e1.

00:32:53 So that's exactly what you have there.

00:32:56 Okay?

00:32:57 So now let's come back to this conclusion.

00:33:02 Okay, so now that we have, yeah, I actually didn't have to go there.

00:33:10 I already included in the next.

00:33:13 That's exactly what we have here.

00:33:15 Okay?

00:33:16 Remember, right?

00:33:18 Let's consider in this case,

00:33:22 a canonical ensemble.

00:33:24 That's the terminology of saying that we have the constant number of atoms in the system, right?

00:33:29 The constant volume and constant temperature.

00:33:33 It's an NVT ensemble called a canonical ensemble.

00:33:36 Okay?

00:33:37 There are different ways of simulating the molecular states.

00:33:40 This is one kind of ensemble.

00:33:43 It's NVT, constant.

00:33:45 Number of atoms, volume and temperature.

00:33:48 There are other kinds of constant choices as well.

00:33:50 For instance, you could have constant pressure, right?

00:33:53 Okay.

00:33:54 So we know that the distribution, right?

00:33:59 The desired distribution is that we want to sample is a Boltzmann distribution, right?

00:34:05 Rho i, the probability that the molecule stay in state i is proportional to the exponential to the minus beta times the energy of state i.

00:34:17 Okay?

00:34:18 So this beta has a physical meaning.

00:34:23 So it's usually one over Kb times temperature T.

00:34:26 But in our simulation, right, very often we're not dealing with the physical system.

00:34:33 So this beta is actually a parameter that, or hyperparameter you can tune by yourself.

00:34:39 Okay?

00:34:40 So, knowing that, we can perfectly figure out the algorithm we learned at the beginning then.

00:34:51 It's exactly what we talked about here, right?

00:34:54 You are proposing a trial sample, right?

00:34:57 That's your proposed J.

00:34:59 And the proposal probability is symmetric, right?

00:35:03 So all I need to do is my acceptance rate is alpha ij, isn't it?

00:35:08 It's a minimum between one and the ratio between rho j and rho i, right?

00:35:13 And the rho j and the rho i are exponential in the energy, which is Boltzmann.

00:35:18 Then you get the exponential of the difference in energy, okay?

00:35:23 Proportional to beta.

00:35:26 So it's very simple, but it's easy to be said than done.

00:35:32 There are a few things you have to consider.

00:35:35 The first thing is easy to understand.

00:35:37 Just like the step size in the gradient-based algorithms,

00:35:41 the perturbation size is also tricky.

00:35:45 If you perturb too small, it could be very slow, right?

00:35:49 It could be very slow because you are making inches of changes.

00:35:54 And you may always accept those inches of changes, but it will take you forever, right?

00:36:00 To sample the desired state.

00:36:02 But if the perturbation is too large, it's a little bit like the step size being too large in the gradient.

00:36:10 But in this case, the context is that if you are perturbing too large, like each atom can move a lot,

00:36:17 then there is a very high chance that they run into each other.

00:36:21 And you propose a much perturbed sample whose energy or function value is very high.

00:36:29 If that's the case, the chance to accept such sample is very low, right?

00:36:35 So in other words, if your perturbation is too small, you will most likely always accept it,

00:36:41 but you are going to make very little progress, right?

00:36:44 If the perturbation is too large, most likely you don't even accept it that often, okay?

00:36:51 So that's one thing to think about.

00:36:54 Another thing is how do you perturb?

00:36:56 I said the magnitude of perturbation is important.

00:37:01 What about the pattern of perturbation?

00:37:04 How do you perturb?

00:37:05 If you have a protein of all atoms, right, how do you perturb?

00:37:10 You treat them as XYZ of atom 1, 2, 3, 4, all the way to M.

00:37:15 And your perturbation will just treat all atoms as if they are independent and let all of them move.

00:37:22 Well, if you let them all move, it's most likely that some of them will run into each other, right?

00:37:31 Because you are not really respecting the bounded and non-bounded interactions, right?

00:37:36 You could move one or few atoms once in every iteration, but if you just move one atom each time,

00:37:44 then you probably end up having a similar issue like this perturbation being too small, isn't it?

00:37:49 Right?

00:37:50 Right?

00:37:51 So, one good idea is that you can consider the collective motions of all atoms.

00:37:58 In other words, yes, all atoms are moving together, but not like they are independent from each other, right?

00:38:04 So, you have this motion of all the atoms, like in my case, all the joints, right, are connected.

00:38:11 So, then you see that there are only some motions that I can do, right?

00:38:16 Right?

00:38:17 Because there are some other motions where, you know, break my legs, right?

00:38:21 So, if you only allow those collective motions, then you can probably have a good balance, okay?

00:38:29 And you can also think about how do we adjust this perturbation scale, including the hyperparameter beta,

00:38:38 which I said earlier doesn't have to be exactly equal to KBT, okay?

00:38:43 So, one idea is that you can adjust these choices to have roughly 50% acceptance rate.

00:38:52 So, try to adjust it and then run it for a long time and see whether you are accepting roughly 50% of the time.

00:39:00 So, that's a good thing to start with, okay?

00:39:02 So, this is not the acceptance probability.

00:39:08 So, this is just saying that running, for instance, hundreds of steps and see, or hundreds of iterations,

00:39:14 and see how often you accept.

00:39:17 If 50% of the time you accept, that is not a bad thing to start with, okay?

00:39:23 So, it's, we will have a homework 2, which is shorter than homework 1,

00:39:28 and only focused on Markov-Chen Monte Carlo.

00:39:31 The art of Markov-Chen Monte Carlo moves, I put it here, will be tested in that homework, okay?

00:39:37 So, it's just implementing the Markov-Chen Monte Carlo, which is very easy,

00:39:42 but there's an art of MC moves here.

00:39:45 And we're not going to minimize the energy of the protein, which is very difficult,

00:39:51 because A, protein has so many atoms, B, the energy function describing the protein,

00:39:59 so-called force field, is very sophisticated.

00:40:03 So, in the homework, we have a very simple, very simple system, okay?

00:40:07 A methane, okay?

00:40:09 One carbon and four hydrogens.

00:40:12 That's it, okay?

00:40:14 But that's already enough, as a prototype system, to demonstrate to you the art of the MC moves, okay?

00:40:21 So, I will put that on Thursday.

00:40:25 You will see the homework 2, okay?

00:40:28 But there's only one question, not two in the homework 1.

00:40:32 Any questions?

00:40:33 Any questions?

00:40:34 Any questions?

00:40:35 Okay.

00:40:36 So, I'm about to finish this module of classical protein structure prediction, and its various scenarios formulated as optimization, okay?

00:40:53 But in the end, I still want to emphasize the algorithm innovation.

00:40:58 I want to ask you, right, even in this case, midnight zone, can we do better?

00:41:08 Then so far, you know, the strategies seem to be, oh, yeah, we can do this kind of global or local samples,

00:41:14 and MCMC is one way, you know, you can use molecular dynamics and so on, or you do some more sophisticated non-convex optimization, right?

00:41:26 But what can you do to make it better?

00:41:29 In this case, we know what better means, right?

00:41:31 More efficiency, more likely to reach the global optimum or its neighbors, right?

00:41:37 So, I'm going to spend about five to ten minutes to talk about the great ideas.

00:41:44 I think they're, I don't want you and I don't need you to learn about the details about these ideas, but I want you to see where these innovation ideas are coming from.

00:41:55 And you can see that if you were put in that moment of history, you can do the same, right?

00:42:03 Because innovation is difficult, but there are very limited ways to innovate, right?

00:42:08 There's a science to innovate, okay?

00:42:12 So, let's see a few examples, okay?

00:42:15 So, let's wrap up this part, and, you know, the gradient-free non-local search, and just talk about some great optimization ideas, okay?

00:42:31 So, without giving you too much hint, too many hint, from what perspective can I think about novel ideas to improve optimization algorithms for protein structure prediction?

00:42:46 What perspectives can I think of?

00:42:48 What are the elements of optimization?

00:42:59 What are the elements of optimization?

00:43:06 The elements of optimization?

00:43:09 Objective function.

00:43:10 Objective function.

00:43:11 Constraints.

00:43:12 Constraints.

00:43:13 Constraints.

00:43:14 Decision variable included.

00:43:16 Right?

00:43:17 Okay.

00:43:18 And, beyond optimization algorithm, which follows a principle, I can also ask a question,

00:43:28 I can also ask at the end, is there additional data I haven't used yet?

00:43:33 Isn't it?

00:43:34 We have seen a flavor of that in the Twilight Zone, right?

00:43:38 When we realized that we never used all the template structures.

00:43:42 We only used the template sequences and figured out, oh, this is a good template, so we used that structure.

00:43:48 But we don't look at the other structures, right?

00:43:51 So, we'll also consider the possibility of additional data, okay?

00:43:55 So, we'll also consider the possibility of additional data, okay?