Structural_Modelling_notes.lyx

#LyX 2.3 created this file. For more info see http://www.lyx.org/
\lyxformat 544
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass book
\begin_preamble
\usepackage{babel}
\usepackage{babel}
\usepackage{babel}





  \providecommand{\assumptionname}{Assumption}
  \providecommand{\axiomname}{Axiom}
  \providecommand{\claimname}{Claim}
  \providecommand{\definitionname}{Definition}
  \providecommand{\lemmaname}{Lemma}
  \providecommand{\propositionname}{Proposition}
  \providecommand{\remarkname}{Remark}
\providecommand{\corollaryname}{Corollary}
\providecommand{\theoremname}{Theorem}



  \providecommand{\axiomname}{Axiom}
  \providecommand{\claimname}{Claim}
  \providecommand{\definitionname}{Definition}
  \providecommand{\remarkname}{Remark}
\providecommand{\corollaryname}{Corollary}
\providecommand{\theoremname}{Theorem}
\end_preamble
\use_default_options false
\begin_modules
theorems-ams-bytype
theorems-ams-extended-bytype
\end_modules
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding iso8859-15
\fontencoding default
\font_roman "cmr" "default"
\font_sans "cmss" "default"
\font_typewriter "cmtt" "default"
\font_math "auto" "auto"
\font_default_family rmdefault
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing double
\use_hyperref true
\pdf_bookmarks true
\pdf_bookmarksnumbered false
\pdf_bookmarksopen false
\pdf_bookmarksopenlevel 1
\pdf_breaklinks false
\pdf_pdfborder true
\pdf_colorlinks false
\pdf_backref false
\pdf_pdfusetitle true
\papersize a4paper
\use_geometry true
\use_package amsmath 2
\use_package amssymb 2
\use_package cancel 0
\use_package esint 2
\use_package mathdots 0
\use_package mathtools 0
\use_package mhchem 0
\use_package stackrel 0
\use_package stmaryrd 0
\use_package undertilde 0
\cite_engine natbib
\cite_engine_type authoryear
\biblio_style plainnat
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 0
\use_minted 0
\index Index
\shortcut idx
\color #008000
\end_index
\leftmargin 1.25in
\topmargin 1.25in
\rightmargin 1.25in
\bottommargin 1.25in
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style english
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Title
Computational Economics: Topics on Decision Making
\end_layout

\begin_layout Author
Victor H.
 Aguiar 
\end_layout

\begin_layout Date
This version: January 2024
\end_layout

\begin_layout Part
Parametric Methods
\end_layout

\begin_layout Chapter
Structural Modeling 
\end_layout

\begin_layout Standard
The Cowles Commision defined econometrics as a 
\begin_inset Quotes eld
\end_inset

branch of economics in which economic theory and statistical methods are
 fused in the analysis of numerical and institutional data
\begin_inset Quotes erd
\end_inset

 Hood and Koopmans (1953).
 Econometrics nowadays has a broader definition, but the branch of econometrics
 that combines economic theories with statistical models is called structural
 econometric models.
 
\end_layout

\begin_layout Section
The Gravity Model of Trade
\end_layout

\begin_layout Standard
We will illustrate an instance of structural modeling using an example from
 international trade.
 The gravity model of trade as formalized by Anderson and Van Wincoop (2003)
 is one of the most successful applications of structural modeling.
 The gravity model of trade tries to provide a theoretical explanation of
 the following empirical fact the nominal bilateral trade is directly proportion
al to the mass of the countries and inversely proportional to distance.
 This fact can be generalized to many countries.
\end_layout

\begin_layout Standard
\begin_inset Separator plain
\end_inset


\end_layout

\begin_layout Example
(Theory) Gravity model of trade.
 
\end_layout

\begin_layout Example
We have 
\begin_inset Formula $I$
\end_inset

 countries, with typical elements 
\begin_inset Formula $i,j\in I$
\end_inset

.
 
\end_layout

\begin_layout Example
We assume that each country specializes in the production of only one good.
 The supply of each good is fixed (equivalently, each region is endowed
 with only positive quantity of one good, and there is no production).
 
\end_layout

\begin_layout Example
If 
\begin_inset Formula $c_{ij}$
\end_inset

 is the consumption by country 
\begin_inset Formula $j$
\end_inset

 consumers of goods from region 
\begin_inset Formula $i$
\end_inset

, consumers in region 
\begin_inset Formula $j$
\end_inset

 maximize
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
U_{j}(c)=\left(\sum_{i\in I}\beta_{i}^{(1-\sigma)/\sigma}c_{ij}^{(\sigma-1)/\sigma}\right)^{\sigma/(\sigma-1)},
\]

\end_inset


\end_layout

\begin_layout Example
subject to the budget constraint
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
\sum_{i}p_{ij}c_{ij}=y_{j}.
\]

\end_inset


\end_layout

\begin_layout Example
We have 
\begin_inset Formula $\sigma$
\end_inset

 as the elasticity of substitution between all goods, 
\begin_inset Formula $\beta_{i}$
\end_inset

 is a positive distribution parameter, 
\begin_inset Formula $y_{j}$
\end_inset

 is a regional income of country 
\begin_inset Formula $j$
\end_inset

 consumers, and 
\begin_inset Formula $p_{ij}$
\end_inset

 is the price of region 
\begin_inset Formula $i$
\end_inset

 good for 
\begin_inset Formula $j$
\end_inset

 consumers.
 
\end_layout

\begin_layout Example
Notice that 
\begin_inset Formula $p_{ij}$
\end_inset

 differs per location 
\begin_inset Formula $j$
\end_inset

 due to trade-costs.
 
\end_layout

\begin_layout Example
Let 
\begin_inset Formula $p_{i}$
\end_inset

 denote the exporter's supply price, net of trade costs, and 
\begin_inset Formula $t_{ij}\geq1$
\end_inset

 is the trade cost factor between 
\begin_inset Formula $i,j$
\end_inset

 (when 
\begin_inset Formula $t_{ij}=1$
\end_inset

 then there is free-trade).
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
p_{ij}=p_{i}t_{ij}.
\]

\end_inset


\end_layout

\begin_layout Example
We assume that trade costs are absorbed by the exporter.
 
\end_layout

\begin_layout Example
Formally, we assume that for each good shipped from 
\begin_inset Formula $i$
\end_inset

 to 
\begin_inset Formula $j$
\end_inset

 the exporter bears a costs equal to 
\begin_inset Formula $t_{ij}-1$
\end_inset

 of country 
\begin_inset Formula $i$
\end_inset

 goods.
 The exporter passes on these trade costs to the importer.
 
\end_layout

\begin_layout Example
The nominal value of exports is:
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
x_{ij}=p_{ij}c_{ij}.
\]

\end_inset


\end_layout

\begin_layout Example
Market clearing implies here that in nominal terms endowments are equal
 to aggregate demand:
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
y_{i}=\sum_{j\in I}x_{ij}.
\]

\end_inset


\end_layout

\begin_layout Example
1) Show that the nominal demand for country 
\begin_inset Formula $i$
\end_inset

 goods by country 
\begin_inset Formula $j$
\end_inset

 consumer is:
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
x_{ij}=\left(\frac{\beta_{i}p_{i}t_{ij}}{P_{j}}\right)^{(1-\sigma)}y_{j},
\]

\end_inset


\end_layout

\begin_layout Example
where 
\begin_inset Formula $P_{j}$
\end_inset

 is the consumer price index of 
\begin_inset Formula $j$
\end_inset

, given by 
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
P_{j}=\left[\sum_{i\in I}(\beta_{i}p_{i}t_{ij})^{1-\sigma}\right]^{1/(1-\sigma)}.
\]

\end_inset


\end_layout

\begin_layout Example
Important: I need step-by-step derivation.
 
\end_layout

\begin_layout Example
2) Show, using the nominal market-clearing conditions and the results from
 1) that:
\end_layout

\begin_layout Example
\begin_inset Formula $\beta_{i}p_{i}=\frac{y_{i}^{1/(1-\sigma)}}{(\sum_{j\in I}(t_{ij}/P_{j})^{1-\sigma}y_{j})^{1/(1-\sigma)}}.$
\end_inset


\end_layout

\begin_layout Example
Important: I need step-by-step derivation.
\end_layout

\begin_layout Example
3) Let 
\begin_inset Formula $y^{W}=\sum_{j\in I}y_{j}$
\end_inset

 be the world income, and income share 
\begin_inset Formula $\theta_{j}=y_{j}/y^{W}$
\end_inset

.
 Show that, replacing 
\begin_inset Formula $\beta_{i}p_{i}$
\end_inset

 on the nominal demand, we can obtain:
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
x_{ij}=\frac{y_{i}y_{j}}{y^{W}}\left(\frac{t_{ij}}{\Pi_{i}P_{j}}\right)^{1-\sigma},
\]

\end_inset


\end_layout

\begin_layout Example
where 
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
\Pi_{i}=\left(\sum_{j\in I}(t_{ij}/P_{j})^{1-\sigma}\theta_{j}\right)^{1/(1-\sigma)}.
\]

\end_inset


\end_layout

\begin_layout Example
Important: I need step-by-step derivation.
 
\end_layout

\begin_layout Example
4) Assume that 
\begin_inset Formula $t_{ij}=t_{ji}$
\end_inset

, where trade barriers are symmetric, show that:
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
\Pi_{i}=P_{i}.
\]

\end_inset


\end_layout

\begin_layout Example
Under this condition, we have an implicit solution to the price indexes
 
\begin_inset Formula $P_{i}$
\end_inset

 given by
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
P_{j}^{1-\sigma}=\sum_{i\in I}P_{i}^{\sigma-1}\theta_{i}t_{ij}^{1-\sigma}\forall j,
\]

\end_inset


\end_layout

\begin_layout Example
show that there is at least one solution to this system of equations.
\end_layout

\begin_layout Example
For this part use the file 
\backslash
GitHub
\backslash
Microeconomics1
\backslash
finalexam
\backslash
theory
\backslash
fixedpoint_contraction_mapping_jacobian.pdf, Theorem 1 and Theorem 2.
 In particular, show that the implicit solution to the price index 
\begin_inset Formula $P_{i}$
\end_inset

 for all 
\begin_inset Formula $i\in I$
\end_inset

 for a contraction mapping.
 You can assume that 
\begin_inset Formula $P_{i}$
\end_inset

 take values in a closed set for simplicity.
 Also note that, that you have to rewrite the price index equation in the
 form.
 
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
P_{j}=g_{j}(P_{1},\cdots P_{I}).
\]

\end_inset


\end_layout

\begin_layout Example
For the gravity model 
\begin_inset Formula $g$
\end_inset

 is continuously differentiable, so you can compute it's Jacobian.
 For the computing the norm of the Jacobian use whatever norm makes easier
 your computation.
 Euclidean or Max matrix norms are good candidates.
 I used the Euclidean matrix norm.
 
\end_layout

\begin_layout Example
Important: Only for this item, assume that 
\begin_inset Formula $I=\{1,2\}$
\end_inset

, 
\begin_inset Formula $P_{i}\geq1\forall i$
\end_inset

, 
\begin_inset Formula $\sigma=\frac{1}{2},t_{ij}=1,\theta_{i}=\frac{1}{2}.$
\end_inset

 Remember you have to show that the the norm of the Jacobian of the mapping
 
\begin_inset Formula $g$
\end_inset

 is less than 1, for all values of 
\begin_inset Formula $P_{i}$
\end_inset

.
 
\end_layout

\begin_layout Example
5) Show that, the gravity model implies that there are constants 
\begin_inset Formula $\alpha_{i}\forall i\in I$
\end_inset

, and 
\begin_inset Formula $\rho=(1-\sigma)$
\end_inset

 such that:
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
z_{ij}=logx_{ij}-log(y_{i})-log(y_{j})
\]

\end_inset


\end_layout

\begin_layout Example
\begin_inset Formula 
\[
z_{ij}=-\alpha_{i}-\alpha_{j}+\rho log(t_{ij}).
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Separator plain
\end_inset


\end_layout

\begin_layout Problem
(Programming Part) The results from Problem 1, can be used here even if
 you did not answered correctly to the previous question.
 No need to proof anything here.
 With the previous results, we obtain the gravity system of equations characteri
zing the general equilibrium of trade:
\end_layout

\begin_layout Problem
\begin_inset Formula 
\[
x_{ij}=\frac{y_{i}y_{j}}{y^{w}}\left(\frac{t_{ij}}{P_{i}P_{j}}\right)^{1-\sigma},
\]

\end_inset


\end_layout

\begin_layout Problem
\begin_inset Formula 
\[
P_{j}^{1-\sigma}=\sum_{i\in I}P_{i}^{\sigma-1}\theta_{i}t_{ij}^{1-\sigma}\forall j.
\]

\end_inset


\end_layout

\begin_layout Problem
1) Solve this system of equations in Julia, for the parameters provided
 in the file /GitHub/Microeconomics1/finalexam/programming/gravity_model_paramet
ers.jl or in the /GitHub/Microeconomics1/finalexam/programming/data t.csv,
 y.csv and lxhat.csv files inside this folder.
 Remember for this you have 
\begin_inset Formula $I=\{1,\cdots,30\}$
\end_inset

.
 
\end_layout

\begin_layout Problem
Hint: This is a triangular system of equations.
 The parameters are 
\begin_inset Formula $y_{i},t_{i,j}\forall i,j\in I$
\end_inset

 and 
\begin_inset Formula $\sigma=1/2$
\end_inset

.
 You do not need anything else.
 
\end_layout

\begin_layout Problem
Hint: Say you want to minimize the following function 
\begin_inset Formula $f(z_{1},z_{1}\cdots,z_{I})=\sum_{j=1}^{I}(\sum_{i=1}^{I}z_{i}\theta_{ij})^{2}$
\end_inset

 in JuMP.
 
\end_layout

\begin_layout Problem
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

import JuMP 
\end_layout

\begin_layout Plain Layout

import Ipopt 
\end_layout

\begin_layout Plain Layout

##Read CSV files and DataFrames management.
\end_layout

\begin_layout Plain Layout

I=30
\end_layout

\begin_layout Plain Layout

theta=ones(I,I)
\end_layout

\begin_layout Plain Layout

example=JuMP.Model(Ipopt.Optimizer) 
\end_layout

\begin_layout Plain Layout

JuMP.@variable(example,z[1:I]>=0)
\end_layout

\begin_layout Plain Layout

JuMP.@NLobjective(,Min,sum((sum( x[i]*theta[i,j] for i in 1:I))^2 for j in
 1:I)) 
\end_layout

\begin_layout Plain Layout

JuMP.optimize!(example)
\end_layout

\begin_layout Plain Layout

#get the solution as a vector
\end_layout

\begin_layout Plain Layout

xsol=JuMP.value.(x) 
\end_layout

\begin_layout Plain Layout

 
\end_layout

\end_inset


\end_layout

\begin_layout Problem
2) I will provide a dataset of: (i) perturbed nominal trade flows 
\begin_inset Formula $log\hat{x}_{ij}=logx_{ij}+\epsilon_{ij}$
\end_inset

, where 
\begin_inset Formula $\epsilon_{ij}$
\end_inset

 is a draw of a random distribution that is mean zero and pure measurement
 error (you can assume it is independent from the observable variables),
 (ii) income by country, (iii) bilateral trade barriers.
 
\end_layout

\begin_layout Problem
Using this dataset, estimate 
\begin_inset Formula $\sigma$
\end_inset

.
 
\end_layout

\begin_layout Problem
Hint: Write down in Julia a contrained OLS problem.
 
\end_layout

\begin_layout Problem
In Problem 1 we showed that the gravity model implies that there are constants
 
\begin_inset Formula $\alpha_{i}\forall i\in I$
\end_inset

, and 
\begin_inset Formula $\rho=(1-\sigma)$
\end_inset

 such tat:
\end_layout

\begin_layout Problem
\begin_inset Formula 
\[
z_{ij}=log\hat{x}_{ij}-log(y_{i})-log(y_{j})
\]

\end_inset


\end_layout

\begin_layout Problem
\begin_inset Formula 
\[
z_{ij}=\alpha_{i}-\alpha_{j}+\rho log(t_{ij})+\epsilon_{ij}.
\]

\end_inset


\end_layout

\begin_layout Problem
Estimate the linear equation above using JuMP and Ipopt.
\end_layout

\begin_layout Problem
3) As the file .../parameters.jl indicates 
\begin_inset Formula $\sigma=1/2$
\end_inset

, use this parameter, to simulate a counterfactual of total trade liberalization
 where 
\begin_inset Formula $t_{ij}^{free}=1$
\end_inset

 for all 
\begin_inset Formula $j,i\in I$
\end_inset

.
\end_layout

\begin_layout Problem
Hint: Use part 1).
 Note that you have to solve the model given 
\begin_inset Formula $\sigma$
\end_inset

, the new 
\begin_inset Formula $t_{ij}^{free}$
\end_inset

, and incomes that have not changes 
\begin_inset Formula $y_{i}\forall i$
\end_inset

.
 
\end_layout

\begin_layout Problem
4) 
\end_layout

\begin_layout Standard
\begin_inset Separator plain
\end_inset


\end_layout

\begin_layout Proof
1) See julia file.
 
\end_layout

\begin_layout Proof
2) 
\begin_inset Formula $log\hat{x}_{ij}=log(y_{i})+log(y_{j})-log(y^{W})+(1-\sigma)logt_{ij}-(1-\sigma)logP_{i}-(1-\sigma)logP_{j}+\epsilon_{ij}$
\end_inset


\end_layout

\begin_layout Proof
\begin_inset Formula 
\[
log\hat{x}_{ij}-log(y_{i})-log(y_{j})=\alpha+\beta log(\frac{t_{ij}}{P_{i}P_{j}})+\epsilon_{ij}
\]

\end_inset


\end_layout

\begin_layout Proof
\begin_inset Formula 
\[
z_{ij}=\alpha+\beta[log(t_{ij})-log(P_{i})-log(P_{j})]+\epsilon_{ij}
\]

\end_inset


\end_layout

\begin_layout Proof
st.
 
\end_layout

\begin_layout Proof
\begin_inset Formula 
\[
P_{j}^{\beta}=\sum_{i\in I}P_{i}^{-\beta}\frac{y_{i}}{\alpha}t_{ij}^{\beta}
\]

\end_inset


\end_layout

\begin_layout Section
Understanding Identification and Reduced Form: Supply and Demand.
\end_layout

\begin_layout Standard
Consider a simple market with aggregate demand given by 
\begin_inset Formula $\mathbf{D}=a-bp+\mathbf{u}$
\end_inset

, with the usual convention that bold letters represent random variables.
 Aggregate supply 
\begin_inset Formula $\mathbf{S}=\alpha+\beta p+\mathbf{v}$
\end_inset

 for a given price 
\begin_inset Formula $p$
\end_inset

.
 The analyst only observes price and quantities in equilibrium.
 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mathbf{y}=\frac{a\beta+b\alpha}{b+\beta}+\frac{\beta\mathbf{u}+b\mathbf{v}}{b+\beta}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mathbf{p}=\frac{a-\alpha}{b+\beta}+\frac{\mathbf{u}-\mathbf{v}}{b+\beta}.
\]

\end_inset


\end_layout

\begin_layout Standard
In other words, the analyst observes 
\begin_inset Formula $(\mathbf{y},\mathbf{p})$
\end_inset

.
 
\end_layout

\begin_layout Standard
This is the joint distribution of quantities and prices in equilibrium.
 Say that a naive analyst wants to obtain the structural elasticity of demand,
 
\begin_inset Formula $b$
\end_inset

, from this observation.
 
\end_layout

\begin_layout Standard
He writes down the model:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mathbf{y}=\gamma_{0}+\gamma_{1}\mathbf{p}+\mathbf{e}.
\]

\end_inset


\end_layout

\begin_layout Standard
He thens assumes that 
\begin_inset Formula $E[\mathbf{e}|\mathbf{p]}=0$
\end_inset

.
 Under this we can obtain:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\gamma_{1}=\frac{Cov(\mathbf{y,p})}{Var(\mathbf{p})}=\frac{\beta\sigma_{u}^{2}-b\sigma_{v}^{2}}{\sigma_{u}^{2}+\sigma_{v}^{2}}.
\]

\end_inset


\end_layout

\begin_layout Standard
It is obvious that 
\begin_inset Formula $\gamma_{1}$
\end_inset

 is not equal to 
\begin_inset Formula $\beta$
\end_inset

, in fact it is a weighted average of 
\begin_inset Formula $\beta$
\end_inset

 and 
\begin_inset Formula $b$
\end_inset

 and one cannot recover 
\begin_inset Formula $b$
\end_inset

 from it.
 This is called 
\series bold
simultaneity bias, 
\series default
which is a form of endogeneity.
 What we have witnessed here is a failure of identification due to simultaneity
 bias.
 
\end_layout

\begin_layout Subsection
Moments and Instrumental Variables
\end_layout

\begin_layout Standard
Demand curves and supply curves are identifiable if there is additional
 variation in our observed data.
 For instance consider the model where we break the demand and supply shocks
 into an observed and an unobserved part.
 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mathbf{u}=c_{u}\mathbf{x}_{u}+\mathbf{\epsilon}_{u}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mathbf{v}=c_{v}\mathbf{x}_{v}+\mathbf{\epsilon_{v}}.
\]

\end_inset


\end_layout

\begin_layout Standard
Moreover, we know that 
\begin_inset Formula $Cov(x_{u},\epsilon_{v})=0$
\end_inset

 and 
\begin_inset Formula $Cov(x_{v},\epsilon_{u})=0$
\end_inset

.
 
\end_layout

\begin_layout Standard
Then we can identify 
\begin_inset Formula $b$
\end_inset

 by noting that we have the following moment:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
E[\mathbf{x}_{v}\mathbf{\epsilon_{u}}]=0.
\]

\end_inset


\end_layout

\begin_layout Standard
The IV estimator of 
\begin_inset Formula $b$
\end_inset

 is:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
b^{IV}=\frac{Cov[\mathbf{y}\mathbf{x_{v}}]}{Cov[\mathbf{p}\mathbf{x}_{v}]}
\]

\end_inset


\end_layout

\begin_layout Standard
Note that:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
E[\mathbf{yx}_{v}]=E[\frac{a\beta+b\alpha}{b+\beta}\mathbf{x}_{v}+\frac{\beta\mathbf{u}\mathbf{x_{v}}+b\mathbf{v}\mathbf{x_{v}}}{b+\beta}]=E[\frac{a\beta+b\alpha}{b+\beta}\mathbf{x}_{v}+\frac{b\mathbf{v}\mathbf{x}_{v}}{b+\beta}]
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
E[\mathbf{px_{v}}]=E[\frac{a-\alpha}{b+\beta}\mathbf{x}_{v}+\frac{\mathbf{u}x_{v}-\mathbf{v}\mathbf{x}_{v}}{b+\beta}]=E[\frac{a-\alpha}{b+\beta}\mathbf{x}_{v}+\frac{\mathbf{v}\mathbf{x}_{v}}{b+\beta}]
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
E[\mathbf{y}]E[\mathbf{x_{v}}]=[\frac{a\beta+b\alpha}{b+\beta}\mathbf{x_{v}}],
\]

\end_inset


\end_layout

\begin_layout Standard
with 
\begin_inset Formula $E[\mathbf{u}]=E[\mathbf{v}]=0$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
E[\mathbf{p}]E[\mathbf{x_{v}}]=E[\frac{a-\alpha}{b+\beta}\mathbf{x}_{v}]
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
b^{IV}=\frac{Cov[\mathbf{y}\mathbf{x_{v}}]}{Cov[\mathbf{p}\mathbf{x}_{v}]}=b.
\]

\end_inset


\end_layout

\begin_layout Standard
Note that this is all done at the population level.
 In real life you will get a finite sample and will have to provide sample
 analogues of the the quantities above and will obtain an estimator 
\begin_inset Formula $\hat{b}^{IV}$
\end_inset

, that will converge to 
\begin_inset Formula $b$
\end_inset

 as the sample size goes to infinity (i.e., consistent estimator).
 The short story about this is that identifying structural parameters often
 needs (i) additional exogenous variation, (ii) assuming a functional form,
 (iii) assuming exclusion restrictions.
 Of course, the credibility of your model and your identification will rely
 on how plausible it is that the exclusion restriction holds.
 
\end_layout

\begin_layout Subsection
Two Stages Least Squares
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mathbf{p}=\frac{a-\alpha}{b+\beta}+\frac{\mathbf{u}-\mathbf{v}}{b+\beta}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mathbf{u}=c_{u}\mathbf{x}_{u}+\mathbf{\epsilon}_{u}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mathbf{p}=\frac{a-\alpha}{b+\beta}+\frac{\mathbf{c_{u}\mathbf{x}_{u}+\mathbf{\epsilon}_{u}}-\mathbf{v}}{b+\beta}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mathbf{p}=\frac{a-\alpha}{b+\beta}+\frac{\mathbf{c_{u}}}{b+\beta}\mathbf{x}_{u}+\frac{\mathbf{\epsilon}_{u}-\mathbf{v}}{b+\beta}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
p=\alpha_{1}+\beta_{1}x_{u}+e_{1}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
e_{1}=\frac{\mathbf{\epsilon}_{u}-\mathbf{v}}{b+\beta}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
E[p|x_{u}]=\frac{a-\alpha}{b+\beta}+\frac{\mathbf{c_{u}}}{b+\beta}\mathbf{x}_{u}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
p=E[p|x_{u}]+e_{1}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mathbf{D}=a-bp+\mathbf{u},
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mathbf{D}=a-b[E[p|x_{u}]+\mathbf{e_{1}}]+\mathbf{u},
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mathbf{D}=a-bE[p|x_{u}]+\mathbf{u}+b\mathbf{e}_{1}
\]

\end_inset


\end_layout

\begin_layout Standard
We can estimate 
\begin_inset Formula $b$
\end_inset

 using 
\begin_inset Formula $E[p]$
\end_inset

 versus quantities, 
\begin_inset Formula $D=Y$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
Y=a-bE[p|x_{u}]+e_{2}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
e_{2}=\mathbf{u}+b\mathbf{e}_{1}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
E[e_{2}E[p|x_{u}]]=0,
\]

\end_inset


\end_layout

\begin_layout Standard
by construction.
 
\end_layout

\begin_layout Chapter
BLP
\end_layout

\begin_layout Standard
Berry, Levinshohn and Pakes (Econometrica, 1995) develop a technique for
 empirically analyzing demand and supply in differentiated product markets.
 
\end_layout

\begin_layout Standard
The econometrician observes for each good 
\begin_inset Formula $j$
\end_inset

: 
\begin_inset Formula $(s_{j},p_{j},x_{j},z_{j})$
\end_inset

 market shares, market prices, product attributes and instruments.
 
\end_layout

\begin_layout Section
Theory: Utility and Demand
\end_layout

\begin_layout Standard
Consumer 
\begin_inset Formula $i$
\end_inset

 chooses good 
\begin_inset Formula $j$
\end_inset

 if and only if 
\begin_inset Formula $U(\zeta_{i},p_{j},x_{j},\xi_{j};\theta)\ge U(\zeta_{i},p_{r},x_{r},\xi_{r};\theta)$
\end_inset

 for 
\begin_inset Formula $r=0,1,\cdots,J$
\end_inset

, where alternatives 
\begin_inset Formula $r=1,\cdots,J$
\end_inset

 represent purchases of differentiated products.
 The vector 
\begin_inset Formula $(x,\xi,p)$
\end_inset

 represents the observed product attributes, the unobserved (to the econometrici
an) product attributes, and the product prices.
 
\end_layout

\begin_layout Standard
Let 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
A_{j}=\{\zeta:U(\zeta,p_{j},x_{j},\xi_{j};\theta)\ge U(\zeta,p_{r},x_{r},\xi_{r};\theta)\forall r=0,1,\cdots,J\}
\]

\end_inset


\end_layout

\begin_layout Standard
then market shares are
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
s_{j}(p,x,\xi;\theta)=\int_{\zeta\in A_{j}}P_{0}d(\zeta).
\]

\end_inset


\end_layout

\begin_layout Standard
A special case of this model that we will be interested here is:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
U(\zeta_{i},p_{j},x_{j},\xi_{j};\theta)=x_{j}\beta-\alpha p_{j}+\xi_{j}+\epsilon_{i,j}=\delta_{j}+\epsilon_{i,j},
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\delta_{j}=x_{j}\beta-\alpha p_{j}+\xi_{j},
\]

\end_inset


\end_layout

\begin_layout Standard
The optimal choice is the one where utility is the highest.
 Since there are unobserved variables, all consumers do not make the same
 choice.
 We solve the model for 
\emph on
choice probabilities
\emph default
, which are driven by the distribution of 
\begin_inset Formula $\varepsilon_{ij}$
\end_inset

 and the distribution of 
\begin_inset Formula $\xi_{j}$
\end_inset

.
 If we let these be extreme value distributions, then the choice probabilities
 follow the familiar logit form.
\end_layout

\begin_layout Standard
In particular, suppose that 
\begin_inset Formula $\xi_{j}=0$
\end_inset

 and 
\begin_inset Formula $\varepsilon_{ij}$
\end_inset

 are iid Type-1- Extreme-Value (T1EV) random variates (or suppose that 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $\xi_{j}+\varepsilon_{ij}$
\end_inset

 are iid T1EV) satisfying 
\begin_inset Formula $f(\varepsilon_{ij})=\exp\left(-\exp\left(-\varepsilon_{ij}\right)\right)\exp\left(-\varepsilon_{ij}\right)$
\end_inset

.
 Then, 
\begin_inset Formula 
\[
P[x_{j}=1]=\frac{\exp\left(x_{j}\beta-\alpha p_{j}\right)}{\sum_{k}\exp\left(x_{k}\beta-\alpha p_{k}\right)}.
\]

\end_inset


\end_layout

\begin_layout Standard
If 
\begin_inset Formula $\varepsilon_{ij}$
\end_inset

 is iid (both across products 
\begin_inset Formula $j$
\end_inset

 for a consumer 
\begin_inset Formula $i$
\end_inset

, and across consumers 
\begin_inset Formula $i$
\end_inset

 for a product 
\begin_inset Formula $j$
\end_inset

), then the distribution of a consumer’s preferences over products other
 than the product it bought does not depend on the product they bought.
 The iid assumption comes at some cost.
\end_layout

\begin_layout Standard
McFadden noted a few problems with this model, all due to the iid nature
 of the T1EV errors.
 First, note that we can write the ratio of probabilities for choosing any
 two products 
\begin_inset Formula $j,k$
\end_inset

 as
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula 
\[
\frac{P[x_{j}=1]}{P[x_{k}=1]}=\frac{\exp\left(x_{j}\beta-\alpha p_{j}\right)}{\exp\left(x_{k}\beta-\alpha p_{k}\right)}.
\]

\end_inset

This ratio of probababilities does not depend on the characteristics or
 price of any other good 
\begin_inset Formula $l$
\end_inset

.
 
\end_layout

\begin_layout Standard
Suppose the price of the product you buy rises.
 Then, you may want to switch.
 But, the good you switch to doesn't depend on the good you switched from.
 That is, if for good 
\begin_inset Formula $j$
\end_inset

, you drew 
\begin_inset Formula $\varepsilon_{ij}$
\end_inset

 such that 
\begin_inset Formula $x_{j}\beta-\alpha p_{j}+\varepsilon_{ij}$
\end_inset

 is not the maximum across all goods, then you could switch to any other
 good with a sufficiently large 
\begin_inset Formula $\varepsilon$
\end_inset

.
 In reality, we might think that 
\begin_inset Formula $\varepsilon_{ij}$
\end_inset

 are correlated across goods 
\begin_inset Formula $j$
\end_inset

 for a given person 
\begin_inset Formula $i$
\end_inset

.
 For example, if some cereals are sweet and some not so sweet, you might
 think that some consumers like the sweet ones and others like the not so
 sweet ones.
 In that case, the 
\begin_inset Formula $\varepsilon's$
\end_inset

 would be correlated such that you either draw a bunch of high values for
 sweet and low values for not sweet, or vice versa.
 This would imply that when a person switches from a sweet cereal, they
 switch to a different sweet cereal.
\end_layout

\begin_layout Standard
Suppose 2 products have the same choice probabilities.
 Then, they have the same own-price derivatives, equal to 
\begin_inset Formula $-\gamma s_{j}$
\end_inset

 where 
\begin_inset Formula $s_{j}$
\end_inset

 is the choice probability.
 This means they'd have the same markups (as these are determined in oligopoly
 by demand responses).
\end_layout

\begin_layout Standard
These problems with the iid errors do not disappear if we include the unobserved
 characteristic 
\begin_inset Formula $\xi_{j}$
\end_inset

.
 Rather, these just act like fixed effects in the logit probability expression
 above.
\end_layout

\begin_layout Standard
BLP address these problems by allowing for valuations 
\begin_inset Formula $\beta$
\end_inset

 that vary across consumers.
 Let 
\begin_inset Formula $x_{j}$
\end_inset

 include both observed product characteristics and 
\begin_inset Formula $p_{j}$
\end_inset

, the price of good 
\begin_inset Formula $j$
\end_inset

.
 (That is, let the price be one of the 
\begin_inset Formula $K$
\end_inset

 characteristics.) Let 
\begin_inset Formula $z_{i}$
\end_inset

 and 
\begin_inset Formula $\nu_{i}$
\end_inset

 be a 
\begin_inset Formula $T^{o}-$
\end_inset

vector 
\emph on
observed
\emph default
 consumer characteristics and a 
\begin_inset Formula $T^{u}$
\end_inset

-vector of 
\emph on
unobserved
\emph default
 consumer characteristics.
 Then, let utility be given by
\begin_inset Formula 
\[
U_{ij}=x_{j}\theta_{i}+\xi_{j}+\varepsilon_{ij},
\]

\end_inset

where
\begin_inset Formula 
\[
\theta_{i}=\overline{\theta}+\Theta^{o}z_{i}+\Theta^{u}\nu_{i}.
\]

\end_inset

This expression for utility is identical to the simple form given above
 in that it depends on observed characteristics, price (one of the characteristi
cs now), an unobserved characteristic and an error term.
 Here, 
\begin_inset Formula $\theta_{i}$
\end_inset

 is a 
\begin_inset Formula $K+1-$
\end_inset

vector of parameters (
\begin_inset Formula $K$
\end_inset

 characteristics and 
\begin_inset Formula $1$
\end_inset

 price) that varies across individuals.
 For a consumer with 
\begin_inset Formula $z_{i}=\nu_{i}=0$
\end_inset

, 
\begin_inset Formula $\theta_{i}=\overline{\theta}$
\end_inset

.
 But, for other consumers, the vector 
\begin_inset Formula $\theta_{i}$
\end_inset

 adds the 
\begin_inset Formula $T^{o}-$
\end_inset

vector of observed characteristics 
\begin_inset Formula $z_{i}$
\end_inset

 multiplied by the 
\begin_inset Formula $T^{o}\times\left(K+1\right)$
\end_inset

-matrix of parameters 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $\Theta^{o}$
\end_inset

, and the 
\begin_inset Formula $T^{u}$
\end_inset

-vector of unobserved characteristics
\family default
\series default
\shape default
\size default
\emph default
\bar default
\strikeout default
\uuline default
\uwave default
\noun default
\color inherit
 
\begin_inset Formula $\nu_{i}$
\end_inset

 multiplied by the 
\begin_inset Formula $T^{u}\times\left(K+1\right)$
\end_inset

-matrix of parameters 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $\Theta^{u}$
\end_inset


\family default
\series default
\shape default
\size default
\emph default
\bar default
\strikeout default
\uuline default
\uwave default
\noun default
\color inherit
.
 The unobserved consumer characteristics break the restriction that everyone
 sees every alternative to their good as identical.
\end_layout

\begin_layout Standard
All utilities are relative to that of an outside good (
\begin_inset Formula $U_{i0}$
\end_inset

), so we think of these as 
\begin_inset Quotes eld
\end_inset

utility above the outside good
\begin_inset Quotes erd
\end_inset

.
 Now the assumption of iid 
\begin_inset Formula $\varepsilon_{ij}$
\end_inset

 does not bite so terribly, because we have 
\begin_inset Formula $\Theta^{u}$
\end_inset

 to allow for correlation across equations.
 So, let 
\begin_inset Formula $\varepsilon_{ij}$
\end_inset

 be iid T1EV (so that we get a multinomial logit at the end).
\end_layout

\begin_layout Standard
Now, we want to express this utility function in terms of the bit that is
 easy to deal with, and the hard bits.
 Substituting the valuations above into the utility function, we get
\begin_inset Formula 
\[
U_{ij}=\delta_{j}+x_{j}\Theta^{o}z_{i}+x_{j}\Theta^{u}\nu_{i}+\varepsilon_{ij},
\]

\end_inset

where
\begin_inset Formula 
\[
\delta_{j}=x_{j}\overline{\theta}+\xi_{j}.
\]

\end_inset

At the market level, we are going to have 
\begin_inset Formula $\delta_{j}$
\end_inset

 which are not troublesome because the unobserved characteristic does not
 vary across 
\begin_inset Formula $i$
\end_inset

 and because 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $\overline{\theta}$
\end_inset

 does not vary across 
\begin_inset Formula $i$
\end_inset

.
 However, we do have 2 potentially troublesome terms: the interaction between
 observed product characteristics 
\begin_inset Formula $x$
\end_inset

 and observed consumer characteristics 
\begin_inset Formula $z$
\end_inset

; and the interaction between observed product characteristics 
\begin_inset Formula $x$
\end_inset

 and unobserved consumer characteristics 
\begin_inset Formula $\nu$
\end_inset

.
\end_layout

\begin_layout Section
Estimation of BLP
\end_layout

\begin_layout Standard
Consider the case where we have product x market level data that gives the
 market share of every product in every market (it doesn't need to be a
 balanced panel though).
 Also, assume there exist some instruments 
\begin_inset Formula $w$
\end_inset

 satisfying 
\begin_inset Formula $E[\xi|w]=0$
\end_inset

.
 Since we only observed these data, we obviously do not observe any consumer
 characteristics 
\begin_inset Formula $z$
\end_inset

.
 All are loaded onto the unobserved consumer characteristics 
\begin_inset Formula $\nu$
\end_inset

.
 We assume that we do know the distribution(s) of these consumer characteristics.
\end_layout

\begin_layout Standard
The parameters of the model are 
\begin_inset Formula $\delta,\theta_{2}$
\end_inset

.
 Note that 
\begin_inset Formula $\delta$
\end_inset

 includes 
\begin_inset Formula $\xi$
\end_inset

.
 Let 
\begin_inset Formula $\theta=(\theta_{1},\theta_{2})$
\end_inset

.
 Rename 
\begin_inset Formula 
\[
\delta_{j}=x_{j}'\theta_{1}+\xi_{j}.
\]

\end_inset


\end_layout

\begin_layout Enumerate
If you know 
\begin_inset Formula $\delta,\theta_{2}$
\end_inset

 and the distribution of 
\begin_inset Formula $v$
\end_inset

, you can compute predicted market shares 
\begin_inset Formula $\sigma_{j}$
\end_inset

.
 Conditional on the unobserved consumer characteristics 
\begin_inset Formula $\nu$
\end_inset

, and given a particular parameter vector 
\begin_inset Formula $\delta,\theta_{2}$
\end_inset

, market shares have the logit form 
\begin_inset Formula $\exp(\tau_{j})/1+\sum_{s}\exp(\tau_{s}$
\end_inset

).
 So, we integrate over the distribution of 
\begin_inset Formula $\nu$
\end_inset

 (there are no observed 
\begin_inset Formula $z$
\end_inset

's) to get market shares 
\begin_inset Formula $\sigma_{j}$
\end_inset

:
\begin_inset Formula 
\[
\sigma_{j}(\delta,\theta)=\int\frac{\exp\left(\delta_{j}+\sum_{k}x_{jk}\theta_{2k}\nu_{k}\right)}{1+\sum_{s}\exp\left(\delta_{s}+\sum_{k}x_{jk}\theta_{2k}\nu_{k}\right)}f(\nu)\partial\nu.
\]

\end_inset

Nobody likes integrating.
 Pakes (1986) suggests sampling some 
\begin_inset Formula $\nu$
\end_inset

 from a distribution, and summing:
\begin_inset Formula 
\[
\sigma_{j}(\delta,\theta;P^{ns})=\sum_{r=1}^{ns}\frac{\exp\left(\delta_{j}+\sum_{k}x_{jk}\theta_{2k}\nu_{rk}\right)}{1+\sum_{s}\exp\left(\delta_{s}+\sum_{k}x_{jk}\theta_{2k}\nu_{rk}\right)}.
\]

\end_inset

Here, 
\begin_inset Formula $P^{ns}$
\end_inset

 is a distribution from which you sample 
\begin_inset Formula $s$
\end_inset

 times for each of the 
\begin_inset Formula $n$
\end_inset

 observations in a particular market.
 This gives a vector of 
\begin_inset Formula $\sigma_{j}$
\end_inset

 given 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $\delta,\theta;P^{ns}$
\end_inset

.
 This step requires a distribution 
\begin_inset Formula $P^{ns}$
\end_inset

 to sample from.
 You might choose a normal, e.g..
 Since 
\begin_inset Formula $\delta_{j}$
\end_inset

 has an intercept, your normal could be mean-zero, thus having only a variance
 parameter.
 
\end_layout

\begin_layout Enumerate
Berry (1994) shows that there's only one 
\begin_inset Formula $\delta$
\end_inset

 that goes with any set of market shares and 
\begin_inset Formula $\Theta$
\end_inset

, and that it is a contraction mapping.
 Alternatively put, market shares 
\begin_inset Formula $s_{j}$
\end_inset

 identify 
\begin_inset Formula $\delta_{j}$
\end_inset

 conditional on 
\begin_inset Formula $\Theta$
\end_inset

.
 So, we can solve for 
\begin_inset Formula $\delta$
\end_inset

.
 BLP (1995) show that can be done by iterating the following linear equation
\begin_inset Formula 
\[
\delta_{j}^{new}(\theta)=\delta_{j}^{old}(\theta)+\ln s_{j}-\ln\sigma_{j}(\theta,\delta^{old};P^{ns})
\]

\end_inset

until 
\begin_inset Formula $\sigma_{j}(\delta,\theta;P^{ns})=s_{j}$
\end_inset

 for all 
\begin_inset Formula $j$
\end_inset

.
 This means we can identify 
\begin_inset Formula $\delta$
\end_inset

 given 
\begin_inset Formula $\theta$
\end_inset

, including identification of 
\begin_inset Formula $\xi$
\end_inset

 given 
\begin_inset Formula $\theta$
\end_inset

.
 In particular, with 
\begin_inset Formula $\theta$
\end_inset

 in our pocket and 
\begin_inset Formula $\delta_{j}$
\end_inset

 identified, we can compute 
\begin_inset Formula $\xi_{j}=\delta_{j}-\sum_{k}x_{jk}\theta_{1,k}$
\end_inset

.
 This iteration step would typically use a 
\family sans
\shape slanted
while
\family default
\shape default
 loop in Stata.
\end_layout

\begin_layout Enumerate
Now we use our instruments for 
\begin_inset Formula $\xi$
\end_inset

 to identify 
\begin_inset Formula $\theta_{2}$
\end_inset

.
 Find 
\begin_inset Formula $\theta_{2}$
\end_inset

 that bring 
\begin_inset Formula $\xi$
\end_inset

 as close as possible to orthogonal to instruments 
\begin_inset Formula $w.$
\end_inset

 In particular, one may use GMM for the moment conditions 
\begin_inset Formula $E[\xi|w]=0$
\end_inset

.
 This is not the friendliest GMM, though, because for each value of 
\begin_inset Formula $\theta$
\end_inset

, we have to do step 2 above.
 Luckily, it is canned in the Stata module 
\family sans
\shape slanted
blp
\family default
\shape default
.
 
\end_layout

\begin_layout Enumerate
The GMM requires instruments 
\begin_inset Formula $w$
\end_inset

 that are uncorrelated with unobserved characteristics 
\begin_inset Formula $\xi$
\end_inset

.
 One might well suspect that observed product characteristics 
\begin_inset Formula $x$
\end_inset

 (and consumer characteristics 
\begin_inset Formula $z$
\end_inset

, if used) are thus elements of 
\begin_inset Formula $w$
\end_inset

.
 But are prices 
\begin_inset Formula $p$
\end_inset

 uncorrelated with unobserved characteristics? This seems a far cry.
 One might use supply-side instruments for prices.
 Or, one might model the supply side of the market, e.g., by modeling the
 pricing equations for oligopolistic supply (this would still require instrument
s).
\end_layout

\begin_layout Subsection
Supply Side
\end_layout

\begin_layout Standard
We consider that there are 
\begin_inset Formula $F$
\end_inset

 firms, each producing some subset of goods 
\begin_inset Formula $\mathcal{F}_{f}$
\end_inset

, of the 
\begin_inset Formula $J$
\end_inset

 products.
 The marginal cost of the firm per good 
\begin_inset Formula $j$
\end_inset

 is assumed to be
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
ln(mc_{j})=w_{j}\theta_{3}+\omega_{j},
\]

\end_inset


\end_layout

\begin_layout Standard
where 
\begin_inset Formula $\gamma$
\end_inset

 is a vector of parameters, 
\begin_inset Formula $w_{j},\omega_{j}$
\end_inset

 are observed and unobserved cost characteristics.
 We can allow 
\begin_inset Formula $x_{j}$
\end_inset

 to be part of 
\begin_inset Formula $w_{j}$
\end_inset

 and 
\begin_inset Formula $\omega_{j}$
\end_inset

 to be correlated with 
\begin_inset Formula $\xi_{j}$
\end_inset

.
 
\end_layout

\begin_layout Standard
The firms profit maximize with full knowledge of the behavior of consumers:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\Pi_{f}=\sum_{j\in\mathcal{F}_{j}}(p_{j}-mc_{j})Ms_{j}(p,x,\xi;\theta),
\]

\end_inset


\end_layout

\begin_layout Standard
where 
\begin_inset Formula $mc_{j}$
\end_inset

 is given above.
 Firms can choose prices to maximize its profit given the attributes of
 products and the prices and attributes of competing products.
 
\begin_inset Formula $M$
\end_inset

 denotes the size of the market.
 
\end_layout

\begin_layout Standard
The first order conditions of the profit problem (assumed that it is well
 behaved) are:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
s_{j}(p,x,\xi,\theta)+\sum_{r\in\mathcal{F}_{f}}(p_{r}-mc_{r})\frac{\partial s_{r}(p,x,\xi;\theta)}{\partial p_{j}}=0.
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\Delta_{jr}=\begin{cases}
-\frac{\partial s_{r}}{\partial p_{j}} & \exists f:r,j\in\mathcal{F}_{f}\\
0 & \text{otherwise}
\end{cases}.
\]

\end_inset


\end_layout

\begin_layout Standard
Price-cost markups:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
s(p,x,\xi;\theta)-\Delta(p,x,\xi;\theta)[p-mc]=0
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
p=mc+\Delta(p,x,\xi,\theta)^{-1}s(p,x,\xi;\theta).
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
ln(p-b(p,x,\xi,\theta))=w\theta_{3}+\omega.
\]

\end_inset


\end_layout

\begin_layout Standard
We impose 
\begin_inset Formula $E[\omega|z]=0$
\end_inset

 as well.
 
\end_layout

\begin_layout Section
References
\end_layout

\begin_layout Enumerate
Berry, Steve, 1994, ”Estimating Discrete Choice Models of Product Differentiatio
n,” RAND, vol.
 25, no.
 2, pp.
 242-262.
\end_layout

\begin_layout Enumerate
Berry, S., J.
 Levinsohn and A.
 Pakes, 1995, ”Automobile Prices in Market Equilibrium,” Econometrica, vol.
 63, no.
 4, pp.
 841-890.
\end_layout

\begin_layout Enumerate
Blow, Laura, Browning, Martin and Crawford, Ian.
 2008.
 "Revealed Preference Methods for the Consumer Characteristics Model" Review
 of Economic Studies, vol 75, pp.
 371-389.
\end_layout

\begin_layout Enumerate
Pakes, Ariel, 1986, ”Patents as Options: Some Estimates of the Value of
 Holding European Patent Stocks,” Econometrica, vol.
 54, pp.
 755-784.
\end_layout

\begin_layout Enumerate
Daniel Ackerberg, C.
 Lanier Benkard, Steven Berry, and Ariel Pakes, 2011, 
\begin_inset Quotes eld
\end_inset

Econometric Tools for Analyzing Market Outcomes
\begin_inset Quotes erd
\end_inset

, Handbook Chapter.
\end_layout

\begin_layout Enumerate
McFadden, Daniel, 1974, 
\begin_inset Quotes eld
\end_inset

The measurement of urban travel demand." Journal of public economics 3.4:
 303-328.
\end_layout

\begin_layout Enumerate
McFadden, Daniel, and Paul Zarembka, 1974, "Conditional logit analysis of
 qualitative choice behavior
\begin_inset Quotes erd
\end_inset

 in Frontiers in Econometrics, 105-142.
\end_layout

\begin_layout Part
Nonparametric Methods
\end_layout

\begin_layout Chapter
Entropic Latent Variable Integration via Simulation (ELVIS)
\end_layout

\begin_layout Standard
We consider again a consumer setup.
 
\begin_inset Formula $X=\mathbb{R}_{+}^{K}$
\end_inset

, 
\begin_inset Formula $K=2$
\end_inset

, and 
\begin_inset Formula $T=2$
\end_inset

, with time window 
\begin_inset Formula $\mathcal{T}=\{1,2\}$
\end_inset

.
 Let 
\begin_inset Formula $\mathbf{x}=(\mathbf{p_{t},c_{t}})_{t\in\mathcal{T}}$
\end_inset

 be an observed random vector of consumptions and prices and 
\begin_inset Formula $\mathbf{e}$
\end_inset

 be an unobserved random vector 
\begin_inset Formula $\mathbf{e}=(\mathbf{\alpha,(\lambda_{t})_{t\in\mathcal{T}}},(\mathbf{w}_{t})_{t\in\mathcal{T}})$
\end_inset

.
 Consider a 
\begin_inset Formula $g$
\end_inset

 vector of moments.
 The consumers are assumed to be Cobb-Douglas 
\begin_inset Formula $u(c,\alpha)=c_{1}^{\alpha}+c_{2}^{(1-\alpha)}$
\end_inset

.
 The first -order-conditions (FOC) of this problem given a lagrange multiplier
 
\series bold

\begin_inset Formula $\mathbf{\mathbf{\mathbf{\mathbf{\lambda}}}}=(\mathbf{\lambda}_{t})_{t\in\mathcal{T}}$
\end_inset

 
\series default
supported on 
\begin_inset Formula $\mathbb{R}_{++}$
\end_inset

 are 
\end_layout

\begin_layout Standard
From the Lagrangian 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mathcal{L}=u(c_{1},c_{2},\alpha)+\lambda(p_{1}c_{1}+p_{2}c_{2}-y)
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\nabla u(c,\alpha)=\left[\begin{array}{c}
\partial_{1}u(c_{1},c_{2},\alpha)\\
\partial_{2}u(c_{1},c_{2},\alpha)
\end{array}\right]
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\nabla u(c,\alpha)=\lambda p=\lambda\left[\begin{array}{c}
p_{1}\\
p_{2}
\end{array}\right]
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
g_{A,t,1}(x,e)=1(c_{t,1}-w_{t,1}=(\frac{\lambda_{t}p_{t,1}}{\alpha})^{\frac{1}{\alpha-1}})-1\forall t
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
g_{A,t,2}(x,e)=1(c_{t,2}-w_{t,2}=(\frac{\lambda_{t}p_{t,2}}{1-\alpha})^{-\frac{1}{\alpha}})-1\forall t
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
g_{M,k}(x,e)=w_{t,k}\forall k
\]

\end_inset


\end_layout

\begin_layout Standard
This means that there is a joint distribution 
\begin_inset Formula $\mu\times\pi_{0}$
\end_inset

, for some measure 
\begin_inset Formula $\mu\in\mathcal{P}_{E|X}$
\end_inset

 and 
\begin_inset Formula $\pi_{0}\in\mathcal{P}_{X}$
\end_inset

 the observed measure, over the support of 
\begin_inset Formula $X\times E$
\end_inset

 such that 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mu\times\pi_{0}(\omega\in\Omega:c_{t,1}(\omega)-w_{t,1}(\omega)=(\frac{\lambda_{t}(\omega)p_{t,1}(\omega)}{\alpha(\omega)})^{\frac{1}{\alpha(\omega)-1}})=1\forall t
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mu\times\pi_{0}(\omega\in\Omega:c_{t,1}(\omega)-w_{t,1}(\omega)=(\frac{\lambda_{t}(\omega)p_{t,2}(\omega)}{1-\alpha(\omega)})^{-\frac{1}{\alpha(\omega)}})=1\forall t
\]

\end_inset


\end_layout

\begin_layout Standard
Then the measurement error moment is known and centered around zero:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
E_{\mu\times\pi_{0}}(w_{t,k})=0\forall t,k.
\]

\end_inset


\end_layout

\begin_layout Standard
Collect all these previous moments into the vector of moments 
\begin_inset Formula $g(x,e)$
\end_inset

.
 
\end_layout

\begin_layout Theorem

\series bold
(Schennach, 2014 ECMA and Aguiar and Kashaev 2022 Restud) 
\series default
The following are equivalent.
\end_layout

\begin_layout Theorem
1.
 A random vector 
\begin_inset Formula $\mathbf{x}=(\mathbf{p_{t},c_{t}})_{t\in\mathcal{T}}$
\end_inset

 almost surely satisfies the FOC of CES utility maximization problem under
 centered measurement error under centered measurement error.
 
\end_layout

\begin_layout Theorem
2.
 
\end_layout

\begin_layout Theorem
\begin_inset Formula 
\[
\inf_{\mu\in\mathcal{P}_{E|X}}||E_{\mu\times\pi_{0}}[g(x,e)]||=0.
\]

\end_inset


\end_layout

\begin_layout Theorem
where 
\begin_inset Formula $\pi_{0}\in\mathcal{P}_{X}$
\end_inset

 is the observed distribution of 
\begin_inset Formula $\mathbf{x}$
\end_inset

.
 
\end_layout

\begin_layout Standard
We now define a way to check (2) in a way that is computationally feasible.
 
\end_layout

\begin_layout Definition
(Maximum-entropy moment) 
\end_layout

\begin_layout Definition
\begin_inset Formula 
\[
h(x;\gamma)=\frac{\int_{e\in E|X}g(x,e)\exp(\gamma'g(x,e))d\eta(e|x)}{\int_{e\in E|X}\exp(\gamma'g(x,e)d\eta(e|x)},
\]

\end_inset


\end_layout

\begin_layout Definition
where 
\begin_inset Formula $\gamma\in\mathbb{R}^{k+q}$
\end_inset

 is a nuisance parameter, and 
\begin_inset Formula $\eta\in\mathcal{P}_{E|X}$
\end_inset

 is an arbitrary user-input distribution supported on 
\begin_inset Formula $E|X$
\end_inset

 such that 
\begin_inset Formula $E_{\pi_{0}}[logE_{\eta}[\exp(\gamma'g(x,e))|x]]$
\end_inset

 exists and twice continuously differentiable in 
\begin_inset Formula $\gamma$
\end_inset

 for all 
\begin_inset Formula $\gamma\in\mathbb{R}^{k+q}$
\end_inset

.
 
\end_layout

\begin_layout Definition
Note that 
\end_layout

\begin_layout Definition
\begin_inset Formula 
\[
\{d\eta^{*}(\cdot|x;\gamma)=\frac{\exp(\gamma'g(x,\cdot))d\eta(\cdot|x)}{\int_{e\in E|X}\exp(\gamma'g(x,e))d\eta(e|x)},\gamma\in\mathbb{R}^{k+q}\}
\]

\end_inset


\end_layout

\begin_layout Definition
is a family of exponential conditional probability measures.
 Thus the maximum entropy moment 
\begin_inset Formula $h$
\end_inset

 is the marginal moment of the function 
\begin_inset Formula $g$
\end_inset

, at which the latent variable has been integrated out using one of the
 members from the above exponential family.
 We call this the Elvis distribution.
\end_layout

\begin_layout Definition
The importance of this distribution is:
\end_layout

\begin_layout Theorem

\series bold
Theorem.
 
\series default
The following are equivalent:
\end_layout

\begin_layout Theorem
1.
 A random vector 
\begin_inset Formula $\mathbf{x}=(\mathbf{p_{t},c_{t}})_{t\in\mathcal{T}}$
\end_inset

 almost surely satisfies the FOC of CES utility maximization problem under
 centered measurement error.
 
\end_layout

\begin_layout Theorem
2.
 
\begin_inset Formula 
\[
\inf_{\gamma\in\mathbb{R}^{k+q}}||E_{\pi_{0}}[h(x;\gamma)]||=0
\]

\end_inset


\end_layout

\begin_layout Theorem
where 
\begin_inset Formula $\pi_{0}\in\mathcal{P}_{X}$
\end_inset

 is the observed distribution over 
\series bold

\begin_inset Formula $x$
\end_inset


\series default
.
 
\end_layout

\begin_layout Standard
The idea or intuition behind this theorem is that there exists a distribution
 that satisfies the moment conditions, then there must be a distribution
 in the family of Elvis distributions, and satisfies the same moment conditions.
 This is a finite problem after we have computed the integral with respect
 to the Elvis distribution for a fixed 
\begin_inset Formula $\gamma$
\end_inset

 parameter.
 
\end_layout

\begin_layout Standard
In Aguiar and Kashaev (AK 2022) we use the following 
\begin_inset Formula $\eta$
\end_inset

 that satisfies all the requirements for the theorem to work: 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\eta(e|x)\propto\exp(-||g_{M}(x,e)||^{2})[1(c_{t,1}-w_{t,1}=(\frac{\lambda_{t}p_{t,1}}{\alpha})^{\frac{1}{\alpha-1}})-1\forall t][1(c_{t,2}-w_{t,2}=(\frac{\lambda_{t}p_{t,2}}{1-\alpha})^{-\frac{1}{\alpha}})-1\forall t].
\]

\end_inset


\end_layout

\begin_layout Standard
Note that we have included the moments of the model 
\begin_inset Formula $g_{A}$
\end_inset

 as a support constraint on 
\begin_inset Formula $\eta$
\end_inset

, and the only the moment 
\begin_inset Formula $g_{M}$
\end_inset

 is used in the density.
 
\end_layout

\begin_layout Section
Simulated GMM and Testing
\end_layout

\begin_layout Standard
The data is 
\begin_inset Formula $\{x_{i}\}_{i=1}^{n}=\{(p_{t,i},c_{t,i})_{t\in\mathcal{T}}\}_{i=1}^{n}$
\end_inset

 where 
\begin_inset Formula $n$
\end_inset

 is the sample size.
 The sample analogue of 
\begin_inset Formula $h$
\end_inset

 is 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\hat{h}_{M}(\gamma)=\frac{1}{n}\sum_{i=1}^{n}h_{M}(x_{i},\gamma)
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\hat{\Omega}(\gamma)=\frac{1}{n}\sum_{i=1}^{n}h_{M}(x_{i},\gamma)h_{M}(x_{i},\gamma)'-\hat{h}_{M}(\gamma)\hat{h}_{M}(\gamma)'.
\]

\end_inset


\end_layout

\begin_layout Standard
We let 
\begin_inset Formula $\Omega^{-}$
\end_inset

 be the generalized inverse of matrix 
\begin_inset Formula $\Omega$
\end_inset

.
 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
TS_{n}=n\inf_{\gamma\in\mathbb{R}^{q}}\hat{h}_{M}(\gamma)\hat{\Omega}^{-}(\gamma)\hat{h}_{M}(\gamma).
\]

\end_inset


\end_layout

\begin_layout Standard
We assume that 
\begin_inset Formula $\{x_{i}\}_{i=1}^{n}$
\end_inset

 is i.i.d.
 
\end_layout

\begin_layout Theorem
Suppose 
\begin_inset Formula $\{x_{i}\}_{i=1}^{n}$
\end_inset

 is i.i.d.
 and the previous assumptions hold then under the null that the data is
 rationalizable it follows that
\end_layout

\begin_layout Theorem
\begin_inset Formula 
\[
lim_{n\rightarrow\infty}Pr(TS_{n}>\chi_{q,1-\alpha}^{2})\leq\alpha
\]

\end_inset


\end_layout

\begin_layout Theorem
for every 
\begin_inset Formula $\alpha\in(0,1)$
\end_inset

.
 
\end_layout

\begin_layout Theorem
If moreover the minimal eigenvalue of the variance matrix 
\begin_inset Formula $V[h_{M}(x,\gamma)]$
\end_inset

 is uniformly, in 
\begin_inset Formula $\gamma$
\end_inset

, bounded away from zero and its maximal eigenvalue is uniformly, in 
\begin_inset Formula $\gamma$
\end_inset

, bounded from above, then under the alternative hypothesis that the data
 is not approximately consistent with rationalizability, it follows that
\end_layout

\begin_layout Theorem
\begin_inset Formula 
\[
lim_{n\rightarrow\infty}P(TS_{n}>\chi_{q,1-\alpha})=1.
\]

\end_inset


\end_layout

\begin_layout Standard
Now we can do some recoverability of parameters of interests by test-inversion.
 
\end_layout

\begin_layout Standard
The 
\begin_inset Formula $(1-\alpha)$
\end_inset

-confidence set for 
\begin_inset Formula $\theta_{0}$
\end_inset

 is
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\{\theta_{0}\in\Theta:TS_{n}(\theta_{0})\leq\chi_{q_{ext},1-\alpha}^{2}\}.
\]

\end_inset


\end_layout

\begin_layout Standard
Note that 
\begin_inset Formula $q_{ext}=q+d$
\end_inset

 where 
\begin_inset Formula $d$
\end_inset

 is the number of new parameters introduced in the problem.
 
\end_layout

\begin_layout Section
Alternatives to ELVIS: Support approaches (Li and Potoms and DeMuynck: Testing
 revealed preference models with unobserved randomness: a column generation
 approach).
 
\end_layout

\begin_layout Standard
Observables in 
\begin_inset Formula $y$
\end_inset

 with support 
\begin_inset Formula $\mathcal{Y}\subseteq\mathbb{R}^{d_{Y}}$
\end_inset

.
 Unobservables are collected in 
\begin_inset Formula $u$
\end_inset

 with support 
\begin_inset Formula $\mathcal{U}\subseteq\mathbb{R}^{d_{U}}$
\end_inset

.
 The unknown joint distribution over observables and unobservables 
\begin_inset Formula $(y,u)$
\end_inset

 is 
\begin_inset Formula $\mu$
\end_inset

 on some measure space 
\begin_inset Formula $(\mathcal{Y}\times\mathcal{U},\mathcal{B})$
\end_inset

 where 
\begin_inset Formula $\mathcal{B}$
\end_inset

 is the Borel 
\begin_inset Formula $\sigma$
\end_inset

-algebra on 
\begin_inset Formula $\mathcal{Y}\times\mathcal{U}\subseteq\mathbb{R}^{d_{U}+d_{Y}}$
\end_inset

.
 
\end_layout

\begin_layout Definition
A model consists of a tuple 
\begin_inset Formula $(\mu_{Y},\Gamma,f,\alpha)$
\end_inset

, where 
\end_layout

\begin_layout Itemize
\begin_inset Formula $\mu_{Y}$
\end_inset

 is the marginal probability measure with respect to observables, 
\end_layout

\begin_layout Itemize
\begin_inset Formula $\Gamma\subseteq\mathcal{Y}\times\mathcal{U}$
\end_inset

 is a 
\begin_inset Formula $\mathcal{B}$
\end_inset

-measurable set that gives all combinations 
\begin_inset Formula $(y,u)\in\mathcal{Y}\times\mathcal{U}$
\end_inset

 that are consistent with the economic model.
 
\end_layout

\begin_layout Itemize
\begin_inset Formula $f:\mathcal{Y}\times\mathcal{U}\to\mathbb{R}^{K}$
\end_inset

 gives a vector of measurable functions 
\begin_inset Formula $f=(f^{1},\cdots,f^{K})$
\end_inset

 that govern the moment conditions imposed by the economic model 
\end_layout

\begin_layout Itemize
\begin_inset Formula $\alpha=(\alpha^{1},\cdots,\alpha^{K})\in\mathbb{R}^{K}$
\end_inset

 is a 
\begin_inset Formula $K$
\end_inset

-dimensional vector of moment values for these functions.
 
\end_layout

\begin_layout Standard
The marginal distribution 
\begin_inset Formula $\mu_{Y}$
\end_inset

 corresponds with the joint
\end_layout

\begin_layout Standard
\begin_inset Formula 
\begin{equation}
\mu_{Y}(A)=\mu(A\times\mathcal{U}).
\end{equation}

\end_inset


\end_layout

\begin_layout Standard
We know that 
\begin_inset Formula $\Gamma$
\end_inset

 encompasses all possible values of 
\begin_inset Formula $(y,u)$
\end_inset

 that can arise in the model 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\begin{equation}
\mu(\Gamma)=1.
\end{equation}

\end_inset


\end_layout

\begin_layout Standard
Also the moment conditions are taken with respect to 
\begin_inset Formula $\mu$
\end_inset

 and the support 
\begin_inset Formula $\Gamma$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
E_{\mu}f^{k}=\int_{\Gamma}f^{k}(y,u)d\mu=\alpha^{k}.
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\begin{equation}
E_{\mu}f=\alpha.
\end{equation}

\end_inset


\end_layout

\begin_layout Standard
The problem is to find a 
\begin_inset Formula $\mu$
\end_inset

 is any such that 1-3 hold.
 
\end_layout

\begin_layout Standard
Now define 
\begin_inset Formula $\mathcal{H}(\mu_{Y},\Gamma)$
\end_inset

 as the collection of all feasible distributions 
\begin_inset Formula $\mu$
\end_inset

 such that 1-2.
 Define the correspondence 
\begin_inset Formula $F:\mathcal{Y}\rightrightarrows\mathbb{R}^{K}$
\end_inset

:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
F(y)=\{f(y,u):(y,u)\in\Gamma\}.
\]

\end_inset


\end_layout

\begin_layout Standard
Note that since 
\begin_inset Formula $y$
\end_inset

 is random 
\begin_inset Formula $F(y)$
\end_inset

 is a random set with support on subsets of 
\begin_inset Formula $\mathbb{R}^{K}$
\end_inset

.
 
\end_layout

\begin_layout Assumption*
(PD-2) (i) The sets 
\begin_inset Formula $F(y)$
\end_inset

 are closed 
\begin_inset Formula $\mu_{Y}-a.s.$
\end_inset

 (ii) There is a measurable function 
\begin_inset Formula $g(y)$
\end_inset

 that only depends on 
\begin_inset Formula $y$
\end_inset

 such that 
\begin_inset Formula $E_{\mu}g(y)<\infty$
\end_inset

 and: 
\begin_inset Formula $g(y)\geq\sup_{(y,u)\in\Gamma}||f(y,u)||$
\end_inset

 
\begin_inset Formula $\mu_{Y}-a.s.$
\end_inset

.
\end_layout

\begin_layout Standard
The problem can be rewritten as 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\min_{\mu\in\mathcal{H}(\mu_{Y},\Gamma)}E_{\mu}||f(y,u)-\alpha||=0,
\]

\end_inset


\end_layout

\begin_layout Standard
where 
\begin_inset Formula $||\cdot||$
\end_inset

 is the Euclidean norm in 
\begin_inset Formula $\mathbb{R}^{K}$
\end_inset

.
 
\end_layout

\begin_layout Standard
We define a support function.
 For a compact set 
\begin_inset Formula $A\subseteq\mathbb{R}^{K}$
\end_inset

, the support function of 
\begin_inset Formula $A$
\end_inset

, 
\begin_inset Formula $h_{A}:\mathbb{R}^{K}\to\mathbb{R}$
\end_inset

 is given by:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
h_{A}(\lambda)=\sup_{x\in A}<\lambda,x>,
\]

\end_inset


\end_layout

\begin_layout Standard
where 
\begin_inset Formula $<\cdot,\cdot>$
\end_inset

 denotes the inner product.
 Let 
\begin_inset Formula $co(A)$
\end_inset

 be convex hull of 
\begin_inset Formula $A$
\end_inset

 and 
\begin_inset Formula $\overline{co}(A)$
\end_inset

 the convex, closed closure of 
\begin_inset Formula $A$
\end_inset

.
 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\overline{co}(A)=\{x\in\mathbb{R}^{K}:\forall\lambda\in\mathbb{S}^{K},<\lambda,x>\leq h_{A}(\lambda)\},
\]

\end_inset


\end_layout

\begin_layout Standard
where 
\begin_inset Formula $\mathbb{S}^{K}=\{\lambda\in\mathbb{R}^{K}:||\lambda||=1\}$
\end_inset

is the 
\begin_inset Formula $K-1$
\end_inset

 dimensional unit simplex.
 
\end_layout

\begin_layout Standard
If (3) is satisfied then by linearity of the expectation:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
E_{\mu}<\lambda,f(y,u)>=<\lambda,\alpha>\forall\lambda\in\mathbb{S}^{K}.
\]

\end_inset


\end_layout

\begin_layout Standard
Now by (2)
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mu(\{(y,u)\in\Gamma:<\lambda,f(y,u)>\leq h_{F(y)}(\lambda)\})=1,
\]

\end_inset


\end_layout

\begin_layout Standard
combining the conditions above we obtain
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
E_{\mu}[h_{F(y)}(\lambda)]\geq E_{\mu}<\lambda,f(y,u)>=<\lambda,\alpha>\forall\lambda\in\mathbb{S}^{K}.
\]

\end_inset


\end_layout

\begin_layout Standard
Notice that
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
E_{\mu}[h_{F(y)}(\lambda)]=E_{\mu_{Y}}[h_{F(y)}(\lambda)],
\]

\end_inset


\end_layout

\begin_layout Standard
then
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
E_{\mu_{Y}}[h_{F(y)}(\lambda)]\geq<\lambda,\alpha>\forall\lambda\in\mathbb{S}^{K}.
\]

\end_inset


\end_layout

\begin_layout Theorem*
(Li-3) If Assumption PT-2 holds, then 
\begin_inset Formula $\min_{\mu\in\mathcal{H}(\mu_{Y},\Gamma)}E_{\mu}||f(y,u)-\alpha||=0,$
\end_inset

 holds iff 
\end_layout

\begin_layout Theorem*
\begin_inset Formula 
\[
\inf_{\lambda\in\mathbb{S}^{K}}E_{\mu_{Y}}[h_{F(y)}(\lambda)-<\lambda,\alpha>]\geq0.
\]

\end_inset


\end_layout

\begin_layout Standard
This is an alternative to ELVIS and characterizes the sharp identified regions
 for partially identified econometric models.
 
\end_layout

\begin_layout Chapter
Finite Mixture Models, Random Utility Model, Bootstrapping
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $X$
\end_inset

 be an abstract grand choice set.
 Let 
\begin_inset Formula $\mathcal{B}$
\end_inset

 a collection of measurable Borel subsets of 
\begin_inset Formula $X$
\end_inset

.
 Let 
\begin_inset Formula $j\in J$
\end_inset

 index one of all choice 
\begin_inset Formula $|J|$
\end_inset

 sets 
\begin_inset Formula $C_{j}\in2^{X}\setminus\emptyset$
\end_inset

.
 Let 
\begin_inset Formula $P_{j}$
\end_inset

 be a probability measure over 
\begin_inset Formula $\mathcal{B}$
\end_inset

.
 Many models of choice in economics can be written as 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
P_{j}(A)=\int f(A|\alpha)d\mu(\alpha)\quad\forall j\in J.
\]

\end_inset


\end_layout

\begin_layout Standard
Where 
\begin_inset Formula $f(A|\alpha)$
\end_inset

 is a prediction of choice conditional on a behavioral model 
\begin_inset Formula $\alpha$
\end_inset

 and 
\begin_inset Formula $\mu$
\end_inset

 is a measure of all behavioral models.
 
\end_layout

\begin_layout Standard

\series bold
Random Utility Model.
 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\alpha=u,u:X\to\mathbb{R}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
f(A|u)=1(argmax_{y\in C_{j}}u(y)\in A)
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
P_{j}(A)=\int1(argmax_{y\in C_{j}}u(y)\in A)d\mu(u).
\]

\end_inset


\end_layout

\begin_layout Standard
This model is complex because the space of utilities is infinite dimensional.
 Also we are considering all elements in 
\begin_inset Formula $\mathcal{B}$
\end_inset

 which is a large collections of sets.
 We have to simplify the problem.
 
\end_layout

\begin_layout Subsection
Finite 
\begin_inset Formula $X$
\end_inset

 and no indifference.
 
\end_layout

\begin_layout Standard
If 
\begin_inset Formula $X$
\end_inset

 is finite then we can let 
\begin_inset Formula $\mathcal{B}$
\end_inset

 to be all singletons.
 For instance, 
\begin_inset Formula $X=\{a,b,c\}$
\end_inset

 then 
\begin_inset Formula $\mathcal{B}=\{\{a\},\{b\},\{c\}\}$
\end_inset

.
 Also, notice that the collection of utilities will map to 
\begin_inset Formula $|X|!$
\end_inset

 linear rankings if we rule out indifference.
 In terms of utilities we require 
\begin_inset Formula $\mu(u:u\quad\text{is injective})=1$
\end_inset

.
 For the running example we have:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\begin{array}{c}
\succ^{1}:a\succ^{1}b\succ^{1}c\\
\succ^{2}:a\succ^{2}c\succ^{2}b\\
\succ^{3}:b\succ^{3}a\succ^{3}c\\
\succ^{4}:b\succ^{4}c\succ^{4}a\\
\succ^{5}:c\succ^{5}a\succ^{5}b\\
\succ^{6}:c\succ^{6}b\succ^{6}a
\end{array}.
\]

\end_inset


\end_layout

\begin_layout Standard
This means that we have mapped the infinite collection of utilities to 
\begin_inset Formula $6$
\end_inset

 rankings over 
\begin_inset Formula $X=\{a,b,c\}$
\end_inset

.
 There is no loss of generality here!
\end_layout

\begin_layout Standard
Now we can write the mixture problem as:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\rho_{j}(a)=P_{j}(\{a\})=\sum_{\succ\in\mathcal{R}}\mu^{*}(\succ)1(a\succ b\forall b\in C_{j}\setminus\{a\}),
\]

\end_inset


\end_layout

\begin_layout Standard
where 
\begin_inset Formula $\mathcal{R}\subseteq X\times X$
\end_inset

 is the set of linear orders/strict preferences on 
\begin_inset Formula $X$
\end_inset

, 
\begin_inset Formula $\mu^{*}\in\Delta(\mathbb{\mathcal{R}})$
\end_inset

, 
\begin_inset Formula $\mu^{*}(\succ)\geq0$
\end_inset

 and 
\begin_inset Formula $\sum_{\succ\in\mathcal{R}}\mu^{*}(\succ)=1$
\end_inset

.
\end_layout

\begin_layout Standard
After discretization, without loss of generality, we can write 
\begin_inset Formula $\rho_{j}\in\Delta(C_{j})$
\end_inset

 and 
\begin_inset Formula $\rho=(\rho_{j})_{j\in J}$
\end_inset

.
 Then we can write down
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\rho=A\mu^{*},
\]

\end_inset


\end_layout

\begin_layout Standard
where 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
A=\begin{array}{c}
\\
a,\{a,b\}\\
b,\{a,b\}\\
b,\{b,c\}\\
c,\{b,c\}\\
a,\{a,c\}\\
c,\{a,c\}\\
a,\{a,b,c\}\\
b,\{a,b,c\}\\
c,\{a,b,c\}
\end{array}\left[\begin{array}{cccccc}
\succ^{1} & \succ^{2} & \succ^{3} & \succ^{4} & \succ^{5} & \succ^{6}\\
1 & 1 & 0 & 0 & 1 & 0\\
0 & 0 & 1 & 1 & 0 & 1\\
1 & 0 & 1 & 1 & 0 & 0\\
0 & 1 & 0 & 0 & 1 & 1\\
1 & 1 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 1 & 1\\
1 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 1
\end{array}\right]
\]

\end_inset


\end_layout

\begin_layout Subsection
(Kitamura Stoye) 
\begin_inset Formula $X=\mathbb{R}_{+}^{L}$
\end_inset

 and linear budgets.
 
\end_layout

\begin_layout Standard
We let 
\begin_inset Formula $X=\mathbb{R}_{+}^{L}$
\end_inset

 and 
\begin_inset Formula $C_{j}=B_{j}=\{x\in X:p_{j}'x\leq w_{j}\}$
\end_inset

 for simplicity we can set 
\begin_inset Formula $w_{j}=1$
\end_inset

 for all 
\begin_inset Formula $j\in J$
\end_inset

.
 We also let 
\begin_inset Formula $U$
\end_inset

 be the set of all 
\begin_inset Formula $u:X\to\mathbb{R}$
\end_inset

 that are strictly (quasi)concave, continuous and monotone.
 We let 
\begin_inset Formula $O$
\end_inset

 be an element of the set of all Borel measurable sets on 
\begin_inset Formula $X$
\end_inset

.
 That means that 
\begin_inset Formula $\mu$
\end_inset

 a measure on 
\begin_inset Formula $U$
\end_inset

 produces choice
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
P_{j}(O)=\int1(argmax_{y\in B_{j}}u(y)\in O)d\mu(u).
\]

\end_inset


\end_layout

\begin_layout Standard
We will discretize the problem.
 First notice that because of monotonicity choices will be on the budget
 lines with probability 
\begin_inset Formula $1$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename figures/KSpatches.png
	lyxscale 60
	scale 60

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Patches
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
Patches are the 
\series bold
coarsest partition
\series default
 of intersecting budgets in a time period (
\begin_inset Formula $I_{j}$
\end_inset

 collects those patches): 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\rho(x_{i|j})=P_{j}(x_{i|j}).
\]

\end_inset


\end_layout

\begin_layout Standard
We then let 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\rho=(\rho(x_{i|j})_{i\in I_{j},j\in J}).
\]

\end_inset


\end_layout

\begin_layout Standard
We then need to obtain the rational demand types:
\end_layout

\begin_layout Standard
\begin_inset Wrap table
lines 0
placement o
overhang 0col%
width "50col%"
status open

\begin_layout Plain Layout
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="5">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $B_{1}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $B_{2}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
rational
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Type 1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\theta(1,1)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x_{1|1}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x_{1|2}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
yes
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Type 2
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\theta(1,2)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x_{1|1}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x_{2|2}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
yes
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Type 3
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\theta(2,2)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x_{2|1}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x_{2|2}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
yes
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Type 4
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\theta(2,1)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x_{2|1}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $x_{1|2}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
no
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Rational Types.
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
WLG, we focus on representative elements of patches (Kitamura and Stoye,
 2018; henceforth KS).
 
\begin_inset Formula $(x_{i|j}^{*}\in x_{i|j}$
\end_inset

).
 Discretization without loss! This has to be proven but we won't do it here.
 
\end_layout

\begin_layout Standard
We then define 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\rho=A\nu
\]

\end_inset


\end_layout

\begin_layout Standard
for 
\begin_inset Formula $\nu\in\Delta(\Theta)$
\end_inset

 where 
\begin_inset Formula $\Theta$
\end_inset

 is the set of demand types.
 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
A=\begin{array}{c}
\\
x_{1|1}\\
x_{2|1}\\
x_{1|2}\\
x_{2|2}
\end{array}\left[\begin{array}{ccc}
\theta(1,1) & \theta(1,2) & \theta(2,2)\\
1 & 1 & 0\\
0 & 0 & 1\\
1 & 0 & 0\\
0 & 1 & 1
\end{array}\right].
\]

\end_inset


\end_layout

\begin_layout Subsection
Statistical Assumptions
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mu_{j}(\alpha)=\mu(\alpha)
\]

\end_inset


\end_layout

\begin_layout Standard
for all 
\begin_inset Formula $j\in J$
\end_inset

.
 This is an exclusion-restriction that says that the distribution of 
\begin_inset Formula $\alpha$
\end_inset

 is independent of the choice situation.
 In the case of RUM this assumption was imposed by McFadden-Richter and
 essentially says that the distribution of utilities is independent from
 budgets:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mu_{j}(u)=\mu(u).
\]

\end_inset


\end_layout

\begin_layout Standard
In experimental datasets this assumptions can hold by design.
 The reason is that budgets can be exogenously varied and they will be independe
nt of preferences.
 In reality this assumption may be broken in survey data where different
 individuals may have preferences (e.g., risk aversion parameter) that is
 correlated with income.
 We will have to deal with this using techniques that can 
\begin_inset Quotes eld
\end_inset

fix
\begin_inset Quotes erd
\end_inset

 this form of endogeneity.
 After discretization we can write down a discrete type space 
\begin_inset Formula $\mathcal{R}$
\end_inset

 that is finite and a discrete number of outcomes 
\begin_inset Formula $x_{k|j}$
\end_inset

 for 
\begin_inset Formula $k=1,\cdots,K_{j}$
\end_inset

, such that 
\begin_inset Formula $a_{k|j}\in C_{j}$
\end_inset

.
 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\rho_{j}(x_{k|j})=\rho(x_{k|j}).
\]

\end_inset


\end_layout

\begin_layout Standard
Then let 
\begin_inset Formula $\rho=(\rho(x_{k|j})_{k\in K_{j},j\in J})$
\end_inset

 and we define 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\rho(x_{k|j})=\sum_{r\in\mathcal{R}}\nu(r)f(x_{k|j}|\phi(r)).
\]

\end_inset


\end_layout

\begin_layout Standard
The key is that for each 
\begin_inset Formula $\alpha\in\mathcal{A}$
\end_inset

 there exists an 
\begin_inset Formula $r\in\mathcal{R}$
\end_inset

 such that 
\begin_inset Formula $f(x_{k|j}|\alpha)=f(x_{k|j}|\phi(r))$
\end_inset

.
 Many 
\begin_inset Formula $\alpha$
\end_inset

's map to a single 
\begin_inset Formula $r$
\end_inset

 and there is no 
\begin_inset Formula $\alpha$
\end_inset

 that cannot be mapped to some 
\begin_inset Formula $r\in\mathcal{R}$
\end_inset

.
 We can then always build a matrix as in the previous examples 
\begin_inset Formula $A_{k|j;r}=f(x_{k|j}|\phi(r)).$
\end_inset


\end_layout

\begin_layout Theorem
The following are equivalent:
\end_layout

\begin_layout Theorem
(i) 
\begin_inset Formula $P$
\end_inset

 is consistent with a mixture 
\begin_inset Formula $P_{j}(A)=\int f(A|\alpha)d\mu(\alpha)$
\end_inset

.
\end_layout

\begin_layout Theorem
(ii) 
\begin_inset Formula $P$
\end_inset

 with vector representation 
\begin_inset Formula $\rho$
\end_inset

 is such that 
\begin_inset Formula $\rho=A\nu$
\end_inset

 for some 
\begin_inset Formula $\nu\in\Delta(\mathcal{R})$
\end_inset

.
 
\end_layout

\begin_layout Subsection
Testing
\end_layout

\begin_layout Standard
In reality we do not observe 
\begin_inset Formula $P_{j}$
\end_inset

, in fact we can only estimate 
\begin_inset Formula $\rho$
\end_inset

 the discrete counterpart in most situations.
 As we observed in the previous part, we can focus in many instances on
 the discretized problem without loss of generality.
 We collect choices from budgets from a population then 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\hat{\rho}_{j}(a)=\hat{\rho}_{j,n}(a)=\frac{1}{N_{j}}\sum_{i=1}^{N_{j}}1(a=c_{i}(C_{j})),
\]

\end_inset


\end_layout

\begin_layout Standard
where 
\begin_inset Formula $c_{i}(C_{j})$
\end_inset

 is the observed choice of individual 
\begin_inset Formula $i$
\end_inset

 from 
\begin_inset Formula $C_{j}$
\end_inset

.
 
\end_layout

\begin_layout Standard
In general we are assuming 
\begin_inset Formula $c_{i}(C_{j})$
\end_inset

 are i.i.d.
 Under that we can apply the law of large numbers to conclude that:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\lim_{n\rightarrow\infty}\hat{\rho}_{j,n}(a)=\rho_{j}(a).
\]

\end_inset


\end_layout

\begin_layout Standard
Notice that even if 
\begin_inset Formula $\rho$
\end_inset

 is consistent with a finite mixture its finite sample analogue 
\begin_inset Formula $\hat{\rho}$
\end_inset

 may be such that there is no 
\begin_inset Formula $\nu\in\Delta(\mathcal{R})$
\end_inset

 such that
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\hat{\rho}=A\nu.
\]

\end_inset


\end_layout

\begin_layout Standard
The reason is that 
\begin_inset Formula $\rho-\hat{\rho}=\epsilon$
\end_inset

 that is not zero in general.
\end_layout

\begin_layout Standard
The null hypothesis is stated formally as:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
H_{0}:\exists\nu\geq0,A\nu=\rho.
\]

\end_inset


\end_layout

\begin_layout Standard
Notice that without loss of generality we have not searched over 
\begin_inset Formula $\nu\in\Delta(\mathcal{R})$
\end_inset

 but only over the convex cone 
\begin_inset Formula $\mathcal{C}=\{z:A\nu=z,\nu\geq0\}$
\end_inset

.
 Alternatively, we can write down the null as:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
H_{0}:\rho\in\mathcal{C}.
\]

\end_inset


\end_layout

\begin_layout Standard
In particular, this is equivalent to testing:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
H_{0}:\min_{\eta\in\mathcal{C}}[\rho-\eta]'\Omega[\rho-\eta]=0,
\]

\end_inset


\end_layout

\begin_layout Standard
for 
\begin_inset Formula $\Omega$
\end_inset

 a deterministic positive definite matrix.
 
\end_layout

\begin_layout Standard
The sample counterpart of 
\begin_inset Formula $H_{0}$
\end_inset

 is
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\min_{\eta\in\mathcal{C}}[\hat{\rho}-\eta]'\Omega[\hat{\rho}-\eta].
\]

\end_inset


\end_layout

\begin_layout Standard
The test statistic 
\begin_inset Formula $\mathcal{J}_{N}$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mathcal{J}_{N}=N\min_{\eta\in\mathcal{C}}[\hat{\rho}-\eta]'\Omega[\hat{\rho}-\eta]
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
=N\min_{\nu\in\mathbb{R}_{+}^{|\mathcal{R}|}}[\hat{\rho}-A\nu]'\Omega[\hat{\rho}-A\nu].
\]

\end_inset


\end_layout

\begin_layout Standard
If 
\begin_inset Formula $J_{N}=0$
\end_inset

 then the null is accepted but what happens when it is above 
\begin_inset Formula $0$
\end_inset

.
 We have to do statistical hypothesis testing using a simulated critical
 value.
 
\end_layout

\begin_layout Subsubsection
Simulating a Critical Value
\end_layout

\begin_layout Standard
We need to obtain 
\begin_inset Formula $\hat{\rho}^{*(b)}$
\end_inset

 for 
\begin_inset Formula $b=1,\cdots,B$
\end_inset

, bootstrap sample.
 
\end_layout

\begin_layout Standard
We need a tuning parameter 
\begin_inset Formula $\tau_{N}=\sqrt{\frac{log(min_{j}N_{j})}{(min_{j}N_{j})}}$
\end_inset

, in reality it can be picked such that 
\begin_inset Formula $\tau_{N}\rightarrow0$
\end_inset

 as 
\begin_inset Formula $\sqrt{N}\tau_{N}\rightarrow\infty$
\end_inset

.
 Restrict 
\begin_inset Formula $\Omega$
\end_inset

 to be diagonal and positive definite and 
\begin_inset Formula $1_{|\mathcal{R}|}$
\end_inset

 is a vector of ones of size 
\begin_inset Formula $|\mathcal{R}|$
\end_inset

.
 
\end_layout

\begin_layout Standard
(i) Obtain 
\begin_inset Formula $\tau_{N}-$
\end_inset

tightened restricted estimator 
\begin_inset Formula $\hat{\eta}_{\tau_{n}}$
\end_inset

 which solves:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\min_{\eta\in\mathcal{\mathcal{C}_{\tau_{N}}}}N[\hat{\rho}-\eta]'\Omega[\hat{\rho}-\eta]=\min_{[\nu-\tau_{N}1_{|\mathcal{R}|}/|\mathcal{R}|]\in\mathbb{R}_{+}^{|\mathcal{R}|}}N[\hat{\rho}-A\nu]'\Omega[\hat{\rho}-A\nu].
\]

\end_inset


\end_layout

\begin_layout Standard
(ii) Define the 
\begin_inset Formula $\tau_{N}-$
\end_inset

tightened recentered boostrap estimator
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\hat{\rho}_{\tau_{N}}^{*(b)}:=\hat{\rho}^{*(b)}-\hat{\rho}+\hat{\eta}_{\tau_{n}},\quad\forall b\in1,\cdots,B.
\]

\end_inset


\end_layout

\begin_layout Standard
(iii) The bootstrap test statistic is
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mathcal{J}_{N}^{*(b)}=min_{[\nu-\tau_{N}1_{|\mathcal{R}|}/|\mathcal{R}|]\in\mathbb{R}_{+}^{|\mathcal{R}|}}N[\hat{\rho}_{\tau_{N}}^{*(b)}-A\nu]'\Omega[\hat{\rho}_{\tau_{N}}^{*(b)}-A\nu],
\]

\end_inset


\end_layout

\begin_layout Standard
for all 
\begin_inset Formula $b=1,\cdots,B$
\end_inset

.
 
\end_layout

\begin_layout Standard
(iv) Use the empirical distribution of 
\begin_inset Formula $\mathcal{J}_{N}^{*(b)}$
\end_inset

, for 
\begin_inset Formula $b=1,\cdots,B$
\end_inset

, to obtain the critical value for 
\begin_inset Formula $\mathcal{J}_{N}$
\end_inset

.
 
\end_layout

\begin_layout Subsection
Dealing with Endogeneity in the Demand Setup (Paper Reference: Revealed
 Price Preference: Theory and Empirical Analysis).
 
\end_layout

\begin_layout Standard
This paper introduces a new model of consumption.
 
\end_layout

\begin_layout Definition
Augmented Utility Functions: Consider 
\begin_inset Formula $\mathcal{D}=\{p^{t},x^{t}\}_{t=1}^{T}$
\end_inset

, from a consumer, each observation consists of the prices 
\begin_inset Formula $p^{t}\in\mathbb{R}_{++}^{L}$
\end_inset

 of the 
\begin_inset Formula $L$
\end_inset

 goods, and the consumer demands 
\begin_inset Formula $x^{t}\in\mathbb{R}_{+}^{L}$
\end_inset

 at those prices.
 We have an augmented utility 
\begin_inset Formula $U:X\times\mathbb{R}_{-}\to\mathbb{R}$
\end_inset

, that (
\begin_inset Formula $X=\mathbb{R}_{+}^{L}$
\end_inset

) rationalizes 
\begin_inset Formula $\mathcal{D}$
\end_inset

 in the following sense:
\end_layout

\begin_layout Definition
\begin_inset Formula 
\[
x^{t}\in argmax_{x\in X}U(x,-p^{t\prime}x)
\]

\end_inset


\end_layout

\begin_layout Definition
for all 
\begin_inset Formula $t=1,\cdots,T$
\end_inset

.
 We assume that this 
\begin_inset Formula $U$
\end_inset

 is monotone on the arguments.
 
\end_layout

\begin_layout Standard
Note that we can define the value function of the problem above that is
 indirect utility over prices: 
\begin_inset Formula $V:\mathbb{R}_{++}^{L}\to\mathbb{R}$
\end_inset

, 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
V(p^{t})=max_{x\in X}U(x,-p^{t\prime}x).
\]

\end_inset


\end_layout

\begin_layout Standard
This is an expenditure-augmented utility function, where 
\begin_inset Formula $U(x,-e)$
\end_inset

 is the consumer's utility when she acquires 
\begin_inset Formula $x$
\end_inset

 at the cost 
\begin_inset Formula $e$
\end_inset

.
 This means that expenditure is endogenous and dependent on prices.
 
\end_layout

\begin_layout Standard
Special case is the quasilinear model:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
U(x,-p^{t\prime}x)=u(x)-p'x.
\]

\end_inset


\end_layout

\begin_layout Standard
We can have also nonseparable models:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
U(x,-p^{t\prime}x)=u(x)/p'x
\]

\end_inset


\end_layout

\begin_layout Standard
Consider the new price preference revelation:
\end_layout

\begin_layout Standard
We say that 
\begin_inset Formula $p^{s}$
\end_inset

 is directly (strictly) revealed preferred to 
\begin_inset Formula $p^{t}$
\end_inset

 (
\begin_inset Formula $p^{s}\succeq_{p}(\succ_{p})p^{t}$
\end_inset

) if 
\begin_inset Formula $p^{s\prime}x^{t}\leq(<)p^{t\prime}x^{t}=e^{t}$
\end_inset

 (note that 
\begin_inset Formula $p^{s}\succeq_{p}(\succ_{p})p^{t})\implies$
\end_inset


\begin_inset Formula $V(p^{s})\geq(>)V(p^{t}$
\end_inset

) when 
\begin_inset Formula $\mathcal{D}$
\end_inset

 are rationalized by a Augmented Utility).
 Then we define indirect price preference 
\begin_inset Formula $p^{s}\succeq_{p}^{*}p^{t}$
\end_inset

 if there is a finite sequence 
\begin_inset Formula $k,r,l,\cdots,n$
\end_inset

, 
\begin_inset Formula $p^{s}\succeq_{p}p^{k}\succeq_{p}p^{r}\succeq_{p}p^{l}\succeq_{p}\cdots p^{n}\succeq_{p}p^{t}$
\end_inset

.
 
\end_layout

\begin_layout Definition
Generalized Axiom of Price Revealed Preference (GAPP).
 We say that 
\begin_inset Formula $\mathcal{D}=\{p^{t},x^{t}\}_{t=1}^{T}$
\end_inset

 satisfies GAPP if there is no 
\begin_inset Formula $s,t$
\end_inset

 such that 
\begin_inset Formula $p^{s}\succeq_{p}^{*}p^{t}$
\end_inset

 and 
\begin_inset Formula $p^{t}\succ_{p}p^{s}$
\end_inset

.
 
\end_layout

\begin_layout Theorem
Given a data set 
\begin_inset Formula $\mathcal{D}=\{(p^{t},x^{t})\}_{t=1}^{T}$
\end_inset

, the following are equivalent:
\end_layout

\begin_layout Enumerate
\begin_inset Formula $\mathcal{D}$
\end_inset

 is rationalized by an augmented utility function.
 
\end_layout

\begin_layout Enumerate
\begin_inset Formula $\mathcal{D}$
\end_inset

 satisfies GAPP.
 
\end_layout

\begin_layout Enumerate
\begin_inset Formula $\mathcal{D}$
\end_inset

 is rationalized by an augmented utility function that is strictly increasing,
 continuous, and concave.
 Moreover, 
\begin_inset Formula $U$
\end_inset

 is such that there is always a maximum for all 
\begin_inset Formula $p\in\mathbb{R}_{++}^{L}$
\end_inset

.
 
\end_layout

\begin_layout Standard
We that the Generalized Axiom of Revealed Preference (GARP).
 We say that 
\begin_inset Formula $x^{t}$
\end_inset

 is directly (strictly) revealed preferred to 
\begin_inset Formula $x^{s}$
\end_inset

 (
\begin_inset Formula $x^{t}\succeq_{x}x^{s})$
\end_inset

 whenever 
\begin_inset Formula $p^{t\prime}x^{t}\geq(>)p^{t\prime}x^{s}$
\end_inset

.
 We define the indirect commodity revealed preference completely analogous
 to the case of the price preference such that we have 
\begin_inset Formula $x^{t}\succeq_{x}^{*}x^{s}$
\end_inset

 when there is a chain of direct revelation.
 
\end_layout

\begin_layout Definition
GARP.
 We say that 
\begin_inset Formula $\mathcal{D}=\{p^{t},x^{t}\}_{t=1}^{T}$
\end_inset

 satisfies GARP if there is no 
\begin_inset Formula $s,t$
\end_inset

 such that 
\begin_inset Formula $x^{t}\succeq_{p}^{*}x^{s}$
\end_inset

 and 
\begin_inset Formula $p^{s}\succ_{p}p^{t}$
\end_inset

.
\end_layout

\begin_layout Proposition
Let 
\begin_inset Formula $\mathcal{D}=\{p^{t},x^{t}\}_{t=1}^{T}$
\end_inset

 be a data set and let 
\begin_inset Formula $\mathcal{D}^{*}=\{p^{t},x^{t*}\}_{t=1}^{T}$
\end_inset

 such that 
\begin_inset Formula $x^{t*}=\frac{x^{t}}{p^{t\prime}x^{t}}$
\end_inset

.
 Then 
\end_layout

\begin_layout Proposition
\begin_inset Formula $\mathcal{D}$
\end_inset

 satisfies GAPP if and only if 
\begin_inset Formula $\mathcal{D}^{*}$
\end_inset

 satisfies GARP.
\end_layout

\begin_layout Standard
This is powerful because we can apply the mixture techniques here using
 the normalized patches, we can essentially do RUM for demand with endogenous
 expenditure.
 
\end_layout

\begin_layout Part
Machine Learning
\end_layout

\begin_layout Chapter
Deep Feedforward Networks
\end_layout

\begin_layout Standard
Deep forward networks, or feedforward neural networks (DFNN), are the 
\series bold
quintessential 
\series default
model of 
\series bold
deep learning
\series default
.
 
\end_layout

\begin_layout Itemize
Objective: Approximate a function 
\begin_inset Formula $f^{*}$
\end_inset

.
 
\end_layout

\begin_layout Standard
For discrete choice, 
\begin_inset Formula $y=f^{*}(x)$
\end_inset

 where an input 
\begin_inset Formula $x$
\end_inset

 (features/attributes) is mapped into a category or choice 
\begin_inset Formula $y$
\end_inset

.
 
\end_layout

\begin_layout Itemize
A DFNN is a model, defined by a mapping:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
y=f(x,\theta),
\]

\end_inset


\end_layout

\begin_layout Standard
where 
\begin_inset Formula $\theta$
\end_inset

 is a parameter.
 The objective of DFNN is to learn the value of 
\begin_inset Formula $\theta$
\end_inset

 that results in the best approximation of the observed instances of 
\begin_inset Formula $f^{*}$
\end_inset

 (dataset).
 
\end_layout

\begin_layout Itemize
Defining features: 
\end_layout

\begin_deeper
\begin_layout Enumerate
DFNN are called 
\series bold
feedforward 
\series default
because information flows through the function being evaluated from 
\begin_inset Formula $x$
\end_inset

, through the intermediate computations used to define 
\begin_inset Formula $f$
\end_inset

, and finally the output 
\begin_inset Formula $y$
\end_inset

.
 No feedback is allowed.
 Counterexample: 
\begin_inset Formula $y_{t}=f(y_{t-1},x_{t},\theta)$
\end_inset

 for 
\begin_inset Formula $t\in\{1,2\}$
\end_inset

.
 
\end_layout

\begin_layout Enumerate
DFNN are called 
\series bold
neural 
\series default
because they are loosely inspired by biological neurons.
 Modernly, they do not try to model a biological brain.
 
\end_layout

\begin_layout Enumerate
DFNN are called 
\series bold
networks 
\series default
because they are typically represented by composing many different functions.
 The model is associated with a 
\series bold
directed acyclical graph
\series default
 describing how functions are composed together: 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
f(x)=(f^{d}\circ f^{d-1}\cdots f^{3}\circ f^{2}\circ f^{1})(x),
\]

\end_inset


\end_layout

\begin_layout Standard
where 
\begin_inset Formula $\circ$
\end_inset

 denotes function composition, 
\begin_inset Formula $f^{1}$
\end_inset

 is called the 
\series bold
first layer
\series default
 of the network, 
\begin_inset Formula $f^{2}$
\end_inset

 is called the 
\series bold
second layer 
\series default
and so on.
 The overall length of the chain, 
\begin_inset Formula $d$
\end_inset

, denotes the 
\series bold
depth 
\series default
of the model.
 (Deep learning!).
 The final layer 
\begin_inset Formula $f^{d}$
\end_inset

 is called the 
\series bold
output layer.
 
\end_layout

\end_deeper
\begin_layout Itemize
Neural network training tries to match 
\begin_inset Formula $f(x)$
\end_inset

 to 
\begin_inset Formula $f^{*}(x)$
\end_inset

.
 The training data provides us with 
\series bold
noisy 
\series default
instances of 
\begin_inset Formula $f^{*}(x)$
\end_inset

.
 Namely, 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
y\simeq f^{*}(x).
\]

\end_inset


\end_layout

\begin_layout Itemize
There is no information about the behavior of each 
\series bold
hidden layer.
 
\series default
The dimensionality of each these hidden layers determines the 
\series bold
width 
\series default
of the model.
 
\end_layout

\begin_layout Itemize
Each entry of the vector 
\begin_inset Formula $x=(x_{k})_{k=1}^{K}\in X\subseteq\mathbb{R}^{K}$
\end_inset

 can be thought as a 
\series bold
neuron.
 
\end_layout

\begin_layout Itemize
Each layer is a vector valued function 
\begin_inset Formula $f^{1}:X\to X^{2}$
\end_inset

, and 
\begin_inset Formula $f^{n}:X^{n-1}\to X^{n}=Y$
\end_inset

, where 
\begin_inset Formula $y\in Y$
\end_inset

.
 Then the entry 
\begin_inset Formula $f_{l}^{1}(x)$
\end_inset

 can be thought as a neuron, that is 
\series bold
activated 
\series default
by receiving information.
 Each entry represents a neuron processing one aspect of this information.
 
\end_layout

\begin_layout Example
Linear Probability Model.
 
\begin_inset Formula $y\in\{0,1\}$
\end_inset

.
 
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
y=f^{1}(x)=x'w+b,
\]

\end_inset


\end_layout

\begin_layout Example
where 
\begin_inset Formula $\theta=(w,b)$
\end_inset

, where 
\begin_inset Formula $w$
\end_inset

 are called 
\series bold
weights, 
\series default
and 
\begin_inset Formula $b$
\end_inset

 are called 
\series bold
biases.
 
\end_layout

\begin_layout Standard
\begin_inset Separator plain
\end_inset


\end_layout

\begin_layout Example
Logit Probability Model.
 
\begin_inset Formula $y\in\{0,1\}$
\end_inset


\end_layout

\begin_layout Example
\begin_inset Formula 
\[
y=(f^{2}\circ f^{1})(x)=\frac{1}{1+exp(x'w+b)},
\]

\end_inset


\end_layout

\begin_layout Example
where 
\begin_inset Formula $\theta=(w,b)$
\end_inset

, where 
\begin_inset Formula $w$
\end_inset

 are called 
\series bold
weights, 
\series default
and 
\begin_inset Formula $b$
\end_inset

 are called 
\series bold
biases, 
\series default
and 
\begin_inset Formula $f^{2}(z)=\frac{1}{1+exp(z)}$
\end_inset

 is the logit 
\series bold
activation function.
 
\end_layout

\begin_layout Standard
\begin_inset Separator plain
\end_inset


\end_layout

\begin_layout Example
Mixed Logit Model.
 
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
y=f^{3}\circ f^{2}\circ f^{1}(x)=\sum_{w\in W}w^{2}(w)\frac{1}{1+exp(x'w+b)}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Separator plain
\end_inset


\end_layout

\begin_layout Example
Closed form solution to the XOR function.
 Consider the XOR function that is defined as 
\begin_inset Formula $f(1,1)=f(0,0)=0$
\end_inset

 and 
\begin_inset Formula $f(1,0)=f(0,1)=1$
\end_inset

.
 The vector of features 
\begin_inset Formula $x=(x_{1},x_{2})$
\end_inset

 is a vector of binary variables.
 We have the following four points 
\begin_inset Formula $\mathbb{X}=\{[0,0]',[0,1]',[1,0]',[1,1]'\}$
\end_inset

.
 We will train a DFNN on this points to learn 
\begin_inset Formula $f$
\end_inset

.
 
\end_layout

\begin_layout Example
We define a loss function MSE:
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
J(\theta)=\frac{1}{4}\sum_{x\in\mathbb{X}}(f^{*}(x)-f(x,\theta))^{2}.
\]

\end_inset


\end_layout

\begin_layout Example
Now we must 
\series bold
choose the model 
\begin_inset Formula $f(x,\theta)$
\end_inset

.
 
\series default
Suppose that we choose first a linear model 
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
f(x;w,b)=x'w+b.
\]

\end_inset


\end_layout

\begin_layout Example
We can minimize 
\begin_inset Formula $J(\theta)$
\end_inset

 to obtain the solution and it will be 
\begin_inset Formula $w=0,b=\frac{1}{2}$
\end_inset

.
 This linear model is such that 
\begin_inset Formula $f(x;0,\frac{1}{2})=\frac{1}{2}$
\end_inset

 for all 
\begin_inset Formula $x$
\end_inset

.
 
\end_layout

\begin_layout Example
Now let's augment the depth of this DFNN, so let's create a first layer
 with two hidden components this is captured by 
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
h=f^{1}(x;W,c)=WX+c,
\]

\end_inset


\end_layout

\begin_layout Example
where 
\begin_inset Formula $f^{1}:X\to\mathbb{R}^{2}$
\end_inset

, and 
\begin_inset Formula $h$
\end_inset

 represents the hidden units.
 Then we have an output layer 
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
y=f^{2}(h;w,b),
\]

\end_inset


\end_layout

\begin_layout Example
\begin_inset Formula $f^{2}:\mathbb{R}^{2}\to\mathbb{R}_{+}$
\end_inset

 we need 
\begin_inset Formula $h^{2}$
\end_inset

 to be nonlinear to learn XOR so we use an activation function.
 A general recommendation is the rectifier linear unit ReLU such that 
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
g(z)=\max\{0,z\},
\]

\end_inset


\end_layout

\begin_layout Example
that is applied elementwise to a vector and denoted for simplicity with
 this notation.
 Then allowing also weights and biases will give us the full neural net:
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
f(x;W,c,w,b)=f^{2}\circ f^{1}(x,\theta)=w'\max\{0,W'x+c\}+b.
\]

\end_inset


\end_layout

\begin_layout Example
The solution to this problem is:
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
W=\left[\begin{array}{cc}
1 & 1\\
1 & 1
\end{array}\right],
\]

\end_inset


\end_layout

\begin_layout Example
\begin_inset Formula 
\[
c=\left[\begin{array}{c}
0\\
-1
\end{array}\right],
\]

\end_inset


\end_layout

\begin_layout Example
\begin_inset Formula 
\[
w=\left[\begin{array}{c}
1\\
-2
\end{array}\right],
\]

\end_inset


\end_layout

\begin_layout Example
and 
\begin_inset Formula $b=0$
\end_inset

.
 
\end_layout

\begin_layout Example
We can now get the points 
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
X=\left[\begin{array}{cc}
0 & 0\\
0 & 1\\
1 & 0\\
1 & 1
\end{array}\right],
\]

\end_inset


\end_layout

\begin_layout Example
\begin_inset Formula 
\[
XW=\left[\begin{array}{cc}
0 & 0\\
1 & 1\\
1 & 1\\
2 & 2
\end{array}\right].
\]

\end_inset


\end_layout

\begin_layout Example
Next we add the bias vector:
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
\left[\begin{array}{cc}
0 & -1\\
1 & 0\\
1 & 0\\
2 & 1
\end{array}\right].
\]

\end_inset


\end_layout

\begin_layout Example
We apply Relu:
\end_layout

\begin_layout Example
\begin_inset Formula 
\[
\left[\begin{array}{cc}
0 & 0\\
1 & 0\\
1 & 0\\
2 & 1
\end{array}\right],
\]

\end_inset


\end_layout

\begin_layout Example
this nonlinear transformation is key as it allows the outter linear model
 to fit the nonlinear XOR, finally multiplying by 
\begin_inset Formula $w$
\end_inset


\end_layout

\begin_layout Example
\begin_inset Formula 
\[
\left[\begin{array}{c}
0\\
1\\
1\\
0
\end{array}\right].
\]

\end_inset


\end_layout

\begin_layout Subsection*
Backpropagation and Chain Rule (based on Roger Grosse notes lecture 2)
\end_layout

\begin_layout Subsection*
Chain Rule
\end_layout

\begin_layout Standard
We assume we have one input and out training example 
\begin_inset Formula $(x,t)$
\end_inset

.
 
\end_layout

\begin_layout Standard
We use a squared error loss function.
 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
z=wx+b
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
y=\sigma(z)
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mathcal{L}=\frac{1}{2}(y-t)^{2}
\]

\end_inset


\end_layout

\begin_layout Standard
Se will consider now a regularizer, that will penalize weights that are
 far from zero.
\end_layout

\begin_layout Standard
\begin_inset Formula 
\begin{equation}
\mathcal{R}=\frac{1}{2}w^{2}
\end{equation}

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\begin{equation}
\mathcal{L}_{r}=\mathcal{L}+\lambda\mathcal{R}.
\end{equation}

\end_inset


\end_layout

\begin_layout Standard
We want to perform gradient descent, we want to compute the partial derivatives
 
\begin_inset Formula $\partial\mathcal{L}\backslash\partial w$
\end_inset

 and 
\begin_inset Formula $\partial\mathcal{L}\backslash\partial b$
\end_inset

.
 
\end_layout

\begin_layout Standard
We will work now on the important idea of backpropagation or 
\series bold
backprop.
\end_layout

\begin_layout Subsection*
Calculus class 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mathcal{L}_{r}=\frac{1}{2}\left(\sigma(wx+b)-t\right)^{2}+\frac{\lambda}{2}w^{2}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\frac{\partial\mathcal{L}_{r}}{\partial w}=\frac{\partial}{\partial w}\left[\frac{1}{2}\left(\sigma(wx+b)-t\right)^{2}+\frac{\lambda}{2}w^{2}\right]
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
=\frac{1}{2}\frac{\partial}{\partial w}\left(\sigma(wx+b)-t\right)^{2}+\frac{\lambda}{2}\frac{\partial}{\partial w}w^{2}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
=\left(\sigma(wx+b)-t\right)\sigma'(wx+b)\frac{\partial}{\partial w}(wx+b)+\lambda w
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
=\left(\sigma(wx+b)-t\right)\sigma'(wx+b)x+\lambda w
\]

\end_inset


\end_layout

\begin_layout Standard
Similar calculations for 
\begin_inset Formula $b$
\end_inset

:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\frac{\partial\mathcal{L}_{r}}{\partial b}=\frac{\partial}{\partial b}\left[\frac{1}{2}\left(\sigma(wx+b)-t\right)^{2}+\frac{\lambda}{2}w^{2}\right].
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
=\frac{1}{2}\frac{\partial}{\partial b}\left(\sigma(wx+b)-t\right)^{2}+\frac{\lambda}{2}\frac{\partial}{\partial b}w^{2}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
=\left(\sigma(wx+b)-t\right)\sigma'(wx+b)\frac{\partial}{\partial w}(wx+b)
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
=(\sigma(wx+b)-t)\sigma'(wx+b).
\]

\end_inset


\end_layout

\begin_layout Standard
This gives a correct answer about the gradient that can be used for optimization
 but: 
\end_layout

\begin_layout Enumerate
Calculations are cumbersome.
 It is error prone, and increasingly so with a realistic neural net.
 
\end_layout

\begin_layout Enumerate
A lot of redundancies.
 For instance, the first 3 steps in the two derivations are almost identical.
 
\end_layout

\begin_layout Enumerate
Both expressions have lots of repeated terms.
 
\end_layout

\begin_layout Enumerate
Backprop shares the repeated computations whenever possible.
 It is clean and modular.
 
\end_layout

\begin_layout Section*
Multivariate chain rule 2 variables
\end_layout

\begin_layout Standard
Recall the univariate chain rule:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\frac{d}{dt}f(g(t))=f'(g(t))g'(t).
\]

\end_inset


\end_layout

\begin_layout Standard
The multivariate chain rule is similar:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\frac{d}{dt}f(x(t),y(t))=\frac{\partial f}{\partial x}\frac{dx}{dt}+\frac{\partial f}{\partial y}\frac{dy}{dt}.
\]

\end_inset


\end_layout

\begin_layout Section*
Convenient notation
\end_layout

\begin_layout Standard
We simplify notation a bit here let 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\overline{v}\equiv\frac{\partial\mathcal{L}}{\partial v}.
\]

\end_inset


\end_layout

\begin_layout Standard
We can rewrite the multivariable Chain rule
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\overline{t}=\overline{x}\frac{dx}{dt}+\overline{y}\frac{dy}{dt}.
\]

\end_inset


\end_layout

\begin_layout Standard
Here we use 
\begin_inset Formula $dx/dt$
\end_inset

 to mean we should actually evaluate the derivative algebraically in order
 to determine the formula for 
\begin_inset Formula $\overline{t}$
\end_inset

, where 
\begin_inset Formula $\overline{x}$
\end_inset

 and 
\begin_inset Formula $\overline{y}$
\end_inset

 are values already computed in previous steps of the algorithm.
 
\end_layout

\begin_layout Subsection*
Using the computation graph
\end_layout

\begin_layout Standard
The technique of backprop of automatic differentiation (autodiff), using
 a computation graph:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
z=wx+b
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
y=\sigma(z)
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mathcal{L}=\frac{1}{2}\left(y-t\right)^{2}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mathcal{R}=\frac{1}{2}w^{2}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\mathcal{L}_{r}=\mathcal{L}+\lambda\mathcal{R}.
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename figures/computationgraph.png

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Computation Graph
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
The computation graph has nodes that correspond to all the values that are
 computed with edges indicating which values are computed from which other
 values.
 
\end_layout

\begin_layout Standard
The goal of backdrop is to compute derivatives 
\begin_inset Formula $\overline{w}$
\end_inset

 and 
\begin_inset Formula $\overline{b}$
\end_inset

.
 We do this applying repeatedly the chain rule.
 
\end_layout

\begin_layout Standard
We have to start with 
\begin_inset Formula $\mathcal{L}_{reg}=\mathcal{L}_{r}$
\end_inset

, and walk backwards trough the graph.
 This explains the name.
 
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $v_{1},\cdots,v_{N}$
\end_inset

 be the notes of the computation graph, in topological order.
 (Topological ordering is any ordering where parents come before children.)
\end_layout

\begin_layout Standard
We want to compute all derivatives 
\begin_inset Formula $\overline{v}_{i}$
\end_inset

, even when we only want a subset.
 
\end_layout

\begin_layout Standard
We first compute all of the values in a 
\series bold
forward pass, 
\series default
and then compute the derivatives in 
\series bold
backward pass.
 
\series default
So we let for this case, 
\begin_inset Formula $v_{N}=\mathcal{L}_{r}$
\end_inset

 or the result of the computation, we let 
\begin_inset Formula $\overline{v}_{N}=1$
\end_inset

 by convention.
 
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\overline{\mathcal{L}}_{r}=1
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\overline{\mathcal{R}}=\overline{\mathcal{L}}_{r}\frac{d\mathcal{L}_{r}}{d\mathcal{R}}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
=\overline{\mathcal{L}}_{r}\lambda
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\overline{\mathcal{L}}=\overline{\mathcal{L}}_{r}\frac{d\mathcal{L}_{r}}{d\mathcal{\mathcal{L}}}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
=\overline{\mathcal{L}}_{r}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\overline{y}=\overline{\mathcal{L}}\frac{d\mathcal{L}}{dy}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
=\overline{\mathcal{L}}(y-t)
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\overline{z}=\overline{y}\frac{dy}{dz}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
=\overline{y}\sigma'(z)
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\overline{w}=\overline{z}\frac{dz}{dw}+\overline{\mathcal{R}}\frac{dR}{dw}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
=\overline{z}x+\overline{\mathcal{R}}w
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\overline{b}=\overline{z}\frac{dz}{db}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
=\overline{z}.
\]

\end_inset


\end_layout

\begin_layout Standard
Now let's apply the method
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\overline{\mathcal{L}}_{r}=1
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\overline{\mathcal{R}}=\overline{\mathcal{L}}_{r}\lambda
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\overline{\mathcal{L}}=\overline{\mathcal{L}}_{r}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\overline{y}=\overline{\mathcal{L}}(y-t)
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\overline{z}=\overline{y}\sigma'(z)
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\overline{w}=\overline{z}x+\overline{\mathcal{R}}w
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\overline{b}=\overline{z}.
\]

\end_inset


\end_layout

\begin_layout Standard
The procedure has no redundant computations so the procedure is modular,
 it is broken into small chunks that can be reused for other computations.
 
\end_layout

\begin_layout Standard
For instance, if we wanted to change the loss function we just had to modify
 the formula for 
\begin_inset Formula $\overline{y}$
\end_inset

.
 
\end_layout

\begin_layout Chapter
Generative Adversarial Networks (GANs)
\end_layout

\begin_layout Section
Introduction to GANs
\end_layout

\begin_layout Standard
Generative Adversarial Networks (GANs) are a groundbreaking approach in
 the field of artificial intelligence and machine learning, particularly
 within the realm of unsupervised learning.
 Proposed by Ian Goodfellow and his colleagues in 2014, GANs have revolutionized
 the way we think about generating new, synthetic data that is indistinguishable
 from real data.
\end_layout

\begin_layout Section
What are GANs?
\end_layout

\begin_layout Standard
GANs consist of two main components: a Generator (G) and a Discriminator
 (D).
 The Generator aims to produce data that is similar to some training set,
 while the Discriminator evaluates the authenticity of the generated data.
 Through their adversarial training, both components improve their performance,
 with the Generator producing increasingly realistic data and the Discriminator
 getting better at distinguishing real from fake data.
\end_layout

\begin_layout Section
Generative Models
\end_layout

\begin_layout Standard
The core idea behind generative models is to learn the underlying distribution
 of a dataset.
 This knowledge allows the generation of new data points that follow the
 same distribution.
 GANs, alongside Variational AutoEncoders (VAEs), are prominent examples
 of generative models, aiming to replicate the statistical properties of
 input data.
\end_layout

\begin_layout Section
Adversarial Training
\end_layout

\begin_layout Standard
The unique aspect of GANs is their use of adversarial training, where the
 Generator and Discriminator are trained simultaneously in a competitive
 setting.
 The Generator's goal is to produce data that the Discriminator cannot distingui
sh from real data, effectively 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

"
\end_layout

\end_inset

fooling
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

"
\end_layout

\end_inset

 the Discriminator.
 Meanwhile, the Discriminator's objective is to accurately classify data
 as real or generated.
 This process leads to a dynamic competition, driving both networks towards
 improved performance.
\end_layout

\begin_layout Section
Training a GAN
\end_layout

\begin_layout Standard
Training a GAN involves several key steps: 
\end_layout

\begin_layout Enumerate
The Discriminator is trained first, using both real data and fake data generated
 by the Generator.
 It learns to classify real data as real and fake data as fake.
 
\end_layout

\begin_layout Enumerate
The Generator is then trained to produce data that the Discriminator will
 classify as real.
 This step is crucial for improving the Generator's ability to create realistic
 data.
 
\end_layout

\begin_layout Enumerate
The process is repeated, with both the Generator and Discriminator being
 iteratively trained to improve their capabilities.
 
\end_layout

\begin_layout Section
Applications
\end_layout

\begin_layout Standard
GANs have found applications in a wide range of fields, from image and video
 generation to more complex tasks like unsupervised translation between
 different domains.
 Their ability to generate new, realistic data from learned distributions
 makes them an invaluable tool in areas requiring creative data synthesis
 and augmentation.
\end_layout

\begin_layout Subsection
Random Number Generation in GANs
\end_layout

\begin_layout Standard
A crucial component in the training of Generative Adversarial Networks (GANs)
 is the generation of random numbers, particularly from a normal distribution.
 This process is essential for initializing the GAN's generator network,
 allowing it to produce diverse and complex data samples.
\end_layout

\begin_layout Subsection
Importance of Randomness
\end_layout

\begin_layout Standard
Randomness introduces variability and novelty in the generated data.
 By sampling from a normal distribution, the GAN's generator learns to produce
 outputs that mirror the statistical properties of the input data distribution.
 This is pivotal for the generative model's ability to create realistic
 and varied data.
\end_layout

\begin_layout Subsection
Implementation in Julia
\end_layout

\begin_layout Standard
In the provided Julia code, random number generation plays a key role in
 training a GAN to simulate data from a normal distribution.
 The script outlines the setup of a GAN environment and utilizes specific
 Julia packages for neural network modeling and optimization.
 Here are some highlights of the code's approach to random number generation:
\end_layout

\begin_layout Itemize

\series bold
Environment Setup:
\series default
 The script begins by activating a new environment for the GAN project,
 ensuring that all necessary packages are available and version-controlled.
 
\end_layout

\begin_layout Itemize

\series bold
Random Seed:
\series default
 A fixed random seed is set using the `Random` package, ensuring reproducibility
 in the random number generation process.
 This is crucial for scientific experiments where consistency is key.
 
\end_layout

\begin_layout Itemize

\series bold
Sampling:
\series default
 The GAN utilizes random numbers sampled from a normal distribution to feed
 into the generator network.
 This allows the generator to learn and adapt, producing data that is statistica
lly similar to the target distribution.
 
\end_layout

\begin_layout Subsection
Benefits for GAN Training
\end_layout

\begin_layout Standard
Using random numbers from a normal distribution enhances the GAN training
 process by: 
\end_layout

\begin_layout Enumerate
Providing a foundation for generating diverse and complex data samples.
 
\end_layout

\begin_layout Enumerate
Facilitating the learning process of the generator to capture the essence
 of the target data distribution.
 
\end_layout

\begin_layout Enumerate
Ensuring reproducibility and consistency across training sessions through
 the use of a fixed random seed.
 
\end_layout

\begin_layout Standard
This approach underlines the significance of randomness in generative modeling,
 particularly for GANs aimed at producing realistic synthetic data.
\end_layout

\begin_layout Standard
This approach underlines the significance of randomness in generative modeling,
 particularly for GANs aimed at producing realistic synthetic data.
 Generative Adversarial Networks (GANs) present several compelling advantages
 over traditional Markov Chain Monte Carlo (MCMC) techniques for random
 number simulation, particularly in the context of efficiency and flexibility.
 One of the most notable benefits is GANs' ability to generate samples in
 parallel, as opposed to the sequential nature of MCMC methods, leading
 to significant improvements in computational efficiency.
 This parallel generation capability allows GANs to produce large volumes
 of samples quickly, making them highly suitable for applications requiring
 substantial amounts of synthetic data.
 Additionally, GANs are not constrained by the need to meticulously design
 proposal distributions, a critical step in MCMC that often requires domain
 expertise and can limit the flexibility of the sampling process.
 GANs learn to simulate the target distribution directly from data through
 adversarial training, automatically capturing complex dependencies without
 explicit modeling.
 Furthermore, GANs can generate high-dimensional data with relative ease,
 whereas MCMC methods might struggle with the curse of dimensionality, making
 GANs particularly advantageous for tasks in image and video generation,
 where the data is inherently high-dimensional.
 Overall, GANs offer a powerful and versatile alternative to MCMC techniques,
 with their ability to efficiently produce diverse and complex samples directly
 from data, bypassing many of the limitations inherent in traditional sampling
 methods.
\end_layout

\begin_layout Chapter
K-means and K-medoids
\end_layout

\begin_layout Standard
(Material adapted from Lester Mackey's slides).
 
\end_layout

\begin_layout Section
Unsupervised learning
\end_layout

\begin_layout Standard
The world is filled with apparent high dimensional complexity however it
 may be that much of the underlying structure is low-dimensional.
 How do we uncover the hidden structure of categories underlying our data?
\end_layout

\begin_layout Standard
Unsupervised learning given covariates 
\begin_inset Formula $x_{1},\cdots,x_{n}$
\end_inset

, we can infer the underlying structure.
 
\end_layout

\begin_layout Standard

\series bold
Clustering: 
\series default
Group these unlabeled images into three clusters or groups.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename figures/Kmeansimages.png

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Example of image clustering for the students
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
We humans seem to be able to easily categorize a set of complex objects
 to simplify understanding, we can apply the same principle to machine learning.
 
\end_layout

\begin_layout Standard
Unsupervised learning is useful because most datasets are in fact unlabeled.
 Also they could be use to obtain compressed representations to save storage
 and computation.
 
\end_layout

\begin_layout Standard
They reduce noise, missing data, and irrelevant attributes in high-dimensional
 data.
 
\end_layout

\begin_layout Standard
It can be used also as a pre-processing step for supervised learning.
 
\end_layout

\begin_layout Section
K-means
\end_layout

\begin_layout Standard
The objective of K-means is to assign each datapoint to one of 
\begin_inset Formula $k$
\end_inset

 clusters so that no average is closer to its cluster mean.
 
\end_layout

\begin_layout Standard
Datapoints 
\begin_inset Formula $x_{i}\in\mathbb{R}^{p}$
\end_inset

, cluster mean is 
\begin_inset Formula $m_{j}\in\mathbb{R}^{p}$
\end_inset

, cluster assignment is 
\begin_inset Formula $z_{i}\in\{1,\cdots,k\}$
\end_inset

.
 
\end_layout

\begin_layout Standard
Objective: 
\begin_inset Formula $J(z_{1:n},m_{1:k})=\sum_{i=1}^{n}||x_{i}-m_{z_{i}}||_{2}^{2}$
\end_inset

, where 
\begin_inset Formula $||\cdot||_{2}^{2}$
\end_inset

 is the squared Euclidean norm.
 
\end_layout

\begin_layout Standard
Goal: Minimize 
\begin_inset Formula $J$
\end_inset

 over 
\begin_inset Formula $z_{1:n}$
\end_inset

 and 
\begin_inset Formula $m_{1:k}$
\end_inset

.
 
\end_layout

\begin_layout Section
Standard 
\begin_inset Formula $k$
\end_inset

-means algorithm/ Lloyd's algorithm
\end_layout

\begin_layout Standard
-Initialize cluster means arbitrarily (e.g.
 sample from datapoints)
\end_layout

\begin_layout Standard
-Alternate until convergence 
\end_layout

\begin_layout Itemize
Update cluster assignments: 
\begin_inset Formula $z_{1:n}\leftarrow argmin_{z_{1:n}}J(z_{1:n}m_{1:k})$
\end_inset

, i.e., assign each point to the cluster with the closest mean.
 
\end_layout

\begin_layout Itemize
Update cluster means: 
\begin_inset Formula $m_{1:k}\leftarrow argmin_{m_{1:k}}J(z_{1:n},m_{1:k})$
\end_inset

, i.e., 
\begin_inset Formula $m_{j}=\frac{\sum_{i=1}^{n}1(z_{i}=j)x_{i}}{\sum_{i=1}^{n}1(z_{i}=j)},$
\end_inset

 the mean of points in cluster 
\begin_inset Formula $j$
\end_inset

.
 
\end_layout

\begin_layout Standard
The objective 
\begin_inset Formula $J$
\end_inset

 
\series bold
always converges.
 
\end_layout

\begin_layout Standard
Lloyd's algorithm is a coordinate descent procedure.
 Each step monotonically decreases the objective.
 
\end_layout

\begin_layout Standard
Only finite number of partitions of data, so the objective must converge
 in finite number of steps.
 
\end_layout

\begin_layout Standard
Technically the algorithm could cycle if ties arise (multiple centroids
 equidistant from point).
 
\end_layout

\begin_layout Standard
We can avoid ties by assigning always the point to the smallest centroid
 under some total ordering of vectors.
 
\end_layout

\begin_layout Section
K-means limitations and Categorical Data
\end_layout

\begin_layout Standard
The Euclidean distance is restrictive for certain dataset like categorical
 features.
 Also the Euclidean distance is sensitive to outliers, and ill-suited for
 datasets with very different units/scales.
 
\end_layout

\begin_layout Standard
Also the K-means optimization problem is NP-hard.
 Lloyd's algorithm usually finds suboptimal solutions.
 Many random restarts often needed to obtain good performance.
 
\end_layout

\begin_layout Standard
Most important 
\series bold
the user must choose
\series default
 
\begin_inset Formula $k$
\end_inset

.
 
\end_layout

\begin_layout Standard
Running time: #features 
\begin_inset Formula $\times$
\end_inset

 datapoints 
\begin_inset Formula $\times$
\end_inset


\begin_inset Formula $k$
\end_inset

 per iteration.
 
\end_layout

\begin_layout Standard
Generalized problem:
\end_layout

\begin_layout Standard
Minimize 
\begin_inset Formula $J_{d}(z_{1:n},m_{1:k})=\sum_{i=1}^{n}d(x_{i},m_{z_{i}})$
\end_inset

.
 
\end_layout

\begin_layout Standard
Arbitrary dissimilarity/discrepancy measure 
\begin_inset Formula $d(x,m)$
\end_inset

.
 
\end_layout

\begin_layout Standard
Optimize via coordinate descent as in Lloyd's algorithm.
 
\end_layout

\begin_layout Standard
The great advantage is that it applies to all data types and dissimilarity
 measures.
 
\end_layout

\begin_layout Standard
Updating cluster representative 
\begin_inset Formula $m_{1:k}$
\end_inset

 may be expensive.
\end_layout

\begin_layout Section
K-medoids algorithm
\end_layout

\begin_layout Standard
Minimize 
\begin_inset Formula $J_{d}$
\end_inset

 above but constrain each cluster representative to be a datapoint i.e., 
\begin_inset Formula $m_{j}\in\{x_{1},\cdots,x_{n}\}$
\end_inset

.
 
\end_layout

\begin_layout Standard
Don't need to store datapoint, only pairwise discrepancies.
 
\begin_inset Formula $d(x_{i},x_{j})$
\end_inset

.
 
\end_layout

\begin_layout Section
Choosing the number of clusters 
\begin_inset Formula $k$
\end_inset


\end_layout

\begin_layout Standard
Best case known beforehand.
 
\end_layout

\begin_layout Standard
Elbow method.
 
\end_layout

\begin_layout Standard
Gap statistic.
 
\end_layout

\begin_layout Chapter
Transformers
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
maketitle
\end_layout

\end_inset


\end_layout

\begin_layout Section
Introduction to the Transformer Model
\end_layout

\begin_layout Itemize
Provides an overview of sequence transduction challenges and introduces
 the Transformer as a solution.
 
\end_layout

\begin_layout Itemize
Discusses the objectives of using the Transformer in machine translation
 and other NLP tasks.
 
\end_layout

\begin_layout Section
Detailed Model Architecture
\end_layout

\begin_layout Subsection
Encoder and Decoder Overview
\end_layout

\begin_layout Itemize
Brief introduction to the overall encoder-decoder architecture.
 
\end_layout

\begin_layout Subsection
Encoder Layers
\end_layout

\begin_layout Itemize
Details the components within the encoder: 
\end_layout

\begin_deeper
\begin_layout Itemize
Multi-head self-attention mechanism 
\end_layout

\begin_layout Itemize
Position-wise feed-forward networks 
\end_layout

\begin_layout Itemize
Residual connections and layer normalization 
\end_layout

\end_deeper
\begin_layout Subsection
Decoder Layers
\end_layout

\begin_layout Itemize
Explanation of the decoder’s unique components: 
\end_layout

\begin_deeper
\begin_layout Itemize
Masked self-attention 
\end_layout

\begin_layout Itemize
Encoder-decoder attention 
\end_layout

\begin_layout Itemize
Position-wise feed-forward networks, residual connections, and normalization
 
\end_layout

\end_deeper
\begin_layout Section
Deep Dive into Self-Attention
\end_layout

\begin_layout Itemize
Discusses the concept of self-attention and how it computes relevance scores
 across input positions.
 
\end_layout

\begin_layout Itemize
Provides the mathematical formulation including equations and calculations
 for scaled dot-product attention.
 
\end_layout

\begin_layout Itemize
Explains the rationale behind using multiple attention heads, enhancing
 the model's ability to focus on different parts of the input sequence.
 
\end_layout

\begin_layout Section
Objectives and Benefits of Self-Attention
\end_layout

\begin_layout Itemize
Details computational efficiency, comparing with RNNs and CNNs in terms
 of parallelization and training speed.
 
\end_layout

\begin_layout Itemize
Discusses performance improvements in translation accuracy and model interpretab
ility.
 
\end_layout

\begin_layout Itemize
Talks about the flexibility and scalability of the model, adaptable to different
 sequence lengths and complexities.
 
\end_layout

\begin_layout Section*
Summary of Self-Attention Neural Network Structure
\end_layout

\begin_layout Standard
The Transformer model, particularly through its use of self-attention, revolutio
nizes the handling of sequences in tasks like translation.
 Self-attention enables the model to evaluate the input sequence in a parallel
 manner, significantly increasing efficiency and model depth.
 Below, we delve into the core elements of the self-attention mechanism
 within the Transformer architecture:
\end_layout

\begin_layout Enumerate

\series bold
Input Embedding
\series default
: 
\end_layout

\begin_deeper
\begin_layout Itemize
The input sequence is converted into a set of embeddings, which are vector
 representations of the input tokens.
 These embeddings are then adjusted by adding positional encodings to inject
 information about the order of tokens.
 
\end_layout

\end_deeper
\begin_layout Enumerate

\series bold
Multi-Head Attention
\series default
: 
\end_layout

\begin_deeper
\begin_layout Itemize
The main innovation of the Transformer, multi-head attention allows the
 model to focus on different parts of the sequence simultaneously.
 
\end_layout

\begin_layout Itemize
For each head, the attention scores are calculated by: 
\end_layout

\begin_deeper
\begin_layout Itemize

\series bold
Query, Key, Value Vectors
\series default
: Derived from the input embeddings.
 
\end_layout

\begin_layout Itemize

\series bold
Attention Scores
\series default
: Computed by taking the dot product of the query with all keys, scaled
 by the dimension of the keys, followed by a softmax to obtain the weights
 on the values.
 
\end_layout

\end_deeper
\begin_layout Itemize
Outputs from all heads are concatenated and linearly transformed to produce
 the final attention output.
 
\end_layout

\end_deeper
\begin_layout Enumerate

\series bold
Position-Wise Feed-Forward Networks
\series default
: 
\end_layout

\begin_deeper
\begin_layout Itemize
After attention, each position passes through a feed-forward network applied
 independently to each position.
 This network consists of two linear transformations with a ReLU activation
 in between.
 
\end_layout

\end_deeper
\begin_layout Enumerate

\series bold
Residual Connection and Layer Normalization
\series default
: 
\end_layout

\begin_deeper
\begin_layout Itemize
Each sub-layer (attention and feed-forward) includes a residual connection
 around it, followed by layer normalization.
 
\end_layout

\end_deeper
\begin_layout Enumerate

\series bold
Decoder Structure
\series default
: 
\end_layout

\begin_deeper
\begin_layout Itemize
The decoder also features multi-head attention layers, but with masking
 to prevent positions from attending to future positions in the sequence.
 
\end_layout

\begin_layout Itemize
It includes an additional multi-head attention layer that attends over the
 encoder's output.
 
\end_layout

\end_deeper
\begin_layout Standard
This architecture supports efficient training by parallelizing the computation
 across all positions in the sequence, and it allows the model to learn
 complex dependencies in data.
\end_layout

\begin_layout Section*
Pseudo-Code for Implementing Self-Attention
\end_layout

\begin_layout Standard
Here's a high-level pseudo-code that outlines the implementation of the
 self-attention mechanism:
\end_layout

\begin_layout Standard
\begin_inset listings
lstparams "language=Python"
inline false
status open

\begin_layout Plain Layout

function SelfAttention(Q, K, V):
\end_layout

\begin_layout Plain Layout

    d_k = size(K, last_dimension)
\end_layout

\begin_layout Plain Layout

    scores = matmul(Q, K.transpose()) / sqrt(d_k)
\end_layout

\begin_layout Plain Layout

    weights = softmax(scores)
\end_layout

\begin_layout Plain Layout

    output = matmul(weights, V)
\end_layout

\begin_layout Plain Layout

    return output
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

function TransformerEncoder(input):
\end_layout

\begin_layout Plain Layout

    # Convert input tokens to embeddings
\end_layout

\begin_layout Plain Layout

    X = Embedding(input) + PositionalEncoding(length(input))
\end_layout

\begin_layout Plain Layout

    for each layer in layers:
\end_layout

\begin_layout Plain Layout

        # Apply multi-head attention
\end_layout

\begin_layout Plain Layout

        Q, K, V = [Linear(X) for _ in range(3)]
\end_layout

\begin_layout Plain Layout

        X = Concat([SelfAttention(q, k, v) for q, k, v in zip(Q, K, V)])
\end_layout

\begin_layout Plain Layout

        X = Linear(X)
\end_layout

\begin_layout Plain Layout

        # Apply position-wise feed-forward network
\end_layout

\begin_layout Plain Layout

        X = ReLU(Linear(X))
\end_layout

\begin_layout Plain Layout

        X = Linear(X)
\end_layout

\begin_layout Plain Layout

        # Add residual connection and normalize
\end_layout

\begin_layout Plain Layout

        X = LayerNorm(X + residual)
\end_layout

\begin_layout Plain Layout

    return X
\end_layout

\end_inset


\end_layout

\begin_layout Section*
Explanation of Multi-Head Attention
\end_layout

\begin_layout Standard
Imagine you have a toy storybook in front of you with lots of pictures and
 words.
 Now, imagine you have several magnifying glasses that let you look at many
 different parts of the page at the same time.
 This is like the 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

"
\end_layout

\end_inset

multi-head attention
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

"
\end_layout

\end_inset

 in a Transformer model.
 Let's break it down:
\end_layout

\begin_layout Subsection*
Several Magnifying Glasses (Multi-Head Attention):
\end_layout

\begin_layout Standard
Instead of one, you have several magnifying glasses (these are the 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

"
\end_layout

\end_inset

heads
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

"
\end_layout

\end_inset

).
 Each one can look at different things on the same page.
 This way, you can see many details at once!
\end_layout

\begin_layout Subsection*
Choosing What to Look At (Query, Key, Value Vectors):
\end_layout

\begin_layout Itemize

\series bold
Query
\series default
 is like asking, 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

"
\end_layout

\end_inset

What should I look at in this picture?
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

"
\end_layout

\end_inset

 
\end_layout

\begin_layout Itemize

\series bold
Key
\series default
 is like having clues on each part of the picture that answer, 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

"
\end_layout

\end_inset

Is this part interesting to look at for your question?
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

"
\end_layout

\end_inset

 
\end_layout

\begin_layout Itemize

\series bold
Value
\series default
 is the actual part of the picture you will see through the magnifying glass
 if your clues (keys) say it's interesting.
 
\end_layout

\begin_layout Subsection*
Deciding How Interesting Each Part Is (Attention Scores):
\end_layout

\begin_layout Itemize
First, each magnifying glass decides how closely the clues (keys) match
 the question (query).
 This is like measuring how interesting each part of the picture is based
 on your question.
 
\end_layout

\begin_layout Itemize
Then, to make it fair, each magnifying glass uses a rule (softmax) to make
 sure that the most interesting parts stand out a lot more than the less
 interesting ones.
 
\end_layout

\begin_layout Subsection*
Looking Through the Glasses (Outputs):
\end_layout

\begin_layout Itemize
After all the magnifying glasses have looked at the parts they found interesting
, they all come together.
 
\end_layout

\begin_layout Itemize
You combine everything they saw into one big picture so you can understand
 the whole story better.
 
\end_layout

\begin_layout Standard
With the use of multi-head attention, the Transformer model can pay attention
 to many different parts of the information (like your storybook) at the
 same time, helping it understand the whole story better!
\end_layout

\begin_layout Section*
Summary of Transformers for Time Series Analysis
\end_layout

\begin_layout Standard
Transformers have demonstrated significant success in various domains like
 NLP and computer vision, and this has inspired their application in time
 series analysis.
 Their ability to handle long-range dependencies makes them particularly
 suitable for this task.
 Here are the key adaptations and applications of transformers in time series
 analysis:
\end_layout

\begin_layout Subsection*
1.
 Adaptations for Time Series
\end_layout

\begin_layout Itemize

\series bold
Positional Encodings:
\series default
 Time series data is inherently sequential, so it's crucial to maintain
 this ordering.
 Transformers use positional encodings to retain temporal order.
 Variants include: 
\end_layout

\begin_deeper
\begin_layout Itemize

\series bold
Absolute Positional Encoding:
\series default
 Uses sine and cosine functions of different frequencies.
 
\end_layout

\begin_layout Itemize

\series bold
Relative Positional Encoding:
\series default
 Focuses on pairwise positional relationships rather than absolute positions.
 
\end_layout

\end_deeper
\begin_layout Itemize

\series bold
Multi-head Attention:
\series default
 Enables the model to focus on different parts of the sequence simultaneously,
 which is particularly beneficial for capturing complex temporal dynamics
 in time series data.
 
\end_layout

\begin_layout Itemize

\series bold
Efficient Attention Mechanisms:
\series default
 To handle longer sequences typical in time series, modifications like sparse
 attention and low-rank approximations reduce computational complexity.
 
\end_layout

\begin_layout Subsection*
2.
 Applications in Time Series
\end_layout

\begin_layout Itemize

\series bold
Forecasting:
\series default
 Transformers are used for various forecasting tasks, including standard
 time series forecasting, spatial-temporal forecasting (combining spatial
 and temporal data), and event forecasting (predicting the times and marks
 of future events).
 
\end_layout

\begin_layout Itemize

\series bold
Anomaly Detection:
\series default
 The ability of transformers to model normal patterns over time helps in
 identifying anomalies when these patterns are disrupted.
 
\end_layout

\begin_layout Itemize

\series bold
Classification:
\series default
 Transformers can classify time series data based on learned temporal dynamics,
 useful in fields like finance and healthcare.
 
\end_layout

\begin_layout Subsection*
3.
 Empirical Performance
\end_layout

\begin_layout Itemize
Studies indicate that transformers can outperform traditional models like
 ARIMA and LSTM in handling complex dependencies in time series data.
 
\end_layout

\begin_layout Itemize
Robustness analyses show that transformers maintain performance advantages
 even with varying input lengths and complexities.
 
\end_layout

\begin_layout Subsection*
4.
 Future Directions
\end_layout

\begin_layout Itemize

\series bold
Incorporating Inductive Biases:
\series default
 Applying domain-specific knowledge such as periodicity and trends directly
 within the transformer model to enhance performance.
 
\end_layout

\begin_layout Itemize

\series bold
Combining with Graph Neural Networks (GNNs):
\series default
 For multivariate time series, integrating GNNs to model relationships among
 multiple time series effectively.
 
\end_layout

\begin_layout Itemize

\series bold
Pre-trained Transformers:
\series default
 Leveraging large-scale pre-training, similar to approaches in NLP, to improve
 time series model performance with less data.
 
\end_layout

\end_body
\end_document