### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Machine Learning CMPS 242

UCSC

GPA 4.0

### View Full Document

## 32

## 0

## Popular in Course

## Popular in ComputerScienence

This 47 page Class Notes was uploaded by Dr. Elyssa Ratke on Monday September 7, 2015. The Class Notes belongs to CMPS 242 at University of California - Santa Cruz taught by Staff in Fall. Since its upload, it has received 32 views. For similar materials see /class/182259/cmps-242-university-of-california-santa-cruz in ComputerScienence at University of California - Santa Cruz.

## Popular in ComputerScienence

## Reviews for Machine Learning

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/07/15

An Adaptive Disk Spindown Algorithm Corrie Scalisi University of California Santa Cruz April 16 2007 cozosnozE e Introduction 0 Algorithm for deciding when to spin down a disk to save power 0 Based on Helmbold et al MONET 2000 0 Uses a Mixture of Experts and Weighted Majority Approach 0 See Littlestone and Warmuth 1994 Mirodn na 9 Datasets OnIine Data 0 Temporally correlated o Predictable given history 0 Randomly permute an online dataset to break these correlations 0 Significant visual difference between original data and permutation a Our algorithm must perform considerably better on the original data than it does on a random permutation Cello2 Dataset First 3000 iterations of the Cello2 Dataset 39U w 7 15 8 8 5 X XX XX XX X I X X xiXXX X WXX XXX mg c X XX XXXXXXQX Xigx XX XX 5ng XXXXXZX X XX XXX XXXquotX g 5 07 XXX XXX XXX XKXXWXXXXXXXXX X X XX XX XEXXXXXXX XXX 7 g XXXX XX X X XX amp X X X XX XX X X X X X X X X X XX XX XX X g X MMXXXXXXX X X X X X X D 395 X X quotXX XX X X XX XX XX 15 XXXMXX X fa x XX X XX X X XXXX X X X X 2 X 39 X XX X X X X 4 Xw 0 500 1000 1500 2000 2500 3000 E 5 X X X X X X r X XXXXXonxXXXX XXX XXXXXX XXX XXX X XXXX XXXX XX XXX XXX XX XX X X XX X X XXX X XX X X XXX X X X X X X X XX XXXX XXXXXXXXXXX x X X XXXX XXXXXX XX XXXX X X logeDura on in Seconds 0 Adaptive Disk 39 Algorithm Intel Dataset First 3000 Iterations of the Intel Dataset 7 l l l logelDuration in Seconds l l l l 0 500 1000 1500 2000 2500 3000 0 Already looks like a randomized permutation Corrie Scalisi UCSC An Adaptive Disk Spindown Algorithm April 16 2007 730 Mirodn na D e Experts 03 Fun Our algorithms use a set of experts which each specify a timeout value The optimal set of experts for a dataset always includes 0 and actual idle durations within the dataset Always include 0 and spindown cost in set of experts rrtrtt tr 0 Spin down cost Choosing idle durations in dataset as timeouts minimizes the difference between the loss and the optimal Experts mew mmm m am an mum mummy mam m an expanenha v waned he ween u and m m 5 2m 25 an mm M expth Energy used by timeout idle time it idle time g timeout Losstlmeout tImeout splndown cost It Idle tIme gt tImeout Energy used by optimal idle time it idle time g spindown cost spindown cost it idle time gt spindown cost Lossoptimal Energy Used By Timeout Fixed Timeout may Used bv lalvmg idieiime W mm mm Spindawn Casi i mm mme m Wm Energy used by Varying idietime with Fixed TlmEmA Spinduwn Cust Energy n 32 Wm If t2 gt t1 then t2 has smaller loss in interval t1 t2 If there is high certainty that the idle period is about to end then the disk should be kept running I i Ene y Used By Timeout Fixed Idle Time Energy Used by Varying Timeout With Fixed Idle Time timeout gt idletimequot Spindown Cost Energy in Sec 0 idletime Timeout o If timeout lt idletime Loss Spindown Cost Timeout o If timeout gt idletime don t spin down Loss idletime Corrie Scalisi UCSC An Adaptive Disk Spindown Algorithm April 16 2007 1530 e BestShiftK BestShiftK 0 Dynamic programming 0 Illustrates how adaptively changing the timeout value lowers the amount of energy used a Maintains a table B holding minimum Loss values a Run on a dataset and a random permutation in order to capture whether the data is quotonlinequot Be SMMKSmdeA omhm I trial number k max number of times the timeout value can change 0 Dynamic Programming algorithm 0 Maintain loss for each I k pair Bt k 0 Maintain last expert used Et k LossWithoutShitt Bt 7 1k Losst Et k LossWithShitt anBt7 m k 71 Losst Et 7 m k I77 mimi o tQk1 7 7 minLossWithoutShittLossWithShitt tgt0kgt1 0 Running Time 0T2K BestShiftK Improved Algorithm I trial number k max number of times the timeout value can change i the index into a list of timeout values 0 itt0k1 BUM Btit1iLossti itk1tgt0 7 7 minBti1kiLossti minBuihki1Lossti ittgt0kgt1 0 We need to consider TKN table entries 0 Create M a KN sized table for each ttrom O to T BestShiftK 0 To calculate entries in M1 we will refer to entries in M14 0 On each k n combination we must consider a a The entry k n of MM the minimum cost of using a partition that includes expert n on the If 1 trial 9 b The minimal entry in the k 71 row of MM the cost of using a partition that includes a different expert on the If 1 trial a The k n entry of M is the minimum of a and b MH loss trial H M loss on trial 1 An AdaIZIIIVe Disk Splndown Algorithm BestShift Running Time 0 Note minBt71k71j Losst i minBt71k 71j Losst i o If we compute minBt71k 7 1j for each Inf the running time is OTKNZ 0 However the minimum holds for all since it is the minimum over all j in the k 71 row of Mt1 0 Therefore it we maintain the minimum we can use the quantity for each entry in the k th row of M 0 Then the runtime is OTKN BestShift for Cello2 BestShiftK on Cello2 Data 50 experts exponentially spaced betm een 0 and 10 1 l l BestShiftK BestShiftK Randomized 03995 7 quotquot39 Optimal 0n 085 a d g g 08 E E m 075 8 d l 07 r E lt1 065 a 0 055 a l l l l l 0 50 100 150 200 250 300 K of shifts of timeout value 2558785 trials of Cello2 Spindown Cost 10 sec 0 Takes advantage of temporal similarities in the original data 0 BestShift curve for randomized permutation of data is very flat because of lower temporal correlation Corrie Scalisi UCSC An Adaptive Disk Spindown Algorithm April 16 2007 2230 BestShift for Intel Dataset BestShif tK on Intel dataset 50 experts exponentially spaced between 0 and 10 l l BestShif tK 4 N l l Average cost per idle time b l I l l l 0 50 100 150 200 250 300 K of shifts of timeout value 12458 trials of Intel Data Spindown Cost 10 sec 0 Similar for original and permuted data because of low temporal correlationin both 0 Only 1751 idletimes greater than 10 Approaches optimal quickly by shifting at most costly idletimes Corrie Scalisi UCSC An Adaptive Disk Spindown Algorithm April 16 2007 2330 line Ic C 03 m 1quot EL 5 3 6 Sharing Algorithm Sharing Algorithm 0 Weight vector W W1 W2W l l l o Experts 1 1112 t 0 Make prediction based on weights of experts n timeout Z WT i1 0 Calculate loss for each expert t ener used b t39 LossI gy y I spIndown cost 0 Loss update reduce weights and then normalize 7 i W f 21 Wje nLoss a Share update redistribute weight VariableShare Update 0 Calculate pool of weight to share n weightToShare 7 Z oldWeightU 1 7 1 7 0540 i1 o Distribute weight amongst experts weighti 7 oldWeightU 1 7 0550 WeightToShare o VariableShare update from Herbster and Warmuth 95 e Other Share Updates 0 Fixed Share to Start Vector Update Fixed Share to Past Average etc P9 0 mance of Adaptive Algorithm on Cello2 Energy Usage for Adaptive Disk Spin Down Algorithm mall modifications in or and n parameters All combinations ofn 1234 and x 00100501051 l l l 14 l l l 1 2 r x 1 d g 2 E 08 a 3 8 0 6 a m E lt2 O tImal 04 a p Best Fixed Timeout 02 a Sharing Algorithm with varying n or i l l l l l l l 0 2 4 6 8 10 12 14 16 18 Spindown cost in seconds 2558785 idle durations of Cello2 data 25 exponentially spaced experts between 0 and the spindown cost Corrie Scalisi Adaptive Disk Spindow Algorithm April 18 2007 2730 nce of Adaptive Algorithm on Intel Data mm Usage 1m Adamwe w Spm Dawn Ngamhm man mammm m a and n Palmem An cammnmm m mama a lt um ms nu us 0 mum can we mm Sh W valvmg n a a Spmdawn mu m ecand a ta 25 expanenha v waned expev ween u Performance of Adaptive Algorithm on Cello2 Compared to Loss Curve BestShif39tK and Share Algorithm on Cello2 dataset 25 experts exponentially spaced between 0 and 5 l 055 l l g 05 R C 8 E n1oc0001 n 3 or 01 E i 045 r e E quot BestFixed I g BestShiftK g BestShif39tK Randomized Permutation gt1 o4 e quotquot39 Share Algorithm l Optimal l l l l l l 50 100 150 200 250 300 K of shifts of timeout value 2558785 trials of Cello2 Spindown Cost 5 sec Corrie Scalisi UCSC An Adaptive Disk Spindown Algorithm April 18 2007 2930 Performance of Adaptive Algorithm on Intel data Compared to Loss Curve BestShif tK and Share Algorithm on Intel dataset 25 experts exponentially spaced between 0 and 5 l l n4oc025 4 n 3 or 0005 9quot BestFixed BestShif tK Average cost per idle time in39 seconds BestShiftK Randomized Permutation quotquot39 Share Algorithm munm Optimal l l l l l 0 50 100 150 200 250 300 K of shifts of timeout value 12458 trials of Intel Data Spindown Cost 5 sec 4 o 0 Corrie Scalisi UCSC An Adaptive Disk Spindown Algorithm April 18 2007 3030 Tracking a Small Set of Experts by Mixing Past Posteriors Olivier Bousquet Ecole Polytechnique France and BIOwulf Technologies New York Manfred K Warmuth UC Santa Cruz Outline o Motivate on line learning relative loss bounds o Comparator on line as well 0 Shifting back 0 Mixing Update 0 Experimental Results 0 Future work Oi Bousquet amp MiKi Warmuth Tracking a Small Set of Experts by Mixing Past Posteriors COLT July 19 2001 Common Batch Learning Paradigm 0 Given batch of random examples 0 Goal Find discriminator that predicts well on random unseen examples Oi Bousquet amp MiKi Warmuth Tracking a Small Set of Experts by Mixing Past Posteriors COLT July 19 2001 On Line Learning Loop for each trial if 1 T Get next instance act Make prediction Qt Get label yt true outcome lncur loss My gt 0 No statistical assumptions on the data 0 Choose comparison class of predictors experts act t7171 t7271 t73 mm vector of experts predictions Goal 0 Do well compared to the best off line comparator Oi Bousquet amp MiKi Warmuth Tracking a Small Set of Experts by Mixing Past Posteriors COLT July 19 2001 What kind of performance can we expect L1HT7A be the total loss of algorithm A LluT v be the total loss of i th expert E 0 Form of bounds for all sequence 1111 213T yT L1TA S m1DL1T C 10g 71 where c is constant 0 Bounds the loss of the algorithm relative to the loss of best expert Oi Bousquet amp MiKi Warmuth Tracking a Small Set of Experts by Mixing Past Posteriors COLT July 19 2001 General Expert Algorithm 0 Master algorithm predicts with weighted average Qt 39Ut 39 wt 0 The weights are updated according to the Loss Update Ut Z 8777 Ltd mm 3 7 norrnaliz where Lm is loss of expert i in trial If gt Weighted Majority Algorithm LW89 gt Generalized by Vovk Vovk90 Oi Bousquet amp MiKi Warmuth Tracking a Small Set of Experts by Mixing Past Posteriors COLT July 19 2001 Comparator Changes with Time Expert 7 20 4 Sequence of trials 0 Off line algorithm partitions sequence into sections and chooses best expert in each section 0 Goal 0 well compared to the best off line partition 0 Problem Loss Update learns too well and does not recover fast enough 51 Oi Bousquet amp MiKi Warmuth Tracking a Small Set of Experts by Mixing Past Posteriors COLT July 19 2001 Modi cations to the Expert Alg HW98 O Predict Qt Ut 39 13 0 Loss Update Ume Lm m m normaliz 0 Share Update Fixed Share to Start Vector small or vt11 0011 owe 1 1 1 Z7577n where 110 Static Expert corresponds to or O m 39Ut1 39Ut 0 Bousquet amp M K Warmuth Tracking a Small Set of Experts by Mixing Past Posteriors COLT July 19 2001 Static Expert Alg Versus Share Alg 9 I 90 39 Typical Expert 39 Static 80 FS Start Best Partition 7O 6O 3 50 E a 5 4O 39 3O 139d 20 f 10 O 1 2 3 4 5 6 7 Best Expert 0 Square loss Vovk s prediction labels always 0 typical experts predict uniform in 0 5 current best expert predicts uniform in 0 12 o T 1400 trials 71 20000 experts k 6 shifts O Bousquet amp MiK Warmuth Tracking a Small Set of Experts by Mixing Past Posteriors COLT July 19 2001 Weights of Fixed Share Alg 0 Tracks the best expert I 09 08 07 06 05 Weight 04 03 02 01 0 4 Best Expert O Bousquet amp MK Warmuth Tracking a Small Set of Experts by Mixing Past Posteriors COLT July 19 2001 Shifting Bounds 11 0 Recall Static Expert bound L1HTA S mzinL1HT 0log 71 Comparison Class set of experts o Bounds for Share Algorithms HW98 L1HT7A g rnlin L1HT7P O of bits for P Comparison Class set of partitions of bits for partitions with k shifts T klognlog Oi Bousquet amp MiKi Warmuth Tracking a Small Set of Experts by Mixing Past Posteriors COLT July 19 2001 Freund s Problem 0 Number of possible experts n is large n w 106 o Experts in partition Chosen from small subset of size m m w 10 o of bits for partitions with k shifts n T l l 1 0g 16 0gm 0g o Naive algorithm runs Fixed Share to Start Vector alg for every subset of m out of 71 experts Oi Bousquet amp MiKi Warmuth Tracking a Small Set of Experts by Mixing Past Posteriors COLT July 19 2001 Mixing Update O Predict Qt Ut 39 13 7 L vt e 7 t2 0 Loss Update 112 7 m o Mixing Update t t m vt1 E 31Hqu 7 Where 2 t 1 q0 q0 o Mixing schemes t1q Bt1 q t1q 1 1 1 104 104 at V V V 0 1 2 1 1 t q 0 1 2 1 1 t q 0 1 2 1 1 t F8 to Start Vector F8 to Uniform Past F8 to Decaying Past 01 Bousquet amp MiKi Warmuth Tracking a Small Set of Experts by Mixing Past Posteriors COLT July 19 2001 Total Loss Plots 9O 80 7O 6O 50 40 Total Loss 30 20 I Typical Expert Static FS Start FS Decaying Past Best Partition l Mm i o T 1400 trials 71 20000 experts o k 6 shifts every 200 trials m 3 experts in the small subset 2 Best Expert U i O Bousquet amp MiK Warmuth Tracking a Small Set of Experts by Mixing Past Posteriors COLT July 19 2001 Weights of Fixed Share to Start Vector Alg 08 07 06 05 Weight 04 03 02 01 1 2 1 2 3 1 Best Expert O Bousquet amp MK Warmuth Tracking a Small Set of Experts by Mixing Past Posteriors COLT July 19 2001 Weights of Fixed Share to Decaying Past Alg 0 Improved recovery when expert used before 1 09 08 07 06 05 Weight 04 03 02 01 0 1 2 1 2 3 Best Expert O Bousquet amp MK Warmuth Tracking a Small Set of Experts by Mixing Past Posteriors COLT July 19 2001

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.