Mercurial > hg > medcouple

annotate talk/talk.tex @ 74:305b7361a5bd default tip @

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
showalgo: save a snapshot instead of waiting for keyboard input
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Sun, 29 May 2016 19:05:01 -0400
parents d5ec0659b26b
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
44
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
1 %%% BEGIN BEAMER PREAMBLE %%%
60
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
2 \documentclass[blue]{beamer}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
3 \usepackage{bm, fourier, anyfontsize, xcolor}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
4 \newcommand{\MC}{\operatorname{MC}}
61
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
5 \newcommand{\signum}{\operatorname{signum}}
60
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
6 \newcommand{\IQR}{\operatorname{IQR}}
44
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
7
61
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
8 \theoremstyle{definition}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
9 \newtheorem*{defn}{Definition}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
10
44
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
11
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
12 \mode<presentation>
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
13 {
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
14 \usetheme{boxes}
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
15 \usecolortheme{crane}
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
16 }
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
17 \beamertemplatenavigationsymbolsempty
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
18
47
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
19 \AtBeginSection[]
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
20 {
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
21 \begin{frame}<beamer>
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
22 \frametitle{Outline}
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
23 \tableofcontents[currentsection]
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
24 \end{frame}
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
25 }
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
26
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
27
44
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
28 \usepackage{times}
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
29 %%% END BEAMER PREAMBLE %%%
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
30
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
31
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
32 %%% BEGIN METADATA %%%
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
33
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
34 \author{Jordi G. H. $\langle$jordigh@octave.org$\rangle$ }
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
35
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
36
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
37 \title{The Medcouple}
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
38 \subtitle{A robust measure of skewness}
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
39 \date{}
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
40
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
41 %%% END METADATA%%%
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
42
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
43 \begin{document}
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
44
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
45 \begin{frame}
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
46 \titlepage
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
47 \end{frame}
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
48
47
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
49 \begin{frame}
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
50 \frametitle{Outline}
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
51 \tableofcontents
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
52 \end{frame}
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
53
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
54 \section{Outliers and Boxplots}
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
55
60
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
56 \begin{frame}{What is an outlier?}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
57 \pause
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
58 \begin{center}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
59 \pgfimage[height=2.5in]{img/normal-boxhistplot.pdf}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
60 \end{center}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
61 A simple answer: Tukey's boxplots
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
62 \end{frame}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
63
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
64 \begin{frame}{Anatomy of a boxplot}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
65 \begin{overlayarea}{\textwidth}{8cm}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
66 \only<1>{\pgfimage[width=4in]{img/normal-points}}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
67 \only<2>{\pgfimage[width=4in]{img/normal-boxplot}}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
68 \only<3>{\pgfimage[width=4in]{img/normal-boxplot-bare/base}}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
69 \only<4>{\pgfimage[width=4in]{img/normal-boxplot-bare/median}}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
70 \only<5>{\pgfimage[width=4in]{img/normal-boxplot-bare/q1q3}}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
71 \only<6>{\pgfimage[width=4in]{img/normal-boxplot-bare/IQR}}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
72 \only<7>{\pgfimage[width=4in]{img/normal-boxplot-bare/whiskers}}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
73 \only<8>{\pgfimage[width=4in]{img/normal-boxplot-bare/15}}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
74 \only<9>{\pgfimage[width=4in]{img/normal-boxplot-bare/outliers}}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
75 \end{overlayarea}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
76 \end{frame}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
77
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
78 \begin{frame}{Anatomy of a boxplot}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
79 \begin{itemize}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
80 \item Why 1.5?
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
81 \pause
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
82 \item Tukey responded: ``it's less than 2 and more than 1''
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
83 \end{itemize}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
84 \end{frame}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
85
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
86 \begin{frame}{Outliers}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
87 \pause
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
88 \begin{center}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
89 \pgfimage[height=2.5in]{img/normal-boxhistplot}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
90 \end{center}
61
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
91
60
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
92 The boxplot identifies $10$ outliers out of $1000$ points ($1\%$)
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
93 \end{frame}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
94
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
95 \begin{frame}{Skew distributions}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
96 Remember:
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
97 \begin{center}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
98 \pgfimage[width=4in]{img/skew-distributions}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
99 \end{center}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
100 \end{frame}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
101
47
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
102 \begin{frame}
60
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
103 For skew distributions...
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
104 \end{frame}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
105
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
106 \begin{frame}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
107 \begin{overlayarea}{\textwidth}{8cm}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
108 \only<1>{
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
109 \pgfimage[height=3in]{img/geometric-boxhistplot}
61
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
110
60
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
111 $433$ outliers out of $10 000$ points ($4.3\%$)
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
112 }
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
113 \only<2>{
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
114 \pgfimage[height=3in]{img/boys-and-girls}
61
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
115
60
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
116 $578$ and $644$ outliers for actors and actresses respectively
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
117 ($1.2\%$ and $3\%$)
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
118 }
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
119 \end{overlayarea}
47
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
120 \end{frame}
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
121
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
122 \begin{frame}
60
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
123 \begin{itemize}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
124 \item Too many outliers...
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
125 \pause
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
126 \item Idea: adjust whisker lengths taking into account skewness:
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
127 \end{itemize}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
128 \emph{M. Hubert; E. Vandervieren (2008). "An adjusted boxplot for skewed
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
129 distributions". Computational Statistics and Data Analysis 52
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
130 (12): 5186-5201. doi:10.1016/j.csda.2007.11.008.}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
131 \end{frame}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
132
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
133 \begin{frame}{Adjusted boxplot}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
134 \begin{overlayarea}{\textwidth}{3cm}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
135 \only<1>{
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
136 Recall normal whiskers:
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
137 % Trick to hide medcouple, use whiteout, so that the text gets
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
138 % positioned the same with or without it.
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
139 \begin{align*}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
140 \text{lower} &= Q_1 - 1.5 \IQR\textcolor{white}{e^{a \MC}} \\
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
141 \text{higher} &= Q_3 + 1.5 \IQR\textcolor{white}{e^{b \MC}}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
142 \end{align*}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
143 }
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
144 \only<2>{
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
145 Instead, use adjusted whiskers:
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
146 \begin{align*}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
147 \text{lower} &= Q_1 - 1.5 \IQR\textcolor{red}{e^{a \MC}} \\
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
148 \text{higher} &= Q_3 + 1.5 \IQR\textcolor{red}{e^{b \MC}}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
149 \end{align*}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
150 \begin{itemize}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
151 \item[$\MC$] -- the \emph{medcouple}, a measure of skewness
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
152 \item[$a, b$] -- parameters to fit across some sample distributions
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
153 \end{itemize}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
154 }
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
155 \end{overlayarea}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
156 \end{frame}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
157
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
158 \begin{frame}{Adjusted boxplot}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
159 For the whiskers, Hubert and Vandervieren recommend:
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
160 \[
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
161 \begin{cases}
61
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
162 [Q_1 - 1.5 \IQR e^{-3 \MC}, Q_3 + 1.5 \IQR e^{4 \MC}] &\text{if } \MC > 0 \\
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
163 [Q_1 - 1.5 \IQR e^{-4 \MC}, Q_3 + 1.5 \IQR e^{3 \MC}] &\text{if } \MC < 0
60
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
164 \end{cases}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
165 \]
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
166 \pause
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
167 Of course, if $\MC = 0$ (no skewness) then no adjustment
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
168 \end{frame}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
169
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
170 \begin{frame}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
171 Let's see some adjusted boxplots...
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
172 \end{frame}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
173
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
174 \begin{frame}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
175 \begin{overlayarea}{\textwidth}{8cm}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
176 \only<1>{
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
177 \pgfimage[height=3in]{img/geometric-boxhistplot}
61
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
178
60
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
179 $433$ outliers out of $10 000$ points ($4.3\%$)
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
180 }
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
181 \only<2>{
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
182 \pgfimage[height=3in]{img/geometric-boxhistplot-adjusted}
61
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
183
60
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
184 \textcolor{red}{$25$ outliers} out of $10 000$ points
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
185 (\textcolor{red}{$0.25\%$}) (\textcolor{blue}{$\MC = 0.25$})
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
186 }
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
187 \end{overlayarea}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
188 \end{frame}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
189
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
190 \begin{frame}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
191 \begin{overlayarea}{\textwidth}{8cm}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
192 \only<1>{
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
193 \pgfimage[height=3in]{img/normal-boxhistplot}
61
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
194
60
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
195 $10$ outliers out of $1 000$ points ($1\%$)
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
196 }
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
197 \only<2>{
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
198 \pgfimage[height=3in]{img/normal-boxhistplot-adjusted}
61
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
199
60
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
200 \textcolor{red}{$10$ outliers} out of $1 000$ points
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
201 (\textcolor{red}{$1\%$}) (\textcolor{blue}{$\MC = 0.0006$})
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
202 }
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
203 \end{overlayarea}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
204 \end{frame}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
205
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
206 \begin{frame}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
207 \begin{overlayarea}{\textwidth}{8cm}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
208 \only<1>{
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
209 \pgfimage[height=3in]{img/boys-and-girls}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
210
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
211 $578$ and $644$ outliers for actors and actresses respectively
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
212 ($1.2\%$ and $3\%$)
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
213 }
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
214 \only<2>{
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
215 \pgfimage[height=3in]{img/boys-and-girls-adjusted}
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
216
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
217 \textcolor{red}{$346$} and \textcolor{red}{$657$} outliers for
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
218 actors and actresses respectively
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
219 (\textcolor{red}{$0.69\%$} and \textcolor{red}{$3\%$})
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
220 (\textcolor{blue}{$\MC = 0.12$} and \textcolor{blue}{$\MC = 0.231$})
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
221
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
222 }
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
223 \end{overlayarea}
47
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
224 \end{frame}
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
225
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
226 \section{The Medcouple}
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
227
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
228 \begin{frame}
61
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
229 \emph{G. Brys; M. Hubert; A. Struyf (November 2004). "A Robust
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
230 Measure of Skewness". Journal of Computational and Graphical
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
231 Statistics 13 (4): 996-1017. doi:10.1198/106186004X12632.}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
232 \end{frame}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
233
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
234 \begin{frame}{Motivation}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
235 Consider the quartile skewness:
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
236 \[
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
237 B_1 = \frac{(Q_3 - Q_2) - (Q_2 - Q_1)}{Q_3 - Q_1}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
238 \]
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
239 $Q_2 = \text{median}$
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
240 \end{frame}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
241
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
242 \begin{frame}{Definition}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
243 Idea: compute this kernel over all couples split along the median:
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
244 \[
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
245 h(x_i, x_j) =
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
246 \begin{cases}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
247 \frac{(x_i - m) - (m - x_j)}{x_i - x_j} \\
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
248 \signum(p - 1 - i - j) & \text{if } x_i = m = x_j
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
249 \end{cases}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
250 \]
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
251 \pause
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
252 where
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
253 \begin{itemize}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
254 \item $m = \text{median}$
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
255 \item $x_i \geq m \geq x_j$
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
256 \item $p = |\{x_i \geq m\}|$
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
257 \end{itemize}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
258 \pause
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
259 \begin{defn}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
260 The \emph{medcouple} is the median of the kernel of all couples
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
261 above.
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
262 \end{defn}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
263 \end{frame}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
264
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
265 \begin{frame}{Properties}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
266 It is easy to see that medcouple is
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
267 \pause
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
268 \begin{itemize}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
269 \item location-invariant
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
270 \pause
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
271 \item scale-invariant
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
272 \pause
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
273 \item between $-1$ and $1$
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
274 \pause
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
275 \item a measure of skewness
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
276 \end{itemize}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
277 \end{frame}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
278
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
279 \begin{frame}{Properties}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
280 The medcouple is a \emph{robust} measure of skewness.
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
281 \pause
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
282 \begin{defn}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
283 A statistic is \emph{robust} if it does not depend on the values
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
284 of extreme values (outliers).
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
285 \end{defn}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
286 \pause
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
287 \begin{itemize}
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
288 \item The median has maximum robustness. Its breakdown point is $50\%$.
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
289 \pause
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
290 \item The medcouple's breakdown point is $25\%$.
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
291 \end{itemize}
47
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
292 \end{frame}
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
293
58
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
294
60
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
295 \begin{frame}{Computing the medcouple}
58
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
296 \begin{center}
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
297 \pgfimage[width=4in]{img/naive/x-orig.png}
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
298 \end{center}
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
299
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
300 Take some $X$ random numbers.
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
301 \end{frame}
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
302
60
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
303 \begin{frame}{Computing the medcouple}
58
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
304 \begin{center}
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
305 \pgfimage[width=4in]{img/naive/x-sorted.png}
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
306 \end{center}
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
307
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
308 Sort them.
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
309 \end{frame}
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
310
60
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
311 \begin{frame}{Computing the medcouple}
58
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
312 \begin{center}
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
313 \pgfimage[width=4in]{img/naive/sortx-red.png}
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
314 \end{center}
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
315
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
316 Pick the median.
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
317 \end{frame}
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
318
60
cd940f75aab6 Finish section 1, two more to go
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 58
diff changeset
319 \begin{frame}{Computing the medcouple}
58
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
320 \begin{overlayarea}{\textwidth}{8cm}
64
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
321 \only<1>{
58
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
322 \begin{center}
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
323 \pgfimage[height=2in]{img/naive/medc-computation-init.png}
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
324 \end{center}
64
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
325 Split up $X$ into $X^+$ and $X^-$ along the median.
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
326 }
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
327 \only<2>{
58
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
328 \begin{center}
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
329 \pgfimage[height=2in]{img/naive/medc-computation.png}
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
330 \end{center}
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
331 Evaluate the kernel for all couples.
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
332 \[
61
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
333 \frac{ (x_i - x_m) - (x_m - x_j)}{x_i - x_j},
73b369370665 Finish section 2
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 60
diff changeset
334 \quad x_i \in X^+, \quad x_j \in X^-
64
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
335 \]
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
336 }
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
337 \only<3>{
58
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
338 \begin{center}
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
339 \pgfimage[height=2in]{img/naive/medc-computation-done.png}
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
340 \end{center}
64
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
341 The median of this matrix is the medcouple.
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
342 }
58
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
343 \end{overlayarea}
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
344 \end{frame}
57a0f3beaba8 talk: add naïve medcouple algorithm
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 47
diff changeset
345
64
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
346 \begin{frame}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
347 Problem: this algorithm is $O(n^2)$!!
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
348 \end{frame}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
349
47
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
350 \section{Computation of the Medcouple}
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
351
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
352 \begin{frame}
64
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
353 Now pure CS:
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
354 \pause
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
355 \begin{problem}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
356 Find the median of a matrix with sorted rows and sorted columns.
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
357 \end{problem}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
358 \end{frame}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
359
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
360 \begin{frame}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
361 \emph{Donald B. Johnson; Tetsuo Mizoguchi (May 1978). "Selecting The
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
362 Kth Element In X + Y And X1 + X2 +...+ Xm". SIAM Journal of
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
363 Computing 7 (2): 147-153. doi:10.1137/0207013.}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
364 \pause
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
365 \begin{itemize}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
366 \item Old paper, hard to read. But cool ideas!
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
367 \pause
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
368 \item Paper generalises to $n$-dimensional array with sorted slices
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
369 \end{itemize}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
370 \end{frame}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
371
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
372 \begin{frame}{Preliminaries}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
373 Helper algorithms:
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
374 \pause
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
375 \begin{description}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
376 \item[Selection Algorithm:] e.g. quickselect,
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
377 \texttt{nth\_element} in C++ or \texttt{partition} in numpy, $O(n)$ time
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
378 \pause
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
379 \item[Weighted Median:] binary search using
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
380 selection algorithm, $O(n)$ time.
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
381 \end{description}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
382 \end{frame}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
383
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
384 \begin{frame}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
385 We now make two important observations
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
386 \end{frame}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
387
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
388 \begin{frame}{Two observations}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
389 Compare against whole matrix in $O(n)$ time
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
390 \begin{overlayarea}{\textwidth}{6cm}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
391 \only<1>{
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
392 \begin{center}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
393 \pgfimage[width=2in]{img/kth-pair/greater-than}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
394 \end{center}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
395
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
396 Bottom-up.
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
397 }
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
398 \only<2>{
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
399 \begin{center}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
400 \pgfimage[width=2in]{img/kth-pair/less-than}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
401 \end{center}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
402
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
403 Top-down.
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
404 }
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
405 \end{overlayarea}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
406 \end{frame}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
407
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
408 \begin{frame}{Two observations}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
409 Compare against half the matrix in $O(1)$ time
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
410 \begin{center}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
411 \pgfimage[width=2in]{img/kth-pair/middle-of-middle}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
412 \end{center}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
413 \end{frame}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
414
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
415 \begin{frame}{Putting it together}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
416 Iteratively, we have bounds for the global median
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
417 \begin{center}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
418 \pgfimage[width=2in]{img/kth-pair/row-medians}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
419 \end{center}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
420 \end{frame}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
421
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
422 \begin{frame}{Putting it together}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
423 If we align the row medians...
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
424 \begin{center}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
425 \pgfimage[width=2in]{img/kth-pair/row-medians-aligned}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
426 \end{center}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
427 \end{frame}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
428
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
429 \begin{frame}{Putting it together}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
430 With the weighted median (in $O(n)$ time), we compare to at least half the
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
431 remaining entries, discarding at least $1/4$.
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
432 \begin{center}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
433 \pgfimage[width=2in]{img/kth-pair/row-medians-compared}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
434 \end{center}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
435 \end{frame}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
436
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
437 \begin{frame}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
438 So, final algorithm!
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
439 \end{frame}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
440
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
441 \begin{frame}{Grand finale}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
442 Procedure (serves one medcouple)
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
443
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
444 \begin{enumerate}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
445 \item Compute ingredients for medcouple matrix: $O(n \log n)$
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
446 \pause
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
447 \begin{enumerate}[(A)]
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
448 \item \label{loop} Compute $t = \text{median of row medians}$: $O(n)$
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
449 \pause
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
450 \item \label{compare} Compare $t$ to the whole matrix: $O(n)$
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
451 \pause
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
452 \item Found the median? Found the medcouple! DONE.
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
453 \pause
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
454 \item \label{compare} Use comparison from \eqref{compare} to
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
455 throw out entries.
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
456 \pause
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
457 \item More than $n$ entries remaining? LOOP TO \eqref{loop}.
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
458 \end{enumerate}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
459 \pause
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
460 \item Use selection algorithm on remaining entries: $O(n)$.
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
461 \end{enumerate}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
462 \pause
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
463
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
464 Step \eqref{compare} throws out at least $1/4$ of all entries, so
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
465 the whole algorithm is $O(n \log n)$.
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
466 \end{frame}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
467
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
468 \begin{frame}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
469 \begin{center}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
470 \LARGE{Questions?}
d5ec0659b26b write last section
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 61
diff changeset
471 \end{center}
47
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
472 \end{frame}
1b15b9a0f336 insert first image into slides
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents: 44
diff changeset
473
44
83f8cf24a8e3 init medcouple presentation
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
474 \end{document}