\input{preamble}

\title{6 - OPTIMERING}

\begin{document}
\pagenumbering{gobble}


%få inn rangen til en matrise
 

\maketitle

\begin{comment}
På begynnelsen av 1800-tallet oppdaget Guiseppe Piazzi asteroiden Ceres, 
men han ble syk, 
og så forsvant Ceres bak solen. 
Når man skulle lete den opp igjen på andre siden av solen litt senere,
var det ikke så godt å vite den nøyaktige posisjonen,
men Gauss kastet seg over problemet, 
og klarte å spå temmelig presist hvor den kom til å dukke opp. 
Han oppfant i den forbindelse \textbf{minste kvadraters metode}.\footnote{
    \url{https://en.wikipedia.org/wiki/Least_squares}
}
Dette er et av standardverktøyene i kofferten, 
\end{comment}

Du står på toppen av 
et fjell $f: \mathbb{R}^2 \to \mathbb R$
gitt ved
\begin{align*}
	f(x) = - x_1^2 - x_1x_2 - 2x_2^2 + 4 x_1 + 6x_2 + 8.
\end{align*}

\begin{oppgave}{1}
	Hva er koordinatene til toppen?
	Hvordan vet du at du er på toppen?
\end{oppgave}

En funksjon av to variable har fire andrederiverte. 
Hvis du partiellderiverer to ganger med hensyn på én variabel, 
får du de \textbf{rene} annenordens partiellderiverte
\[
\frac{\partial^2 f}{\partial x_1^2}
\quad
\text{og }
\quad
\frac{\partial^2 f}{\partial x_1^2}
\]
og deriverer du med hensyn på én variabel og så med hensyn på den andre, 
får du de \textbf{blandede}
\[
\frac{\partial^2 f}{\partial x_1\partial x_2}
\quad
\text{og }
\quad
\frac{\partial^2 f}{\partial x_2 \partial x_1}.
\]

\begin{oppgave}{2}
	Finn de dobbeltderiverte til fjellet $f$ over.
\end{oppgave}

Det er vanlig å sette opp de andreordens deriverte i 
\textbf{hessematrisen}:\footnote{
	\url{https://en.wikipedia.org/wiki/Hessian_matrix}
}
\[
f''(x)=
\left(\;
\begin{matrix}
\frac{\partial^2 f}{\partial x_1^2} &\frac{\partial^2 f}{\partial x_1x_2}  \\[3mm]
\frac{\partial^2 f}{\partial x_2x_1} &\frac{\partial^2 f}{\partial x_2^2}
\end{matrix}
\;\right)
\begin{comment}
\begin{pmatrix}
\frac{\partial^2 f}{\partial x_1^2} &\frac{\partial^2 f}{\partial x_1x_2} & \cdots&\frac{\partial^2 f}{\partial x_1x_n} \\[2mm]
\frac{\partial^2 f}{\partial x_2x_1} &\frac{\partial^2 f}{\partial x_2^2} & \cdots&\frac{\partial^2 f}{\partial x_2x_n} \\[2mm] 
\vdots & \vdots & \vdots & \vdots \\[2mm]
\frac{\partial^2 f}{\partial x_nx_1} &\frac{\partial^2 f}{\partial x_n x_2} & \cdots&\frac{\partial^2 f}{\partial x_n^2} \\ 
\end{pmatrix}
\end{comment}
\]
Denne er som regel symmetrisk,
men ikke alltid -  
se ukens nøtter.

\begin{oppgave}{3}
Finn fram til Taylors andreordens formel for en funksjon fra $f: \mathbb R^2 \to \mathbb R$
\[
f\left(x+ h\right)\approx f(x)+f'\left(x\right)h + h^T f''(x)h
\]
ved å sende en rett linje gjennom $x$ i retning $h$ og bruke kjerneregelen.
\end{oppgave}


I hessematrisen finner vi info om hvorvidt et kritisk punkt er topp eller bunn. 


\begin{oppgave}{4}
	Forklar hvorfor vi nå trenger å vite om hessematrisen 
	er positivt eller negativt definitt eller ingen av delene, og
	vis at fjellet over har et toppunkt i 
	$(3/7,1/7)^T$. %og ikke et bunnpunkt eller en sadel. 
\end{oppgave}


\begin{oppgave}{5}
	Klassifiser det kritiske punktet til $f(\beta) = (y-X\beta)^T(y-X\beta)$ fra forrige økt.
	%$\beta = \left( X^TX \right)^{-1}X^Ty$.
\end{oppgave}

\begin{center}\includegraphics[scale=.27]{../figurer/L1007196-2}\end{center}


\clearpage

De kritiske punktene på forrige side er alle enten globale minima eller globale maksima.
På gymnaset lærte du at $f: \mathbb{R} \to \mathbb{R}$ kan ha maksima eller minima i\\
\begin{minipage}{80mm}
\begin{itemize}
	\item kritiske punkter.\\[-2mm]
	\item punkter der $f$ eller $f'$ er diskontinuerlig.\\[-2mm]
	\item endepunktene i definisjonsmengden.
\end{itemize} 
\end{minipage}
\begin{minipage}{80mm}
	\vspace{-2mm}
\begin{center}
    \begin{tikzpicture}[thick]
 
		\draw[thick] (2,1) sin (4,4);		  
		\draw[thick] (2,1) sin (1,3);

		\node[above] at (3.5,1.6){\color{red}Lokale};  
 		\node[above] at (3.5,1.3){\color{red}minima};
		\node at (5,2){$\color{red}\circ$};

		\node[below] at (2,4.1){\color{blue}Lokale};
		\node[below] at (2,3.8){\color{blue}maksima};

		\node at (2,.98){$\color{red}\circ$};
		\node at (4,4){$\color{blue}\circ$};
		\node at (1,2.99){$\color{blue}\circ$};
		\draw[-] (4,3) -- (5,2);
        \draw[->] (0,1) -- (7,1);
        \draw[->] (0,1) -- (0,3.5) ;
    \end{tikzpicture}
  \end{center}
\end{minipage}
	
I flere dimensjoner er det litt mer komplisert, 
men grunnprinsippene er de samme. 
La oss introdusere litt notasjon. 
La $\Omega$ være en sammenhengende punktmengde i $\Omega \in \mathbb R^2$.
Hvis en kurve $\Gamma$ er randen til $\Omega$, skriver vi
	\begin{align*}
		\partial \Omega = \Gamma.\\[-10mm]
	\end{align*}
\begin{minipage}{115mm}
\begin{oppgave}{6}
	Et område $\Omega \in \mathbb R^2$ formet 
	ved å ta snittet av første kvadrant med en ellipse med halvakser 4 og 3, 
	se figur. 
	Du går en skitur på fjellet fra forrige side langs $\partial \Omega$ og ønsker å finne toppunktet på turen.\\
	(Du kan for eksempel sette opp parametriseringer for alle de tre bitene av $\Gamma$ og sjekke.)
\end{oppgave}
\end{minipage}
\begin{minipage}{80mm}
\includegraphics[scale=.18]{../figurer/arkitektonisk-perle-1}
\end{minipage}




De fleste land har sitt høyeste punkt på toppen av et fjell. 
Men noen land, 
for eksempel Monaco og Finland, 
har sitt høyeste punkt i en oppoverbakke et eller annet sted på landegrensen.
Kina og Nepal har på en måte begge deler, 
siden de deler Mount Everest.
For funksjoner fra 
$\Omega \in \mathbb{R}^2$
til
$\mathbb{R}$
gjelder det samme - 
de kan ha maksima og minima inne på $\Omega$ eller et eller annet sted på $\partial \Omega$.


\begin{oppgave}{7}
	La nå $\Omega$ være området på figuren over og $f$ fjellfunksjonen. 
	Hva er $f:\Omega \to \mathbb{R}^2$ sitt globale maksimum og minimum?\footnote{
		Egentlig må vi nå være nøye på å skille mellom \textbf{åpne} og \textbf{lukkede} mengder. 
		Mengden $\Omega$ er åpen dersom du kan slå en liten sirkelskive rundt hvert punkt i $\Omega$ 
		og så er alle punkter i sirkelskiven inneholdt i $\Omega$ dersom radien er liten nok. 
		I dette kurset er det nok å forstå den intuitive ideen - 
		$\Omega$ er lukket dersom randkurven $\partial \Omega$ er en del av 
		$\Omega$ og åpen dersom $\partial \Omega$ ikke er en del av $\Omega$.
		Slår du en sirkelskive om et punkt på $\partial \Omega$ 
		vil noe av skiven legge seg utenfor $\Omega$ uansett hvor liten radien er.
	} 
\end{oppgave}



\begin{center}\includegraphics[scale=.28]{../figurer/L1020235}\end{center}



\clearpage

Dersom du skal finne lokale maksima og minima til en deriverbar funksjon 
må du altså lete på $\partial \Omega$ 
i tillegg til å lete opp de kritiske punktene til funksjonen.
På forrige side parametriserte du antagelig bitene av $\partial \Omega$, 
men det finnes en annen teknikk som kalles
\textbf{Lagranges multiplikatormetode}.\footnote{
	\url{https://en.wikipedia.org/wiki/Lagrange_multiplier}
}
La oss si at du går på fjellet gitt av $f$ og at gps-sporet
ditt er gitt av en kurve med likning $g(x)=c$.
Figuren under viser trajektorien til en sliten universitetslektor 
på orrfugljakt.
Ekvidistanselinjene på kartet er de brune nivåkurvene til $f$, 
og han går en tur gitt av den rosa kurven. 

\begin{oppgave}{8}
Forklar ved hjelp av figuren at for det høyeste punktet på turen,
bør gradientene til $f$ og $g$ være parallelle,
og at dersom nivåkurvene er glatte, 
finnes det i dette punktet en konstant $\lambda$ slik at
\[
\nabla f(x)=\lambda \nabla g(x).
\]
\end{oppgave}

\begin{center}\includegraphics[scale=.39]{../figurer/lagrange.png}\end{center}

\begin{oppgave}{9}
Hvorfor er dette det samme som å lete etter kritiske punkter til 
\begin{align*}
	L(x,\lambda) = f(x) + \lambda g(x)?
\end{align*}
	Prøv oppgave 7 på nytt med Lagranges mutliplikatormetode.
\end{oppgave}




\begin{oppgave}{10}
Du går på elliptisk skitur på fjellet 
$h(x)=1-x_1^2-x_1x_2-x_2^2$, 
langs trajektorien gitt ved ellipsen med likning
$
x_1^2+\frac{x_2^2}{4}=1.
$ 
Finn turens høyeste punkt.
\end{oppgave}

\begin{oppgave}{11}
En ellipse med halvakser $a=\frac{1}{2}$ og $b=\frac{\sqrt{3}}{2}$, 
rotert $\pi/4$ radianer i forhold til koordinataksene, 
tilfredsstiller likningen
\[
6(x_1+x_2)^2+2(x_1-x_2)^2=3.
\]
%Hvor lange er halvaksene?
%og har parametrisering
%\[
%x(t)=\begin{pmatrix}\cos t\\ \cos(t+\pi/3)\end{pmatrix}
%\]
Finn den største verdien til 
$
	f(x) = x_1 + 2x_2   
$
på ellipsen.
\end{oppgave}
%Trenger du flere oppggaver, kan du gjøre oppgave 8-12 i kap 9.7, og 1-7 i 9.20. 

\begin{center}\includegraphics[scale=.3]{../figurer/L1020214}\end{center}

\clearpage

Lagranges multiplikatormetode dukker opp i et overraskende antall anvendelser. 
En av de viktigste i dag er kanskje flervariabel regresjon. 

\begin{oppgave}{12}
	En kjemiker har målt lengde og vekt og diameter og så videre på alle erlenmeyerkolbene på laben. 
	Han har målt lengdene både i tommer og i centimeter og ønsker å sjekke om variasjonen i vekt er forklart av variasjonen i lengde og bredde. 
	Men når han prøver å finne den første ordens lineære regresjonen, 
	får han feilmeldingen 
	\begin{lstlisting}
		numpy.linalg.LinAlgError: Singular matrix
	\end{lstlisting}
	\vspace{-4mm}
	når han prøver å løse normallikningene i python. 
	Han er forvirret.
	Hvorfor skjer dette?
\end{oppgave}

Om datamatrisen $X$ ikke har full rang
får man problemer når man skal løse normallikningene. 
På papiret skjer dette når det er perfekt samvariasjon mellom to variable, 
men i praksis får man numeriske problemer allerede når samvariasjonen er høy, 
for da blir kolonnene i $X$ nesten lineært avhengige.
Standardmålet på hvor store problemer en matrise har med nesten lineært avhengige kolonner,
er \textbf{kondisjonstallet}\footnote{
	\url{https://en.wikipedia.org/wiki/Condition_number}
}
\begin{align*}
    \kappa(A)
    = 
    \frac{\sigma_1}{\sigma_r}
\end{align*}
der $\sigma_1$ 
og 
$\sigma_r$ 
er den største og minste singulærverdien.\footnote{
	\url{https://en.wikipedia.org/wiki/Singular_value_decomposition}
}
Problemet med store kondisjonstall,
er at \textit{små endringer i matrisen gir store endringer i annet,
for eksempel egenverdier.}
Dette gjør at modeller kan bli ubrukelige i praksis,
siden små målefeil kan gi store endringer i prediksjon.\footnote{
	\url{https://en.wikipedia.org/wiki/Butterfly_effect}
}

\begin{oppgave}{13}
	I python heter det np.linalg.cond.
    Regn ut kondisjonstallet til 
    \[
        \left(\;
        \begin{matrix}
        1 & a \\
        b & 1 
        \end{matrix}
        \;\right)
    \] 
    for forskjellige verdier for $a$ og $b$.
\end{oppgave}


Tilnærmet lineær avhengighet mellom kolonnene i $X$ er så og si garantert når det blir mange nok kolonner,
og en klassisk teknikk for å håndtere dette
kalles \textbf{ridgeregresjon}.\footnote{
	\url{https://en.wikipedia.org/wiki/Ridge_regression}
}
Teknikken er enkel å forstå om man har grepet på lagrangemultiplikatorer - 
du gir opp å lete etter et globalt minimum for $(y-X\beta)^T(y-X\beta)$,
og leter heller etter minimum på $\Omega$ gitt ved ulikheten $|\beta|^2 \leq r$.
Nå ligger det i sakens natur at det globale minimum til $(y-X\beta)^T(y-X\beta)$ ikke skal ligge inne på $\Omega$ 
(i så fall tilfører rigderegresjon ingenting)
så vi leter etter minimum på $|\beta|^2 = r$. 


\begin{oppgave}{14}
	Hva er minimumspunktet når vi minimerer $(y-X\beta)^T(y-X\beta)$ på $|\beta|^2 = r$? 
\end{oppgave}

\begin{oppgave}{15}
	På eksamen i TMA4106 i vår fant du det første ordens tovariable regresjonspolynomet til punktmengden 
	$(1,0,1)$, $(0,1,1)$, $(1,1,1)$ og $(0,0,0)$.
	Sentrér punktmengden og finn ridgeregresjonen med $r=1/10$.
\end{oppgave}

\clearpage

Når Hoerl og Kennard i 1970 omtaler det at kovariansen 
\say{avviker vesentlig fra enhetsmatrisen},
mener de at kovariansen har høyt kondisjonstall.\footnote{
	\url{https://www.jstor.org/stable/1267351}
}
Enhetsmatrisen er nemlig verdens beste matrise - 
den har kondisjonstall 1. 

\begin{oppgave}{16}
	Vis dette.
\end{oppgave}

Hvis du gjorde nøttene i økt 2-6 i TMA4106, 
husker du kanskje aksiomene for lengde:\footnote{
	\url{https://en.wikipedia.org/wiki/Norm_(mathematics)}
}
\begin{align*}
1: | x | > 0 \; \text{dersom} \; x \neq 0
\hspace*{20mm}
2: |ax | =|a|| x | 
\hspace*{20mm}
3: |x + y |\leq | x | + | y |
\end{align*}



\begin{oppgave}{17}
Den euklidske distansen $\| \mathbf x \|=\sqrt{\sum_k x_k^2}$ over er et spesialtilfelle av $p$-normen
\[
\| \mathbf x \|_p=\sqrt[p]{\sum_k |x_k|^p}.
\]
Vis at 2-normen er en lengde. Skisser enhetssirkelen i $\mathbb{R}^2$ for forskjellige valg av $p$.\\
Fun fact: Fontenen på Sergelplassen i Stockholm har form som enhetssirkelen for $p=4$.
\end{oppgave}


Velger vi $p=2$,
blir $|A|=\sigma_1$,
altså den største singulærverdien. 

\begin{oppgave}{18}
    Vis dette og at $\kappa(A) = |A||A^{-1}|$.
\end{oppgave}

En ulempe med ridgeregresjon er at kun unntaksvis setter komponenter i $\beta$ lik null. 
\textbf{Lassoregresjon}\footnote{
	\url{https://en.wikipedia.org/wiki/Lasso_(statistics)}
} 
fikser dette ved å bruke 1-normen istedet for 2-normen. 
Da kan du kvitte deg med overflødige kolonner i datamatrisen. 

\begin{oppgave}{19}
    Forklar hvorfor lasso klarer dette, men ikke ridge.
\end{oppgave}

Dette leder oss over på \textbf{lineær programmering}.\footnote{\url{https://en.wikipedia.org/wiki/Linear_programming}}
Dette betyr bare at kostfunksjonen er $c^Tx$ og at $\Omega$ er polygonisk. 
Når $\partial \Omega$ har knekkpunkter, 
vil man som regel finne maksima og minima på disse. 
    Studass Bjerkehagen laget en gang en hel økt om lineær programmering, 
	og da introduserte han temaet med omtrent denne problemstillingen.

\begin{oppgave}{20}
	Du har snart eksamen i to grusomme fag,
	og har hundre timer nødpugging igjen til rådighet. 
	Dette koster deg \textit{strev og møye}.
	Det ene faget koster $2.1$ \textit{strev} 
	og $2.9$ \textit{møye} per time,
	mens det andre koster $5.0$ \textit{strev} 
	og $4.1$ \textit{møye} per time. 
	Du tåler $200.0$ \textit{strev} og $300.0$ \textit{møye} totalt. 	
	Skisser $\Omega$.\footnote{
		Hva faen er møye egentlig?
	}
\end{oppgave}

\begin{oppgave}{21}
	Du scorer ett prosentpoeng på eksamensscore per time lesing i det ene faget og to per time i det andre faget.
	Finn den optimale balansen.
\end{oppgave}

\begin{oppgave}{22}
	Rasjonelle studenter ønsker å maksimere karakter, 
	ikke poengscore. 
	Hva er den optimale balansen om du ønsker å få best mulig karakter dersom UiOs karakterskala ligger til grunn?\footnote{
		\url{https://www.uio.no/studier/eksamen/karakterer/fagspesifikk-karakterbeskrivelse/mn-math.html\#skriftlig}
	}
	Enn NTNU sin skala?\footnote{
	\url{https://i.ntnu.no/wiki/-/wiki/norsk/prosentvurderingsmetoden}
	}
\end{oppgave}


\clearpage

\section*{UKENS NØTTER}


Et viktig matrisemåletall er
\textbf{spektralradien}
\begin{align*}
    \rho(A) = \max_k |\lambda_k|.
\end{align*}

\begin{oppgave}{1}
    Vis at dette ikke er en lengde. 
\end{oppgave}

For å forklare at hessematrisen gir info om kritiske punkt, 
er det nyttig å vite at den er symmetrisk. 
Men det finnes altså patologiske tilfeller der den ikke er det. 

\begin{oppgave}{2}
	Er hessematrisen til 
	$
		f(x) = 
		\begin{cases}
			\frac{x_1x_2\left( x_1^2-x_2^2 \right)}{x_1^2+x_2^2} & x \neq 0 \\
			0 & x=0
		\end{cases}
	$
	symmetrisk?
\end{oppgave}

Newtons metode er en teknikk for å løse ikkelineære likningssett,
men også en teknikk for å finne kritiske punkter til skalarfelt.\footnote{
	\url{https://en.wikipedia.org/wiki/Newton\%27s_method_in_optimization}
}

\begin{oppgave}{3}
	Finn og klassifiser de kritiske punktene til 
	\begin{align*}
		V(x)=x_1^3 + x_1^2x_2 + x_1x_2^2 + 2x_2^3 - x_1^2 - x_2^2 - x_1x_2- x_1 -x_2.
	\end{align*}
\end{oppgave}

Her kommer en vanskelig en. 
Vi skal siden se hvorfor den er så vanskelig. 

\begin{oppgave}{4}
	Finn en harmonisk funksjon med et topp- eller bunnpunkt. 	
\end{oppgave}

\begin{center}\includegraphics[scale=.27]{../figurer/L1007227}\end{center}

\clearpage 

Nå er vi i posisjon til å introdusere minste kvadraters metode. 
Studass Hausken gikk over en blomstereng en gang. 
Blomsterengen inneholdt $n$ blomster med 
koordinater $(x_k,y_k)$ der $k$ løp fra 1 til $n$,
og Hausken syntes det var praktisk å organisere disse koordinatene i to vektorer:
\[
    \mathbf x = 
    \begin{pmatrix}
        x_1 \\
        x_2 \\
        \vdots \\
        x_n 
    \end{pmatrix}    
    \hspace*{10mm}
    \text{og}
    \hspace*{10mm}
    \mathbf y = 
    \begin{pmatrix}
        y_1 \\
        y_2 \\
        \vdots \\
        y_n 
    \end{pmatrix}    
\]
Blomstene duftet godt, 
så Hausken ønsket å gå gjennom engen på en rett linje slik at duftopplevelsen ble maksimert. 
Han tenkte det var best å summere opp kvadratet av 
den vertikale avstanden fra hver blomst til den rette linjen 
\[
    y = \beta_1 x + \beta_0
\]
og så minimere denne summen:
\begin{align*}
    f\left( \beta_1,\beta_0 \right) =& 
    \sum_{k=1}^n\left( \beta_1 x_k + \beta_0 - y_k \right)^2\\[2mm]
    =&\sum_{k=1}^n\left( \beta_1 x_k + \beta_0 - y_k \right)\left( \beta_1 x_k + \beta_0 - y_k \right)\\[2mm]
    =&\sum_{k=1}^n 
    \left(
    \beta_1^2 x_k^2 
    + \beta_0^2 
    + y_k^2 
    + 2\beta_1\beta_0 x_k 
    - 2\beta_1x_k y_k 
    - 2\beta_0 y_k
    \right)\\[2mm]
    =&
    \sum_{k=1}^n 
    \beta_1^2 x_k^2 
    + 
    \sum_{k=1}^n 
    \beta_0^2 
    +
    \sum_{k=1}^n 
     y_k^2 
     +
    \sum_{k=1}^n 
    2\beta_1\beta_0 x_k 
    - 
    \sum_{k=1}^n 
    2\beta_1x_k y_k 
    - 
    \sum_{k=1}^n 
    2\beta_0 y_k\\[2mm]
    =&
    \beta_1^2 \|\mathbf x\|^2
    + n\beta_0^2 
    + \|\mathbf{y}\|^2
    + 2\beta_1\beta_0 n\overline{\mathbf{x}}
    - 2\beta_1\mathbf x^T \mathbf y
    - 2\beta_0 n\overline{\mathbf{y}}
\end{align*}
Slik oppfant han den enkleste formen for \textbf{regresjon}.\footnote{
    \url{https://en.wikipedia.org/wiki/Linear_regression}
}
Jeg har bevisst tatt med dette slik at du skal forstå at 
matrisemultiplikasjon vil spare deg for masse kronglete notasjon i TMA4245.

\begin{oppgave}{13}
    Siden $f$ er en positiv kvadratisk funksjon av $\beta_1$ og $\beta_0$,
    er rimelig klart at det må finnes et bunnpunkt et eller annet sted. 
    Sett gradienten til $f$ lik null,
    og utled uttrykkene
    for  \textbf{regresjonskoeffisientene}
    \[
        \beta_1 = \frac{ \mathbf{x}^T \mathbf{y} - n \bar{\mathbf x} \bar{\mathbf y}}{\|\mathbf x\|^2 - n\left( \bar{\mathbf x} \right)^2}
    \hspace{10mm}
    \text{og}
    \hspace*{10mm}
        \beta_0 = \overline{\mathbf y}-\beta_1\overline{\mathbf x}
    %     \frac{ \bar{\mathbf y}\|\mathbf x\|^2 -\bar{\mathbf x}  \left( \mathbf{x}^T\mathbf{y} \right)}{\|\mathbf x\|^2 - n\left( \bar{\mathbf x} \right)^2}.
    \]
\end{oppgave}

\begin{center}\includegraphics[scale=.3]{../figurer/M1004363}\end{center}



\clearpage

Regresjon betyr 
å finne en kurve som \say{passer til} datasettet
på en eller annen måte.
Det alle lærer først er å finne det første ordens 
regresjonspolynomet ved minste kvadraters metode,
fordi dette er enklest, 
og fordi man ofte lurer på om det finnes en rettlinjet avhengighet mellom to størrelser.
Denne type regresjon er \textbf{lineær},
siden uttrykket over er lineært i $\beta_1$ og $\beta_0$.
Variabelen $x$ kalles \textbf{forklaringsvariabelen},
og $y$ kalles \textbf{responsvariabelen}. 
%La oss anta at du har en forklaringsvariabel $x$ og responsvariabel $y$,
%og et datasett med masse målte par $\left( x_k,y_k \right)$.
%Tenk at $k$ er en bil, 
%$x_k$ er bilens målte sylindervolum,
%og $y_k$ er bilens målte drivstofforbruk. 
%Antagelig korrelerer disse to variablene ganske bra,
%siden poenget med en sylinder er at den fylles opp med drivstoff og så eksploderer det. 
%Jo større sylinder, 
%jo mer drivstoff går det. 
Husk at korrelasjon ikke impliserer kausalitet!\footnote{\url{https://www.tylervigen.com/spurious-correlations}}


Uttrykket for regresjonen over kan utledes på en annen måte. 
Du husker kanskje hvordan vi polynominterpolerte i TMA4101. 
Hvis vi krever at det første ordens polynomet skal reise gjennom 
alle datapunktene, 
får vi $n$ likninger:
\begin{align*}
    y_1 &= \beta_1 x_1 + \beta_0 \\
    y_2 &= \beta_1 x_2 + \beta_0 \\
    &\vdots  \\
    y_n &= \beta_1 x_n + \beta_0 
\end{align*}
Det sier seg selv at dette ikke har noen løsning med mindre korrelasjonen er perfekt, 
altså at punktene virkelig ligger på en rett linje. 
På matriseform blir likningssystemet $A\mathbf v = \mathbf y$,
der
\[ 
    \mathbf{y}=
    \begin{pmatrix}
        y_1 \\
        y_2 \\
        \vdots \\
        y_n
    \end{pmatrix}
    \hspace*{10mm}
    A=
    \begin{pmatrix}
        x_1 & 1 \\
        x_2 & 1 \\
        \vdots & \vdots \\
        x_n & 1
    \end{pmatrix}
    \hspace{10mm}
    \mathbf v=
    \begin{pmatrix}
        \beta_1 \\
        \beta_0
    \end{pmatrix}
\]

\begin{oppgave}{14}
    Gang likningssystemet med $A^T$ fra venstre og løs for $\mathbf v$.
    Hvis du regner riktig, 
    skal du få det samme som i forrige oppgave.\\
    (Se figur for geometrisk tolkning. Kolonnene i $A$ kalles $A_1$ og $A_2$.)
\end{oppgave}

\begin{center}
    \includegraphics[scale=.43]{../figurer/projeksjon-3.png}
\end{center}


Hvis du tar et overbestemt likningssystem
og ganger med den transponerte av systemmatrisen fra venstre og løser,
løser du noe som kalles \textbf{normallikningene}.
Grunnen er enkel. 
Systemet 
\[
    A^TA\mathbf{v} = A^T\mathbf{y}
\]
kan like gjerne skrives
\[
    A^T\left( A\mathbf{v} - \mathbf{y} \right) = \mathbf{0}
\]
og dette forklarer geometrisk hva som skjedde i forrige oppgave.

\begin{oppgave}{15}
    Hvis du skjønte transponeringsoperasjonen og hvordan vi skriver skalarprodukt,
    bør det nå være klart at likningssystemet over 
    krever at $A\mathbf{v} - \mathbf{y}$ står ortogonalt på alle kolonner i $A$.
    Dette betyr at vi velger $\mathbf{v}$ slik at avstanden mellom $A\mathbf{v}$ og 
    $\mathbf{y}$ blir minimert; 
    se figuren på forrige side. 
\end{oppgave}

Oppgaven over gjør i bunn og grunn det samme som oppgave 14 i forrige uke.  
Forskjellen er at kolonnene i $A$ ikke er ortogonale;
er de det kan vi regne ut $\mathbf{v}$ slik:
\[
    \mathbf{v} = 
    \frac{\mathbf{y}^TA_1}{A_1^TA_1}A_1+
    \frac{\mathbf{y}^TA_2}{A_2^TA_2}A_2
\]
Fordelen med å forstå den geometriske ideen bak normallikningene,
er at man nå kan forstå hvordan man kjører regresjon basert på 
andre ting enn rette linjer. 
Man setter opp et lineært likningssystem,
og så løser man normallikningene.
Et kvadratisk regresjonspolynom skrives for eksempel
\[
    y = \beta_2x^2 + \beta_1x + \beta_0.
\]
Merk at denne regresjonen også er lineær,
siden uttrykket for det kvadratiske regresjonspolynomet
er lineært i $\beta_2$, $\beta_1$ og $\beta_0$. 
\vspace{-5mm}

\begin{minipage}{120mm}    
\begin{oppgave}{16}
    Finn det kvadratiske regresjonspolynomet til 
    dette datasettet:
\end{oppgave}
\end{minipage}
\begin{minipage}{40mm}
    \begin{center}
        \begin{tabular}{| c | c |}
        \hline
            $x$ & $y$ \\
            \hline
            1 & 2 \\
            2 & 3 \\
            3 & 4 \\
            4 & 5 \\
            5 & 1 \\
             \hline
            \end{tabular}
        \end{center}        
    \end{minipage}

    \begin{center}
        \includegraphics[scale=.25]{../figurer/L1007227}
      \end{center}
      

    \clearpage


\begin{minipage}{135mm}
        Det går fint å regregere med andre typer funksjoner enn polynomer. 
        Teknikken er det samme, 
        minimer summen av kvadratene av avstandene mellom responsvariabelens datapunktener
        og regresjonskurven evaluert i de korresponderende datapunktene for forklaringsvariabelen.
        Jeg var på en hytte i Kragerø en gang og badet i en sirkulær badestamp med et sirkulært høl i bånn. 
        Når jeg skulle tømme den, 
        målte jeg vannstanden etterhvert som stampen tømtes,
        og fikk tabellen i margen.
        Hvis man ikke visste bedre, 
        ville det kanskje være plausibelt å anta 
        at utstrømningen er proporsjonal 
        med vannhøyden,
        siden vanntrykk er proporsjonalt med vanndybde:
        \[
        \dot h = a h.
        \]
        \end{minipage}
        \begin{minipage}{4cm}
        \begin{center}
        \begin{tabular}{c | c}
        $t$\; (s) & $h$\; (cm)\\
        \hline
        0 & 48\\
        10 & 38\\
        20 & 28\\
        30 & 20\\
        40 & 14\\
        50 & 8 
        \end{tabular}
        \end{center}
    \end{minipage}
        
        
        
    \begin{oppgave}{17}
        Finn $h$ og estimér $a$. Hva med integrasjonskonstanten $C$? 
    \end{oppgave}
        
        
    Ifølge fysikkboken er det Torricellis lov som gjelder: 
    \[
        h(t) = h_0\left( 1-\frac{t}{T} \right)^2 \hspace{10mm} T=\frac{V_0}{A}\sqrt{\frac{2}{gh_0}}
    %\dot h = - \sqrt{\frac{2gh}{b^2-1}} 
    \]
    der $g$ er tyngdeakselerasjonen,
    $V_0$ er vannvolumet ved $t_0$ og $A$ er arealet til tappehullet.\footnote{\url{https://en.wikipedia.org/wiki/Torricelli's_law}}
    
    \begin{oppgave}{18}
        Radien til stampen var om lag en meter,
        men jeg målte aldri tappehullet. 
        Hvor stort var det? 
    \end{oppgave}

    \begin{oppgave}{19}
    	Torricellis lov sier jo at $h$ skal være en parabel. 
	Kjør vanlig andreordens polynomregresjon på datasettet 
	(slik som i oppgave 16),
	og sammenlikne med forrige oppgave.
    \end{oppgave}
    

    I eksmeplet denne økten startet med, 
    er temperaturmålingene\\
    np.array([57.4,53.6,49.6,47.4,44.5,42.6,40.4,36.0,35.4,33.8,32.8,30.5,29.5,27.6,27.1,25.1,23.1])\\
    og måletidspunktene (i minutter etter start)\\
    np.array([0,5,10,15,20,25,31,44,50,58,64,76,87,110,119,147,257])
    
    \begin{oppgave}{20}
        Estimer $\alpha$ ved minste kvadraters metode. Temperaturen i omgivelsene var 22 grader.
    \end{oppgave}

\begin{center}\includegraphics[scale=.37]{../figurer/L1001032.jpg}\end{center}

    \begin{comment}
    
    \begin{figure}[H]
    \begin{center}
    \includegraphics[scale=.26]{../figurer/L1019713}
    \caption{Elsys Torjus koser seg i badestampen}
    \end{center}
    \end{figure}
    \vspace{-5mm}
    \begin{figure}[H]
    \begin{center}
    \includegraphics[scale=.26]{../figurer/L1019719}
    \caption{Elsys Torjus hopper i havet og en bikkje}
    \end{center}
    \end{figure}

    \end{comment}
\clearpage
%\begin{comment}

\section*{UKENS NØTTER}


\begin{minipage}{150mm}
    Forestill deg at du har et måleapparat
    og at du måler en normalfordelt størrelse,
    men så vet du at den ene halen i normalfordelingen
    er under deteksjonsgrensen for måleapparatet.\footnote{For eksempel ved at du prøver å finne 
    høyden på den gjennomsnittlige nordmann
    med en målestokk som ikke kan måle kortere lengder enn 170cm.}
    Hvis du nå ønsker å estimere $\mu$ og $\sigma$,
    kan du ikke ta gjennomsnitt og empirisk standardavvik,
    for gjennomsnittet til treffe for høyt
    og det empiriske standardavviket for lavt.
    
    \begin{oppgave}{1}
        I datasettet over bredden på kaibordene 
        fra integraløkten i TMA4101
        har jeg her tatt ut de laveste målingene
        (tre bord på 153 og et på 152).
        Finn estimater for $\mu$ og $\sigma$ i normalfordelingen
        \[
            f(x) = \frac{1}{\sqrt{2\pi}\sigma} e^{-\left( x-\mu \right)^2/2\sigma^2}
        \]
        ved å kjøre minste kvadraters metode.
        Det blir et ikkelineært problem; 
        det enkleste er nok å implementere noe som heter 
        \say{steepest descent method},
        eller en av de andre liknende variantene som leter etter 
        minimumspunkter til flervariable funksjoner.\\
        (På springer finner du optimeringsboken til Nocedal og Wright. 
        Den er grei å ha.)\\
    \end{oppgave}
        
    \begin{center}
        \includegraphics[scale=1.2]{../figurer/kai-5}
    \end{center}
\end{minipage}
\begin{minipage}{30mm}
        \begin{center}
        \includegraphics[scale=.8]{../figurer/kai-4}
        \end{center}
\end{minipage}        
%\end{comment}


\end{document}
