\subsubsection*{\bf{#1}}}
\newcommand{\alg}[1]{Algorithm~\ref{#1}}
\newcommand{\fig}[1]{Figure~\ref{#1}}
\newcommand{\tab}[1]{Table~\ref{#1}}
\newcommand{\sect}[1]{\S\ref{#1}}
\newcommand{\sv}[1]{\textcolor{red}{SV: #1}}
\newcommand{\marginaliasv}[1]{\marginpar{\small\itshape\color{red}#1}}
\newcommand{\rg}[1]{\textcolor{blue}{RG: #1}}
\newcommand{\cs}[1]{\textcolor{orange}{CS: #1}}

\begin{document}
\title{Facets of Fairness in Search and Recommendation
\author{Sahil Verma\inst{1}\and
Ruoyuan Gao\inst{2}\orcidID{0000-0002-8784-4171} \and
Chirag Shah\inst{1}\orcidID{0000-0002-3797-4293}}
\institute{University of Washington, Seattle WA 98195, USA \\
\email{\{vsahil,chirags\}@uw.edu} \and
Rutgers University, New Brunswick NJ 08901, USA\\
\email{ruoyuan.gao@rutgers.edu}}
\maketitle
\begin{abstract}
    Several recent works have highlighted how search and recommender systems exhibit bias along different dimensions.
    Counteracting this bias and bringing a certain amount of fairness in search is crucial to not only creating a more balanced environment that considers relevance and diversity but also providing a more sustainable way forward for both content consumers and content producers.
    This short paper examines some of the recent works to define relevance, diversity, and related concepts.
    Then, it focuses on explaining the emerging concept of fairness in various recommendation settings.
    In doing so, this paper presents comparisons and highlights contracts among various measures, and gaps in our conceptual and evaluative frameworks.
    \keywords{Search bias \and Fairness \and Evaluation metrics \and Fairness in recommendation \and Fair ranking.}
\end{abstract}

\section{Introduction}
Recommendations or ranking candidates for any purpose is an integral part of the technologies we use each day.
Each potential candidate is scored with relevance which is used to rank them in a recommendation list.
The algorithms used in the underlying software are not only complicated, but they also take clues from the previous actions of the users on the platform.
This feedback loop potentially leads to discrimination against future users, for example, women less likely to be shown advertisements for high-paying jobs~\cite{womenlessHPJ,guardianwomenlessHPJ}.

Left unchecked, such implicit biases can amount to increased stereotypes and polarized opinions.
Mitigation of bias in automated decisions is an emerging area in machine learning and related domains.
Classification and ranking/filtering are the two important categorizations of automated decisions using machine learning.
Fairness in automated decisions has gained significant traction, and many papers published in the recent years have attempted to 1) devise metrics to quantize fairness, 2) design frameworks using which fair models can be produced (according to the fairness desired metric) or 3) modify data to fight bias in the historical data.
There have been many works of the kinds mentioned beforehand in both classification and recommendation settings.
A recent work summarized and explained various fairness metrics used in the classification tasks~\cite{fairness-classification}.
Unlike classification, recommendations have widely different facets and application scenarios.
One of the significant differences lies in the output space, which is very restricted in the case of classification.
In contrast, the output space for ranking or recommendation could be the entire list of ranked items.
Owing to the sheer abundance of the fairness metrics and their applicability in specific scenarios, understanding their differences and similarities is complicated.

We review papers from major conferences which received submissions related to fairness in ranking and recommendation, including KDD, WSDM, WWW, SIGIR, ECIR, RecSys, IP\&M, and FAT*, from 2015 to 2020.
We found twenty-two relevant papers that propose new fairness metrics and provide frameworks to optimize models using them.
In this paper, we collect and intuitively explain the fairness metrics used in five major recommendation settings: non-personalized recommendation setting, crowd-sourced recommendation setting, personalized recommendation setting, online advertisements and marketplace.
Since literature has proposed several metrics for each of the settings above, we present all the metrics but we do not attempt to develop arguments in favor of any particular metric, we rather explain the underlying similarities and differences between them, and show how these metrics affect other dimensions of ranking.
We also develop a clear distinction between fairness in various recommendation settings from often related terms such as diversity, novelty, and relevance.
We have categorized fairness metrics according to the setting they are applied.
The main contribution of this work is intuitive categorization and explanation of \textit{twenty-five} fairness definitions in various recommendation settings and identification of relationships between them.

The remainder of this paper is organized as follows.
Section 2 presents the definitions of commonly used terms in the recommendation literature.
Sections 3 to 7 delineates the fairness metrics in various settings.
Section 8 outlines the conclusions.

\section{Dimensions of Search and Recommendation results evaluation}
We formally define three dimensions for evaluating search and recommendation results -- relevance, diversity, and novelty.
These dimensions help to gauge the quality of ranking for a search query or recommendation.

\begin{itemize}
    \item \textbf{Relevance}~\cite{gao}: Search results are relevant if they accurately answer or describe various aspects of the query or recommendation.
    It focuses on whether and to what extent a search result relates to the given query.
    For example, it can be considered as the documents containing some keywords in the query, answering the query, or providing information related to the topic of the query.
    Relevance only considers the match between the query and the results, often disregarding a user's intent.

    \item \textbf{Diversity}~\cite{gao}: Search results for each query might have several topics. For example, given the query ``Lisbon'', the topics include geographic and historical facts, tourism information, and the weather.
    Diversity refers to the constitution of the search results from its various topics.
    Various metrics have been defined to measure diversity, such as those found in~\cite{diversity-defs,sakai_simple_2010}.

    \item \textbf{Novelty}~\cite{gao}: Given several relevant results pertaining to a query, novelty requires the presentation of results that deliver considerably different information content than the results already shown.
    It thus encourages uniqueness in the shown results with a purpose of maximizing information gain.

\end{itemize}

\section{Fairness Metrics in Non-Personalized Recommendation Settings}
We collect the following metrics from literature to capture fairness in search and recommendations.
We consider the setting where a ranker wants to rank a set of candidates that are relevant to a query or for recommendation.
The ranker does not account for individual preferences of the consumers of the ranked list.
The fairness in this setting addresses how the candidates are ranked.
We assume the existence of protected and unprotected groups (binary setting), which are defined by law~\cite{protected}.

    \subsection{Accuracy-based fairness metrics}
    Most fairness metrics for recommendations either state the condition for their satisfaction (ideal ranking) or provide a measure of deviation from the ideal ranking.
    These metrics require a certain proportion of candidates from the protected group in the ranking, or given a ranked list they calculate the divergence from that required proportion in it.
    Collectively they are called \textit{accuracy-based fairness metrics}.

    \begin{enumerate}

    \item \textbf{Statistical/demographic Parity:
    A ranker is said to be satisfying statistical parity if the proportion of candidates from the protected and unprotected groups match the underlying proportion in the top-k rank search results.
    Therefore statistical parity can be defined at any $k$ length of the ranking.
    For example, in the image search query, ``CEO'', if the displayed results show an equal proportion of male and female CEOs, the results are said to satisfy statistical parity.
    Singh et al.~\cite{Singh-Joachims} define \textit{exposure} as the resource allocated to a candidate that is computed as a measure of its relevance and position in the ranking.
    Average exposure to each demographic group also implies statistical parity.
    If the average exposure to the candidates belonging to different demographic groups is not equal, the ranker is said to violate statistical parity.

    \item \textbf{Disparate Treatment: }
    Disparate treatment refers to the unequal treatment of a candidate due to their membership in a protected group~\cite{disp-treatment}.
    The candidate would have been treated differently if they had belonged to another group.
    If the average exposure of different groups is not proportional to their average relevance, then the ranker is said to exhibit disparate treatment~\cite{Singh-Joachims}.

    \item \textbf{Disparate Impact: }
    Disparate impact is the practice of not allocating favorable outcomes to protected groups.
    For searches and recommendations, a click on a candidate is the favorable outcome, which is called as candidate's click-through rate.
    If the expected click-through rate for members of protected and unprotected groups is not proportional to their average relevance, then the ranker is said to cause disparate impact~\cite{Singh-Joachims}.
    Click-through rates for a ranked item can be estimated with the help of several techniques~\cite{click-estimate}.

    \item \textbf{Search Neutrality: }
    Search neutrality refers to the search engines' lack of editorial power.
    It means that the search engine should return results to a query impartially and based solely on relevance.
    It should not promote/demote or differentiate based on websites~\cite{search-neutrality}.
    Google, Facebook, and other tech companies have been accused of violating search neutrality to promote websites that pay them for higher rankings~\cite{google-accused}.

    \item \textbf{Top-k fairness: }~\label{top-k}
    Zehlike et al.~\cite{zehlike2017} describe a ranking as a top-k fair ranking if the top-k candidates in the ranking contain a required proportion of members from the protected group.
    Given a required proportion, the algorithm they propose ranks candidates in a manner that fairly represents the protected group.
    Within the protected and unprotected groups, the candidates are ranked by relevance.
    If the required proportion is equal to the underlying proportion between the populations of the protected and unprotected groups, top-k fairness and statistical parity are equivalent.

    \item \textbf{Skew@k: }
    Geyik et al.~\cite{Geyik2019} define Skew@k as the logarithm of the ratio of proportions of the candidates belonging to the protected group in the top-k ranked candidates to the desired proportion of the protected group in top-k ranks.
    A negative skew implies lower than desired representation in the top-k ranks.
    Zero skew implies a top-k fair ranking (Definition \ref{top-k}).
    Therefore a zero skew with the required proportion equal to underlying proportion would imply equivalence between Skew@k, top-k fair ranking and statistical parity.
    They also define minskew@k and maxskew@k to extend the metric beyond binary groups.

    \item \textbf{Normalized Discounted Difference (rND)}
    Yang et al.~\cite{julia-paper} point out that establishing statistical parity at higher ranks (e.g., top-10) is more important than establishing it at lower ranks (e.g., top-100).
    To account for this, they measure set-based fairness metrics at discrete points (e.g., top-10, top-20) and use logarithmic discounts for lower ranks.
    Normalized discounted difference (rND) computes the difference between the proportion of the protected group members in top-k results and the overall population proportion.
    If the protected group is proportionally represented, a lower rND value is achieved, which is preferable.
    If the desired proportion equals to the actual population proportion, then the rND score is correlated with top-k fairness, Skew@k and statistical parity.

    \item \textbf{Normalized Discounted KL-divergence (rKL)}
    Normalized discounted KL-divergence(rKL) \cite{julia-paper} measures the expected difference between the proportion of the protected group members in the top-k rank and the overall population proportion.
    The metric rKL resembles rND, only it is a smoother measure (and therefore optimizable in gradient-based optimization setting) and can be applied to multiple group settings.

    \item \textbf{Normalized Discounted Ratio (rRD)}
    Normalized discounted ratio(rRD) \cite{julia-paper} takes the difference between the ratio of the protected to unprotected group members among the top-k ranking and the ratio of underlying sizes of the protected and unprotected groups.
    A score of zero rRD implies zero skew@k rank, top-k fair ranking and a ranking that satisfies statistical parity.
    The metric rRD is considered to be useful when the protected group is a minority, in which case it resembles rND and rKL values; otherwise, rRD is meaningless.
    \end{enumerate}

    \subsection{Error based fairness metrics}
    Kuhlman et al.~\cite{kuhlman_fare_2019} point out that fairness in classification setting has several metrics that are error-based, i.e., they require the classifier to have similar error-rates across the protected and unprotected groups.
    They claim that those metrics carry value and should be used for measuring fairness in rankings.
    Unlike a classification task where the error is readily computable, there exists no such error in case of ranking.
    Therefore, Kuhlman et al. propose to use pair-inversions to measure ranking errors.
    They assume the existence of a ground-truth rank for each candidate.
    If a ranker ranks a candidate higher than its ground-truth rank, they call it a false positive case.
    Similarly, a candidate that is ranked lower is called a false negative case.
    Each definition that follows has roots in the counterparts described in fairness in classification literature~\cite{fairness-classification}.
    \begin{enumerate}

    \item \textbf{Rank Equality: }
    Rank equality has its origins in the metric called \textit{equalized odds}, which requires equal classification error rates (false positive and false negative error) across the protected and unprotected groups.
    Rank equality error captures the number of times a candidate from a group has been falsely given a higher rank than a candidate of another group; the score is calculated for each such inverted pair.
    This metric does not penalize the ranking where a candidate from the same group has been falsely ranked higher.

    \item \textbf{Rank Calibration: }
    Rank calibration~\cite{kuhlman_fare_2019} has roots in calibration which enforces equal precision of classifiers across the protected and unprotected groups.
    It checks how correctly the ranker predicts candidates in each demographic group.
    Rank calibration error is calculated as the number of times a candidate from one group is falsely ranked higher than candidates of all groups; the score is calculated for each such inverted pair.

    \item \textbf{Rank Parity: }
    Rank parity criterion~\cite{kuhlman_fare_2019} has roots in statistical parity.
    It requires proportional representation of members from the protected and unprotected groups in the ranking.
    The rank parity error is computed as the number of candidates belonging to one group that were ranked higher than candidates from another group; the score is calculated for each such inverted pair.
    \end{enumerate}

    \subsection{Causal approach for mitigating discrimination}
    Wu et al.~\cite{Wu-2018} use a causal graph to counteract bias contained in historical data.
    They use a score variable (instead of rank) to account for individual qualifications and the path-specific effect technique to capture direct and indirect discrimination based on one's membership in the protected group.
    Having detected discrimination, each individual's score is modified to remove the bias, keeping the distribution of new scores close to the original distribution.
    The modified scores are applied to create a fairer ranking.

\section{Fairness Metrics in Crowd-Sourced Non-Personalized Recommendation Settings}
    Chakraborty et al.~\cite{Chakraborty2019} consider the setting of top-k trending recommendations on platforms like Twitter or Yelp which is a non-personalized setting.
    Generally, recommendations are the top-voted candidates using a procedure that resembles an election (with some differences).
    Each person on the platform can vote (e.g., via a click) for multiple candidates and that too multiple times.
    \begin{enumerate}

    \item \textbf{Equality of Voice: }
    In the setting described above, trends are subject to manipulations by hyper-active group or campaigners of all kinds.
    This can lead to a veneer of popularity for a particular candidate.
    To avoid this situation, Chakraborty et al. propose a ``one person, one vote'' election procedure in which everyone has an equal say.
    Each person is asked to specify their preferences across a set of candidates.
    The first position is assigned to the candidate, which is the first preference of the majority.

    \item \textbf{Proportionality for Solid Coalitions: }
    Chakraborty et al.~\cite{Chakraborty2019} point out that due to the abundance of options, user's votes might get split across irrelevant or redundant alternatives, e.g. if there are three candidates out of which the first two are very close.
    Assume that 60\% of the people are interested in the first two candidates.
    Due to their similarity, votes would split among them.
    Thus, even though the sum of the votes across these two candidates is more, a less popular third candidate would emerge as the winner.
    To avert this, proportionality for solid coalitions requires the diversity of opinions in the overall population should be proportionally represented in the top-k recommendations.

    \item \textbf{Anti-Plurality: }
    Chakraborty et al. also propose that if a majority of users dislike a candidate, it should not be in the top-k recommendations.
    In the previous example, the third candidate, disliked by 60\% of the population, would not be recommended.
    \end{enumerate}

\section{Fairness Metrics in Personalized Recommendation Settings}
    Beutel et al.~\cite{beutel_fairness_2019} consider fairness metrics for personalized recommendation settings.
    Consider $M$ total candidates, out of which $M'$ are relevant to a query, but only $K$ candidates are useful as part of personalization.
    Since they are dealing with personalized ranking along with clicking, Beutel et al. also consider the engagement of the user with a recommended candidate.
    Engagement between a given user and recommended candidate can be estimated.
    They compare ranked candidates pairwise and define \textbf{pairwise accuracy} as the probability that a clicked candidate is ranked above another relevant unclicked candidate.
    \begin{enumerate}

    \item \textbf{Pairwise Fairness: }
    A ranker is said to satisfy pairwise fairness if the probability of a clicked candidate being ranked higher than another relevant unclicked candidate is the same across groups, conditioned on the candidates that have the same predicted engagement score.
    Pairwise fairness does not eliminate systematic preference between demographic groups.
    For example, one can rank all candidate belonging to a favored group that are not relevant to the query and give a lower rank to candidates from the other group that are relevant to the query.

    \item \textbf{Inter-Group Pairwise Fairness: }
    A ranker satisfies inter-group pairwise fairness~\cite{beutel_fairness_2019} if the probability of a clicked candidate being ranked higher than a relevant but unclicked candidate in the other group is the same across pairs of demographic groups, conditioned on the candidates that have same engagement score.

    \item \textbf{Intra-Group Pairwise Fairness: }
    A ranker is said to satisfy intra-group pairwise fairness~\cite{beutel_fairness_2019} if the probability of a clicked candidate being ranked higher than another relevant but unclicked candidate in the same group is equal across demographic groups, conditioned on the candidates that have the same predicted engagement score.
    \end{enumerate}

    \noindent A combination of Intra-Group and Inter-Group Pairwise Fairness can reduce systematic bias against a demographic group.

\section{Fairness Metrics in Advertisement Settings}
    Chawla et al.~\cite{chawla2019multicategory} present fairness concerns from an entirely different perspective.
    Thus far, we have described metrics that view fairness from the perspective of a candidate to be ranked or recommended.
    Chawla et al. describe fairness from the perspective of individuals who are being served advertisements.
    Individual fairness~\cite{fairness-classification} states that the advertisements shown to two similar individuals should be similar.
    For instance, qualifications of an individual can characterize the similarity.
    Nevertheless, the solution to the problem does not lie in showing an equal proportion of advertisements from all categories to similar people, as individuals have needs and preferences.

    \begin{enumerate}

    \item \textbf{Envy-Freeness: }
    Envy-freeness~\cite{chawla2019multicategory,serbos-fairness-2017} is a complementary notion to individual fairness, in which only a user's preference is considered for advertisements and a user's qualifications (therefore, similarities) are not reasoned.
    It requires every user to be content with their share of advertisements.

    \item \textbf{Inter-Category Envy-Freeness: }
    Enforcing individual fairness for all categories of advertisements is problematic since it does not recognize individual preferences.
    Inter-category envy-freeness~\cite{chawla2019multicategory} allows each user to specify individual preferences, and the criterion requires that all users interested in a category should be served the same amount of advertisements belonging from that category.
    For example, two individuals interested in jobs should be shown the same number of job-related ads.

    \item \textbf{Total Variation Fairness: }
    Inter-category envy-freeness does not ensure a fair distribution of advertisements within a category.
    For instance, two equally qualified individuals belonging to different demographic groups can be unfairly shown high-paying and low-paying jobs respectively, while satisfying that metric.
    Total variation fairness~\cite{chawla2019multicategory} overcomes this limitation by requiring that all subsets of the advertisements from any category shown to two similar individuals must be the same.
    Consequently, it evades the problem of unfairly showing high-paying job ads to one user.

    \item \textbf{Compositional Fairness: }
    Compositional fairness~\cite{chawla2019multicategory} combines inter-category envy-freeness and total variation fairness.
    Compositional fairness has two requirements: 1) a user's preferences must be recognized, and advertisements served to them belong to their preferred categories only (\textit{envy-freeness}) and 2) within each category, the proportions of advertisements should be the same across all users interested in that category.
    This lets an advertiser serve advertisements from different categories with varying probabilities to a user (based on their preference).
    However, the mix of advertisements from each category should be the same across all interested users.
\end{enumerate}

\section{Fairness Metrics in Marketplace Settings}

    Advertisement setting brings us to a discussion related to marketplaces, in which consumers are shown advertisements about products which the suppliers want to publicize.
    Marketplaces are ubiquitous.
    Almost all online platforms we interact with serve as a marketplace for consumers and service providers.
    These multi-sided recommendation platforms have complicated fairness constraints.
    Historically, most marketplaces have optimized for consumer satisfaction, but given the rising competition among different platforms, the satisfaction of service providers has also gathered attention.
    For example, Spotify would like to recommend tracks that a particular consumer would find relevant and is likely to listen.
    But it would be problematic if Spotify only recommends songs from a few popular artists to the consumers because: 1) it gives low exposure to less popular artists, and 2) the consumer may not find the recommendations interesting after sometime.
    There has been a few recent works discussing and addressing these concerns~\cite{mehrotra_towards_2018,abdollahpouri_multi-stakeholder_2019,wan_addressing_2020,ferraro_artist_2019,abdollahpouri_recommender_2017,burke_multisided_2017}.

    There are several classes of multi-sided recommendation: 1) Multi-receiver recommendation -- when a target audience is a group of people rather than an individual, e.g., students on an education platform; 2) Multi-provider recommendation -- when several suppliers provide the recommendation content, and the platform needs to choose between them, e.g., Airbnb and Spotify, and 3) Side stakeholder recommendation -- when there are parties other than suppliers and consumers involved in the marketplace, the recommendations need to consider their preferences as well, e.g., drivers in the Uber Eats platform.

    \begin{enumerate}
        \item \textbf{Consumer Fairness: }
        A recommendation satisfies consumer fairness~\cite{abdollahpouri_multi-stakeholder_2019} it is does not cause any disparate impact on members of protected groups.
        For example, consumers of all groups should be served the same distribution of job ads.

        \item \textbf{Provider Fairness: }
        A recommendation satisfies provider fairness~\cite{abdollahpouri_multi-stakeholder_2019} if all the providers have an equal chance of exposure to the consumers.
        For example, Spotify recommends both famous and less famous artists publishing a specific genre of music to users who prefer that genre.

        \item \textbf{Side Stakeholder Fairness: }
        A recommendation satisfies side stakeholder fairness~\cite{abdollahpouri_multi-stakeholder_2019} if it takes into consideration the preferences of side stakeholders.
        For example, fairly distributing consumer orders and commute distance among drivers in Uber Eats.
    \end{enumerate}

\section{Conclusion}
In this short survey, we collect and present various metrics proposed in the emerging literature on fairness in recommendations.
Succinct and distinct categorization of fairness metrics would help people understand the landscape and triage missing gaps, consequently fuelling future research.
We are already experiencing an adoption of this research in the industry. For instance,
Geyik et al.\cite{Geyik2019}, in a first large-scale deployment, enforced fair ranking in Linkedln search.
We envision such deployments to other major search engines in the future.

\bibliographystyle{splncs04}


\section{Introduction} \label{Section1}
SMS text normalization focuses on translating texting language, often filled with abbreviations and marred by typing errors into plain English text. With the smartphone revolution and massive popularisation of social media platforms, users often transmit messages consisting of up to thousands of words in a single day. However, these text messages consist of numerous abbreviations and errors. This often arises due to a lack of formalities between users, human error, and in more severe cases due to disabilities. With an increase in the screen sizes, this is becoming more of a concern especially when the user resorts to one handed typing. Thus, shorter message length and semantic unambiguity end up working antagonistically which gives shape to a compressed, non-standard form of language called NetSpeak \cite{crystal_2006}, commonly known as the texting language. Unfortunately, traditional NLP methods perform rather poorly when dealing with these kinds of texts \cite{10.5555/1214993}. As described in \cite{Kobus2008NormalizingSA}, texting language contains many non-standard abbreviations, have unique characteristics and behave quite differently which may be the reason for poor performance of traditional NLP methods.
\newpage
In \cite{Li2012NormalizationOT} the problem was approached by leveraging the phonetic information but required a dictionary for phonetic transcription. \cite{article1} used a dictionary for erroneous words but used an ambiguous ranking mechanism. \cite{6495103} used a completely heuristic rule based model and employed a dictionary for typos as well which in all the three cases caused the time complexity to grow with the size of the dictionary. \cite{Veliz2019ComparingMA} compared machine translation models such as SMT and NMT and showed their critical dependence on high quality training data. In \cite{article}, a Hidden Markov Model based approach was used for each word present in the corpus to model all possible normalized or corrected texts and their probabilities of occurrence. This was further used to rank all the possible normalised words and the highest ranking word would be selected for output as the semantically correct word. In \cite{inbook}, a Trie based probability generation model was proposed, and was shown to outperform HMM-based models whenever the incorrect word was within an edit distance one after prepossessing for phonetic errors. However, in some cases the target word did not end up having the highest rank. For example, `mate', the intended target word was ranked $4^{th}$ in the suggestions list for the word `m8'.\\
Through this work we address the limitations of this Trie based probability generation model. We make a set of improvements  over the scheme proposed in \cite{inbook} which we consider to be the baseline system for the present work. Firstly, unlike \cite{inbook} where a new word is added in a Trie only once when it is encountered for the first time during the training phase,  a dynamic training environment is used in the proposed model. In the proposed model the Trie is initially constructed with a certain corpus of most commonly used words and is then deployed. After deployment, the tries learns dynamically  from the texting habits of the users over time i.e. it keeps adding the same words repeatedly as and when they are encountered. We show that the new model in the described environment is able to estimate the real probability of occurrence of a word through its own new probability generating algorithm. Hence it facilitates 0-1 loss minimisation in a decision theoretic setup. This in turn minimizes the chances of the target word not being ranked as the highest one. \\
Additionally, as explained in \cite{Keyboards2019ImprovingTA} , it is computationally infeasible to generate all the words which are at
an edit distance two from a given word. This limited the spelling correction abilities of the baseline model. In this work we propose some novel heuristics that help in overcoming the above shortcoming significantly.
\\
The contributions of the present work are
\begin{enumerate}
    \item We suggest a structural modification to the Trie-based reasoning scheme to improve model accuracy and performance.
    \item We prove mathematically that in the described dynamic environment, the expectation of the thus generated Trie probability equals the occurrence probability for each word.
    \item We further prove that the Trie probability of each word in the corpus almost surely(a.s.) converges to its occurrence probability.
    \item Develop a set of heuristics for error correction.
    \item Provide empirical results through simulations to support the presented theorems and highlight the superiority of the new model.
\end{enumerate}

\section{Background} \label{Section2}
From existing literature on the behaviour of users while using texting language \cite{Grinter2001}, one can classify most of the linguistic errors as:
\begin{enumerate}
    \item Insertion Error: Insertion of an extra alphabet in the word. Eg. `hoarding'$\rightarrow$`hoardingh'
    \item Deletion Error: Deletion of an alphabet from the word. Eg. `mobile'$\rightarrow$`moble'
    \item Replacement Error: Replacement of an alphabet by another in the word. Eg. `amazing'$\rightarrow$`anazing'
    \item Swap Error: Swapping of two adjacent characters in the word. Eg. `care'$\rightarrow$`caer'
    \item Phonetic Error: A group of alphabets is replaced by another group of alphabets or numbers having the same sound. Eg. `tomorrow'$\rightarrow$`2morrow'
\end{enumerate}
To deal with these errors, an elaborate error correction algorithm has already been proposed in the baseline model wherein given an erroneous/non-lexical word, a suggestion list of possible target words was prepared. The probability of occurrence for each word in the list was generated using a Trie based algorithm as described in Section \ref{Section2.2} which was used for ranking the words in the suggestion list. The highest ranking word was given out as the likely intended word.

\subsection{Design of the TRIE}
Trie is a memory efficient data structure primarily used for storing of words. The search complexity in the data structure is $\mathcal{O}$($M$), where $M$ represents the number of characters in the longest word stored in the Trie which makes it a computationally efficient data structure for the problem.\\
 Each node contains an integer variable \textit{Count} and a Boolean variable \textit{End-Of-Word}. The Trie is set up by initializing it with a number of English words. \textit{Count} for each node is initiated to zero and incremented by one each time a word is inserted through that node. \textit{End-Of-Word} represents if a word ends at the given node and is set to \textit{True} at the ending node of each word. Each time a new word is inserted, the \textit{Count} variables of the passing nodes are updated and if at any point the next node is not already present for the insertion of a character, a new node is created and added as a child. At the end of the new word, \textit{End-Of-Word} is switched from \textit{False} to \textit{True}.
\begin{figure}[t]
    \centering
    \includegraphics[width=\linewidth, height=9cm]{Trie.jpg}
    \caption{Trie: The model has been trained with 8 words each once. Green represents a \textit{True} value for \textit{End-Of-Word} for the coloured node.}
    \label{fig:Trie}
\end{figure}

\subsection{TRIE probability of a Word}\label{Section2.2}
Assigning probability of occurrence to a word through the Trie is a task of prime importance in the model. In the baseline model this was done in a simplistic manner as described below.  \\
The probability of choosing the $i^{th}$ child node was estimated by dividing its \textit{Count} variable, to be referred as \textit{Count}(\textit{i}) by \textit{Total}(\textit{i}) which was defined as:
\begin{equation}\label{TotalEqn}
    Total(i)=Count(i)+\sum_{j\in Sibling(i)}Count(j)
\end{equation}
Where \textit{Sibling}(\textit{i}) refers to the set of all the other child nodes of the common parent node. Hence the probability of the $i^{th}$ child node was set to be:
\begin{equation} \label{TrieProbabEqn}
    P(i)=\frac{Count(i)}{Total(i)}
\end{equation}
Further, to get the probability of a string $s_1s_2\ldots s_n$ from the Trie, the conditional rule of probability was used as:
\begin{equation}
    P(s_1s_2\ldots s_n)=P(s_1)P(s_2|s_1)\ldots P( s_n|s_1s_2\ldots s_{n-1})\nonumber
\end{equation}
For example, consider the string 'bird', then
\begin{equation}
    P(bird)=P(b)P(i|b)P(r|bi)P(d|bir) \nonumber
\end{equation}
Hence, from Fig.\ref{fig:Trie} we get that $P(bird)=\frac{1}{2}\times\frac{3}{4} \times\frac{1}{3} \times\frac{1}{1}=\frac{1}{8}$.
\section{The Improved Trie}\label{Section3}
We consider the user to be modelled as a corpus of words denoted by $\mathcal{S}$ where each word $w_i\in \mathcal{S}$ has an occurrence probability of $p_i$. Note that then the training and probability calculations as proposed in the baseline Trie does not account for an important case. This is when the corpus of words $\mathcal{S}$ contains two words say $w_1$ and $w_2$ with occurrence probabilities $p_1$ and $p_2$, $p_1\neq p_2$ such that $w_1$ is a prefix of $w_2$ or vice versa. For example consider the two words 'bill' and 'bills' in Fig.\ref{fig:Trie}. No matter what the occurrence probabilities of those two words are, they will always end up with the same Trie probability\footnote{Generally, in more branched Tries, whenever $w_1$ is a prefix of $w_2$, Trie probability of $w_2$ $\leq$ Trie probability of $w_1$} even after training the Trie a large number of times after random sampling from $\mathcal{S}$. While the deviation from occurrence probabilities might not vary a lot in the example considered since one word happens to be the plural of the other, it will matter much more in words such as 'lips' \& 'lipstick' and `dear' \& `dearth'.\\
To overcome this we propose the introduction of a dummy node. This dummy node is added as a child of every node which has \textit{End-Of-Word} set as \textit{True} but has at least one non-dummy node as its child. The \textit{Count} variable of this dummy node is set to be the count variable of the parent reduced by the count variable of all the siblings of the new dummy node.
\begin{equation} \label{dummyEqn}
    Count(D)=Count(P)-\sum_{j\in Siblings(D)}Count(j)
\end{equation}
\\
Where $D$ denotes the dummy node and $P$ denotes the parent of the dummy node. Algorithm I in this section outlines the procedure for training the new Trie as described above.
\\
In addition to the training algorithm, we also propose Algorithm II which is used to generate the Trie probability of a given string. \\
Further, to justify usage of the new Trie mathematically, the proposed training algorithm and the algorithm for the Trie probability generation, we present Theorem 3.1, Theorem 3.2 and Corollary 3.3.
\newpage
\hrule
\vspace{0.03cm}
\textbf{Algorithm I: The Training}
\hrule
\vspace{0.1cm}
\textbf{Input:} $w$, root\\
\textbf{Initialization:} $str\leftarrow w$, $m\leftarrow str$.length, $parent \leftarrow$ root, $Flag\leftarrow 0$\\
\textbf{For} $j\leftarrow 1$ to $m$
\begin{enumerate}
    \item \textbf{If} $parent$.children does not contain $str$.charAt[$j$] node
    \begin{enumerate}
        \item Insert new node corresponding to $str$.charAt[$j$]
        \item $Flag\leftarrow 1$
    \end{enumerate}
    \item $parent\leftarrow$ child corresponding to $str$.charAt[$j$]
    \item $parent$.Counter $\leftarrow parent$.Counter$+1$
\end{enumerate}
$parent$.End-Of-Word$\leftarrow$True\\
\textbf{If} a dummy node $D$ is already a child of $parent$
\begin{enumerate}
    \item Increment Counter of $D$ by 1
\end{enumerate}
\textbf{Else if} $Flag$ is 0 and $parent$ has at least 1 non-dummy child
\begin{enumerate}
    \item Insert new dummy node as a child of $parent$
    \item set Counter of dummy as in Eqn.(\ref{dummyEqn})
\end{enumerate}
 \textbf{End}
\vspace{0.1cm}
\hrule
\vspace{0.15cm}
\hrule
\vspace{0.08cm}
\textbf{Algorithm II: The Trie Probability Generation}
\hrule
\vspace{0.1cm}
\textbf{Input:} $w$, root\\
\textbf{Output:} Trie probability of $w$\\
\textbf{Initialization:} $str\leftarrow w$, $m\leftarrow str$.length, $parent \leftarrow$ root, $probab\leftarrow 1$\\
\textbf{For }$j\leftarrow1$ to $m$
\begin{enumerate}
    \item \textbf{If} $parent$.children does not contain str.charAt[j] node
    \begin{enumerate}
        \item \textbf{return} $0$
    \end{enumerate}
    \item $child\leftarrow$ child corresponding to str.charAt[j]
    \item Update $probab$ using Eqn.(\ref{TotalEqn}) \& Eqn.(\ref{TrieProbabEqn}) for $child$
    \item $parent\leftarrow child$
\end{enumerate}
\textbf{If} $parent$.End-Of-Word is True
\begin{enumerate}
    \item \textbf{If} $parent$ has dummy node
    \begin{enumerate}
        \item Update $probab$ using Eqn.(\ref{TotalEqn}) \& Eqn.(\ref{TrieProbabEqn}) for $parent$
    \end{enumerate}
    \item \textbf{return} $probab$
\end{enumerate}
\textbf{return} $0$\\
\textbf{End}
\vspace{0.1cm}
\hrule
\vspace{0.3cm}

\textbf{Theorem 3.1:} Let $\mathcal{S}$ denote a corpus of finite words. Let $w_i\in \mathcal{S}$ be a word of the corpus with an occurrence probability $p_i$ and let $\hat{p}_i$ denote the word probability generated by the Trie. Let the Trie be trained $n$ number of times after randomly sampling(with replacement) from $S$ such that the Trie is trained with each $w_i\in \mathcal{S}$ at least once. Then, $\mathbb{E}[\hat{p}_i] = p_i$.
\\ \\
\textit{Proof:} We use strong induction over the number of words present in the corpus to prove the theorem.\\
\textbf{Base Case:} Consider a corpus $\mathcal{S}$ consisting of two words $w_1$ and $w_2$ with occurrence probabilities $p_1$ and $p_2$. Then three cases are possible as shown in Fig.\ref{fig:basecaseDiag}.\\
\textit{Case I:} The starting characters of $w_1$ and $w_2$ are different. Then, after using the random sample from $\mathcal{S}$ to train the Trie $n$ number of times. The Trie along with all the expected values of the \textit{Count} variables are shown in Fig.\ref{fig:basecaseDiag}(a). Clearly,
\begin{equation} \label{BaseCaseEqn1}
    \mathbb{E}[\hat{p}_1]=\frac{np_1}{np_1+np_2}=p_1
\end{equation}
and
\begin{equation} \label{BaseCaseEqn2}
    \mathbb{E}[\hat{p}_2]=\frac{np_2}{np_1+np_2}=p_2
\end{equation}
\textit{Case II:} Both $w_1$ and $w_2$ have a common string of characters in the front. For illustration, `more' and `most' have `mo' common at the front. Hence similar to Case I, it can be argued from Fig.\ref{fig:basecaseDiag}(b). that Eqn.(\ref{BaseCaseEqn1}) and Eqn.(\ref{BaseCaseEqn2}) hold true.\\
\textit{Case III:} $w_1$ can be obtained by appending a string of characters at the end of $w_2$ or vice versa. Here, as described earlier we introduce a dummy node, seen as the blue box in Fig.\ref{fig:basecaseDiag}(c). Similar to previous arguments, it can be seen that Eqn.(\ref{BaseCaseEqn1}) and Eqn.(\ref{BaseCaseEqn2}) hold.\\
Hence, for the base case when $|\mathcal{S}|=2$, the theorem is true.
\begin{figure}[t]
    \centering
    \includegraphics[width=\linewidth, height=8cm]{BaseCase.jpg}
    \caption{Induction Base Cases}
    \label{fig:basecaseDiag}
\end{figure}
\\
\textbf{Induction:} Assume that the theorem holds whenever $|\mathcal{S}|\leq k$ for some positive integer $k$. We now show that the theorem holds true for any corpus of size $k+1$. Hence assume that we are given the words $w_1,w_2,\ldots ,w_{k+1}$ with occurence probabilities $p_1,p_2,\ldots p_{k+1},$ respectively.

\textit{Case I:} Similar to Case I and Case II of the base case, all the words branch out at the same node together as in Fig.\ref{fig:inductionCase1}. The figure also shows the expected values of the $Counter$ variables after training the Trie $n$ number of times.
\begin{figure}
    \centering
    \includegraphics[width=\linewidth, height=8cm]{Induction1.jpg}
    \caption{Induction Step Case I}
    \label{fig:inductionCase1}
\end{figure}
Hence we can easily conclude that for each $i=1,2,\ldots k,k+1$,
\begin{equation}\label{inductionEqn1}
    \mathbb{E}[\hat{p}_i]=\frac{np_i}{np_1+\ldots +np_{k+1}}=p_i
    \vspace{-0.1cm}
\end{equation}
since $\sum_{i=1}^{k+1}{p_i}=1$.\\
\textit{Case II:} In this case, consider all such possible Tries which are not covered by Case I. These Tries are in a way ``more branched" than the ones considered in Case I. Consider $T$ to be any such Trie and denote its root by $R$. Notice that there must exist a subtree $T'$, which contains strictly less than $k+1$ and at least two nodes which have their \textit{End-Of-Word} set as \textit{True}. It is easy to see that if not so, then $T$ lies in Case I which is a contradiction. Let us denote the root of $T'$ by $R'$. Let us assume that the nodes in $T'$ for which $End-Of-Word$ is set to $True$ represent the words $w_{(1)},w_{(2)},\ldots ,w_{(r)}$ with probabilities $p_{(1)},p_{(2)},\ldots ,p_{(r)}$ respectively where $2\leq r <k+1$. Now suppose that $T$ instead of having the words $w_{(1)},w_{(2)},\ldots ,w_{(r)}$, has a word whose characters are defined by travelling from $R$ to $R'$ in the Trie as shown in Fig.\ref{fig:inductionCase2}. Let this prefix word be $w_\alpha$ with a probability of $p_\alpha=p_{(1)}+p_{(2)}+\ldots +p_{(r)}$. Hence $T$ now practically contains strictly less than $k+1$ words. Hence by the induction hypothesis, when we train $T$, such that each one of the $k+2-r$ words is used for training at least once, the expectation of the Trie probabilities matches the occurrence probabilities. This means for each $w_i\in T$ whose last node doesn't lie in $T'$, Eqn.(\ref{inductionEqn1}) holds true.
Also, at the end of the training,
\begin{align}
    \mathbb{E}[Count(R')] &= n\times (p_{(1)}+p_{(2)}+\ldots+p_{(r)}) \nonumber \\
    &= \alpha \times \sum_{i=1}^{r}{\frac{p_{(i)}}{p_{(1)}+p_{(2)}+\ldots+p_{(r)}}} \label{inductionEqn2}
\end{align}
where $\alpha=n\times (p_{(1)}+p_{(2)}+\ldots+p_{(r)})$. We can now consider $T'$ to be a standalone Trie by itself, consisting of  words $w_{(1)},w_{(2)},\ldots ,w_{(r)}$ but truncated from the front so as to remove the characters of $w_\alpha$. Let these truncated words in $T'$ be denoted by $w'_{(1)},w'_{(2)},\ldots ,w'_{(r)}$ with occurrence probabilities $p'_{(1)}+p'_{(2)}+\ldots+p'_{(r)}$. Now notice that $T'$ has been trained $\alpha$ number of times and since $r<k+1$, the expectation of probabilities of $T'$ will be the same as occurrence probabilities of the truncated words which from $T$ are given by:
\begin{equation}\label{newProbabEqn}
    p'_{(i)}=P_{occurrence}(w_{i}|w_\alpha)=\frac{p_{(i)}}{p_{(1)}+p_{(2)}+\ldots+p_{(r)}}
\end{equation}

\begin{figure}[t]
    \centering
    \includegraphics[width=6cm, height=6cm]{Induction2.jpg}
    \caption{Induction Step Case II}
    \label{fig:inductionCase2}
\end{figure}
Hence, as described earlier, using induction, for each $w'_{(i)}$, $i=1,\ldots ,r$
\begin{equation}\label{InductionEqn3}
    \mathbb{E}[\hat{p}'_{(i)}]=\frac{p_{(i)}}{p_{(1)}+p_{(2)}+\ldots+p_{(r)}}
\end{equation}
Let us consider the entire tree $T$ with its original words $w_{(1)},w_{(2)},\ldots ,w_{(r)}$ and not $w_\alpha$. Note that for each $w_{(i)}$, $i=1,2,\ldots,r$
\begin{equation}\label{InductionEqn4}
    \hat{p}_{(i)}=\hat{p}'_{(i)} \times \hat{p}_\alpha
\end{equation}
One may further notice that this is the same as $P_{Trie}(w_{(i)})=P_{Trie}(w_{(i)}|w_\alpha)\times P_{Trie}(w_\alpha)$, which implies that $\mathbb{E}[P_{Trie}(w_{(i)})]=\mathbb{E}[P_{Trie}(w_{(i)}|w_\alpha)]\times \mathbb{E}[P_{Trie}(w_\alpha)]$ since both of the random variables on the RHS are independent by definition. Also since $\mathbb{E}[\hat{p}_\alpha]=p_{(1)}+p_{(2)}+\ldots +p_{(r)}$, we can use Eqn.(\ref{InductionEqn3})
and Eqn.(\ref{InductionEqn4}) to get that, for each $w_{(i)}$, $i=1,\ldots ,r$
\begin{align}
    \mathbb{E}[\hat{p}_{(i)}]&=\mathbb{E}[\hat{p}'_{(i)}]\times \mathbb{E}[\hat{p}_\alpha] \nonumber \\
    &=\frac{p_{(i)}}{p_{(1)}+p_{(2)}+\ldots +p_{(r)}} \times (p_{(1)}+p_{(2)}+\ldots +p_{(r)}) \nonumber \\
    &=p_{(i)} \nonumber
\end{align}
Hence for each $w_i \in T$, $\mathbb{E}[\hat{p}_i]=p_{i}$ when $|\mathcal{S}|=k+1$.\\
\qed\\
\\
While Theorem 3.1 justifies the use of Trie through equality of occurrence probability and the expected Trie probability at any stage of training, the next theorem provides a more desired result.
\\ \\
\textbf{Theorem 3.2:} For each $w_i\in\mathcal{S}$, $\hat{p}_i \xrightarrow{a.s.}p_i$
as $n\rightarrow \infty$.\\

\textit{Proof:} Let $\eta_j$ denote a node of the Trie such that each time any one of the words $w_{(1)},\ldots w_{(\eta_j)}$ from $\mathcal{S}$ is sampled and used for training, its $Counter$ variable is incremented by 1. Let $W_{\eta_j}=\{w_{(1)},\ldots w_{(\eta_j)}\}$.\\
Define, a random variable $\mathbbm{1}_n^{\eta_j}$ such that,
\[
\mathbbm{1}_n^{\eta_j} =
     \begin{cases}
       1 &\quad\text{if }n^{th}\text{ training word }\in W_{\eta_j}\\
       0 &\quad\text{otherwise.} \\
     \end{cases}
\]
For a fixed node $\eta_j$, $\mathbbm{1}_n^{\eta_j}$ are i.i.d random variables for $n\in \mathbbm{N}$. Also for each $n\in \mathbbm{N}$, $\mathbb{E}[\mathbbm{1}_n^{\eta_j}]=p_{(1)}+\ldots +p_{(\eta_j)}$. Note that the $Counter$ variable of $\eta_j$ is actually $\sum_{i=1}^{n}{\mathbbm{1}_i^{\eta_j}}$. Hence by using the Strong Law Of Large Numbers,
\begin{equation} \label{a.s.MainEqn}
    \frac{Counter(\eta_j,n)}{n}=\frac{\sum_{i=1}^{n}{\mathbbm{1}_i^{\eta_j}}}{n} \xrightarrow[n\rightarrow \infty]{a.s.} p_{(1)}+\ldots +p_{(\eta_j)}
\end{equation}
With the above in mind, we proceed for induction over the number of words in $\mathcal{S}$.\\
\begin{figure}
    \centering
    \includegraphics[width=4cm, height=4cm]{Theorem2BaseCase.jpg}
    \caption{Base Case with Node Labels}
    \label{fig:Theorem2BaseCaseFig}
\end{figure}

\textbf{Base Case:} Let $\mathcal{S}$ contain two words $w_1$ and $w_2$ with occurrence probabilities $p_1$ and $p_2$. Then as in the previous theorem, we can get three cases which can be for our purposes be depicted by Fig.\ref{fig:Theorem2BaseCaseFig}. It is possible for $\eta_0$ to be the root note as well. It is also possible for exactly one of $\eta_1$ or $\eta_2$ to be a dummy node. This would cover all the three cases. \\
Now for $w_1,$
\begin{align}
    \hat{p}_1=&\frac{Counter(\eta_1,n)}{Counter(\eta_1,n)+Counter(\eta_2,n)} \nonumber \\
    =&\frac{Counter(\eta_1,n)/n}{Counter(\eta_1,n)/n+Counter(\eta_2,n)/n} \nonumber
\end{align}
Note that $Counter(\eta_1,n)/n \xrightarrow[n\rightarrow\infty]{a.s.}p_1$ and that $Counter(\eta_2,n)/n \xrightarrow[n\rightarrow\infty]{a.s.}p_2$. Hence, by using the Continuous Mapping Theorem \cite{van2000asymptotic}, we get that
\begin{equation}
    \hat{p}_1\xrightarrow[n\rightarrow\infty]{a.s.}\frac{p_1}{p_1+p_2}=p_1 \nonumber
\end{equation}
We can similarly show that $\hat{p}_2\xrightarrow[n\rightarrow\infty]{a.s.}p_2.$ Hence our base case i.e. $|\mathcal{S}|=2$ holds true.\\
The proof of the induction step is similar to that of Theorem 3.1 and is being skipped due to page constraint.\\
\qed\\\\
From Theorem 3.1 and Theorem 3.2 we conclude that from the perspective of Theory of Estimation and using the fact that almost sure convergence is stronger than convergence in probability, we get the following corollary\\
\\ \textbf{Corollary 3.3:} For each $w_i \in \mathcal{S}$, the Trie probability $\hat{p}_i$ is an unbiased and consistent estimator of the occurrence probability $p_i$.
\\ \\
Through the results above, we can infer that the new Trie can learn the occurrence probabilities for any set of words through sufficient training which in turn implies that the new Trie can adapt to the texting and typing style of any user when deployed on either a mobile phone, laptop or any such other device.
\begin{figure}
    \centering
    \includegraphics[width=\linewidth,height=7cm]{ASfig.jpg}
    \caption{Almost sure convergence to occurrence probabilities}
    \label{fig:asfigure}
\end{figure}

\section{Error Checking Algorithm}\label{Section4}
In this section, we built upon the error correction schemes used in the baseline model.
\subsection{The Bayesian approach}
As mentioned earlier in Section \ref{Section2}, in \cite{inbook} the words in the suggestions list were ranked solely based on the Trie probabilities. However, following \cite{Keyboards2019ImprovingTA}, we use a Bayesian noisy channel approach to rank the words based on the type of error committed by the user. This requires assignment of probabilities to the types of error for which confusion matrices in \cite{inproceedings} can be used. Hence
\begin{equation}
     P(w|\Tilde{w})\propto P(\Tilde{w}|w)P(w) \nonumber
\end{equation}
where $w$ denotes a possible correction for $\Tilde{w}$. $P(\Tilde{w}|w)$ depends on the type of error committed to get $\Tilde{w}$ from $w$ and $P(w)$ is the occurrence probability of $w$ estimated using the Trie.

\subsection{Character Bigram}
It was observed in \cite{inbook} that the Trie could generate suggestions up to a Damerau-Levenshtein distance of one. This is because generating an exhaustive list of words at a DL distance of two is computationally very expensive and is of time complexity $\mathcal{O}(26^{2M})$ where $M$ is the length of the error word. However, 80\% of human errors lie within a DL distance of one and almost all within a DL distance two \cite{10.1145/363958.363994}. To partially overcome this, we propose a heuristic on the lines of beam search algorithm \cite{6591953}, wherein we maintain a character probability bigram denoted by $C$ where $C[i][j]$ represents the probability of the next letter being 'j' given that the current letter is 'i'. At each stage of error correction, we provide a score to each word say $`s_1s_2\ldots s_n'$ as:
\begin{equation}
    score(word)=\Pi_{i=1}^{n-1}{C[s_{i}][s_{i+1}]}
\end{equation}
and set a threshold, say $\Gamma$. If the score exceeds the threshold, the word is passed on to the next stage of error correction. This ensures that most of the intermediate low probability words are discarded while only the ones with a very high probability are passed on further.
\begin{figure}
    \centering
    \includegraphics[width=\linewidth,height=7cm]{E.jpg}
    \caption{Equality of expectation to occurrence probabilites}
    \label{fig:efigure}
\end{figure}
\begin{figure*}
    \centering
    \includegraphics[width=\textwidth,height=10cm]{Compare.jpg}
    \caption{Performance comparison of the two TRIE based models}
    \label{fig:comparison}
\end{figure*}
\section{Simulations}\label{Section5}
\subsection{Almost sure convergence} \label{Section5.1}
In light of Theorem 3.2, a simulation was performed where we trained the new Trie using the training and probability generation algorithms defined in Section 3 with the eight words used in Section 2. The Trie probabilities denoted by the bold lines evidently converge to the occurrence probabilities denoted by the dotted lines in Fig.\ref{fig:asfigure}.
\subsection{Equality of expectation}
Similar to the simulation done in Section \ref{Section5.1}, we train 30 Tries and take the average of their probabilities. The bold lines can be seen to converge much faster to the dotted lines in Fig.\ref{fig:efigure} than in Fig.\ref{fig:asfigure}. This supports the theorem stating the equality of expectation of the Trie probabilities to the occurrence probabilities.
\subsection{Comparison}
In this simulation, we consecutively train both, the new Trie model proposed by us and the baseline Trie model using a corpus of twenty words. The assigned occurrence probabilities to these words are depicted in Fig.\ref{fig:comparison}. The new Trie clearly outperforms the one proposed baseline Trie. An important observation is that the baseline Trie probabilities clearly sum up to more than one, hence not a valid probability measure.

\subsection{Error correction}
We use a corpus of 3000 highest frequency English words\footnote{https://gist.github.com/h3xx/1976236} and use Zipf's Law\footnote{Value of the exponent characterising the distribution was set to 0.25} to fit\footnote{Not needed once deployed, model learns probability directly from the user.} a probability distribution over the ranked data. Comparative analysis with the baseline shown in Table \ref{ErrorCorrectionTable} clearly showcases superiority of the new model.
\begin{table}[h]
\caption{\label{tab:errorprobab}Comparison of output with baseline Trie}
 \centering
 \resizebox{\linewidth}{2.7cm}{
 \begin{tabular}{|c|c|c|c|c|}
 \hline
 Impure & Target & Top 5 Suggestions &Rank &Rank in \cite{inbook}\\ [0.5ex]
 \hline\hline
 tran & train & than, train , ran, trap, tan &2&5\\
 \hline
 lng & long & long, lang, log, leg, an, gang&1&4\\
 \hline
 aple&apple&pale, alle, able, apple, ample&4&5\\
 \hline
 beleive& believe &believe, believed, believes&1&1\\
 \hline
 gost& ghost & host, lost, most, past, ghost&5&1\\
 \hline
 moble & noble & noble, nobler, nobles&1&2\\
 \hline
 cuz & cause & use, case, cause, cut, cup&3&8\\
 \hline
 cin&seen &in, can, sin, son, skin &13&17\\
 \hline
 dem&them&them, then, den, chem, the&1&11\\
 \hline
 m8&mate&mate, might, eight, ate, mare&1&6\\
 \hline
 thx&thanks&the, thy, tax, thanks, them&4&1\\
 \hline
 h8&hate&hate, height, hare, ate, haste&1&-\\
 \hline
 \end{tabular}}
 \label{ErrorCorrectionTable}
\end{table}

\section{Conclusions}\label{Section6}
In the paper, we first pointed out a a limitation in the Trie based probability generating model proposed in existing literature, to overcome which, we proposed a structural modification, a training algorithm and a probability generating scheme. We further proved rigorously that the new Trie generated probabilities are an unbiased and consistent estimator of the occurrence probabilities. These occurrence probabilities vary user to user which the new Trie is capable of adapting to. We performed simulations, the results of which strongly support both the presented theorems and demonstrated superiority in error
correction.


\section{Introduction}
Fully automatic cardiac segmentation methods can help clinicians to quantify the heart structure (e.g. left ventricle (LV), myocardium (MYO), and right ventricle (RV)) from cardiac magnetic resonance (CMR) images for diagnosis of multiple heart diseases \cite{bernard2018deep}.
Deep learning-based methods have shown promising avenues for cardiac image segmentation \cite{chen2020deep}. However,
existing work \cite{yan2020mri} have shown that the segmentation performance of such methods may drop in when they are directly tested to scans acquired from different centres or vendors. The degradation of performance is not only caused by the varying cardiac morphology but also the differences of acquisition parameter, resolution, intensity distribution, etc. \cite{petitjean2011review} as shown in Fig. \ref{samples}. All these factors pose obstacles for deploying deep learning-based segmentation algorithms in real-world clinical practice.

\begin{figure}
	\centering
    \includegraphics[height=0.37\textwidth,width=\textwidth]{distribution.png}
    \caption{The differences of image appearance, resolution and intensity distributions in the cardiac structures (i.e. LV, MYO, RV) of three vendors.}
	\label{samples}
\end{figure}

One simple way to address the above issues
is to fine-tune a model learned from some datasets (source domains) with extra labelled data from another dataset (target domain). However, collecting sufficient pixel-level labelled medical data for all centres and vendors is extremely difficult which require fully clinical studies. To mitigate these issues, domain adaptation methods have been proposed to generalise one algorithm trained on some datasets (source domain) with additional data (either labelled or not labelled) from another dataset
(target domain) \cite{chen2019synergistic,zhuang2020cardiac,yan2019domain}. Data augmentation-based methods are further proposed to enhance the generalisability of cardiac image segmentation models \cite{zhang2020generalizing,chen2019improving}. Generally, it is clinically relevant to explore how to learn a generalisable model that can be successfully applied to other datasets without additional model tuning.

In this work, we present a fully automatic segmentation framework to segment three cardiac structures (i.e. LV, MYO, and RV) and to mitigate the above issues caused by domain shifts. It is achieved by leveraging generative adversarial networks to transfer image style and stacked image processing techniques to augment the training samples and thus to generalise the segmentation model to unseen domains. Specifically, our approach mainly consists of three modules:\\
\noindent{(i) A target domain transfer network.} This module is used for learning the underlying intensity distribution of the unlabeled vendor and translate the labeled vendor to the target vendor, to augment the training set with \textbf{synthetic vendor-C-like} images and annotation from vendor \emph{A} and \emph{B }. Specifically we develop an attention-GANs with a focus on the cardiac structure. \\
\noindent{(ii) A stacked image transformation function. To simulate real-world testing conditions and to increase data variations, we apply a stack of six spatial and intensity transformations to overcome the domain shifts.} \\
\noindent{(iii) A segmentation model. A residual U-shape convolutional neural network with dilated convolutions \cite{li2018automatic} with a larger receptive field compared with U-Net is used to perform segmentation. It can capture richer context information with less parameters and is trained with all the data simulated above.}

\section{Methodology}

\begin{figure}[t]
	\centering
    \includegraphics[height=0.36\textwidth,width=\textwidth]{framework.png}
    \caption{Schematic view of our approach. It consists of three modules: a) image style transfer involving an attention GAN with a focus on cardiac structure, b) stacked data augmentation of several image transformations, and c) a segmentation network called \emph{DRUNET} with lighter number of weight but capture rich context information. }
	\label{framework}
\end{figure}

Given the challenge setting \footnote{https://www.ub.edu/mnms/}, the proposed method aims at learning an generalisable segmentation model for labelled vendor \emph{A} and labelled vendor \emph{B}:\{(x$_{A}$, y$_{A}$), (x$_{B}$, y$_{B}$)\}, unlabelled vendor \emph{C}: \{x$_{C}$\} where 25 scans were given but without labels, and the unseen vendor \emph{D}, where the data was hidden.

As shown in Fig. \ref{framework}, our framework mainly included three modules as mentioned above. Specifically, the image style transfer module translated the images from vendor \emph{A} and vendor \emph{B} to unlabeled vendor \emph{C} and further augmented the training set with {synthetic vendor-C-like} images and the annotations from vendor \emph{A} and \emph{B}. We enhanced the image quality by introducing an attention loss. The stacked data augmentation module aimed to further increase the data variation by employing several intensity and spatial transformation on the original and synthetic data after the first module. Last, the segmentation models were trained with all the original and synthetic data and performed inference with an ensemble model.

\subsubsection{Generative Adversarial Network with Attention.}
\begin{figure}
	\centering
    \includegraphics[height=0.35\textwidth,width=0.9\textwidth]{GANs.png}
    \caption{Overview of the image translation network. An attention- reconstruction loss was introduced to enhance the image quality of cardiac region. }
	\label{GANs}
\end{figure}

We adopted the CycleGAN \cite{zhu2017unpaired} as the basic architecture for one-to-one image translation. This included a pair of generators $\{G_{1}, G_{2}\}$ and a pair of domain discriminators $\{D_{1}, D_{2}\}$. As illustrated in Figure \ref{GANs}, generator $G_{1}$ aimed to translate images from a source vendor to a target vendor while generator $G_{2}$ aimed to translate from the target one to the source one. Discriminators $\{D_{1}, D_{2}\}$ are trained to distinguish if the generated images are real or fake in the two domains respectively. In a min-max game, the generators try to fool the discriminators by good image translation. However, since the cardiac structures were of interests, we further introduced a attention-reconstruction loss with a focus on cardiac structure:
\begin{equation}
	\mathcal{L}_{a\_rec} = \mathbb{E}_{x \sim \mathcal{S}}[||(x -G_{2}(G_{1}(x)))\odot m||_{1}] + \mathbb{E}_{y \sim \mathcal{T}}[||y-G_{1}(G_{2}(y))||_{1}]
	\end{equation}
Notably the mask \emph{m} was only applied to the source domains where the labels are available.
Thus, in addition to the original global reconstruction loss $\mathcal{L}_{g\_rec}$, we used a composite loss function which consists of two loss terms: $\mathcal{L}_{rec} =  \mathcal{L}_{g\_rec} + \lambda \mathcal{L}_{a\_rec}$. In
our experiments, we set $\lambda$ = 0.5 to balance the contribution of the two losses.
\vspace{-0.1cm}
\subsubsection{Stacked Augmentation.}
We proposed a sequence of $k$ stacked image transformations $f(\cdot)$ to simulate image distributions for unseen domains.
Given training data $x_{t}$ and the corresponding label $y_{t}$, augmented data $\hat{x}_{S}$ and the paired label $\hat{y}_{t}$ can be generated after $k$ transformations.
 \begin{equation}
 	(\hat{x}_{t}, \hat{y}_{t}) = f^{k}(f^{k-1}(...f^1(x_{t}, y_{t})))
 \end{equation}
We selected three intensity transformations and three spatial transformations: \\
\noindent{(1) image blurring and sharpening. Gaussian filtering was utilised to smooth the image to simulate blurry produced by motions. The standard deviation of a Gaussian kernel is ranged between [0.1, 2]. Meanwhile, we sharpened the image by using a unsharp masking. \\
\noindent{(2) intensity perturbation. The intensity range was shifted with a magnitude range between [-0.05, 0.05]}.\\
\noindent{(3) gamma correction.} This was used to adjust the contrast of the image with a range between [0.6, 1.7].\\
\noindent{(4) shearing.} This was aimed to equip the network with variance to deformations with a magnitude range between [-0.1, 0.1] was used for both images and masks.\\
\noindent{(5) rotation. A range between [-15\degree, 15\degree ] was used for both images and masks.} \\
\noindent{(6) scaling. This enforces the network to be scale-invariant to resolution. A magnitude range between [-0.1, 0.1]} was used for both images and masks. \\
\subsubsection{Segmentation Network.}
We adopted a top-perform 2D architecture named Dilated Residual U-Net (DRUNet) \cite{li2018automatic}, which was used for both brain and cardiac segmentation.
DRUNet exploited the inherent advantages of the skip connections, residual learning and dilated convolutions to capture rich context information with a minimal number of trainable parameters. The network was trained with a weight cross entropy loss function.

\section{Experiments}
\begin{table*}[htpb]
  \caption[table: Data Properties]{Multi-vendor datasets. Resolutions of scans from the same vendor are even different.}
  \label{tab:datasets}
  \centering
   \begin{tabular}{l c c c c }
    \hline
     Vendor& A & B & C  & D \\
    \hline
      {\tabincell{l}{Numbers\\(training/test)}}   & 75/50& 75/50  & 25/50 &0/50\\
     \hline
      {\tabincell{l}{Annotation\\Availability~(\%)}}  & yes& yes  & no & no\\
     \hline
  \end{tabular}

\end{table*}

\subsection{Experimental Setting}

\noindent\textbf{Datasets.} The released training set consists of 150 annotated scans from two different MRI vendors (75 for each) and 25 unannotated scans from a third vendor as shown in Table \ref{tab:datasets}. The CMR scans have been segmented by experienced clinicians, with contours for the left (LV) and right ventricle (RV) blood pools, and the left ventricular myocardium (MYO). The segmentation pipeline was evaluated on it and the results on the hidden validation set provided by the challenge organisers were presented. To optimise the segmentation model We use four labeled scans (2 from vendor A and 2 from vendor B) as a validation set, and the remains as a training set. For the final submission, we used all the whole released training set.

\noindent\textbf{Pre- and post- processing.}  The pre-processing of all the images (including the hidden test set) were performed in a slice-wise manner by three steps. First, non-local means denoising was performed for each slice to reduce the noise level considering that the image quality from multiple centres are diverse; second, the intensity range was normalised to [0,~1] to facilitate the model training; third, the images and masks are cropped or padded to [256,~256]. For post-processing, we performed connected component analysis and removed small structures with less than 30 voxels.

\noindent\textbf{Network training.}  (1) For the image translation network, we used the CycleGAN implementation for the one-to-one mappings: \emph{A} $\rightarrow$ \emph{C}, and  \emph{B} $\rightarrow$ \emph{C}. Network configuration and hyper-parameters were kept the same as in \cite{zhu2017unpaired} except the input and output images are single-channel 2D images. It was trained for 100 epochs with a batch size of 5 involving around 3500 images for each vendor including scans from multiple time points. (2) For training the segmentation model, the weights for background, LV, MYO, and
RV in the weighted cross entropy loss were empirically set to 0.19 : 0.24 : 0.31 : 0.26 based on the performance on the validation set. The algorithm was implemented using python and Tensorflow and was trained for
100 epochs in total on an NVIDIA® Titan V GPU. The training of the segmentation model took around 5 hours.

\subsection{Results}
We conducted three experiments to illustrate the effectiveness of our approach. First, we trained the DRUNet on solely the labeled datasets: vendor \emph{A} and \emph{B}, referred as \emph{baseline} in Table \ref{tab:results_Dice}. Second, we used the attention-GANs to generate good-quality vendor \emph{C}-like images and include those synthetic images and their corresponding labels for training, referred as \emph{baseline+a-GANs} in Table \ref{tab:results_Dice}. Lastly, we further incorporated the stacked image transformation and train the model from scratch, referred as \emph{ours} in the table. We found that after including the stacked image transformation, we drastically improved the segmentation performance on the hidden vendor \emph{D}, e.g. Dice for RV is improved from 14.5\% to 72.7\%. On the unlabeled vendor \emph{C}, we achieved average Dice score of 86.8\% for the left ventricle, 83.4\% for the myocardium, and
83.2\% for the right ventricle; on the hidden vendor, we achieved average Dice score of \textbf{89.3\%} for the left ventricle, \textbf{83.4\%} for the myocardium, and
72.7\% for the right ventricle.  Qualitative segmentation result from vendor \emph{C} is shown in Fig. \ref{samples}.

\begin{table}
\centering
\caption{Average Dice scores of all vendors, the highest performance in each class is highlighted.}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\multirow{2}{*}{Method}      &  \multicolumn{3}{c|}{Dice$_A$(\%)} &\multicolumn{3}{c|}{Dice$_B$(\%)} & \multicolumn{3}{c|}{Dice$_C$(\%)} &\multicolumn{3}{c| }{Dice$_D$(\%)}  \\
\cline{2-13}
 ~ &LV & MYO&RV& LV& MYO & RV & LV & MYO & RV  &LV & MYO&RV\\
\hline
Baseline &85.7 &77.1 & 66.6 & 92.2 &  83.9& 87.7  & 86.0  & 81.0 & 76.5 & 72.3  & 51.7 &14.5 \\

Baseline+a-GANs & 88.5  & 81.6 &71.8  & \textbf{94.2} & 86.6 & \textbf{91.5} & \textbf{87.7}  & \textbf{84.5} & 80.1 & 65.9 & 58.0 &13.3 \\
Ours (a-GANs+Stacked) &  \textbf{90.5} & \textbf{84.1} & \textbf{85.1}  & {93.6} & \textbf{87.5} & {91.1} & {86.8}  & {83.4} & \textbf{83.2} & \textbf{89.3} & \textbf{81.4} & \textbf{72.7}  \\
\hline
\end{tabular}
\label{tab:results_Dice}
\end{table}
\vspace{-0.2cm}
\begin{table}
\centering
\caption{Average Hausdorff distance (HD) of all vendors, the highest performance in each class is highlighted.}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\multirow{2}{*}{Method}      &  \multicolumn{3}{c|}{HD$_A$(mm)} &\multicolumn{3}{c|}{HD$_B$(mm)} & \multicolumn{3}{c|}{HD$_C$(mm)} &\multicolumn{3}{c| }{HD$_D$(\%)}  \\
\cline{2-13}
 ~ &LV & MYO&RV& LV& MYO & RV & LV) & MYO & RV  &LV & MYO&RV\\
\hline
Baseline &23.7  & 37.0 & 44.11 & 14.0 & 20.7 &23.4 &17.7 &19.4 &31.5 &27.5 &35.8  &61.8 \\

Baseline+a-GANs & 21.4  &31.2  &21.1  &\textbf{7.5}  &{11.7}  &12.4  &14.4  &16.3  &\textbf{16.7 } &22.3  &30.3  &42.0 \\
Ours (a-GANs+Stacked) &  \textbf{15.8} & \textbf{16.7} & \textbf{16.2}  & {7.9} & \textbf{11.0} & \textbf{11.5} & \textbf{10.9}  & \textbf{15.0} & {23.6} & \textbf{17.3} & \textbf{24.6} & \textbf{17.6}  \\

\hline
\end{tabular}
\label{tab:results_Dice}
\end{table}
\vspace{-0.2cm}

\begin{figure}
	\centering
    \includegraphics[height=0.75\textwidth,width=\textwidth]{samples.png}
    \caption{Qualitative segmentation result of one subject from vendor \emph{C}. a) baseline results; b) results of baseline+a-GANs; c) results of our method. Please note that the ground truth for vendor \emph{C} is not available.}
	\label{samples}
\end{figure}

\section{Conclusion}
We proposed a cardiac structure segmentation framework and segmented three structures: LV, MYO, and RV.
We demonstrated that domain shifts in heterogeneous cardiac imaging datasets can be drastically reduced by two aspects: 1) good-quality synthetic data by learning the underlying target domain distribution, and 2) stacked classical image transformation techniques for data augmentation.
\bibliographystyle{splncs04}