We've boiled down our max ent. prescription
into 2 steps. The first thing is you want the
probability distribution to satisfy this constraint
on the average value of the waiting time.
And the second thing is we want
that particular probability distribution to
have the maximum entropy - to maximize the
function p log p, and I always forget the negative
sign. So in fact, we're maximizing the function
negative sum over all states of the system
p log p. And remember, states of the system
here are how long you've waited for a particular
cab. Or rather, how long you've waited from
a particular time you decided to start waiting.
So, this turns out to be a hard problem, or
at least a non-trivial problem. If you have
a little calculus, you're really good at maximizing
functions, so let's start there. Let's imagine
in particular...and I'll use this very simple example
of maximizing a function over a 2-dimensional
space. Let's call these the x1 and x2 axes.
So I have some function. I'm just
going to draw the contours for you.
So here we go. And what I'm going to do is
make it such that there's a single maximum over
this space. And what we'll talk about in one of
the appendices, if we have time, is why we can
prove that the entropy function has a unique
maximum even what you subject it to these
constraints. For now, you can take it on faith
that, in fact, this problem has a unique solution.
So, here's a function. I've given it a unique
maximum, and so we'll call this function f.
So, using your amazing calculus skills, you know
that the maximum of this function is defined as
the point where the derivative of f with
respect to x is 0. And remember this is a vector
here so what this means is df/dx1 is 0 and
df/dx2 is zero. Now, yes, you might have
accidentally hit a minimum, so just check to
make sure it's actually a minimum. That's
what you would do. So now the problem is that
we're not allowed to range over this entire space.
We're restricted to some subspace. We're restricted
in particular to some constraint here. So how
can we find the maximum of the function, not
the global maximum, but the maximum that
is also satisfying a set of constraints and what I'll
do is I'll draw those constraints as a line
in this space. A point here is a valid argument
for the function f, but it doesn't satisfy this
constraint here and what I'll do is
define this constraint in the following way.
I'll say the constraint is that g(x) = c, where c
is some number. And just to be clear, for us,
it's better to write g(p). We set that equal to
4 minutes. That's just to remind you our particular
constraint is that the function g is equal to 4.
This is the general case here. So what we want
to do now is not find the maximum point, the top
of the mountain. We want to find the point
that is the maximum along this line - this
line defined by g(x) = c. So let me give you
a little intuition about how you might do this.
Imagine you're on a train going through this
mountainous landscape, and as you're going
through, down here, you'll see you're crossing
contours of the function f. In this case, you're
going uphill - the function is increasing - so you
know a point there is not a maximum of the function
along this line because if you wait a little bit
longer, you'll get to this point here and you've
already crossed the contour line. So here,
you're going up. Notice here, you're going down
the other side of the mountain - you're crossing
contour lines in the other way, so you know,
in fact, that the maximum can't be over here
because you were already higher over here.
So, somewhere between here and here is the
maximum - somewhere in the middle you reach the
peak. You reach the peak when the contours of the
function f are parallel to the track that you are taking -
where there is a tangent point between the contour
and the direction of your motion on this fictitious
train. So, we know how to get the directions of the
contours of the function f - those are, indeed, just the
gradient of the function...this is a vector, remember.
And we are going to say these are equal to the
perpendiculars to the train tracks. So if the
perpendicular to the contour is parallel to the
perpendicular to the train track, that means
that the direction of the contour is parallel
to the direction of the train track. If the two
perpendiculars are parallel, so are the two
original vectors. So then the next question is
how can I get the perpendicular to the train track.
What I want you do is imagine this is the train
track for g(x) = c, and here is the train track
for g(x) = c' and so forth. So here is another set
of contours defined by the function g and we
want the perpendiculars to these contours to
be parallel to the contours for f - the
perpendiculars for the contours of f. So what
that means is that this gradient here - these arrows
here, and in particular, these arrows right here -
are equal to some real number lambda times
the gradient of the constraint. When this equation
is satisfied, that means that these contours here
are precisely parallel to these contours here.
So in order to maximize a function f subject
to a set of constraints, don't solve this here.
Don't solve this problem, solve this problem.
And now you notice you have this mysterious
value lambda. This is called the Lagrange multiplier.
So what we're going to do is try to find a solution
where the gradients are parallel to each other.
In other words, that one can be transformed into
another by scaling by some constant factor
along all axes. So this is the intuitive motivation
for how to solve the problem of maximization
subject to constraints when you have only
a single constraint. What we do is find the point
at which these two gradients align. There's a wrinkle.
The wrinkle is the following. It looks like we have only
one constraint here and our contraint is just
that this function is equal to 4. But we actually have
2 constraints. Our second constraint is overall
normalization and it says that we want this
function p here to normalize to 1. If you
sum the probabilities of all the arrival times, they
have to equal 1. Now, of course, p is a probability
so we know that has to be true. We didn't talk about
this explicitly, but when we start wandering over
function space - when these xs here become ps,
we start manipulating the probabilities - what we
want to do is be able to relax the constraint
that they sum to 1 when we consider maximizing
this function f. We want to be able to range over
the entire space including, for example, points
where all the probabilities - all the ps - are 0.
And then later what we'll do is we'll impose the
normalization constraint. So we actually have
2 constraints, and not just 1.
Hemos reducido nuestra descripción de máxima entropía
En dos simples pasos.
Lo primero que queremos es que
la distribución de probabilidad
satisfaga esta restricción
el valor promedio del tiempo de espera.
y lo segundo que queremos
es que esa distribución de probabilidad
tenga la máxima entropía, para maximizar
la función p log p
siempre olvido el signo negativo
de hecho, queremos maximizar la función negativa
sumatoria sobre todos los estados del sistema p log p.
Y recuerden, los estados del sistema aquí
corresponden a cuanto tiempo espero un taxi en particular
O mas bien, el tiempo que esperó desde
el momento en particular en el que deicidio empezar a esperar.
Entonces, este resulta ser un problema difícil,
o al menos un problema no trivial.
Si ha estudiado un poco de calculo
y es realmente bueno maximizando funciones...
Bien, vamos a empezar aquí
imaginemos en particular...
y uso este simple ejemplo
de maximización de funciones
en un espacio bidimensional
Vamos a llamar estos los ejes x1 y x2.
Entonces tengo alguna función.
Voy a dibujar los contornos para usted
así que aquí vamos, y lo que voy a hacer es
forzar que tenga un solo máximo en este espacio
Y vamos a hablar acerca de esto en uno de los apéndices
si tenemos tiempo es porque podemos probar que
la función de entropía tienen un único máximo
incluso cunado se somete a estas restricciones.
Por ahora, puede aceptar con fe que
de hecho, este problema tiene una solución única.
Entonces, aquí tenemos una función, le he dado
un único máximo, y vamos a llamar esta función f.
Así, usando sus increíbles habilidades de calculo,
sabe que el máximo de esta función
esta definido como
el punto donde la derivada de f
con respecto de x es 0.
Y recuerde que esto es un vector
lo que significa es df/dx1 es 0 y df/dx2 es cero.
Ahora, si, tal vez alcanzo por accidente un mínimo
así que para estar seguros que de verdad no es un mínimo
eso es lo que usted haría.
Entonces ahora el problema es que
no tenemos permitido acceder a todo el espacio.
Estamos restringidos a un sub-espacio.
Estamos limitados en particular
por una restricción, aqui.
Así que
¿Como podemos hallar el máximo de la función?
No el máximo global,
sino el máximo que también satisface
un conjunto de restricciones,
y lo que voy a hacer es dibujar esas restricciones
como una linea en este espacio.
Un punto aquí
es un argumento valido para la función f,
pero este no satisface esta restricción,
y lo que haré es definir esta
restricción de la siguiente manera.
Diré que esta restricción es g(x) = c, donde c
es algún numero.
Y solo para dejarlo claro, para nosotros g(x)
De hecho es mejor para nosotros escribir g(p) es...
lo hacemos 4 minutos.
Eso es para recordarle
que nuestra restricción particular
es que la función g(p) es igual a 4.
Este aquí es el caso general.
Así que lo que queremos hacer ahora no es encontrar el punto máximo,
la cúspide de la montaña,
queremos encontrar el punto
que es el máximo a lo largo de esta linea
esta linea definida por g(x) = c.
Déjeme darle una pequeña pista
de como puede hacer esto.
Imagine que esta viajando en tren
por un paisaje montañoso,
a medida que avanza, aquí abajo,
estará cruzando los contornos de la función f.
En este caso usted esta yendo cuesta arriba,
la función esta incrementando, así que
sabe que un punto allí
no es el máximo de la función
a lo largo de esta linea, porque si espera un poco mas
llegara a este punto aquí, y usted ya ha cruzado el contorno,
entonces aquí esta subiendo, note que aquí, esta bajando
por el otro de la montaña, esta cruzando
los contornos en el otro sentido, así,
usted sabe que de hecho el máximo no puede estar por aquí.
Porque usted ya estuvo mas alto por aquí.
Así que en algún lugar entre aquí y aquí esta el máximo,
Usted va subiendo y después va bajando
la función es continua
en algún lugar en el medio alcanzo el pico.
y en particular
y dependiendo de su imaginación visual
Usted alcanzo el pico cuando
los contornos de la función f
son paralelos a las vías que esta usando,
allí donde hay un punto tangente entre los contornos
y la dirección de su movimiento en el tren ficticio.
que viaja sobre la restricción
Entonces, sabemos como conseguir la dirección
de los contornos de la función f,
esos son, en efecto, solo el
gradiente de la función...
Esto es un vector, recuérdelo.
Y vamos a decir que estas son iguales a
las perpendiculares de las vías del tren.
Así que
si las perpendiculares al contorno son paralelos a
las perpendiculares de las vías del tren,
eso significa
que la dirección del contorno es paralelo a la dirección
de las vías del tren. Si dos perpendiculares
son paralelas también los son los vectores originales.
Así, la siguiente pregunta es
¿como puedo conseguir la perpendicular a las vías del tren?
Lo que quiero que hagan es que imaginen que esta
es la vía del tren para g(x) = c,
y aquí esta la vía del tren para g(x) = c'
y así sucesivamente, entonces
aquí esta un grupo de contornos definido por la función g
y queremos que las perpendiculares a estos contornos
sean paralelas a los contornos para f,
las perpendiculares a los contornos de f.
Lo que esto significa es que este gradiente de aquí,
esta flechas aqui, y en particular,
estas flechas justo aquí
son iguales a algún numero real 'lambda' veces
el gradiente de la restricción.
Cuando esta ecuación se satisface,
cuando esta ecuación de aquí se satisface,
significa que estos contornos aquí
son precisamente paralelos a estos contornos de aquí.
Así que para poder maximizar la función f sujeta
a un grupo de restricciones, no resuelva esto de aquí,
no resuelva este problema,
resuelva este problema.
Y ahora usted notara que tiene este misterioso
valor lambda,
este se conoce como multiplicador de Lagrange.
Entonces lo que haremos sera
tratar de encontrar una solución
donde los gradientes sean paralelos entre si.
En otras palabras, que uno pueda ser transformado
en el otro re-escalándolo por un factor
constante en todos los ejes.
Entonces esta es la motivación intuitiva original
de como resolver el problema de
la maximización sujeto a restricciones
cuando usted tiene solo una restricción.
Lo que hacemos es encontrar un punto
en el cual estos dos gradientes se alineen.
Pero hay un giro,
el giro es el siguiente,
parece que solo tenemos solo
una restricción aquí
y que nuestra restricción es
solo esta función que es igual a 4,
pero realmente tenemos 2 restricciones.
Nuestra segunda restricción
es la normalización global
y dice lo siguiente,
queremos que esta función p de aquí...
se normalice a 1.
Si usted suma todas las probabilidades de tiempo de llegada
tienen que ser iguales a 1.
Ahora, claro, p es una probabilidad,
así que sabemos que tiene que ser cierto,
no hablamos de eso explícitamente,
pero cuando empezamos a vagar por
el espacio de funciones, cuando esta xs de aquí
se convierte en ps,
empezamos a manipular las probabilidades
lo que queremos es ser capaces de relajar la restricción
de que tienen que sumar 1 cuando consideramos
maximizar esta función f,
queremos ser capaces de movernos sobre
todo el espacio, incluyendo, por ejemplo,
puntos donde todas las probabilidades, todas las ps, son 0.
Y después lo que haremos es imponer
las restricciones de normalización.
Así que en realidad tenemos dos restricciones y no solo una.
Messa a fuoco la formula per il maxent
nel secondo passo, anzitutto, si vuole che
la distribuzione di probabilità la soddisfi
sui valori medi del tempo di attesa;
e, poi, che la particolare distribuzione
di probabilità abbia la massima entropia
Per massimizzare la funzione p log p
dimentico sempre il segno negativo.
Infatti, stiamo massimizzando la funzione
negativa somma su tutti gli stati del sistma
p log p. Gli stati del sistema
qui rappresentano l'attesa di un particolare
taxi. O piuttosto, l'attesa dal tempo
esato dal quale aveto iniziato ad aspettarlo.
Ecco qui un problema complicato, o
almeno non facilissimo. Di fronte ad
un elementare calcolo, si è davvero bravi a massimizzare
le funzioni. Immaginate in particolare...
e userò un esempio semplice
di una funzione su uno spazio bidimensionale
Assi x1 e x2 con alcune funzioni.
Ne segnerò
i termini generali.
Ecco, farò in modo che
ci sarà un solo massimo nello spazio.
Edi questo parleremo in una delle appendici,
se avremo tempo, perché possiamo
provre che la funzione di entropia ha solo
un massimo persino con questa funzione.
Per ora, prendete per buono
l'unicità della soluzione al problema.
Qui la funzione con un unico punto
di massimo, la funzione f.
Con le vostre grandionse capacità di calcolo
il punto di massimo di f è definito come
il punto delle derivate rispetto a x
uguale a 0. Si tratta di vettore
per cui df/dx1 è 0 e
df/dx2 è 0. Ora potreste raggiungere
per sbaglio un minimo, controllate
bene come fareste.
Non possiamo ora più considerare
l'intero spazio. Ma restringiamo ad alcuni
sottospazi, nello specifico ad alcune
funzioni. Come trovare, dunque,
il punto di massimo della funzione,
non globale, ma che soddisfi una serie
di condizioni, disegnate come linee
nello spazio. Un punto è un valido
argomento per la funzione f
ma non soddisfa la condizione
specifica. Pertanto, la definiremo
come g(x) = c, dove c è un numero
particolare. E per essere chiari
sarebbe meglio scrivere g(p)
uguale a 4 minuti.
La nostra particolare condizione è che
la funzione g sia ugiale a 4.
É un esempio generale. Dobbiamo ora
trovare il punto di massimo, la cima della
montagna. Vogliamo trovare il punto che
rappresenti il massimo lungo questa linea
g(x) = c
In maniera intuitiva, immaginate che
un treno percorra una zona di montagna
andate giù, lungo i contorni
della funzione f. In questo caso, salite
- la funzione cresce - toccando
dei punti che non rappresentano
il punto massimo della funzione
lungo la linea, se aspettate un po'
di più, arrivate qui e avete di già
superato il controno. Qui, salite.
Scendete poi lungo la montagna
Superate la linea di contorno
in altro modo, ben sapete
che il pinto di massimo non può essere qui
perché avete toccato punti più alti.
Quindi, in qualche parte tra questi punti
c'è il punto di massimo - nel mezzo
arrivatee in cima, quando cioè i contorni
della funzione f sono paralleli al percorso dei binari
dove c'è un punto di tangenza tra il contorno
e la direzione del treno.
Sappiano come procedono le direzioni
dei contorni della funzione f - questi sono solo
il gradiente della funzione...è un vettore, ricordatelo.
E questi sono uguali alla perpendicolare
dei binari. Se questa è parallela
alla perpendicolare dei contorni,
la direzione dei contorni è parallela
alla direzione dei binari.
Se le due perpendicolari sono
parallele, sono i due vettori d'origine.
La prossima domanda sarà
come ottenere la perpendicolare ai binari.
Immaginate che questo sia il percorso del
treno per g(x) = c, e questo per
g(x) = c' e così via. Qui un altro insieme
di contorni definito come funzione g e
vogliamo trovare le sue perpindicolari
parallete ai contorni per f
le perpendicoali per i contorni di f.
Questo gradiente, qui - queste frecce
e, in particolare, queste frecce qui -
sono uguali al numero reale lambda volte
il gradiente. QUando questa equazione
è soddisfatta, significa che questi contorni
sono esattamente paralleli a questi contorni.
Per massimizzare la funzione f soggetta
ad una serie di condizioni, non risolvetela qui.
Non risolvete questo problema, ma quest'altro.
E scoprirete questo misterioso valore lambda.
Questo è chiamato il moltiplicatore di Langrange.
Proveremo a trovare una soluzione
dove i gradiente siano paralleli tra di loro.
In altri temrini, questo può essere trasformato
in altro lungo i fattori costanti degli assi.
Il motivo intuititvo per la soluzione
a determinate condizioni quando ne avete
solo una. Ora, troviamo il punto
di allineamento dei due gradienti.
É come una piega.
Sembra che abbiamo una sola condizione da rispettare
cioè che questa funzione sia uguale a 4. Ma
abbiamo 2 condizioni. L'altra è
la normalizzazione generale, cioè
che la funzione p venga normalizzata per 1
Se sommate le probabilità dei tempi
di arrivo, saranno uguali a 1.
Ora p è la probabilità
e sappiamo che dev'essere vera. Non lo
sappiamo esplicitamente, ma quando
andiamo nella funzione - dove xs diventano ps,
manipoliamo le probabilità
vogliamo esplicitare la condizione che
la somma sia uguale a 1 quando consideriamo
il punto massimo della funzione f. Vogliamo
spaziare nello spazio intero, per esempio,
dove tutte le probabilità siano 0.
E poi vogliamo imporre
la condizione di normalizzazione. Abbiamo così
2 condizioni, non 1 soltanto.