in the proportion of loans from MBF over time and reductions in aggregate loan
volume shares from informal lenders.

###  B.3 Data: Borrowing and Savings Amounts

Figure B.2: Distribution of borrowing and savings Amount Figure B.3:
Distribution of Borrowing Amount by Lenders _Notes:_ Amount of borrowing and
savings represents annualized sums for each lending and saving categories for
each household. (The Million Baht Fund had a limited number of transactions
close to the end of 2001.) See Section 3.2.2 for detail.

###  B.4 Data: Reported Fees and Transport Costs for Formal Borrowing

Figure B.4: Fees and Transport Cost for BAAC and Million Baht Fund _Notes:_
The Million Baht Fund is administered by village committees, and hence require
fewer fees and transport costs to access. Formal borrowing fees and transport
costs decrease significantly after 2001 as Million Baht Fund became the
leading provider of formal loans. See Section 3.2.3 for detail. Table B.2:
Fees and Transport Cost for Each Loan by Lender Types (Baht) Relatives
Neighbor Moneylender mean(sd) mean(sd) mean(sd) Fees and Transport Cost 25.8
(133.6) 4.0 (41.9) 22.1 (38.3) Commercial-Bank BAAC Million Baht Fund Fees and
Transport Cost 379.7 (737.6) 51.6 (92.1) 11.3 (16.6) _Notes:_ Commercial bank
loans are rare, likely due to the high fixed costs associated with getting
them. Fees and Transport costs are only a proportion of the total pecuniary
fixed costs associated with borrowing. There are also possibly non-pecuniary
costs of borrowing. See Section 3.2.3 for detail.

###  B.5 Data: Repayment Rate Based on Payment History

Table B.3:  Repayment of Loans Fully Repaid Not Fully Paid Formal Loans
Percentage of Loans 97.01 2.99 Informal Loans Percentage of Loans 95.16 4.84
_Notes:_ Every month, new loans that households take out are recorded and the
month in which repayment should be completed is also recorded. Then every
month, repayment of each loan is tracked until full repayment is made. Table
B.3 shows that most households repay their loans and that the repayment
difference between formal and informal loans is small. Given these data, this
paper does not model default. See Section 3.2.4 for detail. Table B.4:
Repayment Percentage for Loans That Are Not Fully Paid By Month 24 By Month 36
By Month 48 Formal Loans Percentage of Principal Repaid 30.3 36.7 39.1
Informal Loans Percentage of Principal Repaid 32.4 39.9 44.0 _Notes:_ For the
2.99 percent of formal loans that are not fully repaid, and 4.84 percent of
informal loans that are not fully repaid, Table B.4 shows that a significant
proportion of the principal on these loans is repaid within two years of the
start of the loans. Given this information and data, as shown in Table B.3,
the repayment gap between formal and informal loans is very small; hence, this
paper does not model default. See Section 3.2.4 for detail.

##  Appendix C Solution and Estimation Algorithm (Online Appendix)

The model is computationally intensive to estimate. Building on standard
solution and estimation concepts, I develop a global optimization routine that
minimizes the use of loops and iteration by parallel computing. The routine
solves and estimates the heterogeneous agent equilibrium model with discrete
and constrained continuous choices.C.1C.1C.1There has been significant
progress made in using endogenous grid methods to solve and estimate models
with discrete and continuous choices [25, 36]. Some of the steps described
here can potentially be combined with endogenous grid or other methods when
the model structure allows. The resulting algorithm is resource intensive
concurrently but saves time if concurrency is possible. The algorithm is also
designed to accurately capture the impacts of differences in fixed costs,
interest rates and collateral constraints on the choice sets, the average
costs (returns) of loans (savings), and the conditional asset distributions
facing households across the credit market options.

Typically, university computing clusters have a maximum set of computing
resources that are shared, which limits resources that are available to
individual researchers. Cloud computing services such as Amazon Web Services
(AWS) offers from the econometrician’s perspective potentially unlimited
concurrent resources. On AWS’s managed containerized services, the cost of
running 1 CPU for 10000 minutes is identical to running 10000 CPUs for 1
minute. The idea here is to take advantage of scalable on-demand concurrent
computing resources by modifying some standard solution and estimation steps.
If the estimation task can be parallelized explicitly or implicitly, then the
researcher has more control over how much time estimation should take, given
their budget.

In terms of solution algorithms, I reduce the iterative steps required for
joint continuous and discrete optimization through a "zooming-in" algorithm
(Section C.1.1), I adopt a non-simulation based procedure for deriving steady
state asset distributions (Section C.1.3), and I solve for equilibrium
interest rates using a multi-section algorithm (Section
C.1.5).C.2C.2C.2Implementation examples for using aspects of the solution
algorithms can be found at the MEconTools repository.

For estimation, I add additional initialization steps to standard estimation
routines. These initial steps help me find initialization parameters that are
potentially closer to the minimizers of the estimation objective function. I
do this by simulating the model at a large set of parameter values given data,
and then conducting an initial round of multi-start estimation using a set of
polynomials that approximate components of the estimation objective functions.
I describe the estimation algorithm in Section C.2.1 and its implementation on
AWS in Sections C.2.2, C.2.2, C.2.3, and C.2.4.C.3C.3C.3Examples for how to
use AWS web services can be found at the Py4Econ repository.

###  C.1 Solution Algorithm

####  C.1.1 Iterative Optimization on Asset Share Grids

##### Triangular Asset Choice Sets

Figure C.1: Borrowing Choice Set _Notes:_ The figure shows the effects of
wealth, fixed costs, collateral constraints, and interest rates on the
borrowing and risky investment choice set. Within a borrowing discrete choice
$j$, households face a three dimensional choice set over $c$, risky
investments $k^{\prime}$, and borrowing $b^{\prime}$. Given that households
cannot have negative consumption today or tomorrow, the domain of the choice
set is an individual and choice $j$ specific triangular pyramid. The figure
here plots the base of the pyramid where the x-axis is the borrowing choice
$b^{\prime}$ and the y-axis is the risky investment choice $k^{\prime}$. The
implicit but not shown z-axis is consumption $c$, which is chosen to clear
budgets. The percentage asset solution algorithm used in this paper relies on
taking advantage of the geometry of this figure.

Interest rates, fixed costs and collateral constraints differences across
credit market options determine the choice set for risky investment and the
cost of financing risky investment. Using $\widehat{b^{{}^{\prime}}}$ to
denote principal borrowed for here, the average cost of borrowing,
$\frac{\widehat{b^{{}^{\prime}}}r_{j}+\psi_{j}}{\widehat{b^{{}^{\prime}}}}$,
is increasing in $\psi_{j}$ and decreasing in $\widehat{b^{{}^{\prime}}}$.
With minimum output equal to zero, the natural borrowing constraint restricts
interest and principal due next period to be less than the depreciated risky
investment. This means a portion of risky investment must be financed by
existing wealth. The marginal effect of additional wealth on the maximum risky
investment level is constant and equal to $1+\frac{1-\delta}{r_{j}+\delta}$.
This ratio is the borrowing multiplier. Lower $r_{j}$ expands the choice set
by increasing the multiplier. Lower $\psi_{j}$ also expands the choice set by
increasing usable wealth. The collateral constraint restricts the choice set
if it is tighter than the natural borrowing constraint. Graphically, interest
rates, fixed costs, and collateral constraints shift vertices of an obtuse
triangle that represents the choice set, as shown in Figure C.1. Formal and
informal borrowing choices form separate obtuse triangle choice sets. Given
combinations of wealth, informal interest rates, and informal borrowing fixed
costs, borrowing choices are constrained as shown by Figure C.1.C.4C.4C.4If
exogenous quantity constraints are imposed as well, graphically, they would be
vertical lines cutting potentially through the obtuse triangles shown in
Figure C.1.

For savings, the average return to savings is decreasing in $\psi_{j}$ and
increasing in the amount saved. An increase in $\psi_{j}$ reduces one to one
the maximum risky investment, and increases in the savings interest rate
reduce next period’s wealth and subsequent risky investment choice sets.

##### Bounds on Continuous Choices

Following previous notations, I rewrite the continuous choice problem over
safe asset $b^{{}^{\prime}}$ and risky asset $k^{{}^{\prime}}$ for each
household $i$ as:

$\displaystyle\begin{split}\max_{\begin{array}[]{c}j\in\left\\{1,...,7\right\\}\\\
\end{array}}{\left\\{\max_{\begin{array}[]{c}b^{{}^{\prime}}\in\left(b_{ij}^{{}^{\prime}\text{min}},b^{\text{loan-
smallest}}_{j}\right]\\\
\end{array}}{\left\\{\max_{\begin{array}[]{c}k^{{}^{\prime}}\in\left(k_{ij\left(b^{{}^{\prime}}\right)}^{{}^{\prime}\text{min}},k_{ij\left(b^{{}^{\prime}}\right)}^{{}^{\prime}\text{max}}\right)\\\
\end{array}}\mathcal{U}_{j}\left(\mathcal{A},\mathit{\mathcal{W}},\phi_{j};b^{{}^{\prime}},k^{{}^{\prime}}\right)\right\\}}\right\\}}\end{split}$
(C.1)

where, given the $b^{{}^{\prime}}$ choice, the minimum and maximum for the
$k^{{}^{\prime}}$ choice are:

$\displaystyle k_{ij\left(b^{{}^{\prime}}\right)}^{{}^{\prime}\text{max}}=$
$\displaystyle\left(\mathcal{W}_{i}-\psi_{j}\right)-\frac{b^{{}^{\prime}}}{1+r_{j}}$
(C.2) $\displaystyle
k_{ij\left(b^{{}^{\prime}}\right)}^{{}^{\prime}\text{min}}=$
$\displaystyle\begin{cases}\max\left\\{-\dfrac{y^{\text{min}}}{\left(1-\delta\right)\cdot
r_{j}}-\dfrac{b^{{}^{\prime}}}{1-\delta},0\right\\}&\text{if }j\text{ is
borrow}\\\ 0&\text{if }j\text{ is save}\\\ \end{cases}$ (C.3)

To maintain positive consumption in the current period, $k^{{}^{\prime}}$ must
be less than $k_{ij\left(b^{{}^{\prime}}\right)}^{{}^{\prime}\text{max}}$, and
to maintain positive consumption in all states in the next period,
$k^{{}^{\prime}}$ must be greater than
$k_{ij\left(b^{{}^{\prime}}\right)}^{{}^{\prime}\text{min}}$. For borrowing,
geometrically, plotting $k^{{}^{\prime}}$ along the y-axis, and
$b^{{}^{\prime}}$ along the x-axis, Equation (C.2) and Equation (C.3)
represent two intersecting lines where the intersection point is in the region
of positive $k^{{}^{\prime}}$ and negative $b^{{}^{\prime}}$ as shown in
Figure C.1. Individual $i$ can only borrow less than the $b^{{}^{\prime}}$
value at the intersecting point, which is:

$\displaystyle b_{ij}^{{}^{\prime}\text{min}}=$
$\displaystyle-\left(\mathcal{W}_{i}-\psi_{j}+\frac{y^{\text{min}}}{\left(1-\delta\right)\cdot
r_{j}}\right)\cdot\frac{\left(1+r_{j}\right)\cdot\left(1-\delta\right)}{\delta+r_{j}}\thinspace.$
(C.4)

Household $i$’s $k^{{}^{\prime}}$ choice must be less than the
$k^{{}^{\prime}}$ value associated with $b_{ij}^{{}^{\prime}\text{min}}$ at
the intersecting point.

##### Discretization using Asset Share Indexes

The geometry of the problem allows me to solve for the minimum and maximum
asset choices as shown above. I now transform the problem in Equation (C.1),
which is continuous, to the percentage-grid asset choice problem in Equation
(C.5), which has identical scales for all households. This homogenization of
the choice grid allows for efficient vectorization.C.5C.5C.5Utility
maximization requires two matrix operations only, and utility evaluation and
maximization can fully take advantage of single instruction parallelization
without additional code.

To approximate the exact optimal choice, I solve the discretized percentage
asset choice problem $\left(\iota\right)$ times. This is a type of iterative
grid search method, which has long been used in the literature, starting
perhaps with [35]. After each iteration, an index operation is used to find
the closest set of surrounding share indexes in each direction from the
current optimal index. I solve this model here with $N_{k}=50$, $N_{b}=50$ and
$\left(\iota\right)=3$. Specifically, using $\left(\iota\right)$ as a
superscript to indicate the current index search iteration, the iterative
percentage maximization problem can be written as:

$\displaystyle\begin{split}(n^{*\left(\iota\right)}_{k},n^{*\left(\iota\right)}_{b})=\operatorname*{arg\,max}_{\begin{array}[]{c}n_{k}^{\left(\iota\right)}\in{0,...,N_{k}}\\\
n_{b}^{\left(\iota\right)}\in{0,...,N_{b}}\\\
\end{array}}\mathcal{U}_{j}^{\left(\iota\right)}\left(\mathcal{A},\mathit{\mathcal{W}},\phi_{j};b^{{}^{\prime}}_{ij(n_{b}^{\left(\iota\right)})},k^{{}^{\prime}}_{ij(n_{b}^{\left(\iota\right)})(n_{k}^{\left(\iota\right)})}\right)\end{split}$
(C.5)

Choices $n_{b}^{\left(\iota\right)}$, $n_{k}^{\left(\iota\right)}$ are indexes
for sequences
$\left\\{b^{{}^{\prime}}_{ij(n_{b}^{\left(\iota\right)})}\right\\}^{N_{b}}_{n_{b}=0}$
and
$\left\\{k^{{}^{\prime}}_{ij(n_{b}^{\left(\iota\right)})(n_{k}^{\left(\iota\right)})}\right\\}^{N_{k}}_{n_{k}=0}$,
where
$b^{{}^{\prime}}_{ij(n_{b}^{\left(\iota\right)})}=b_{ij}^{{}^{\prime}\text{max},\left(\iota\right)}\cdot\frac{n_{b}}{N_{b}}+b_{ij}^{{}^{\prime}\text{min},\left(\iota\right)}\cdot\left(1-\frac{n_{b}}{N_{b}}\right)$
and
$k^{{}^{\prime}}_{ij(n_{b}^{\left(\iota\right)})(n_{k}^{\left(\iota\right)})}=k_{ij(n_{b}^{\left(\iota\right)})}^{{}^{\prime}\text{max},\left(\iota\right)}\cdot\frac{n_{k}}{N_{k}}+k_{ij(n_{b}^{\left(\iota\right)})}^{{}^{\prime}\text{min},\left(\iota\right)}\cdot\left(1-\frac{n_{k}}{N_{k}}\right)$.

By the $\left(\iota\right)=I-1$ iteration, the difference between the optimal
choice $b_{ij}^{{}^{\prime}*}$ and the approximate choice
$b^{{}^{\prime}}_{ijn^{*\left(\iota=I-1\right)}_{b}}$ is less than a fraction
determined by $N_{b}$ and $\left(\iota\right)$:C.6C.6C.6Equation (C.7) applies
to constrained maximization problems that are possibly non-differentiable but
concave. With sufficient grid points in each iteration, the method should also
generally find optimal choices for non-concave problems. If the non-
concaveness is due to fixed costs or other clearly defined parameters—as is
the case for this model (Equation (C.1))—the problem could be restated as
multiple concave continuous-choice problems nested within discrete-choice
problems.C.7C.7C.7Assuming that $N_{k}=N_{b}$, the maximum bounds of
$b^{{}^{\prime}}$ for the $\left(\iota\right)=I^{\text{th}}$ iteration are:
$\displaystyle\begin{split}b_{ij}^{{}^{\prime}\text{max},\left(\iota=I^{\text{th}}\right)}=&\frac{b_{ij}^{{}^{\prime}\text{max}}-b_{ij}^{{}^{\prime}\text{min}}}{N_{b}^{I-1}}\cdot\min\left\\{\sum_{s=1}^{I-1}N_{b}^{s-1}\cdot
n^{*\left(\iota=(I-s)^{\text{th}}\right)}_{b}+1,N_{b}^{I-1}\right\\}+b_{ij}^{{}^{\prime}\text{min}}\\\
b_{ij}^{{}^{\prime}\text{min},\left(\iota=I^{\text{th}}\right)}=&\frac{b_{ij}^{{}^{\prime}\text{max}}-b_{ij}^{{}^{\prime}\text{min}}}{N_{b}^{I-1}}\cdot\max\left\\{\sum_{s=1}^{I-1}N_{b}^{s-1}\cdot
n^{*\left(\iota=(I-s)^{\text{th}}\right)}_{b}-1,0\right\\}+b_{ij}^{{}^{\prime}\text{min}}\\\
\end{split}$ (C.6)

$\displaystyle\begin{split}\lvert
b_{ij}^{{}^{\prime}*}-b^{{}^{\prime}}_{ijn^{*\left(\iota=I-1\right)}_{b}}\rvert\leq\left(b_{ij}^{{}^{\prime}\text{max}}-b_{ij}^{{}^{\prime}\text{min}}\right)\cdot\frac{2}{N_{b}^{I-1}}\end{split}$
(C.7)

If $b_{\text{maxgap}}=\max_{i,j}\lvert
b_{ij}^{{}^{\prime}\text{max}}-b_{ij}^{{}^{\prime}\text{min}}\rvert$ among all
$i$ in the state space solution grid and all $j\in J$, then with $N_{b}=50$
and $\left(\iota\right)=3$: $\lvert
b_{ij}^{{}^{\prime}*}-b^{{}^{\prime}}_{ijn^{*\left(\iota=3\right)}_{b}}\rvert\leq\frac{b_{\text{maxgap}}}{62500}\text{
, }\forall i\text{ and }\forall j$.

####  C.1.2 Value Function Iteration and Expectation

To solve the dynamic stochastic programming problem, within a value function
iteration step and after optimization, I integrate over the value of the
continuation value function in Equation (4):

$\displaystyle
E_{\epsilon,\Phi}\left({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}v}\left(\mathcal{A},k,b,\epsilon,\Phi\right)\right)$
$\displaystyle=\int\int\max_{j\in
J}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}v_{j}}\left(\mathcal{A},k,b,\epsilon,\phi_{j}\right)\mathrm{d}F\left(\Phi\right)\mathrm{d}F\left(\epsilon\right)\thinspace,$

where $\left\\{\phi_{j}\right\\}_{j\in\left\\{1,...7\right\\}}$ are assumed
i.i.d and extreme-value Type I distributed. Hence:

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\upsilon}\left(\mathcal{A},k,b,\epsilon\right)=\int\max_{j\in
J}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}v_{j}}\left(\mathcal{A},k,b,\epsilon,\phi_{j}\right)\mathrm{d}F\left(\Phi\right)=\log\left(\sum_{j\in
J}\exp\left({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\hat{v}_{j}}\left(\mathcal{A},k,b,\epsilon\right)/\sigma_{\phi}\right)\right)\thinspace.$
(C.8)

Using the optimization routine described earlier, I solve
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\upsilon}\left(\mathcal{A},k,b,\epsilon\right)$
at all combinations of a grid of $k$, a grid of $b$, and three $\epsilon$ grid
points
$\epsilon\in\left\\{\epsilon-3\sigma_{\epsilon},0,\epsilon+3\sigma_{\epsilon}\right\\}$.
I obtain an $\mathcal{A}$ specific interpolant
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}E\widetilde{\upsilon}}_{\mathcal{A}}\left(\mathit{\mathcal{W}}\left(\mathcal{A},k,b,\epsilon\right),k\right)$
based on multi-linear spline. Using
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}E\widetilde{\upsilon}}_{\mathcal{A}}$
in combination with $D$ $\epsilon$ draws for each
$\left(b,k\right)$,C.8C.8C.8To avoid extrapolation, I restrict the $\epsilon$
draws to be within the $\epsilon$ points where I solved
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\upsilon}$.
I approximate this expectation:

$E_{\epsilon}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\upsilon}\left(\mathcal{A},k,b,\epsilon\right)\approx\frac{1}{D}\sum_{d}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}E\widetilde{\upsilon}}_{\mathcal{A}}\left(\left\\{b+\left(1-\delta\right)k+\exp\left(\epsilon_{D}+\mathcal{A}\right)\cdot
k^{\alpha}\right\\},k\right)$ $\textit{Interpolants, 1st:
}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}E\widetilde{\upsilon}}_{\mathcal{A}}\left(\mathit{\mathcal{W}}\left(\mathcal{A},k,b,\epsilon\right),k\right)\textit{
2nd:
}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}E\accentset{\approx}{\upsilon}}_{\mathcal{A}}\left(b,k\right)$

With these simulated averages, I estimate a second $\mathcal{A}$ specific
interpolant
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}E\accentset{\approx}{\upsilon}}_{\mathcal{A}}\left(b,k\right)$
based on multi-linear spline. This second interpolant captures the
differential marginal effects on expected future utility from investments in
safe and risky assets. I substitute the
${{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}E\accentset{\approx}{\upsilon}}_{\mathcal{A}}}$
for the integral over expected value function in Equation (4). Value function
iteration continues until convergence. The method here is similar in structure
to the value function approximation method in [34].C.9C.9C.9[34] present a
model with both continuous state space and continuous choice space. In that
model, individuals make human capital and financial asset choices.

It should be noted that the multinomial logit assumption for credit category
shocks significantly reduces the integration burdens here. As an alternative,
multinomial normal errors would accommodate correlations among discrete
category shocks with a seven by seven variance-covariance matrix for the seven
credit alternatives. Estimating the covariance matrix would substantially add
to estimation costs. In the context of this paper, the gains of allowing for
multinomial normal errors might be limited. First, the dominant drivers for
credit market participation are asset positions and productivity types, which
are captured by the modeled component of the choice-specific value functions.
Second, credit categories share the same productivity shocks, which means that
overall uncertainty is not uncorrelated across credit category alternatives.

An additional issue to note is that due to the multinomial shocks, CEV changes
can not be computed analytically following standard procedures under CRRA
preference assumptions [18]. For the welfare analysis, holding policy
functions constant, I recompute value functions for each element of a dense
grid of consumption percentage changes. The resulting array of values for each
state-space element is compared against value function outputs under policy
shifts to find the percentage consumption changes that minimize the
differences.

####  C.1.3 Steady State Distribution Conditional on Type

##### Conditional $\mathcal{W}^{{}^{\prime}}$ distribution

The stationary asset distribution is determined by the conditional transition
$f\left(\mathcal{W}^{{}^{\prime}}\mid\mathcal{W}\right)$, which equals to:

$\displaystyle\begin{split}f\left(\mathcal{W}^{{}^{\prime}}\mid\mathcal{W}\right)=\int_{\mathcal{A}}\sum_{j}P_{j}\left(\mathcal{A},\mathit{\mathcal{W}}\right)f\left(\mathcal{W}^{{}^{\prime}}\mid\mathcal{A},\mathcal{W},j\right)f\left(\mathcal{A}\right)\mathrm{d}\mathcal{A}\thinspace\thinspace.\\\
\end{split}$ (C.9)

Given the structure of the problem,
$f\left(\mathcal{W}^{{}^{\prime}}\mid\mathcal{A},\mathcal{W},j\right)$ is:

$\displaystyle\begin{split}f\left(\mathcal{W}^{{}^{\prime}}\mid\mathcal{A},\mathcal{W},j\right)=\begin{cases}0&\text{
if
}\mathcal{W}^{{}^{\prime}}\leq\mathcal{W}^{{}^{\prime}\text{min}}\left(\mathcal{A},\mathcal{W},j\right)\\\
f_{\epsilon}\left(\epsilon^{*}\left(\mathcal{W}^{{}^{\prime}}\right)\right)&\text{
otherwise }\\\ \end{cases}\thinspace\thinspace,\end{split}$ (C.10)

where:

$\displaystyle\begin{split}\mathcal{W}^{{}^{\prime}\text{min}}\left(\mathcal{A},\mathcal{W},j\right)&=\mathit{k^{{}^{\prime}}_{j}}\left(\mathcal{A},\mathit{\mathcal{W}}\right)\left(1-\delta\right)+\mathit{b^{{}^{\prime}}_{j}}\left(\mathcal{A},\mathit{\mathcal{W}}\right)+y^{\text{min}}\\\
\epsilon^{*}\left(\mathcal{W}^{{}^{\prime}}\right)&=\log\left(\dfrac{\mathcal{W}^{{}^{\prime}}-\mathcal{W}^{{}^{\prime}\text{min}}\left(\mathcal{A},\mathcal{W},j\right)}{\exp(\mathcal{A})\cdot\mathit{k^{{}^{\prime}}_{j}}\left(\mathcal{A},\mathit{\mathcal{W}}\right)^{\alpha}}\right)\\\
\end{split}$ (C.11)

Hence, the conditional probability that $\mathcal{W}^{{}^{\prime}}$ falls
between
$\left[\mathcal{W}^{{}^{\prime}}_{x},\mathcal{W}^{{}^{\prime}}_{y}\right]$ is:

$\displaystyle\begin{split}P\left(\mathcal{W}^{{}^{\prime}}_{y}-\mathcal{W}^{{}^{\prime}}_{x}\mid\mathcal{A},\mathcal{W},j\right)=\begin{cases}0&\text{
if
}\mathcal{W}^{{}^{\prime}}_{x}\leq\mathcal{W}^{{}^{\prime}\text{min}}\left(\mathcal{A},\mathcal{W},j\right)\\\
F_{\epsilon}\left(\epsilon^{*}\left(\mathcal{W}^{{}^{\prime}}_{y}\right)\right)-F_{\epsilon}\left(\epsilon^{*}\left(\mathcal{W}^{{}^{\prime}}_{x}\right)\right)&\text{
otherwise}\\\ \end{cases}\end{split}$ (C.12)

The method described here follows the spirit of the inverse decision rule
method [56].

##### Discretizing Conditional $\mathcal{W}^{{}^{\prime}}$ distribution

I discretize $\mathcal{W}$ along a grid with $N_{\mathcal{W}}$ grid points.
The mid-points sequence with $N_{\mathcal{W}}-1$ elements is
$\left\\{\mathcal{W}_{{n_{\mathcal{W}}}}\right\\}^{N_{\mathcal{W}}-1}_{{n_{\mathcal{W}}}=1}$
where
$\mathcal{W}_{{n_{\mathcal{W}}}}=\left(\frac{\mathcal{W}^{\text{max}}-\mathcal{W}^{\text{min}}}{N_{\mathcal{W}}}\right)\cdot\left({n_{\mathcal{W}}}+0.5\right)+\mathcal{W}^{\text{min}}$.
The corresponding end-points sequence is
$\left\\{\mathcal{W}_{\widehat{{n_{\mathcal{W}}}}}^{{}^{\prime}}\right\\}^{N_{\mathcal{W}}}_{\widehat{{n_{\mathcal{W}}}}=1}$
where
$\mathcal{W}_{\widehat{{n_{\mathcal{W}}}}}^{{}^{\prime}}=\left(\frac{\mathcal{W}^{\text{max}}-\mathcal{W}^{\text{min}}}{N_{\mathcal{W}}}\right)\cdot\left(\widehat{{n_{\mathcal{W}}}}\right)+\mathcal{W}^{\text{min}}$.
Given these, I define:

$\displaystyle\begin{split}P\left(\mathcal{W}_{{n_{\mathcal{W}}}}^{{}^{\prime}}\mid\mathcal{A},\mathcal{W}_{{n_{\mathcal{W}}}},j\right)\coloneqq
P\left(\mathcal{W}_{(\widehat{{n_{\mathcal{W}}}}+1)}^{{}^{\prime}}-\mathcal{W}_{\widehat{{n_{\mathcal{W}}}}}^{{}^{\prime}}\mid\mathcal{A},\mathcal{W}_{{n_{\mathcal{W}}}},j\right)\thinspace,\end{split}$
(C.13)

where the right-hand side is evaluated using Equation (C.12). The discretized
conditional cash-on-hand distribution for a particular productivity type
$\mathcal{A}_{q}$ is:

$\displaystyle\begin{split}P\left(\mathcal{W}_{{n_{\mathcal{W}}}}^{{}^{\prime}}\mid\mathcal{A}_{q},\mathcal{W}_{{n_{\mathcal{W}}}}\right)=\sum_{j}P_{j}\left(\mathcal{A}_{q},\mathcal{W}_{{n_{\mathcal{W}}}}\right)P\left(\mathcal{W}_{{n_{\mathcal{W}}}}^{{}^{\prime}}\mid\mathcal{A}_{q},\mathcal{W}_{{n_{\mathcal{W}}}},j\right)\thinspace.\\\
\end{split}$ (C.14)

Given the policy functions derived in Sections C.1.1 and C.1.2, computing this
conditional probability for all current- and next-period grid points involves
simply finding the cumulative normal probabilities over a matrix of quantile
points. The procedure is vectorizable and almost instantaneous. When there are
multiple persistent shocks, the potential dimensionality of this discretized
full-states transition matrix increases exponentially. However, the
computational size increases only linearly with the usage of sparse matrices.
C.10C.10C.10For examples with multiple persistent shocks, see Dynamic Asset
Code Repository.

##### Discretized marginal $\mathcal{W}^{{}^{\prime}}$ distribution

I now solve for
$P\left(\mathcal{W}_{{n_{\mathcal{W}}}}\mid\mathcal{A}_{q}\right)$ using
$P\left(\mathcal{W}_{{n_{\mathcal{W}}}}^{{}^{\prime}}\mid\mathcal{A}_{q},\mathcal{W}_{{n_{\mathcal{W}}}}\right)$
following standard first order Markov transition procedure. At this stage,
either an eigenvector or projection approach could be taken. The projection
approach is more stable generally, but some languages’ eigenvector algorithm
is more efficient for large sparse full-states transition matrices. For
projection, suppose $b$ is a $1\times(N_{\mathcal{W}}-1)$ vector, which is all
zero except for the final element which equals $1$, $Q$ is the
$(N_{\mathcal{W}}-1)\times(N_{\mathcal{W}}-1)$ Markov transition matrix where
each row corresponds to a different $\mathcal{W}_{{n_{\mathcal{W}}}}$ and each
cell corresponds to
$P\left(\mathcal{W}_{{n_{\mathcal{W}}}}^{{}^{\prime}}\mid\mathcal{A}_{q},\mathcal{W}_{{n_{\mathcal{W}}}}\right)$
minus corresponding values in an identity matrix. Given these, I compute
$P=\left(b\cdot Q^{\intercal}\right)\cdot\left(Q\cdot
Q^{\intercal}\right)\raisebox{4.95134pt}{$\scriptscriptstyle-\\!1$}$, where
each ${n_{\mathcal{W}}}$ element of matrix $P$ is equal to the marginal
distribution for $\mathcal{W}_{{n_{\mathcal{W}}}}$ conditional on
$\mathcal{A}_{q}$,
$P_{{n_{\mathcal{W}}}}=P\left(\mathcal{W}_{{n_{\mathcal{W}}}}\mid\mathcal{A}_{q}\right)$.
As the number of discrete points increases, the discretized marginal
distribution approaches the continuous marginal distribution.

####  C.1.4 Integration over Productivity Types

Integration over types and solving for equilibrium interest rate both involve
solving the model at different parameters. This is in contrast to the solution
procedures described in Sections C.1.1, C.1.2, and C.1.3, where computations
share common instructions and benefit from vectorization-based
parallelization. Here, I solve the model at different productivity types and
interest rates in separate concurrent processes.

I assume that the productivity type is normal, and lognormal with respect to
output. I solve the model concurrently along a sequence of productivity types
$\left\\{\mathcal{A}_{q}\right\\}^{Q}_{q=1}$ where
$\mathcal{A}_{q}=z_{q}\cdot\sigma_{\mathcal{A}}\cdot\sqrt{2}+\mu_{\mathcal{A}}$.
$\left\\{z_{q}\right\\}^{Q}_{q=1}$ are Hermite Quadrature points, with
associated weights sequence $\left\\{\omega_{q}\right\\}^{Q}_{q=1}$. Following
the previous section’s notations, the unconditional distribution of
$\mathcal{W}$ is approximated by:

$\displaystyle\begin{split}\int_{x=\mathcal{W}_{\widehat{{n_{\mathcal{W}}}}}^{{}^{\prime}}}^{y=\mathcal{W}_{(\widehat{{n_{\mathcal{W}}}}+k)}}f\left(\mathcal{W}\right)\mathrm{d}\mathcal{W}\approx&\sum_{{n_{\mathcal{W}}}=\widehat{{n_{\mathcal{W}}}}}^{(\widehat{{n_{\mathcal{W}}}}+k-1)}\sum_{q=1}^{Q}\frac{1}{\sqrt{\pi}}\cdot\omega_{q}\cdot
P\left(\mathcal{W}_{{n_{\mathcal{W}}}}\mid\mathcal{A}_{q}\right)\\\
\end{split}$ (C.15)

####  C.1.5 Equilibrium Interest Rates

##### Multi-section algorithm

To solve for the equilibrium interest rate, I solve the model in
$\left(\tau\right)$ iterations and during each iteration concurrently at $G$
different interest rate points. If $G=1$, this is equivalent to bisection. In
each iteration, I find:C.11C.11C.11The initial minimum and maximum interest
rates should be picked to generate more borrowing than savings and more
savings than borrowing, respectively. Given that, Equation (C.16) looks for
the smallest borrowing and savings gap among rates that generate more
borrowing than savings.

$\displaystyle\begin{split}r^{I}_{m^{\left(\tau\right)*}}=\operatorname*{arg\,max}_{r^{I}\in\left\\{r^{I}_{m^{\left(\tau\right)}}\right\\}_{m^{\left(\tau\right)}=1}^{M^{\left(\tau\right)}}}\left\\{\widehat{\mathrm{E}}\left(b^{{}^{\prime}I};r^{I}\right)\mid\widehat{\mathrm{E}}\left(b^{{}^{\prime}I};r^{I}\right)<0\right\\}\thinspace,\\\
\end{split}$ (C.16)

where the net difference in borrowing savings is:

$\displaystyle\begin{split}\widehat{\mathrm{E}}_{\mathcal{A}_{q}}\left(b^{{}^{\prime}I};r^{I}_{m^{\left(\tau\right)}}\right)=&\sum_{n_{\mathcal{W}}}P\left(\mathcal{W}_{{n_{\mathcal{W}}}}\mid\mathcal{A}_{q};r^{I}_{m^{\left(\tau\right)}}\right)\cdot\left(\sum_{j}P_{j}\left(\mathcal{A}_{q},\mathcal{W}_{{n_{\mathcal{W}}}};r^{I}_{m^{\left(\tau\right)}}\right)\cdot\mathit{b^{{}^{\prime}I}_{j}}\left(\mathcal{A}_{q},\mathcal{W}_{{n_{\mathcal{W}}}};r^{I}_{m^{\left(\tau\right)}}\right)\right)\\\
\widehat{\mathrm{E}}\left(b^{{}^{\prime}I};r^{I}_{m^{\left(\tau\right)}}\right)=&\sum_{q=1}^{Q}\left(\frac{1}{\sqrt{\pi}}\cdot\omega_{q}\right)\cdot\widehat{\mathrm{E}}_{\mathcal{A}_{q}}\left(b^{{}^{\prime}I};r^{I}_{m^{\left(\tau\right)}}\right)\\\
\end{split}$ (C.17)

and where the discrete constrained choice set for each $\left(\tau\right)$
evolves following:

$\displaystyle\begin{split}\left\\{r^{I}_{m^{\left(\tau+1\right)}}\right\\}_{m^{\left(\tau+1\right)}=1}^{M^{\left(\tau+1\right)}=M^{\left(\tau\right)}+G}=\left\\{r^{I}_{m^{\left(\tau\right)}}\right\\}_{m^{\left(\tau\right)}=1}^{M^{\left(\tau\right)}}\cup\left\\{r_{g}\mid\begin{array}[]{c}\dfrac{r^{I}_{m^{\left(\tau\right)*}+1}-r^{I}_{m^{\left(\tau\right)*}}}{G+1}\cdot
g+r^{I}_{m^{\left(\tau\right)*}}\\\ \text{, }g\in\mathbb{N}\text{, }1\leq
g\leq G\\\ \end{array}\right\\}\thinspace.\end{split}$ (C.18)

If the equilibrium rate is between $1.00$ and $1.30$, setting $G=8$, after
$\left(\tau=3\right)$ iterations, I arrive at an approximated equilibrium
interest rate within $0.053$ percentage points of the equilibrium interest
rate:
$\widehat{r}^{I,equi}=r^{I}_{m^{\left(\tau+3\right)},G=8}\in\left[r^{I,equi}-0.00053,r^{I,equi}+0.00053\right]$.

At some values of the fixed costs parameters, given grids on productivity and
assets, in the absence of the credit category shocks, there might be no
households that are willing to save or borrow within the bounds on interest
rates. The credit category shocks help to improve the numerical stability of
equilibrium solution and estimation by assuring non-zero aggregate borrowing
and savings levels as the estimator explores possibly high fixed costs.

Overall, solving the model involves Monte-Carlo integration for expected value
function, weighting the probabilities of each credit participation category
$j$, the analytical integration of
$P\left(\mathcal{W}^{{}^{\prime}}_{y}-\mathcal{W}^{{}^{\prime}}_{x}\mid\mathcal{A},\mathcal{W},j\right)$,
Riemann-sum mid-point integration to approximate
$\int_{x=\mathcal{W}_{\widehat{{n_{\mathcal{W}}}}}^{{}^{\prime}}}^{y=\mathcal{W}_{(\widehat{{n_{\mathcal{W}}}}+k)}}f\left(\mathcal{W}|\mathcal{A}_{q}\right)\mathrm{d}\mathcal{W}$,
and the Hermite Quadrature integration here.

##### Tradeoffs between $G$ and $\left(\tau\right)$

Table C.1: Concurrency and iteration: solving equilibrium, if $r^{I,equi}\in[1.0,1.3]$ |  $G=1$ 1 model evaluation per iteration (bisection) |  $G=4$ 4 concurrent model evaluations per iteration |  $G=8$ 8 concurrent model evaluations per iteration
---|---|---|---
_Iterations_ |  Number of Model Evaluations |  Accuracy ($r^{I}$ percentage points) |  Number of Model Evaluations |  Accuracy ($r^{I}$ percentage points) |  Number of Model Evaluations |  Accuracy ($r^{I}$ percentage points)
$\left(\tau=1st\right)$ |  3 |  15 |  4 |  10 |  8 |  4.3
$\left(\tau=2nd\right)$ |  4 |  7.5 |  8 |  2 |  16 |  0.48
$\left(\tau=3rd\right)$ |  5 |  3.75 |  12 |  0.3 |  24 |  0.053
$\left(\tau=6th\right)$ |  8 |  0.47 |  24 |  0.00003 |  48 |  0.0000007

Table C.1 explains the trade-off between $G$ and $\left(\tau\right)$. If
concurrent model evaluation is not possible due to computing limitations,
bisection is the most efficient as shown in Table C.1 in terms of the number
of model evaluationsC.12C.12C.12Model evaluation refers to the number of times
the model has to be solved for up to and including integrating over
productivity types. required to reach a fixed level of accuracy. Bisection
achieves higher precision with 9 model evaluations than $G=4$ (4 concurrent
model evaluations) achieves with 12 model evaluations. When computing
resources are available, as shown in Table C.1, to achieve about 0.5
percentage point equilibrium interest rate accuracy, $G=8$ requires only 2
iterations, using one-third of the time as bi-section.

###  C.2 Estimation Algorithm

####  C.2.1 Algorithm

I describe in this section the four steps of the more parallel estimation
algorithm summarized in Section 4.3. First, I draw $\mathcal{N}$ sets of
parameters:

$\left\\{\Theta_{\mathit{n}}\right\\}_{\mathit{n}=1}^{\mathcal{N}}=\left\\{\left\\{\theta_{\mathit{n}\mathit{q}}\right\\}_{\mathit{q}=1}^{\mathcal{Q}}\right\\}_{\mathit{n}=1}^{\mathcal{N}}$

Draws are made uniformly within upper and lower bounds for each parameter,
$\theta_{\mathit{n}\mathit{q}}\in\left[\theta_{\mathit{q}}^{\text{min}},\theta_{\mathit{q}}^{\text{max}}\right]$.
For each draw, I evaluate the model at $\mathcal{M}$ relevant components of
the estimation objective function.C.13C.13C.13These could be different moments
for moment estimation, or they could be different individual components of the
likelihood function. For my estimation here, $\mathcal{M}$ equals the number
of households in each region plus the gaps between observed and model
generated period specific equilibrium informal interest rates. This means that
there is a separate polynomial approximation for each household’s contribution
to the overall likelihood. This creates a $\mathcal{N}{\times}\mathcal{M}$
matrix $\mathbb{\mathcal{O}}$, where each element
$\mathbb{\mathcal{O}}_{\mathit{n}}^{\mathit{m}}\left(\left\\{\theta_{\mathit{n}\mathit{q}}\right\\}_{\mathit{q}=1}^{\mathcal{Q}}\mid\mathbb{\mathcal{X}}_{\mathit{m}}\right)$
is determined by the $\mathit{m}^{\text{th}}$ component of the estimation
objective function, the $\mathit{n}^{\text{th}}$ set of randomly drawn
parameters, and $\mathit{m}$ specific data matrix
$\mathbb{\mathcal{X}}_{\mathit{m}}$.

Second, I approximate the estimation objective function using
polynomials.C.14C.14C.14Solving the dynamic programming problem often involves
interpolation, sometimes using polynomials [42]. In my solution algorithm, I
used multi-linear spline rather than polynomials to preserve the relative
expected returns of the safe and risky assets in Section C.1.2. The idea here
is to use polynomials to approximate potentially not only the value function
but also components of the estimation objective function. For each set of
$\mathcal{Q}$ parameters from the $\mathcal{N}$ draws, I create a
$\mathcal{D}^{\text{th}}$ order full polynomial with $\mathcal{P}$ polynomial
terms.C.15C.15C.15Given $\mathcal{Q}=15$ and $\mathcal{D}=3$, then
$\mathcal{P}=816$. Full third order polynomial means all polynomial
combinations with degree less than or equal to $3$. The number of polynomial
terms equal to:
$\mathcal{P}=\underbrace{\left(0\right)}_{\begin{subarray}{c}0^{\text{th}}\text{
Deg.}\\\ \text{i.e.: }1\\\
\end{subarray}}+\underbrace{\left(\mathcal{Q}\right)}_{\begin{subarray}{c}1^{\text{st}}\text{
Deg.}\\\ \text{i.e.: }x\text{, }y\\\
\end{subarray}}+\underbrace{\left(\mathcal{Q}+\binom{\mathcal{Q}}{2}\right)}_{\begin{subarray}{c}2^{\text{nd}}\text{
Degree}\\\ \text{i.e.: }x^{2}\text{, }x\cdot y\text{, }y^{2}\\\
\end{subarray}}+\underbrace{\left(\mathcal{Q}+\mathcal{Q}\cdot\left(\mathcal{Q}-1\right)+\binom{\mathcal{Q}}{3}\right)}_{\begin{subarray}{c}3^{\text{rd}}\text{
Degree}\\\ \text{i.e.: }x^{3}\text{, }x^{2}\cdot y\text{, ... }x\cdot
y^{2}\text{, }y^{3}\\\ \end{subarray}}$ (C.19) Standard machine learning
packages have routines that generate full polynomials, I use the
PolynomialFeatures module from scikits.learn. This creates a
$\mathcal{N}{\times}\mathcal{P}$ matrix of polynomials. I regress each
$\mathit{m}$ column of matrix $\mathbb{\mathcal{O}}$ on the polynomial matrix.
$\mathbb{\mathcal{R}}$ denotes the $\mathcal{M}{\times}\mathcal{P}$
coefficient matrix. For $\mathcal{D}=3$, for each $\mathit{m}$,
$\mathbb{\mathcal{R}}_{0}^{\mathit{m},0}$ is the intercept,
$\mathbb{\mathcal{R}}^{\mathit{m},1}$ is the coefficients vector for the
linear terms, $\mathbb{\mathcal{R}}^{\mathit{m},2}$ is the coefficients vector
for the quadratic terms, and $\mathbb{\mathcal{R}}^{\mathit{m},3}$ is the
coefficients vector for the cubic terms. Specifically:

$\begin{split}\mathbb{\mathcal{O}}_{\mathit{n}}^{\mathit{m}}\left(\left\\{\theta_{\mathit{n}\mathit{q}}\right\\}_{\mathit{q}=1}^{\mathcal{Q}}\mid\mathbb{\mathcal{X}}_{\mathit{m}}\right)=&\mathbb{\mathcal{R}}_{0}^{\mathit{m},0}+\sum_{\mathit{q}_{1}=1}^{\mathcal{Q}}\left(\mathbb{\mathcal{R}}_{\mathit{q}_{1}}^{\mathit{m},1}\theta_{\mathit{n}\mathit{q}_{1}}\right)\\\
&+\sum_{\mathit{q}_{1}=1}^{\mathcal{Q}}\left(\sum_{\mathit{q}_{2}=1}^{\mathit{q}_{2}\leqslant\mathit{q}_{1}}\left(\mathbb{\mathcal{R}}_{\mathit{q}_{1}\mathit{q}_{2}}^{\mathit{m},2}\theta_{\mathit{n}\mathit{q}_{1}}\theta_{\mathit{n}\mathit{q}_{2}}\right)\right)\\\
&+\sum_{\mathit{q}_{1}=1}^{\mathcal{Q}}\left(\sum_{\mathit{q}_{2}=1}^{\mathit{q}_{2}\leqslant\mathit{q}_{1}}\left(\sum_{\mathit{q}_{3}=1}^{\mathit{q}_{3}\leqslant\mathit{q}_{2}}\left(\mathbb{\mathcal{R}}_{\mathit{q}_{1}\mathit{q}_{2}\mathit{q}_{3}}^{\mathit{m},3}\cdot\theta_{\mathit{n}\mathit{q}_{1}}\theta_{\mathit{n}\mathit{q}_{2}}\theta_{\mathit{n}\mathit{q}_{3}}\right)\right)\right)\\\
&+\mathit{e}_{\mathit{n}}^{\mathit{m}}\\\ \end{split}$ (C.20)

After $\mathcal{M}$ regressions, I obtain a $\mathcal{M}{\times}\mathcal{P}$
matrix of regression coefficients:

$\hat{\mathbb{\mathcal{R}}}(\left\\{\theta_{\mathit{n}\mathit{q}}\right\\}_{\mathit{q}=1}^{\mathcal{Q}},\mathbb{\mathcal{X}})=\left[\begin{array}[]{@{}c|ccc|ccc|ccc@{}}\hat{\mathbb{\mathcal{R}}}^{1,0}&\hat{\mathbb{\mathcal{R}}}^{1,1}_{1}&\ldots&\hat{\mathbb{\mathcal{R}}}^{1,1}_{\mathcal{Q}}&\hat{\mathbb{\mathcal{R}}}^{1,2}_{1,1}&\ldots&\hat{\mathbb{\mathcal{R}}}^{1,2}_{\mathcal{Q},\mathcal{Q}}&\hat{\mathbb{\mathcal{R}}}^{1,3}_{1,1,1}&\ldots&\hat{\mathbb{\mathcal{R}}}^{1,3}_{\mathcal{Q},\mathcal{Q},\mathcal{Q}}\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
\hat{\mathbb{\mathcal{R}}}^{\mathcal{M},0}&\hat{\mathbb{\mathcal{R}}}^{\mathcal{M},1}_{1}&\ldots&\hat{\mathbb{\mathcal{R}}}^{\mathcal{M},1}_{\mathcal{Q}}&\hat{\mathbb{\mathcal{R}}}^{\mathcal{M},2}_{1,1}&\ldots&\hat{\mathbb{\mathcal{R}}}^{\mathcal{M},2}_{\mathcal{Q},\mathcal{Q}}&\hat{\mathbb{\mathcal{R}}}^{\mathcal{M},3}_{1,1,1}&\ldots&\hat{\mathbb{\mathcal{R}}}^{\mathcal{M},3}_{\mathcal{Q},\mathcal{Q},\mathcal{Q}}\end{array}\right]$
(C.21)

Third, I estimate the model now by evaluating the objective function using the
polynomial approximation matrix $\hat{\mathbb{\mathcal{R}}}$:

$\min_{\begin{subarray}{c}\Theta\\\ \text{initialize at:
}\Theta_{\mathit{n}}\\\
\end{subarray}}\hat{\mathbb{\mathcal{O}}}\left(\left\\{\hat{\mathbb{\mathcal{O}}}^{\mathit{m}}\left(\left\\{\theta_{\mathit{q}}\right\\}_{\mathit{q}=1}^{\mathcal{Q}},\hat{\mathbb{\mathcal{R}}}^{\mathit{m}}\left(\mathbb{\mathcal{X}}_{\mathit{m}}\right)\right)\right\\}_{\mathit{m}=1}^{\mathcal{M}}\right)$
(C.22)

I estimate this approximated objective function at the $\mathcal{N}$ sets of
parameter draws. The parameter space should have the same bounds as before to
avoid extrapolation. Evaluating $\hat{\mathbb{\mathcal{O}}}$ is fast, and
derivative-based numerical algorithms can efficiently and stably obtain local
minima given polynomials. Initializing estimation at each
$\Theta_{\mathit{n}}$ draws, I obtain a vector of parameters,
$\left\\{\Theta^{*}_{\mathit{n}}\right\\}_{\mathit{n}=1}^{\mathcal{N}}$, which
locally minimize $\hat{\mathbb{\mathcal{O}}}$ given different starting points.

Fourth, I estimate the model with the non-polynomial approximated objective
functions using results from earlier steps as starting points. Specifically:

$\begin{split}\min_{\begin{subarray}{c}\Theta\\\ \text{initialize at:
}\Theta^{\text{init}}\\\
\end{subarray}}\mathbb{\mathcal{O}}\left(\left\\{\mathbb{\mathcal{O}}^{\mathit{m}}\left(\left\\{\theta_{\mathit{q}}\right\\}_{\mathit{q}=1}^{\mathcal{Q}}\mid\mathbb{\mathcal{X}}_{\mathit{m}}\right)\right\\}_{\mathit{m}=1}^{\mathcal{M}}\right)\\\
\text{where:
}\Theta^{\text{init}}=\operatorname*{arg\,min}_{\left\\{\Theta^{*}_{\mathit{n}}\right\\}_{\mathit{n}=1}^{\mathcal{N}}}\left\\{\hat{\mathbb{\mathcal{O}}}\left(\Theta^{*}_{1}\right)\text{,
...,
}\hat{\mathbb{\mathcal{O}}}\left(\Theta^{*}_{\mathcal{N}}\right)\right\\}\\\
\end{split}$ (C.23)

The first three steps provide Equation (C.23) with starting values that are
potentially close to the global minimizers. For this step, one could implement
standard routines and use parallel resources for multi-start. One could also
use parallel iterative optimizing algorithms [31]. If Equation (C.20) has very
high explanatory power, then $\Theta^{\text{init}}$ would be close to global
minimizers, and convergence should be fast. If Equation (C.20) has low
explanatory power, the first three steps of this algorithm might not improve
convergence speed for the fourth step. When that is the case, it indicates
potentially that convergence to a global minimum using any estimation routine
could be difficult, and the econometrician might need to adjust the estimation
objective function or transform the estimation parameter domain.

The first three steps described above are parallelizable. To implement, the
model would be solved concurrently across $\mathcal{N}$ parameter draws. In
the first step, the time it takes to solve the model $\mathcal{N}$ times is
the same as solving the model once. The second step involves $\mathcal{M}$
linear projections. The third step is also fully parallelizable, and each task
has a minimal computational footprint. The fourth step is computationally
intensive, but with the first three steps providing the final step with
potentially good initial guesses, the number of computationally-intensive full
estimation tasks is potentially dramatically lowered.

####  C.2.2 Container Orchestration

Container orchestration allows for large-scale multi-start simulation or
estimation. The idea is to first "containerize" the model codes and
dependencies, then specify the CPU and memory requirements of the container
and run separate processes across containers. Before proceeding to the
polynomial approximation step, all containerized tasks need to be completed.
Under managed container services, depending on the CPU-to-memory ratio as well
as the price and availability of EC2 units, AWS determines which sets of
machines to concurrently start to complete the containerized tasks.

####  C.2.3 AWS Cluster and Containers

I create computing clusters with the maximum CPU count set at 2560. For each
container, memory requirement is set at the maximum level required for solving
the model. Computing resources can be used more efficiently when the model
solution code has consistent and flat memory usages. I set the CPU requirement
for each containerized task at 8, and the memory requirement at 45 GB. An EC2
instance with 64 CPUs and 360 GB of memory can run eight containers
concurrently.

####  C.2.4 Costs

AWS launches a combination of these types of instances during my estimation
runs: m4.16xlarge instances (each with 64 virtual CPUs and 256 GB of memory),
m5.24xlarge instances (each with 96 virtual CPUs and 384 GB of memory), and
r4.16xlarge instances (each with 64 virtual CPUs and 488 GB of memory). Using
Spot pricings, these three main instance types in fall of 2018 generally cost
$1 per dollar (in the fall of 2018).

On average, the model algorithm, described previously, takes 2 minutes and 30
seconds to complete using 8 CPUs. For estimation, given each set of
parameters, I need to run the model four times for the two periods and two
regions. This means that given each set of parameters, finding the overall
estimation objective takes 10 minutes for each container.

For the initial step of the estimation process described in Section C.2.1, the
estimation objective is solved at 12800 random initial points (6400 for each
region). Given this, the first three steps of the estimation algorithm take
about 3 hours with total cluster maximum CPU count set at 2560, and costs
between $100 to $150. Holding the model fixed, if the econometrician decides
to change which components to include in the estimation objective or how they
are weighted, this first costly step does not need to be repeated.


#  Hi Model, generating nice instead of good is not as bad as generating rice!
Towards Context and Semantic Infused Dialogue Generation Loss Function and
Evaluation Metric

Abhisek Tiwari1, Muhammed Sinan1, Kaushik Roy2, Amit Sheth2, Sriparna Saha1
and Pushpak Bhattacharyya3
1Indian Institute of Technology Patna, India
2Artificial Intelligence Institute, University of South Carolina, USA
3Indian Institute of Technology Bombay, India

###### Abstract

Over the past two decades, dialogue modeling has made significant strides,
moving from simple rule-based responses to personalized and persuasive
response generation. However, despite these advancements, the objective
functions and evaluation metrics for dialogue generation have remained
stagnant, i.e., cross-entropy and BLEU, respectively. These lexical-based
metrics have the following key limitations: (a) word-to-word matching without
semantic consideration: It assigns the same credit for failure to generate
“nice” and “rice” for “good”. (b) missing context attribute for evaluating the
generated response: Even if a generated response is relevant to the ongoing
dialogue context, it may still be penalized for not matching the gold
utterance provided in the corpus. In this paper, we first investigate these
limitations comprehensively and propose a new loss function called Semantic
Infused Contextualized diaLogue (SemTextualLogue) loss function. Furthermore,
we formulate a new evaluation metric called Dialuation, which incorporates
both context relevance and semantic appropriateness while evaluating a
generated response. We conducted experiments on two benchmark dialogue
corpora, encompassing both task-oriented and open-domain scenarios. We found
that the dialogue generation model trained with SemTextualLogue loss attained
superior performance (in both quantitative and qualitative evaluation)
compared to the traditional cross-entropy loss function across the datasets
and evaluation metrics.

##  1 Introduction

Building a human-like conversational agent has always been one of the primary
goals of artificial intelligence Allen et al. (2001). Initially designed to
aid humans, it has now evolved to such a degree that it is even being employed
for casual conversation to fulfill the human desire for social interaction.
Started with ruled-based ALIZA to moving to advanced chatbots like
Alexa111https://developer.amazon.com/alexa and
ChatGPT222https://chat.openai.com/chat clearly evidence the relevance and
importance of building an adequate dialogue assistant. Over the past few
years, there has been significant progress in the advancement of task-oriented
dialogue assistants across several domains, even in sensitive areas such as
healthcare Chen et al. (2017). The primary expectation from an adequate
dialogue assistant is to provide an appropriate and contextually relevant
response Valizadeh and Parde (2022). To incorporate the objective and evaluate
the performance, a loss function, and evaluation metric are utilized. Thus,
loss function and evaluation metrics are the backbone and soul of a learning
framework.

Figure 1: Illustration of the key limitation of cross entropy for dialogue
generation. Some adequate responses ($y_{1}$ and $y_{2}$) are equally or more
penalized as useless response ($y_{2}$)

The most widely employed dialogue generation loss function is cross entropy
(CE). The CE loss used in dialogue generation was borrowed from machine
translation (MT) with the belief that the two tasks are identical. However,
there are some substantial differences between the two tasks Hu et al. (2020):
MT does not consider context, whereas it is a crucial aspect of dialogue
generation. Furthermore, MT emphasizes lexical-based matching of generated
text with reference target. The limitations caused by the discrepancies
between the tasks are demonstrated in Figure 1. The generation model with CE
loss has a fixed output expectation, which means that even semantically
relevant responses ($y_{1}$) are being unfairly punished to the same extent or
even more so than completely useless responses ($y_{2}$). The loss for the
third response ($y_{3}$) is much higher because it has no uni-gram matches
with the ground truth response. However, from a human perspective, the
generated response appears to be contextually relevant and aligned with the
reference response.

Our objective in AI-based models is to replicate the process of human
learning. Since humans are the ultimate consumers and evaluators of these
models, their perception of learning and evaluation is crucial. Recently, many
dialogue generation works have discovered that word-based evaluation metrics
do not strongly align with human judgment Sato et al. (2020). Humans consider
a response appropriate and relevant if it conveys a similar meaning as
expected in the context, rather than a word-to-word match. Based on this
observation, we were curious to investigate the importance of semantic-based
evaluation and context relevance for dialogue loss and evaluation functions.

Research Questions The paper aims to investigate the following three research
questions related to dialogue generation: (i) Can the addition of a semantic-
based evaluation component to the lexical-based loss function provide more
accurate feedback on generated responses and thus improve the overall quality
of dialogue generation? (ii) Can incorporating context relevance evaluation in
the loss function improve the model’s ability to generate responses that are
more appropriate and coherent to the discourse? (iii) Will integrating the
semantic component into the lexical-based evaluation metrics in dialogue
generation result in a better correlation with human judgment?

Key Contributions To address this, we develop a new dialogue generation loss
function that incorporates semantic and contextual appropriateness in addition
to lexical matching. Furthermore, we formulate a new context-infused,
semantic-aware dialogue generation evaluation metric to validate the
effectiveness of the loss function and assess its correlation with human
judgment. The key contributions are enumerated as follows:

  * •

We thoroughly examine, analyze, and present some of the major drawbacks of the
existing dialogue loss functions and evaluation metrics.

  * •

Inspired by human judgment, we propose a new dialogue function called
SemTextualLogue loss, which leverages semantic space to incorporate the
relevance of generated response and its relevance to the ongoing discourse.

  * •

We formulate a new dialogue generation evaluation metric named Dialution,
which incorporates semantic similarity and contextual relevance.

  * •

The proposed loss function archives state-of-the-art performances over
multiple datasets and across different evaluation metrics, including human
evaluation. Furthermore, the evaluation matrix was found to be more related to
human judgment compared to the existing matrices such as BLEU and ROUGE.

##  2 Background

The proposed work is relevant to the following three research areas: Dialogue
generation, Dialogue loss functions, and Dialogue generation evaluation
metrics. In the following paragraphs, we have summarized the relevant works
and highlighted the research gap.

Dialogue Generation Dialogue generation can be approached using two primary
methods: modular Griol et al. (2008), and end-to-end Serban et al. (2016). The
latter approach, end-to-end dialogue modeling, has gained popularity in recent
years as a result of the modular approach’s high demand for annotated data. In
the last few years, there have been three kinds of works carried out:
knowledge-grounded dialogue generation Zhao et al. (2020), transfer-learning-
based dialogue generation Golovanov et al. (2019), and multimodal dialogue
generation Shen et al. (2021). In Li et al. (2017), the authors build a
generative adversarial network (GAN) based dialogue generation framework. The
framework involves a sequence-to-sequence model serving as the generator
module and a reinforcement learning model acting as the discriminator. The
generator generates responses, while the discriminator evaluates the
distinguishability of the generated responses from the corpus and provides
feedback to the generator accordingly.
Dialogue Generation Loss Functions Table 1 illustrates all the existing
dialogue loss functions and some of their key limitations. In Kovaleva et al.
(2018), the authors have also considered generated words’ semantic similarity
with words of gold response in addition to word-to-word matching to mitigate
the fixed target issue. However, it’s worth noting that although they
incorporated word-to-word semantics, there could be cases where different word
arrangements have nearly identical meanings, such as with the phrases Nice to
see you and I am happy to meet you. The CE loss favors maximum likelihood, and
thus it suffers from a lack of diversity. To tackle this problem, the
researchers Ueyama and Kano (2020) devised an inverse n-gram frequency (INF)
loss function, which is a weighted cross-entropy function based on n-gram
frequency calculated from the entire corpus context. The INF loss function
assigns weights to n-gram mismatches based on the inverse of their frequency,
giving rare tokens more weight. This weighting mechanism results in more
diverse responses, effectively addressing the issue of low diversity.

loss function | Methodology | C | S | WK
---|---|---|---|---
Cross Entropy De Boer et al. (2005) | word probability distribution divergence | $\times$ | $\times$ | $\times$
FOCAL loss Wang et al. (2021) | token frequency aware cross entropy | $\times$ | $\times$ | $\times$
ITF loss Ueyama and Kano (2020) | token frequency aware cross entropy | $\times$ | $\times$ | $\times$
Inverse N-gram Nakamura et al. (2019) | n-gram frequency aware cross entropy | $\times$ | $\times$ | $\times$
FACE Jiang et al. (2019) | dynamic frequency aware cross entropy | $\times$ | $\times$ | $\times$
SBR Kovaleva et al. (2018) | CE loss with word wise semantic similarity | $\checkmark$ | $\times$ | $\times$

Table 1: Existing dialogue generation loss functions and their
characteristics. Here C, S, and WK denote context, semantic, and world
knowledge, respectively

Evaluation Metrics There are mainly two kinds of evaluation: automatic and
human. All the existing popular automatic dialogue generation evaluation
metrics are described in Table 2. The most utilized automatic evaluation
metrics include BLEU, ROUGE, and METEOR. Despite dialogue being a contextual
phenomenon, none of the metrics consider dialogue context for judging the
relevance of the generated text. Consequently, many recent dialogue generation
works and surveys Sato et al. (2020); Feng et al. (2021) on dialogue
generation have reported a poor correlation between these metrics and human
judgment. Most of them (other than BERT similarity) are based on the n-gram
overlap principle. In Zhang et al. , the authors proposed an embedding-based
BERT semantic similarity evaluation metric, which computes cosine similarity
between the BERT embeddings of generated text and expected response.

Evaluation Metric | Methodology | C | S | WK
---|---|---|---|---
BLEU Papineni et al. (2002) | n-gram overlap | $\times$ | $\times$ | $\times$
ROUGE Lin (2004) | n-gram overlap | $\times$ | $\times$ | $\times$
METEOR Banerjee and Lavie (2005) | n-gram overlap | $\times$ | $\times$ | $\times$
BERT Similarity Zhang et al. | embedding-based similarity | $\times$ | $\checkmark$ | $\times$
Sentiment Distance Conley et al. (2018) | sentiment coherence | $\times$ | $\times$ | $\times$
Jaccard Similarity Niwattanakul et al. (2013) | n-gram overlap | $\times$ | $\times$ | $\times$
SynSet Distance Conley et al. (2018) | semantic knowledge-base distance | $\times$ | $\checkmark$ | $\checkmark$
BLEURT Sellam et al. (2020) | pre-trained LLM | $\times$ | $\checkmark$ | $\times$

Table 2: Most widely used text generation evaluation metrics and their
limitations for dialogue generation. Here C, S, and WK denote context,
semantic, and world knowledge, respectively Figure 2: Proposed architecture of
semantic and context-reinforced dialogue generation. The encoder encodes
dialogue context and current utterance; the decoder generates output tokens
autoregressively. Based on the generated output, it calculates context and
semantic relevance score (Contanic) and reinforces the feedback with the
traditional cross-entropy loss

##  3 Proposed Methodology

In a typical dialogue generation model, there are two segments: encoder and
decoder. The former encodes dialogue context, and the latter generates a
sequence of words as a response. In order to incorporate the proposed dialogue
generation loss function easily into any generation framework, we added it on
top of the decoder. The proposed semantic and context-infused loss function
incorporated dialogue generation model is illustrated in Figure 2. It contains
the following sub-modules: encoder-decoder (Dialogue generation), Contanic,
and SemTexLogue loss. The working of each of the sub-modules is explained and
illustrated in the following sub-sections. Finally, we illustrate the
formulation of our proposed semantic and context-guided dialogue evaluation
metric called Dialution.

###  3.1 Dialogue Generation

The input sequence (context and current utterance) is first tokenized into a
sequence of tokens, and each token is represented as a vector using an
embedding layer. It computes an input embedding of each word of the input as
follows:

$h^{i}_{T},h^{i}_{P}=TE(u_{i}),PE(u_{i})$ (1)
$\hat{u_{i}}=h^{i}_{T}+h^{i}_{P}$ (2)

where $u_{i}$, $h^{i}_{T}$, and $h^{i}_{P}$ represent the $ith$ word of the
input, the word’s token embedding, and its positional embedding, respectively.
These embeddings are then fed into a multi-layered transformer encoder, which
consists of several identical layers, each of which performs two main
operations: multi-head self-attention and position-wise feed-forward networks.

In the proposed dialogue generation framework, the decoder unit is also a
transformer-based network. It takes the encoded representation ($h_{e}$) and
generates a token at each time step as follows:

$\hat{y}_{t}=argmax_{i}P(V_{i}|y_{1},y_{2},...,y_{t-1},h_{e})$ (3)

where $V$ denotes vocabulary space and $\hat{y}_{t}$ are the generated token
at $t^{th}$ time step. The final continuation of all generated tokens
represents the generated output sequence ($\hat{(}y)$).

###  3.2 Contanic Score

In traditional dialogue generation, the predicted probability distribution is
compared with the actual output sequence, and entropy deviation is calculated.
The deviation is back-propagated to the network, and the parameter gets
adjusted accordingly. In order to incorporate semantic and contextual adequacy
of the generated text, we added another component called context and semantic
based score called Contanic. It considers two fundamental expectations of a
dialogue response: context relevance and adequate response, which are computed
as follows:

Context Relevance Given a context, there may be several suitable responses, so
a fixed output matching approach usually suffers from a low diversity issue.
Instead, assessing the relevance of a generated response in the given context
and providing this feedback to the model would guide the model to generate
appropriate and coherent responses. Thus, we calculate the relevance of the
generated text for a context ($con$) as follows:

$CR=Cosine(e_{con},e_{gen})$ (4)

$e_{con}=BERT(<X_{1},Y_{1},X_{2},Y_{2}...X_{t-1},Y_{t-1},X_{t})$

(5)

where $e_{con}$, and $e_{gen}$ are the representations for dialogue context
and generated text, which are taken from BERT Devlin et al. (2018). Here, the
context is compromised of all previous utterances.

Semantic Similarity In natural language, we can convey the same information in
various ways, i.e., a different combination of words. Thus, semantic
evaluation is indeed a crucial factor in judging the adequateness of a
generated text. We calculate semantic similarity (SS) between the gold
sentence and generated response as follows:

$SS=Cosine(e_{gold},e_{gen})$ (6)

where $e_{gold}$ and $e_{gen}$ are semantic embedding representations for gold
response and generated text, respectively. Finally, the Contanic score is
computed as follows:

$Contanic=\alpha\cdot CR+\beta\cdot SS$ (7)

where $\alpha$ and $\beta$ are hyperparameters. We experimented with the two
different combinations of the CE loss and Contanic: (a) Weighted Cross-Entropy
and (b) Contanic Reinforced Dialogue generation called SemTextualLogue, which
are explained below.

###  3.3 Weighted Cross Entropy

We first experimented with the addition of Contanic and CE loss, which
performs as equivalent to CE loss. The reason was the non-differentiability of
the Contanic score due to the involvement of the argmax function, and the
added component becomes zero during backpropagation. To overcome this issue,
we further experimented with the multiplication of these scores as a loss
function. The weight parameter of the generation model is updated as follows:

$\displaystyle w_{new}$ $\displaystyle=w_{cur}-\alpha\frac{dl_{L}}{dw}$ (8)
$\displaystyle=w_{cur}-\alpha\frac{d(1-\text{contanic})L_{CE}}{dw}$
$\displaystyle=w_{cur}-\alpha(1-\text{contanic score})\frac{dL_{CE}}{dw}$

where $L$ and $\alpha$ denote total loss and learning rate, respectively. We
multiplied (1-contanic) with CE, as when gold utterance and generated text
were semantically similar but lexically different, the component (1-contanic)
would be lower, and the weightage to the CE loss would be reduced. Conversely,
when the contanic score is low (contextually and semantically less
appropriate), this component would be high, and thus the loss would be
prioritized accordingly.

###  3.4 SemTextualLogue Loss

Over the past few years, reinforcement learning has emerged as a highly
effective approach for integrating key aspects into a model. Inspired by its
effectiveness, we introduce a dialogue generation model based on reinforcement
learning that reinforces contextualization and semantic behavior in addition
to the conventional cross-entropy loss. We build a baseline estimator, which
acts as a human perception evaluator and reinforces the feedback as a reward.
The baseline estimator takes the output probability distribution from the
generation model and computes its relevance. The relevance estimate is
combined with the CE loss, and the final loss is computed. The loss
calculation is explained below.

$L_{final}=\lambda\cdot L_{CE}+(1-\lambda)\cdot L_{RL}+\sigma\cdot L_{BSE}$
(9) $L_{RL}=(1-BSEscore)\cdot L_{CE}$ (10)
$L_{CE}=-\sum_{j=0}^{j=n}p(y_{j})\log p(\hat{y_{j}})$ (11)
$L_{BSE}=MSE(BSEScore,ContanicScore)$ (12)

where $L_{CE}$, $L_{RL}$, and $L_{BSE}$ are the CE loss, reinforcement
learning loss, and baseline estimator loss, respectively. The term, $MSE$
indicates mean squared error loss. Here, $\lambda$ and $\sigma$ ($\lambda$,
$\sigma$ $\in$ [0, 1]) are hyperparameters. In the CE loss equation, $y$ and
$\hat{y}$ are true probability distributions and the influenced distribution
of the gold response and the generated response, respectively. Here, $n$ is
the output sequence length.

###  3.5 Dialution

The evaluation metrics, BLEU, ROUGE, and METEOR, only emphasize word-level
matching and overlook other crucial aspects of dialogue, such as context and
semantics, resulting in limited correlation with human judgments Liu et al.
(2016). One such example is illustrated in Figure 3. Response 1 is
semantically very similar to the gold response, but response 2 is neither
meaningful nor relevant to the context. Here, the automatic evaluation score
and human evaluation are not in sync with each other. This is because the
evaluation only looks at word matching, which overlooks the fact that words
like "fantastic" and "superb" carry a similar connotation.

Figure 3: One example demonstrating the significance of context and sentence
semantics for evaluating dialogue responses.

To overcome the conflicts, we first propose a contextualized semantic-driven
dialogue evaluation metric called Dialuation. Dialuation is a weighted average
of contextual relevance (CR) and semantic score (SS). It is determined as
follows:

$Dialution=(\frac{\delta_{c}\cdot CR+\delta_{ss}\cdot
SS}{\delta_{c}+\delta_{ss}})\cdot 100$ (13)

where $\delta_{c}$ and $\delta_{ss}$ ($\in$ [0, 1]) are the hyperparameters,
which signify the importance of contextual relevance and semantic similarity,
respectively. The Diluation score would lie between 0 to 100.

##  4 Experimental Setup

We have utilized the PyTorch framework for implementing the proposed model. We
have experimented with the two most widely used dialogue datasets: MultiWoz
2.2 Zang et al. (2020), and PersonaChat Zhang et al. (2018). The datasets’
statistics are provided in Table 3. The train-validation-test ratios for both
the datasets models were 8:1:1. We have considered a context window of 3,
i.e., dialogue context consists of only the last three utterances. The final
values for hyperparameters, which are determined empirically, are as follows:
source length (256), target length (256), learning rate (3e-05), batch size
(32), $\alpha$ (0.3 for MultiWoz), (0.2 for PersonaChat) $\beta$ (0.7),
$\sigma$ (1) and activation function (ReLU).

Entity |  MultiWoz 2.2 | PersonaChat
---|---|---
nature |  Task-oriented | Chit-Chat
# of dialogues |  9575 | 8938
# of utterances |  71,514 | 65,719
# of unique words |  25,714 | 18,417
avg dialogue length |  7.47 | 7.35

Table 3: Statistics of MultiWoz 2.2 and PersonaChat dialogue datasets

##  5 Result and Discussion

We employed the most popular automatic evaluation metrics, namely BLEU, Rouge,
and METEOR Papineni et al. (2002); Lin (2004); Banerjee and Lavie (2005), to
evaluate the generation quality with different loss functions.

Model | BLEU-1 | BLEU-2 | BELU-3 | BELU-4 | BLEU | ROUGE - 1 | ROUGE - 2 | ROUGE- L | METEOR
---|---|---|---|---|---|---|---|---|---
CE loss Shi et al. (2021) | 32.35 | 12.47 | 7.46 | 4.49 | 10.78 | 27.77 | 32.59 | 13.15 | 31.11
Weighted Semantic CE | 34.16 | 13.58 | 8.27 | 5.07 | 11.55 | 27.64 | 32.38 | 13.49 | 31.02
Weighted Semantic and context CE | 33.99 | 13.63 | 8.34 | 5.13 | 11.87 | 28.13 | 32.79 | 13.75 | 31.39
Semantic Reinforcement | 35.19 | 13.97 | 8.47 | 5.19 | 12.02 | 28.39 | 33.44 | 13.92 | 31.97
SemTextualLogueLoss | 33.64 | 13.06 | 7.73 | 4.60 | 11.18 | 28.56 | 33.43 | 13.64 | 31.95

Table 4: Performance of the dialogue generation framework with different loss
functions on MultiWoz dataset

Model | BLEU-1 | BLEU-2 | BELU-3 | BELU-4 | BLEU | ROUGE - 1 | ROUGE - 2 | ROUGE- L | METEOR
---|---|---|---|---|---|---|---|---|---
CE loss Shi et al. (2021) | 17.72 | 3.91 | 1.08 | 0.31 | 2.21 | 17.07 | 4.41 | 16.72 | 12.73
Weighted Semantic CE | 19.42 | 4.18 | 1.12 | 0.28 | 2.23 | 17.40 | 4.27 | 16.77 | 14.14
Weighted Semantic and Context CE | 19.69 | 4.19 | 1.16 | 0.37 | 2.30 | 17.47 | 4.40 | 17.15 | 12.96
Semantic Reinforcement | 18.85 | 4.33 | 1.16 | 0.33 | 2.36 | 15.96 | 4.18 | 15.63 | 13.52
SemTextualLogueLoss | 20.17 | 4.41 | 1.19 | 0.36 | 2.37 | 17.44 | 4.37 | 17.09 | 13.26

Table 5: Performance of the dialogue generation framework with different loss
functions on PersonaChat dataset

Baselines and Results To make the model generic, which could be applied to any
dialogue setting, we utilize only dialogue context, i.e., no additional
semantic information such as intent, slot, and belief state. Thus, we compared
the model with our baselines, and traditional CE loss utilized state-of-the-
art model that employs only dialogue context for response generation. The
performances of the dialogue generation model with different loss functions on
the MultiWoz and PersonChat datasets are reported in Table 4 and Table 5.
Table 6 and Table 7 summarize the performance of these loss functions in terms
of BERT score and the newly introduced evaluation metric called Dialuation.
All the reported values in the following tables are statistically significant,
which are validated using the statistical t-test Welch (1947) at a significant
level of 5%.
Human Evaluation To rule out the possibility of under informative assessment
carried out by automatic metrics, we conducted the human evaluation of 150
test samples from each dataset. In this assessment, three researchers (other
than the authors) were employed to evaluate the generated responses (50
samples of each model) of different models without revealing their names. The
samples are assessed based on the following five metrics: adequacy, fluency,
coherence, naturalness, and completeness on a scale of 0 to 5. The obtained
scores for both datasets are provided in Table 8 and Table 9.

Findings and Observations Based on the experimental findings, we report the
following answers (with evidence) to our investigated research questions
(RQs).

RQ 1: Can the addition of a semantic-based evaluation component to the
lexical-based loss function provide more accurate feedback on generated
responses and thus improve dialogue generation quality? The performances of
models with traditional CE and proposed Semantic Reinforcement and SemTexLogue
loss functions are reported in Table 4, Table 5 (in terms of traditional
evaluation metrics), Table 6, and Table 7 (in terms of BERT and Dialuation
scores). We can see a significant improvement across different metrics on the
datasets (CE vs Semantic Reinforcement): MultiWoz (BERT: +1.86, Dialution:
0.42, ROUGE-L: +1.38, and METEOR: +1.48), PersonaChat (BERT: +1.65, Dialution:
+3.30 ROUGE-L: +0.37, and METEOR: +0.53). Moreover, we also observed a
significant enhancement in human evaluation. These improvements firmly
establish that there is a role of semantic evaluation infusion in the loss
function.

#### RQ 2: Can incorporating context relevance evaluation in the loss function
improve the model’s ability to generate more appropriate and coherent
responses to the discourse?

We observed some small improvements across the various evaluation metrics when
we utilized dialogue context relevance in the loss function modeling (Table 4:
Semantic Reinforcement vs SemTexLogue Loss; Table 5: Semantic Reinforcement vs
SemTexLogue Loss). Similar behavior has also been found in embedding-based
evaluation (Tables 6 and 7). Thus, our findings support the hypothesis that
the inclusion of context can provide additional feedback to the dialogue
generation model about the adequateness of generated response, and hence it
can lead to enhancement in generation quality.

#### RQ 3: Will integrating the semantic and contextual components to the
lexical-based evaluation metrics in dialogue generation result in better
correlation with human judgment?

We found that the performance of the SemTexualLogue on the Multiwoz dataset is
very close to baselines in terms of BLEU; however, the model significantly
outperforms others in human evaluation. A similar notation as human evaluation
is being reflected in our newly introduced loss function, Dialuation. We found
many cases where a response was very relevant but did not match with the gold
utterance; thus, both Dialuation and human score were high despite low BLEU
score. One such instance is as follows: context: Hi, …lets watch a new movie,
generated: I prefer some new web-series, gold: lets go! We can watch it. It
firmly shows that the Diluation, which considers both semantic and context
relevance, is more aligned with human evaluation than any other metrics,
including the BERT score.

Model | BERT Score | Dialution
---|---|---
CE Shi et al. (2021) | 57.58 | 51.43
Weighted Semantic CE | 57.91 | 51.22
Weighted Semantic and Context CE | 57.94 | 51.27
Semantic Reinforcement | 58.36 | 51.85
SemTextualLogue | 58.83 | 52.38

Table 6: Vector-embedding based evaluation result on Multiwoz dataset

Model | BERT Score | Dialution
---|---|---
CE Shi et al. (2021) | 32.72 | 26.64
Weighted Semantic CE | 32.84 | 28.50
Weighted Semantic and Context CE | 34.05 | 28.82
Semantic Reinforcement | 33.35 | 26.52
SemTextualLogue | 34.37 | 29.94

Table 7: Vector-embedding based evaluation result on PersonaChat dataset

Model | Adequacy | Fluency | Coherence | Naturalness | Completeness | Avg.
---|---|---|---|---|---|---
CE Shi et al. (2021) | 3.28 | 4.16 | 3.34 | 3.85 | 3.6 | 3.64
Weighted Semantic CE | 3.34 | 4.14 | 3.43 | 3.96 | 3.51 | 3.68
Weighted Semantic and Context CE | 3.42 | 4.20 | 3.71 | 3.94 | 3.73 | 3.80
Semantic Reinforcement | 3.45 | 4.18 | 3.6 | 4.08 | 3.89 | 3.84
SemTextual Logue | 3.56 | 4.23 | 3.84 | 4.11 | 4.01 | 3.95

Table 8: Human evaluation of generation models with different loss functions
on MultiWoz dataset

Model | Adequacy | Fluency | Naturalness | Coherence | Completeness | Avg.
---|---|---|---|---|---|---
CE Shi et al. (2021) | 1.65 | 2.05 | 1.68 | 1.87 | 1.91 | 1.83
Weighted Semantic CE | 1.75 | 1.98 | 1.65 | 1.95 | 1.89 | 1.84
Weighted Semantic and Context CE | 1.82 | 2.13 | 1.71 | 1.91 | 1.98 | 1.91
Semantic Reinforcement | 1.81 | 2.08 | 1.69 | 1.92 | 1.95 | 1.89
SemTextual Logue | 1.83 | 2.21 | 1.75 | 1.89 | 2.01 | 1.94

Table 9: Human evaluation of generation models with different loss functions
on PersonaChat dataset

##  6 Case Study and Analysis

We have analyzed the models’ performances for common test cases, and a few
samples are shown in Table 10. The comprehensive analyses of the performances
of different models lead to the following key observations: (i) Due to the
incorporation of semantics and context, our model generates more
contextualized and consistent responses, as shown in Table 10. (ii) We
observed that the number of synonyms for a word is very limited in the
MultiWoz dataset’s vocabulary space, so the influence of semantic infusion is
comparatively less than the performance gain observed on the PersonaChat
dataset. (iii) In some cases, more often in the persona dataset, the proposed
model repeats some words (persona entities) in response, primarily due to the
fact that they occur more often in the corpora.

Context: $<$domain$>$ restaurant,taxi,attraction $<$domain$>$ $<$history$>$
$<$user$>$ Hi, I’m looking for a nightclub in town please. $<$user$>$
$<system>$ There are several nightclubs in town. I recommend ballare. It is
found in the center of town.$<system>$ … $<$history$>$ $<$curr-utterance$>$
Are there any steakhouses in the centre? $<$curr-utterance$>$
---
Utterance: Are there any steakhouses in the centre?
Gold Response: Unfortunately not. Do you want to broaden your search?
CE: I have found several restaurants that serve British food. What type of
food would you like?
Weighted Semantic and Context CE: I have found two restaurants that meet your
criteria. One is in the centre and the other is in the centre of town. Do you
have a preference?
SemTextual Logue: I have no restaurants that serve British food in the centre
of town. Would you like to try another type of food?
Context: $<$domain$>$ train,hotel $<$domain$>$ $<$history$>$ $<$user$>$ I’d
like a moderately priced hotel with free parking, please. $<$user$>$
$<$system$>$ acorn guest house is a 4-star hotel located in 154 chesterton
road, should i book it for you? $<$system$>$ …$<$user$>$ Is that located in
the north. I really want to stay somewhere in the north. $<$user$>$
$<$system$>$ Yes that is located in the north. Should I book it for you?
$<$system$>$ $<$history$>$
Utterance: Does it include free parking?
Gold Response: Yes it does. Would you like me to book you a room?
Weighted CE: Yes, it does have free parking.
SemTextual Logue: Yes, it does have free parking. Would you like me to book it
for you?

Table 10: Case study- generated responses by different models for some common
test cases

##  7 Conclusion and Future Work

The core of a learning framework is the objective function and evaluation
metrics, which are used to train the underlying task and assess its
performance. Cross entropy (CE) and BLEU are the commonly employed loss
function and evaluation metrics for dialogue generation, but they have the
drawback of fixed target comparison. To address this issue, we propose a
semantic-infused contextualized dialogue (SemTextual Logue) loss function. We
formulate two different variations of the loss function to investigate the
effectiveness of infusion of the semantic and context: (a) weighted cross
entropy and (b) reinforced SemTextual loss function. Moreover, we introduced a
new dialogue evaluation metric called Dialuation, which also considers
dialogue context in addition to gold text to assess the relevance of generated
response. We experimented with both kinds of dialogue corpora, namely task-
oriented and chit-chat. The proposed SemTextual Logue obtained superior
performance on both datasets across various evaluation metrics, including
human evaluation. The obtained improvements and analysis firmly establish the
efficacy of dialogue context and semantic evaluation for dialogue generation
loss function. Consequently, we found a strong correlation between human
judgment and the Dialuation metric. When we evaluate a response, we implicitly
use global knowledge in addition to the context, and thus an evaluation by a
child and an evaluation by an experienced individual differ. In the future, we
would like to investigate the role of external knowledge in developing an
appropriate loss function.

##  8 Limitations

Despite the significant improvement demonstrated by the proposed framework
with SemTextualLogueLoss, we also observed some weaknesses and limitations.
These are as follows: (i) The work is certainly limited in scope with
experimenting with non-pre-trained models. However, we believe the pre-
training provides better grounding of context and thus generates more
appropriate responses. It has not much to do with loss function and evaluation
metrics. We aim to investigate the efficacy of the loss function and
evaluation metric with these current state-of-the-art LLMs in future. (ii) The
coherence between a response and the dialogue history is influenced by the
nature of the dialogue. In task-oriented dialogues, each response is typically
more closely aligned with the context compared to chit-chat conversations.
Consequently, the coefficient ($\alpha$) for incorporating context in the loss
function varies accordingly. As a result, we identified two different values
that proved effective for these two settings. However, it is important to note
that our experiments were conducted on only two datasets; the most appropriate
values for these coefficients can be determined with experimentation on
multiple datasets. (iii) Despite employing a contextual semantic vector for
sentence representation, it falls short in capturing the similarity between
two sentences, when one of them contains a negation and antonym word, despite
having a similar meaning.

## References

  * Allen et al. (2001) James F Allen, Donna K Byron, Myroslava Dzikovska, George Ferguson, Lucian Galescu, and Amanda Stent. 2001.  Toward conversational human-computer interaction.  _AI magazine_ , 22(4):27–27.
  * Banerjee and Lavie (2005) Satanjeev Banerjee and Alon Lavie. 2005.  Meteor: An automatic metric for mt evaluation with improved correlation with human judgments.  In _Proceedings of the acl workshop on intrinsic and extrinsic evaluation measures for machine translation and/or summarization_ , pages 65–72.
  * Chen et al. (2017) Hongshen Chen, Xiaorui Liu, Dawei Yin, and Jiliang Tang. 2017.  A survey on dialogue systems: Recent advances and new frontiers.  _Acm Sigkdd Explorations Newsletter_ , 19(2):25–35.
  * Conley et al. (2018) Thomas Conley, Jack St Clair, and Jugal Kalita. 2018.  Improving computer generated dialog with auxiliary loss functions and custom evaluation metrics.  In _15th International Conference on Natural Language Processing_ , page 143.
  * De Boer et al. (2005) Pieter-Tjerk De Boer, Dirk P Kroese, Shie Mannor, and Reuven Y Rubinstein. 2005.  A tutorial on the cross-entropy method.  _Annals of operations research_ , 134:19–67.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Feng et al. (2021) Xiachong Feng, Xiaocheng Feng, and Bing Qin. 2021.  A survey on dialogue summarization: Recent advances and new frontiers.  _arXiv preprint arXiv:2107.03175_.
  * Golovanov et al. (2019) Sergey Golovanov, Rauf Kurbanov, Sergey Nikolenko, Kyryl Truskovskyi, Alexander Tselousov, and Thomas Wolf. 2019.  Large-scale transfer learning for natural language generation.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 6053–6058.
  * Griol et al. (2008) David Griol, Lluís F Hurtado, Encarna Segarra, and Emilio Sanchis. 2008.  A statistical approach to spoken dialog systems design and evaluation.  _Speech Communication_ , 50(8-9):666–682.
  * Hu et al. (2020) Wenpeng Hu, Ran Le, Bing Liu, Jinwen Ma, Dongyan Zhao, and Rui Yan. 2020.  Translation vs. dialogue: A comparative analysis of sequence-to-sequence modeling.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 4111–4122.
  * Jiang et al. (2019) Shaojie Jiang, Pengjie Ren, Christof Monz, and Maarten de Rijke. 2019.  Improving neural response diversity with frequency-aware cross-entropy loss.  In _The World Wide Web Conference_ , pages 2879–2885.
  * Kovaleva et al. (2018) Olga Kovaleva, Anna Rumshisky, and Alexey Romanov. 2018.  Similarity-based reconstruction loss for meaning representation.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 4875–4880.
  * Li et al. (2017) Jiwei Li, Will Monroe, Tianlin Shi, Sébastien Jean, Alan Ritter, and Dan Jurafsky. 2017.  Adversarial learning for neural dialogue generation.  In _EMNLP_.
  * Lin (2004) Chin-Yew Lin. 2004.  Rouge: A package for automatic evaluation of summaries.  In _Text summarization branches out_ , pages 74–81.
  * Liu et al. (2016) Chia-Wei Liu, Ryan Lowe, Iulian Vlad Serban, Mike Noseworthy, Laurent Charlin, and Joelle Pineau. 2016.  How not to evaluate your dialogue system: An empirical study of unsupervised evaluation metrics for dialogue response generation.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 2122–2132.
  * Nakamura et al. (2019) Ryo Nakamura, Katsuhito Sudoh, Koichiro Yoshino, and Satoshi Nakamura. 2019.  Another diversity-promoting objective function for neural dialogue generation.
  * Niwattanakul et al. (2013) Suphakit Niwattanakul, Jatsada Singthongchai, Ekkachai Naenudorn, and Supachanun Wanapu. 2013.  Using of jaccard coefficient for keywords similarity.  In _Proceedings of the International MultiConference of Engineers and Computer Scientists_ , volume 1.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th annual meeting of the Association for Computational Linguistics_ , pages 311–318.
  * Sato et al. (2020) Shiki Sato, Reina Akama, Hiroki Ouchi, Jun Suzuki, and Kentaro Inui. 2020.  Evaluating dialogue generation systems via response selection.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 593–599.
  * Sellam et al. (2020) Thibault Sellam, Dipanjan Das, and Ankur Parikh. 2020.  Bleurt: Learning robust metrics for text generation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7881–7892.
  * Serban et al. (2016) Iulian Serban, Alessandro Sordoni, Yoshua Bengio, Aaron Courville, and Joelle Pineau. 2016.  Building end-to-end dialogue systems using generative hierarchical neural network models.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 30.
  * Shen et al. (2021) Lei Shen, Haolan Zhan, Xin Shen, Yonghao Song, and Xiaofang Zhao. 2021.  Text is not enough: Integrating visual impressions into open-domain dialogue generation.  In _Proceedings of the 29th ACM International Conference on Multimedia_ , pages 4287–4296.
  * Shi et al. (2021) Tian Shi, Yaser Keneshloo, Naren Ramakrishnan, and Chandan K Reddy. 2021.  Neural abstractive text summarization with sequence-to-sequence models.  _ACM Transactions on Data Science_ , 2(1):1–37.
  * Ueyama and Kano (2020) Ayaka Ueyama and Yoshinobu Kano. 2020.  Diverse dialogue generation with context dependent dynamic loss function.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 4123–4127.
  * Valizadeh and Parde (2022) Mina Valizadeh and Natalie Parde. 2022.  The ai doctor is in: A survey of task-oriented dialogue systems for healthcare applications.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 6638–6660.
  * Wang et al. (2021) Yida Wang, Yinhe Zheng, Yong Jiang, and Minlie Huang. 2021.  Diversifying dialog generation via adaptive label smoothing.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 3507–3520.
  * Welch (1947) Bernard L Welch. 1947.  The generalization ofstudent’s’ problem when several different population variances are involved.  _Biometrika_ , 34(1/2):28–35.
  * Zang et al. (2020) Xiaoxue Zang, Abhinav Rastogi, Srinivas Sunkara, Raghav Gupta, Jianguo Zhang, and Jindong Chen. 2020.  Multiwoz 2.2: A dialogue dataset with additional annotation corrections and state tracking baselines.  _ACL 2020_ , page 109.
  * Zhang et al. (2018) Saizheng Zhang, Emily Dinan, Jack Urbanek, Arthur Szlam, Douwe Kiela, and Jason Weston. 2018.  Personalizing dialogue agents: I have a dog, do you have pets too?  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2204–2213.
  * (30) Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q Weinberger, and Yoav Artzi.  Bertscore: Evaluating text generation with bert.  In _International Conference on Learning Representations_.
  * Zhao et al. (2020) Xueliang Zhao, Wei Wu, Can Xu, Chongyang Tao, Dongyan Zhao, and Rui Yan. 2020.  Knowledge-grounded dialogue generation with pre-trained language models.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 3377–3390.