Anders Munk-Nielsen

Programmér dynamisk og kend dig selv — og hvad så?

Ja, ja, ja, økonomisk institut opretter et fag i Dynamic Programming. Men hvad har det med mig at gøre?" Hvis du går med sådanne tanker, så vær ikke bange for at stå frem. En rundspørge blandt unge politstuderende viser, at mange unge går med sådanne tanker. Derfor er det bestemt ikke noget, man skal skamme sig over — kun gennem oplysning kan vi komme fordommene til livs og ruske op i gamle forstokkede billeder.

Det kendte paradigme i mikroøkonometri
Dynamisk programmering repræsenterer et nyt paradigme i forhold til, hvordan man angriber mikrodata empirisk i økonomisk videnskab. På politstudiets bachelordel præsenteres man for økonometriens svar på shotgunnen, og man får i den forbindelse snuset til first-differences og fixed effects. I de senere fag ser man ofte eksempler på, hvordan man med økonometrikerens schweizerkniv, OLS, i den ene hånd og en spændende, eksogen reform/instrument i den anden form kan svare på spændende spørgsmål lige fra (den hellige gral) afkastet af uddannelse til effekten af download på CD salg. 

Uden at vide det, har man med forelæseren som rundviser bevæget sig rundt i den vestlige foyer af økonometriens Madame Tussauds og måbende beundret de klassiske studier i mikroøkonometriens vidunderlige verden. 

Det ukendte paradigme i mikroøkonometri
Men hvad er nu det? En af deltagerne fra gruppen af studerende stikker af fra flokken og lister sig ned i den østlige fløj af museet. Her er støvet og langt mellem gæsterne, men voksfigurerne her er anderledes og skræmmer og ophidser på samme tid den intetanende polit! Voksfiguren af Harold Zurcher markerer indgangen til det forjættede land.

En vred rundvisende forelæser griber nu fat i den forvildede lille polit, som grædende trækkes tilbage til resten af gruppen. Den østlige fløj, “Strukturel Mikroøkonometri”, er et selvstudie, og den er et selvstudie, som man ikke kan nå at se på en almindelig kandidat — det er forment Ph.D.-studierne.

Nu åbnes døren
Men hvad er nu det? Et nyt fag, “Dynamic Programming - Theory, Computation, and Empirical Applications”?  

Mine damer og herrer, for allerførste gang nogensinde bliver det nu muligt at åbne døren ind til den dynamiske verdens magiske vidundere! Det er en unik mulighed for at udvide sin horisont, bliver en dygtigere programmør og lære nogle vanvittigt sexede modeller at kende. 

Faget lover en meget ambitiøst læseplan, men de ugentlige øvelsestimer skal nok trække det hele ned på et praktisk anvendeligt niveau. Præcist som vi kender og elsker det fra Advanced Microeconometrics. For de interesserede er der informationsmøde fredag 21. november (se her).

Hvad er dynamisk programmering?

 Utrolig mange problemer i mikroøkonomi er dynamiske i deres natur, og de spænder meget bredt, fx opsparing, tilbagetrækning/pension, bilkøb og -udskiftning, virksomheders beslutninger om at gå ind på nye markeder osv. I dette paradigme tager man strukturen meget alvorligt. I modsætning til hertil vil man med OLS-tilgangen, hvor man leder efter et y og et x, som der så er en black box forbindelse imellem, så vil man her præcist dykke ned i den black box og tænde lyset. 

Hvor OLS er hammeren i det velkendte “reduced form”-paradigme, så er værdifunktioner og Bellman-ligninger hammeren når man arbejder med dynamiske modeller. Når man først lærer disse at kende (og især hvis man gør det som selvstudie), kan det godt føles som at gå fra en lille læge-banke-på-knæet-hammer til en stor, led forhammer, men netop derfor er det en fremragende mulighed, at der nu bliver oprettet et kursus til formålet! 

Hvorfor dynamisk programmering? 
Mange tror, at man kun arbejder med dynamisk programmering for at få street credit, men der er faktisk meget mere i det. Det primære formål er de kontrafaktiske simulationer (en: counterfactual simulations). Hvor man med OLS typisk kun kan svare på, hvad elasticiteten er mht. nøjagtig den X-variabel, man har i sit datasæt (fx lønnen), så bliver dynamiske modeller brugt til at lave meget rige kontrafaktiske simulationer, hvor man ændrer på forskellige aspekter af det institutionelle framework. 

Fordi man har “tændt lyset” i sin black box giver modellen ofte forudsigelser på en lang række marginer, som man normalt ikke kan sige noget om. Og den kan oftest også svare på, hvad effekten er af at ændre på policies, som man ikke ville kunne ellers. 

9 kommentarer


Casper Nordal Jørgensen

Casper Nordal Jørgensen @ d. 10. december 2014 #2

Fantastisk Anders!
Det er en genial idé med faget. Jeg ville ønske, at der var sådan et tilbud mens jeg var på kandidaten.
Nuvel, jeg vil blot bidrage til den lange række af argumenter for hvorfor dynamisk programmering er fantastisk. Hvis man vil være moderne makroøkonom, er det kritisk at kende til dynamisk programmering. I teoretiske modeller og i empiriske studier er dynamisk programmering top notch.
Derudover er faget (så vidt jeg ved) endnu unikt set i et internationalt perspektiv.


Simon Shine

Simon Shine @ d. 22. december 2014 #3

Da jeg tidligere har læst datalogi og nu læser økonomi, er jeg forundret over den vinkel som dynamisk programmering (DP) her får. På datalogi bliver man undervist i DP som led i et førsteårskursus om algoritmer og datastrukturer. Her lærer man at DP er en programmeringsteknik som får nogle problemer af tilsyneladende overvældende størrelse (eksponentiel køretid) til at kunne løses meget hurtigere (polynomiel køretid).

Et problem af denne slags kunne fx være at man har mønter med værdierne {2, 3, 5} kr. og man bliver bedt om at give byttepenge til beløbet 22 kr. således at man giver færrest muligt mønter tilbage.

En naiv løsning kunne være: Giv så mange af mønten med den største værdi indtil én mønt mere af den slags ville overskride beløbet. Gør dernæst det samme med mønten med den næststørste værdi osv. indtil beløbet er opnået. Et eksempel for 22 kr.: 4*5 kr. giver 20, og en ekstra 5'er ville overskride 22. Tilføj 0*3 kr. da en ekstra 3'er ville overskride 22. Tilføj 1*2 kr. og beløbet er opnået.

Denne løsningsstrategi kaldes grådig fordi man antager at det altid vil være korrekt at vælge flest mulige af den højeste mønt. Men hvis mønterne er valgt uheldigt (hvilket jeg har forsøgt at gøre ovenfor), kan det godt være at det grådige valg ikke virker. Et modeksempel ville være 21 kr.: Hvis man starter med fire 5'ere opnår man aldrig nøjagtigt 21 kr. i byttepenge.

Problemets overvældende størrelse kommer ved at man måske tænker, den eneste løsning her enten er at lægge vilkårligt mange mønter tilbage, man ved uheld har forsøgt sig med (fx for mange 5'ere), eller at man i værste tilfælde konstruerer samtlige bunker af mønter som giver en sum lig 21 (og forsøger at konstruere en masse bunker, man må smide væk fordi de ikke kan summere til 21) og vælger den med færrest mønter i.

Et problem kan løses vha. DP hvis det udviser to egenskaber: Overlappende delproblemer og optimal substruktur.

Overlappende delproblemer betyder at hvis jeg deler et problem (fx at veksle 21 kr.) op i mindre problemer (fx at veksle 5 kr. og at veksle 16 kr.), så skal det være sådan at jeg før eller siden vil få de samme delproblemer flere gange. Fx vil jeg, hvis jeg deler problemet at veksle 16 kr. op i problemet at veksle 5 kr. og at veksle 11 kr. have stødt på problemet at veksle 5 kr. to gange allerede. Tricket er så kun at løse et delproblem én gang, gemme resultatet i en tabel, og næste gang jeg støder på det, slå det op i tabellen.

Og optimal substruktur: Hvis jeg har fundet den optimale måde at veksle 5 kr. på i et delproblem, så skal det også være sådan at det ville være det optimale valg i alle de problemer hvor delproblemet indgår i. For eksempel er løsningen til 21 kr. = 3*5 kr. + 2*3 kr.

Men det interessante og letforståelige her er at bruge en tabel til at gemme resultater i sådan at man sjette gang er nødt til at finde den optimale måde at veksle 10 kr. kan nøjes med et simpelt opslag i stedet for en masse beregninger. Den eneste ulempe er at man nu skal bruge noget hukommelse i computeren på at huske denne tabel.

Og det svære ved DP er typisk at indse hvordan de to egenskaber, overlappende delproblemer og optimal substurktur, gælder for en problemstilling og vise dette matematisk. Det burde derimod ikke afholde én fra at bruge teknikken i ens daglige programmering.

For at trække den her ret lavpraktiske forklaring tilbage til noget af det som Anders Munk-Nielsen siger, kunne man enten tolke DP som en måde at løse eksisterende problemer på meget mere effektivt, eller at der findes en helt ny mængde af problemer som før ikke lod sig løse særlig nemt uden DP, fx problemer med mange parametre som i hvert eneste tilfælde de forekommer skal genberegnes (med mindre man er smart og husker svaret).

Der findes mange problemstillinger som er mere økonomisk relevante end at veksle penge.

Hilsen Simon


Casper Nordal Jørgensen

Casper Nordal Jørgensen @ d. 22. december 2014 #4

@Simon.
Interessant eksempel på den jordnære brugbarhed af dynamisk programmering (DP). De eksempler jeg er stødt på tidligere er udregning af Fibonacci numre og løsning af (subprime perfekte) Nash Ligevægte i spilteori, begge udviser samme struktur som dit eksempel.
Jeg er ikke sikker på hvad du tænker ift. dit spørgsmål? Anders advokerer for DP som en forlængelse af økonometrisk teori (ret mig hvis jeg tager fejl), mens min kommentar advokerede for DP til makroøkonomisk modellering. DP er et stærkt værktøj i begge tilfælde og derfor værd at stifte bekendtskab med.


Simon Shine

Simon Shine @ d. 22. december 2014 #5

@Casper: Jeg har ikke stillet noget spørgsmål. Min kommentar var et perspektiv på formidlingen af hvad DP er. Fagnørder udvikler jo deres eget sprog, og jeg forstod desværre ikke hvad der mentes med kontrafaktisk simulation og institutionelle frameworks. Metaforen om at dykke ned i en sort kasse og tænde lyset er ikke en jeg har tænkt på i forbindelse med at forstå DP, men det er jo spændende at se hvad der fungerer.

Hvad angår beregning af Fibonacci-funktionen, så er DP en smule overkill, da man ikke behøver konstruere en tabel med n indgange for at løse fib(n) idet man kan nøjes med at gemme de to foregående Fibonacci-tal og smide de øvrige væk. En endnu bedre løsning end dét blev fundet af Abraham de Moivre i 1730, der i dag kan formuleres som første indgang i matricen [[1 1] [1 0]]^n for fib(n) [2]. (Dens køretid er O(lg n).)

DP i makroøkonomi lyder interessant. Det kan være, du skal skrive et blogindlæg om det. :)

[1]: https://en.wikipedia.org/wiki/Dynamic_programming#Example:_Mathematical_optimization
[2]: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibformproof.html


Simon Shine

Simon Shine @ d. 22. december 2014 #6

Ups, død kildehenvisning. Nå, i det mindste ligner det at jeg tænker før jeg skriver. Hvis så bare jeg også tænkte *efter* jeg skrev.


Patrick Kofod Mogensen

Patrick Kofod Mogensen @ d. 23. december 2014 #7

@Simon Shine

Anders Munk-Nielsens motivering her er, at faget handler om Dynamisk Programming (DP) i "Theory, Computation, ..." og vigtigt "Emperical Applications." Især den sidste del er vigtig for de to forelæsere (Bertel Schjerning og Thomas Jørgensen) og holdunderviseren (mig).

Det er rigtigt at man i datalogien univers bruger tankegangen bag dynamisk programmering til til at motivere rekursive algoritmer. Den oprindelig anvendelse handler dog om optimeringsproblemer ("programming" var dengang synonymt med "optimization, som i lineær programmering), og vores tilgang er da også optimeringsproblemer med en tidsdimension. Det er vigtigt fordi det er grundpillen i moderne strukturel estimation. Her er det nødvendigt at kunne løse et DP for en virksomhed, eller forbruger, for eksempel, som så giver anledning til en likelihoodfunktion, som man bruger når man vil kæde sin model sammen med data.

For at citere wikipedia (fordi så sej er jeg):

"Dynamic programming is both a mathematical optimization method and a computer programming method. In both contexts it refers to simplifying a complicated problem by breaking it down into simpler subproblems in a recursive manner. While some decision problems cannot be taken apart this way, decisions that span several points in time do often break apart recursively; Bellman called this the "Principle of Optimality". Likewise, in computer science, a problem that can be solved optimally by breaking it into subproblems and then recursively finding the optimal solutions to the subproblems is said to have optimal substructure."

Det er her ret klart at der er et kæmpe stort overlap, men motivationen og målet er ikke altid helt det samme hos matematikere (økonomer) som hos dataloger. Dette forklarer nok hvorfor du studsede en smule over tilgangen. Du er dog yderst velkommen til at kigge forbi og undres videre!


Simon Shine

Simon Shine @ d. 24. december 2014 #8

@Patrick: Jeg er nok med vilje lidt "farveblind" når det kommer til opdelinger mellem matematikere, økonomer, dataloger, filosoffer og andre som måtte gøre sig i abstrakte virkeligheder. For eksempel synes jeg at fornemme et overvældende overlap mellem matematik, datalogi og økonomi når det kommer til operationsanalyse. Jeg er overbevist om at den eneste forskel er præsentationsformen (i fx lærebøger og artikler).

Mange tak for tilbuddet! Det vil jeg gøre. :)


Patrick Kofod Mogensen

Patrick Kofod Mogensen @ d. 24. december 2014 #9

Det er muligt at der kun er jargon til forskel, men jeg tror nu også målet er forskelligt. Det er dog klart at metoderne er de samme (op til notation), så derfor vil du kunne finde artikler i operation research tidsskrifter, som minder ufattelige meget om artikler i tidsskrifter inden for andre fag. Hvis det sænker diffusionshastigheden er det naturligvis super ærgerligt, og en hvis brobygning ville være smart!


Anders Munk-Nielsen

Anders Munk-Nielsen @ d. 26. december 2014 #10

Beklager min fraværelse, jeg kan se, at der er nogle, der har brugt juleaftens dag mere fornuftigt end mig ;)

Men for at svare dig, Simon, så har jeg også selv læst et enkelt fag på datalogi, da jeg var på udveksling ved Melbourne University (og jeg vil anbefale enhver at tage et enkelt fag - det er udfordrende at være et år bagud, men man accelererer sig igennem en masse ting og kan lære en hel masse af, at sidde i et nyt paradigme lige pludselig).

Jeg havde også om DP i en datalogisk kontekst og legede med The Knapsack Problem, som basalt set svarer til byttepengeproblemet, Simon nævner ovenfor. Man kan lære super meget af den typer af problemer, men jeg har ikke fundet DP metoderne fra datalogi direkte anvendelige i økonomisk forskning. Dog er _tankegangen_ SINDSSYGT anvendelig, og det har gjort mig til en MEGET bedre programmør.

Men for at bakke Patrick "The Boss" Mogensen op, så er slægtskabet bestemt til at pege på i ideen og tilgangen på et metaplan, men de konkrete metoder er vidt forskellige. Måske man får noget mere, hvis man går langt videre i datalogien og i økonomien, men et enkelt kursus var i hvert fald ikke nok.


Tak for din kommentar!
Skriv venligst en kommentar der er længere end 5 tegn

Skriv en kommentar

Log ind for at kommentere - eller opret en bruger