R Code below (bold) is an example of Multiplicative Weigths (MW) Algorithm. The purpose of the algorithm is to play a series of rounds, at each round t making a choice i(t), suffering loss M(i(t), t), and achieve time averages (1/t) sum(M(i(1)+ … +M(i(t),t)) closing in on min((1/T) sum(M(i,1)+ … +M(i,T)). Choices are for every t restricted to 1:n for a fixed integer n > 0. Losses M(i,t) must be in [0,1] for the bounds proven in the paper by Freund& Schapire to apply. All losses M[i,t] are revealed to you after you have chosen your i(t) based on all M[i,s], s < t. The algorithm keeps probability weights Pt on 1:t, t in 1:T. These are updated per the description in F&S as t progresses through 1:T. At each t your choice of i(t) is, by this algorithm, made randomly by Pt probability sample. That allows us to use the green color bounds which, according to theory, will converge to one another if T is chosen progressively larger. MW begins with a selection i(1) which is randomly selected from the uniform distribution on 1:n.
Per the classroom presentation of thes ideas, there is a routine 'leaders' which rearranges each column of m3 (replaces M = m2) through the call MW(leaders(m2)). It is intended to close below the original goal.
Using M(leaders(leaders(m3)) gives you some idea of whether to try three applications of leaders.
Submit your solution with your choice of applicatio m3.
Explain why you chose m3.
Consult and reporduce your output including the plot. and short run of MW(m3) vs MW(m3).
Us the t=4 runs of MW(m3) vs MW(leaders(m3)) to explain what leaders does.
How well or poorly have MW(m3), MW(leaders(m3)) performed?
Offer insights per your choice od m3.
The black line plots one step ahead conditional mean time average loss.
The red line plots what the random algorithm produces by way of time average loss.
Define Dt = time average of 1-step ahead conditional variances through time t.
The two green lines are each spaced Dt^0.55 above and below the black line.
Bring your computer and we can go over some examples in groups.
```R
MW=function(X){
X=X[order(X[ ,1]),]
P=X*0
n=length(X[,1])
choices=1:n
T=length(X[1,])
ind=rep(1,T)
m=rep(0,T)
M=rep(0,T)
D=rep(0,T)
loss.total=rep(0,T)
beta=1/(1+sqrt(log(n^2)/T))
P[,1]=rep(1/n,n)
loss.total[1]=X[ind[1],1]
m[1]=P[,1]%*%X[,1]
M[1]=m[1]
D[1]=P[,1]%*%(X[,1]-P[,1]%*%X[,1])^2
for(t in 2:T){
P[,t]=P[,t-1]*beta^X[,t-1]/sum(P[,t-1]*beta^X[,t-1])
ind[t]=sample(choices,1,replace=FALSE,P[,t])
loss.total[t]=loss.total[t-1]+X[ind[t],t]
m[t]=P[,t]%*%X[,t]
M[t]=M[t-1]+m[t]
D[t]=D[t-1]+P[,t]%*%(X[,t]-P[,t]%*%X[,t])^2 }
plot(1:T,ind, type="p")
plot(1:T,loss.total/(1:T),type="l",col="red")
lines(1:T,M/(1:T))
lines(1:T,(M+D^0.55)/(1:T),type="l",col="green")
lines(1:T,(M-D^0.55)/(1:T),type="l",col="green")
for(k in 1:n){
lines(1:T,cumsum(X[k,])/(1:T),type="l",col="blue") }
lines(1:T,loss.total/(1:T),type="l",col="red")
print(loss.total[T]/T)
print(X%*%rep(1,T)/T)
print(sqrt(log(n^2)/T)+log(n)/T)
print(sqrt(D[T])/T) }
leaders=function(xmat){
n=length(xmat[,1])
capT=length(xmat[1,])
i1.t=i2.t=i3.t=i4.t=i5.t=rep(0,capT)
i1.t[1]= order(xmat[,1])[1]
i2.t[1]= order(xmat[,1])[2]
i3.t[1]= order(xmat[,1])[3]
i4.t[1]= order(xmat[,1])[4]
i5.t[1]= order(xmat[,1])[5]
for(t in 2:capT){
i1.t[t]= order(xmat[,1:t]%*%rep(1,t))[1]
i2.t[t]= order(xmat[,1:t]%*%rep(1,t))[2]
i3.t[t]= order(xmat[,1:t]%*%rep(1,t))[3]
i4.t[t]= order(xmat[,1:t]%*%rep(1,t))[4]
i5.t[t]= order(xmat[,1:t]%*%rep(1,t))[5]
}
newxmat=xmat[1:5,]
for(j in 2:capT){
newxmat[1,j]=xmat[i1.t[j-1],j]
newxmat[2,j]=xmat[i2.t[j-1],j]
newxmat[3,j]=xmat[i3.t[j-1],j]
newxmat[4,j]=xmat[i4.t[j-1],j]
newxmat[5,j]=xmat[i5.t[j-1],j]
}
return(newxmat)
}
m2=matrix(abs(sin(1:5000)),nrow=5,ncol=1000,byrow=T)
MW(m2)
MW(leaders(m2))
m2[,1:4]
leaders(m2)[,1:4]
```
AS RUN
```
> MW=function(X){
+ X=X[order(X[ ,1]),]
+ P=X*0
+ n=length(X[,1])
+ choices=1:n
+ T=length(X[1,])
+ ind=rep(1,T)
+ m=rep(0,T)
+ M=rep(0,T)
+ D=rep(0,T)
+ loss.total=rep(0,T)
+ beta=1/(1+sqrt(log(n^2)/T))
+ P[,1]=rep(1/n,n)
+ loss.total[1]=X[ind[1],1]
+ m[1]=P[,1]%*%X[,1]
+ M[1]=m[1]
+ D[1]=P[,1]%*%(X[,1]-P[,1]%*%X[,1])^2
+ for(t in 2:T){
+ P[,t]=P[,t-1]*beta^X[,t-1]/sum(P[,t-1]*beta^X[,t-1])
+ ind[t]=sample(choices,1,replace=FALSE,P[,t])
+ loss.total[t]=loss.total[t-1]+X[ind[t],t]
+ m[t]=P[,t]%*%X[,t]
+ M[t]=M[t-1]+m[t]
+ D[t]=D[t-1]+P[,t]%*%(X[,t]-P[,t]%*%X[,t])^2 }
+ plot(1:T,ind, type=”p”)
+ plot(1:T,loss.total/(1:T),type=”l”,col=”red”)
+ lines(1:T,M/(1:T))
+ lines(1:T,(M+D^0.55)/(1:T),type=”l”,col=”green”)
+ lines(1:T,(M-D^0.55)/(1:T),type=”l”,col=”green”)
+ for(k in 1:n){
+ lines(1:T,cumsum(X[k,])/(1:T),type=”l”,col=”blue”) }
+ lines(1:T,loss.total/(1:T),type=”l”,col=”red”)
+ print(loss.total[T]/T)
+ print(X%*%rep(1,T)/T)
+ print(sqrt(log(n^2)/T)+log(n)/T)
+ print(sqrt(D[T])/T) }
>
> leaders=function(xmat){
+ n=length(xmat[,1])
+ capT=length(xmat[1,])
+ i1.t=i2.t=i3.t=i4.t=i5.t=rep(0,capT)
+ i1.t[1]= order(xmat[,1])[1]
+ i2.t[1]= order(xmat[,1])[2]
+ i3.t[1]= order(xmat[,1])[3]
+ i4.t[1]= order(xmat[,1])[4]
+ i5.t[1]= order(xmat[,1])[5]
+ for(t in 2:capT){
+ i1.t[t]= order(xmat[,1:t]%*%rep(1,t))[1]
+ i2.t[t]= order(xmat[,1:t]%*%rep(1,t))[2]
+ i3.t[t]= order(xmat[,1:t]%*%rep(1,t))[3]
+ i4.t[t]= order(xmat[,1:t]%*%rep(1,t))[4]
+ i5.t[t]= order(xmat[,1:t]%*%rep(1,t))[5]
+ }
+ newxmat=xmat[1:5,]
+ for(j in 2:capT){
+ newxmat[1,j]=xmat[i1.t[j-1],j]
+ newxmat[2,j]=xmat[i2.t[j-1],j]
+ newxmat[3,j]=xmat[i3.t[j-1],j]
+ newxmat[4,j]=xmat[i4.t[j-1],j]
+ newxmat[5,j]=xmat[i5.t[j-1],j]
+ }
+ return(newxmat)
+ }
>
>
> m2=matrix(abs(sin(1:5000)),nrow=5,ncol=1000,byrow=T)
>
> MW(m2)
[1] 0.637013
[,1]
[1,] 0.6361559
[2,] 0.6366539
[3,] 0.6368397
[4,] 0.6368781
[5,] 0.6369758
[1] 0.05834458
[1] 0.009436017
>
> MW(leaders(m2))
[1] 0.4892886
[,1]
[1,] 0.6920100
[2,] 0.5022588
[3,] 0.8176275
[4,] 0.7128819
[5,] 0.4587252
[1] 0.05834458
[1] 0.005517041
>
> m2[,1:4]
[,1] [,2] [,3] [,4]
[1,] 0.8414710 0.9092974 0.1411200 0.7568025
[2,] 0.9199906 0.1672665 0.7392416 0.9660944
[3,] 0.1932959 0.7211630 0.9725880 0.3298201
[4,] 0.7025794 0.9784005 0.3546847 0.5951266
[5,] 0.9835279 0.3793010 0.5736535 0.9991936
>
> leaders(m2)[,1:4]
[,1] [,2] [,3] [,4]
[1,] 0.8414710 0.7211630 0.9725880 0.9660944
[2,] 0.9199906 0.9784005 0.7392416 0.3298201
[3,] 0.1932959 0.9092974 0.5736535 0.7568025
[4,] 0.7025794 0.1672665 0.3546847 0.9991936
[5,] 0.9835279 0.3793010 0.1411200 0.5951266
>
“`