Careful Use of Machine Learning Methods
is needed for Mobile Application
A case study on Transportation-mode
Detection	
By	  Yu	  et	  al	  (2013)	  	  Presented	  by	  Muhammad	  Awais	  Shaﬁque	  Contents	
1. IntroducCon	  2. TransportaCon-­‐mode	  detecCon	  3. PracCcal	  use	  of	  SVM	  4. PiJall	  of	  CV	  accuracy	  5. Model	  size	  reducCon	  6. Fast	  training	  by	  opCmizaCon	  7. MulC-­‐class	  SVM	  method	  8. Non-­‐machine	  learning	  issues	  9. Conclusion	  	Introduction	
• Machine	  learning	  methods	  are	  oUen	  applied	  as	  a	  black	  box.	  
• Example	  is	  transportaCon-­‐mode	  detecCon.	  
• Collect	  data,	  use	  algorithms	  and	  compare	  results.	  
• Default	  se[ngs	  may	  not	  be	  the	  best	  one.	  
• EvaluaCon	  criterion	  (e.g.	  cross-­‐validaCon)	  may	  not	  be	  appropriate.	  
• Some	  methods	  may	  not	  be	  applied	  due	  to	  resource	  constraints	  of	  mobile	  phones.	
This	  paper	  focuses	  on	  using	  SVM	  and	  how	  the	  performance	  can	  be	  opCmized.	

Transportation-mode Detection	• The	  detector	  can	  use	  only	  up	  to	  16	  KB	  of	  memory.	  
• Data	  consists	  of	  log	  ﬁles	  containing	  signals	  from	  gyroscope,	  accelerometer	  and	  magnetometer.	  
• ClassiﬁcaCon	  was	  done	  among	  SCll,	  Walk,	  Run,	  Bike,	  Others	  • Five	  features	  were	  extracted	  by	  calculaCng	  mean	  or	  standard	  deviaCon	  of	  the	  signals.	  
• Decision	  trees,	  AdaBoost	  and	  SVM	  were	  employed.	

Transportation-mode Detection	
• Results	  Classiﬁers	

CV	  accuracy	  (%)	Model	  size	  (KB)	

Decision	  Tree	89.41	

76.02	

AdaBoost	

91.11	

1500.54	

SVM	

84.72	

1379.97	

Practical use of SVM	• Worse	  SVM	  performance	  may	  be	  because	  of	  lacking	  • Data	  scaling	  • Parameter	  selecCon	  • Given	  label-­‐instance	  pairs	  (​𝑦↓1 ,​𝒙↓1 )…(​𝑦↓𝑙 ,​𝒙↓𝑙 ) with	  ​𝑦↓𝑖 =±1,  ​𝒙↓𝑖∈​𝑅↑𝑛 ,  ∀𝑖 as	  the	  training	  set.	  (Primal	  problem)	

Practical use of SVM (Cont.)	
• Because	  w	  becomes	  a	  huge	  vector	  so	  dual	  opCmizaCon	  problem	  is	  solved.	  (Dual	  Problem)	  • Where	  	Practical use of SVM (Cont.)	
• 𝐾(​𝒙↓𝑖 ,​𝒙↓𝑗 ) is	  the	  kernel	  funcCon.	  
• Default	  kernel	  funcCon	  in	  LIBSVM	  is	  RBF	  (Gaussian)	  kernel	  • The	  opCmal	  soluCon	  saCsﬁes	  Practical use of SVM (Cont.)	
• Linear	  scaling	  of	  features	  is	  done	Practical use of SVM (Cont.)	

Practical use of SVM (Cont.)	

Practical use of SVM (Cont.)	
• Parameter	  selecCon	  • RegularizaCon	  parameter	  (C)	  • Kernel	  parameter	  (𝛾 in	  case	  of	  RBF	  kernel)	  • Select	  the	  one	  achieving	  the	  best	  ﬁve-­‐fold	  CV	  accuracy	Practical use of SVM (Cont.)	
• Results	  SVM	  procedures	CV	  accuracy	  (%)	Linear	  scaling	  +	  parameter	  selecCon	

89.20	

Log	  scaling	  +	  parameter	  selecCon	

90.48	

Pitfall of CV accuracy	
• Although	  CV	  accuracy	  is	  most	  widely	  used	  evaluaCon	  measure	  but	  it	  can	  over-­‐esCmate	  the	  real	  performance.	  
• Assume	  each	  user	  records	  10	  log	  ﬁles	  and	  each	  log	  ﬁle	  generates	  100	  feature	  vectors.	  Pitfall of CV accuracy (Cont.)	
• Feature	  vector	  in	  the	  same	  log	  ﬁle	  shares	  some	  informaCon.	  
• In	  CV	  procedure	  if	  data	  from	  one	  log	  ﬁle	  appear	  in	  both	  training	  and	  validaCon	  sets,	  then	  the	  predicCon	  becomes	  easy.	  Pitfall of CV accuracy (Cont.)	
• Therefore	  the	  standard	  instance-­‐wise	  split	  of	  data	  may	  easily	  over-­‐
esCmate	  the	  real	  performance.	  
• To	  eliminate	  the	  sharing	  of	  meta-­‐informaCon,	  data	  split	  should	  be	  made	  at	  higher	  level	  such	  as	  logs	  or	  users.	
CV	  strategy	SVM	  CV	  accuracy	  (%)	Instance-­‐wise	  CV	

90.48	

Log-­‐wise	  CV	83.37	

Pitfall of CV accuracy (Cont.)	
• Although	  log-­‐wise	  CV	  is	  more	  reasonable	  but	  its	  beder	  to	  have	  an	  independent	  test	  set	  collected	  by	  a	  completely	  diﬀerent	  group	  of	  users.	  
Classiﬁers	

CV	  accuracy	  (%)	Test	  accuracy	  (%)	Model	  size	  (KB)	

Decision	  Tree	

89.41	

77.77	

76.02	

AdaBoost	

91.11	

78.84	

1500.54	

SVM	

90.48	

85.14	

1379.97	

• The	  result	  conﬁrms	  that	  instance-­‐wise	  CV	  may	  severely	  over-­‐
esCmate.	  Pitfall of CV accuracy (Cont.)	
• Similarly	  in	  “Towards	  physical	  acCvity	  diary:	  moCon	  recogniCon	  using	  simple	  acceleraCon	  features	  with	  mobile	  phones”	  by	  J.	  Yang	  (2009)	  Reported	  CV	  accuracy	

80	  –	  90	  %	Reported	  Test	  accuracy	<	  70	  %	

2	  folds	

5	  folds	

8	  folds	

CV	  accuracy	

85.05	

83.37	

82.21	

Test	  accuracy	

85.33	

85.14	

84.66	

Model size reduction	
• Although	  good	  accuracy	  achieved	  but	  the	  model	  size	  is	  much	  larger	  than	  16	  KB.	  
• Large	  size	  due	  to	  storage	  of	  opCmal	  soluCon	  𝛼 and	  support	  vectors.	  
• Because	  it	  is	  a	  mulC-­‐class	  problem	  and	  LIBSVM	  uses	  one-­‐against-­‐one	  method	  so	  for	  k-­‐class	  problem	  the	  model	  size	  is	  • Where	  n	  is	  the	  number	  of	  features.	

Model size reduction (Cont.)	
• To	  reduce	  size	  use	  polynomial	  kernel.	  

• Where	  𝛾 is	  the	  kernel	  parameter	  and	  d	  is	  the	  degree.	  
• The	  kernel	  is	  the	  inner	  product	  of	  two	  vectors	  𝜙(​𝑥↓𝑖 ) and	  𝜙(​𝑥↓𝑗 )	  • If	  d	  =	  3	Model size reduction (Cont.)	
• Only	  𝑤 and	  b	  need	  to	  be	  stored.	  

• For	  d	  =	  3,	  the	  model	  size	  turns	  out	  to	  be	  2.28	  KB	Model size reduction (Cont.)	
• Comparison	  among	  kernels	
SVM	  method	

Test	  accuracy	  (%)	Model	  size	  (KB)	

RBF	  kernel	

85.33	

1287.15	

Polynomial	  kernel	

84.79	

2.28	Linear	  kernel	

78.51	

0.24	Fast training by optimization	
1. The	  training	  of	  kernel	  SVM	  is	  known	  to	  be	  slow.	  
2. Because	  of	  using	  𝐾(​𝒙↓𝑖 ,​𝒙↓𝑗 ) rather	  than	  𝜙(​𝑥↓𝑖 ) or	  𝜙(​𝑥↓𝑗 ),	  the	  se[ng	  is	  very	  restricted.	  
• For	  linear	  SVM	  the	  opCmizaCon	  problem	  becomes	  • Where	  𝜉(𝑤;​𝑥↓𝑖 ,​𝑦↓𝑖 )	  is	  the	  loss	  funcCon	  Fast training by optimization (Cont.)	
• Commonly	  used	  loss	  funcCons	  • The	  three	  loss	  funcCons	  are	  related	  so	  they	  give	  similar	  test	  result.	

Fast training by optimization (Cont.)	
• Comparison	  scenarios	  I. LIBSVM:	  polynomial	  kernel	  with	  hinge	  loss.	  
II. LIBLINEAR	  (primal):	  Linear	  SVM	  with	  squared	  hinge	  loss.	  
III. LIBLINEAR	  (dual):	  Linear	  SVM	  with	  squared	  hinge	  loss.	  Fast training by optimization (Cont.)	
LIBSVM	

LIBLINEAR	
Primal	Dual	

Test	  accuracy	

84.79	

84.52	

84.31	

Training	  Cme	30519.10	

1368.25	

4039.20	

• LIBSVM	  and	  LIBLINEAR	  (primal)	  give	  similar	  accuracy.	  
• Training	  Cme	  of	  LIBSVM	  is	  signiﬁcantly	  high.	  
• In	  theory,	  both	  primal	  and	  dual	  solvers	  give	  exactly	  same	  accuracy.	  	Multi-class SVM	• SVM	  is	  designed	  for	  two-­‐class	  classiﬁcaCon.	  
• For	  mulC-­‐class	  two	  methods	  are	  used	  • One-­‐against-­‐one	  	  	  	  (Stores	  k(k-­‐1)/2	  weight	  vectors)	  • One-­‐against-­‐rest	  	  	  	  (Stores	  k	  weight	  vectors)	  • For	  5	  transport	  modes,	  we	  need	  10	  and	  5	  vectors	  respecCvely.	

Multi-class SVM (Cont.)	
• Results	  	  SVM	  method	

Test	  accuracy	  (%)	Model	  size	  (KB)	

One-­‐against-­‐one	

84.52	

2.24	One-­‐against-­‐rest	

83.95	

1.12	Multi-class SVM (Cont.)	

a. 1	  +	  4(4	  –	  1)/2	  =	  7	  weight	  vectors	  b. 1	  +	  1	  +	  3(3	  –	  1)/2	  =	  5	  weight	  vectors	  Multi-class SVM (Cont.)	
• Results	  SVM	  method	

Test	  accuracy	  (%)	Model	  size	  (KB)	

One-­‐against-­‐one	

84.52	

2.24	One-­‐against-­‐rest	

83.95	

1.12	Hierarchy	  1	84.46	

1.57	Hierarchy	  2	84.53	

1.12	Non-machine learning issues	
• Feature	  engineering	  • ExtracCng	  important	  features	  is	  one	  of	  the	  most	  crucial	  steps.	  
• Added	  two	  frequency-­‐domain	  features.	  
a. Peak	  magnitude:	  index	  of	  the	  highest	  FFT	  value.	  
b. RaCo:	  raCo	  between	  largest	  and	  second	  largest	  FFT	  values.	  Non-machine learning issues (Cont.)	
• Results	  CV	  strategy	

5	  features	Adding	  2	  FFT	  features	Instance-­‐wise	  CV	89.90	

92.98	

Log-­‐wise	  CV	85.05	

89.26	

Test	  accuracy	

85.33	

91.53	

Non-machine learning issues (Cont.)	
• Use	  of	  Domain	  knowledge	  • Using	  informaCon	  from	  past	  predicCons.	  
• Power	  saving	  by	  not	  enabling	  the	  classiﬁer	  in	  some	  situaCons.	

Conclusion	
• Direct	  use	  of	  a	  machine	  learning	  method	  may	  not	  give	  saCsfactory	  results.	  
• Careful	  evaluaCon	  criterion	  must	  be	  chosen	  as	  this	  study	  showed	  that	  standard	  CV	  accuracy	  can	  slightly	  over-­‐esCmate.	  
• PracCConer	  should	  take	  care	  while	  employing	  classiﬁers	  and	  should	  have	  deeper	  understanding	  of	  the	  methodology.