text:
# 随机算法 (Fall 2011)/Azuma's Inequality

We introduce a martingale tail inequality, called Azuma's inequality.

 Azuma's Inequality Let ${\displaystyle X_{0},X_{1},\ldots }$ be a martingale such that, for all ${\displaystyle k\geq 1}$, ${\displaystyle |X_{k}-X_{k-1}|\leq c_{k},}$ Then {\displaystyle {\begin{aligned}\Pr \left[|X_{n}-X_{0}|\geq t\right]\leq 2\exp \left(-{\frac {t^{2}}{2\sum _{k=1}^{n}c_{k}^{2}}}\right).\end{aligned}}}

Before formally proving this theorem, some comments are in order. First, unlike the Chernoff bounds, there is no assumption of independence. This shows the power of martingale inequalities.

Second, the condition that

${\displaystyle |X_{k}-X_{k-1}|\leq c_{k}}$

is central to the proof. This condition is sometimes called the bounded difference condition. If we think of the martingale ${\displaystyle X_{0},X_{1},\ldots }$ as a process evolving through time, where ${\displaystyle X_{i}}$ gives some measurement at time ${\displaystyle i}$, the bounded difference condition states that the process does not make big jumps. The Azuma's inequality says that if so, then it is unlikely that process wanders far from its starting point.

A special case is when the differences are bounded by a constant. The following corollary is directly implied by the Azuma's inequality.

 Corollary Let ${\displaystyle X_{0},X_{1},\ldots }$ be a martingale such that, for all ${\displaystyle k\geq 1}$, ${\displaystyle |X_{k}-X_{k-1}|\leq c,}$ Then {\displaystyle {\begin{aligned}\Pr \left[|X_{n}-X_{0}|\geq ct{\sqrt {n}}\right]\leq 2e^{-t^{2}/2}.\end{aligned}}}

This corollary states that for any martingale sequence whose diferences are bounded by a constant, the probability that it deviates ${\displaystyle \omega ({\sqrt {n}})}$ far away from the starting point after ${\displaystyle n}$ steps is bounded by ${\displaystyle o(1)}$.

The proof of Azuma's Inequality uses several ideas which are used in the proof of the Chernoff bounds. We first observe that the total deviation of the martingale sequence can be represented as the sum of deferences in every steps. Thus, as the Chernoff bounds, we are looking for a bound of the deviation of the sum of random variables. The strategy of the proof is almost the same as the proof of Chernoff bounds: we first apply Markov's inequality to the moment generating function, then we bound the moment generating function, and at last we optimize the parameter of the moment generating function. However, unlike the Chernoff bounds, the martingale differences are not independent any more. So we replace the use of the independence in the Chernoff bound by the martingale property. The proof is detailed as follows.

In order to bound the probability of ${\displaystyle |X_{n}-X_{0}|\geq t}$, we first bound the upper tail ${\displaystyle \Pr[X_{n}-X_{0}\geq t]}$. The bound of the lower tail can be symmetrically proved with the ${\displaystyle X_{i}}$ replaced by ${\displaystyle -X_{i}}$.

### Represent the deviation as the sum of differences

We define the martingale difference sequence: for ${\displaystyle i\geq 1}$, let

${\displaystyle Y_{i}=X_{i}-X_{i-1}.}$

It holds that

{\displaystyle {\begin{aligned}\mathbf {E} [Y_{i}\mid X_{0},\ldots ,X_{i-1}]&=\mathbf {E} [X_{i}-X_{i-1}\mid X_{0},\ldots ,X_{i-1}]\\&=\mathbf {E} [X_{i}\mid X_{0},\ldots ,X_{i-1}]-\mathbf {E} [X_{i-1}\mid X_{0},\ldots ,X_{i-1}]\\&=X_{i-1}-X_{i-1}\\&=0.\end{aligned}}}

The second to the last equation is due to the fact that ${\displaystyle X_{0},X_{1},\ldots }$ is a martingale and the definition of conditional expectation.

Let ${\displaystyle Z_{n}}$ be the accumulated differences

${\displaystyle Z_{n}=\sum _{i=1}^{n}Y_{i}.}$

The deviation ${\displaystyle (X_{n}-X_{0})}$ can be computed by the accumulated differences:

{\displaystyle {\begin{aligned}X_{n}-X_{0}&=(X_{1}-X_{0})+(X_{2}-X_{1})+\cdots +(X_{n}-X_{n-1})\\&=\sum _{i=1}^{n}Y_{i}\\&=Z_{n}.\end{aligned}}}

We then only need to upper bound the probability of the event ${\displaystyle Z_{n}\geq t}$.

### Apply Markov's inequality to the moment generating function

The event ${\displaystyle Z_{n}\geq t}$ is equivalent to that ${\displaystyle e^{\lambda Z_{n}}\geq e^{\lambda t}}$ for ${\displaystyle \lambda >0}$. Apply Markov's inequality, we have

{\displaystyle {\begin{aligned}\Pr \left[Z_{n}\geq t\right]&=\Pr \left[e^{\lambda Z_{n}}\geq e^{\lambda t}\right]\\&\leq {\frac {\mathbf {E} \left[e^{\lambda Z_{n}}\right]}{e^{\lambda t}}}.\end{aligned}}}

This is exactly the same as what we did to prove the Chernoff bound. Next, we need to bound the moment generating function ${\displaystyle \mathbf {E} \left[e^{\lambda Z_{n}}\right]}$.

### Bound the moment generating functions

The moment generating function

{\displaystyle {\begin{aligned}\mathbf {E} \left[e^{\lambda Z_{n}}\right]&=\mathbf {E} \left[\mathbf {E} \left[e^{\lambda Z_{n}}\mid X_{0},\ldots ,X_{n-1}\right]\right]\\&=\mathbf {E} \left[\mathbf {E} \left[e^{\lambda (Z_{n-1}+Y_{n})}\mid X_{0},\ldots ,X_{n-1}\right]\right]\\&=\mathbf {E} \left[\mathbf {E} \left[e^{\lambda Z_{n-1}}\cdot e^{\lambda Y_{n}}\mid X_{0},\ldots ,X_{n-1}\right]\right]\\&=\mathbf {E} \left[e^{\lambda Z_{n-1}}\cdot \mathbf {E} \left[e^{\lambda Y_{n}}\mid X_{0},\ldots ,X_{n-1}\right]\right]\end{aligned}}}

The first and the last equations are due to the fundamental facts about conditional expectation which are proved by us in the first section.

We then upper bound the ${\displaystyle \mathbf {E} \left[e^{\lambda Y_{n}}\mid X_{0},\ldots ,X_{n-1}\right]}$ by a constant. To do so, we need the following technical lemma which is proved by the convexity of ${\displaystyle e^{\lambda Y_{n}}}$.

 Lemma Let ${\displaystyle X}$ be a random variable such that ${\displaystyle \mathbf {E} [X]=0}$ and ${\displaystyle |X|\leq c}$. Then for ${\displaystyle \lambda >0}$, ${\displaystyle \mathbf {E} [e^{\lambda X}]\leq e^{\lambda ^{2}c^{2}/2}.}$
Proof.
 Observe that for ${\displaystyle \lambda >0}$, the function ${\displaystyle e^{\lambda X}}$ of the variable ${\displaystyle X}$ is convex in the interval ${\displaystyle [-c,c]}$. We draw a line between the two endpoints points ${\displaystyle (-c,e^{-\lambda c})}$ and ${\displaystyle (c,e^{\lambda c})}$. The curve of ${\displaystyle e^{\lambda X}}$ lies entirely below this line. Thus, {\displaystyle {\begin{aligned}e^{\lambda X}&\leq {\frac {c-X}{2c}}e^{-\lambda c}+{\frac {c+X}{2c}}e^{\lambda c}\\&={\frac {e^{\lambda c}+e^{-\lambda c}}{2}}+{\frac {X}{2c}}(e^{\lambda c}-e^{-\lambda c}).\end{aligned}}} Since ${\displaystyle \mathbf {E} [X]=0}$, we have {\displaystyle {\begin{aligned}\mathbf {E} [e^{\lambda X}]&\leq \mathbf {E} [{\frac {e^{\lambda c}+e^{-\lambda c}}{2}}+{\frac {X}{2c}}(e^{\lambda c}-e^{-\lambda c})]\\&={\frac {e^{\lambda c}+e^{-\lambda c}}{2}}+{\frac {e^{\lambda c}-e^{-\lambda c}}{2c}}\mathbf {E} [X]\\&={\frac {e^{\lambda c}+e^{-\lambda c}}{2}}.\end{aligned}}} By expanding both sides as Taylor's series, it can be verified that ${\displaystyle {\frac {e^{\lambda c}+e^{-\lambda c}}{2}}\leq e^{\lambda ^{2}c^{2}/2}}$.
${\displaystyle \square }$

Apply the above lemma to the random variable

${\displaystyle (Y_{n}\mid X_{0},\ldots ,X_{n-1})}$

We have already shown that its expectation ${\displaystyle \mathbf {E} [(Y_{n}\mid X_{0},\ldots ,X_{n-1})]=0,}$ and by the bounded difference condition of Azuma's inequality, we have ${\displaystyle |Y_{n}|=|(X_{n}-X_{n-1})|\leq c_{n}.}$ Thus, due to the above lemma, it holds that

${\displaystyle \mathbf {E} [e^{\lambda Y_{n}}\mid X_{0},\ldots ,X_{n-1}]\leq e^{\lambda ^{2}c_{n}^{2}/2}.}$

Back to our analysis of the expectation ${\displaystyle \mathbf {E} \left[e^{\lambda Z_{n}}\right]}$, we have

{\displaystyle {\begin{aligned}\mathbf {E} \left[e^{\lambda Z_{n}}\right]&=\mathbf {E} \left[e^{\lambda Z_{n-1}}\cdot \mathbf {E} \left[e^{\lambda Y_{n}}\mid X_{0},\ldots ,X_{n-1}\right]\right]\\&\leq \mathbf {E} \left[e^{\lambda Z_{n-1}}\cdot e^{\lambda ^{2}c_{n}^{2}/2}\right]\\&=e^{\lambda ^{2}c_{n}^{2}/2}\cdot \mathbf {E} \left[e^{\lambda Z_{n-1}}\right].\end{aligned}}}

Apply the same analysis to ${\displaystyle \mathbf {E} \left[e^{\lambda Z_{n-1}}\right]}$, we can solve the above recursion by

{\displaystyle {\begin{aligned}\mathbf {E} \left[e^{\lambda Z_{n}}\right]&\leq \prod _{k=1}^{n}e^{\lambda ^{2}c_{k}^{2}/2}\\&=\exp \left(\lambda ^{2}\sum _{k=1}^{n}c_{k}^{2}/2\right).\end{aligned}}}

Go back to the Markov's inequality,

{\displaystyle {\begin{aligned}\Pr \left[Z_{n}\geq t\right]&\leq {\frac {\mathbf {E} \left[e^{\lambda Z_{n}}\right]}{e^{\lambda t}}}\\&\leq \exp \left(\lambda ^{2}\sum _{k=1}^{n}c_{k}^{2}/2-\lambda t\right).\end{aligned}}}

We then only need to choose a proper ${\displaystyle \lambda >0}$.

### Optimization

By choosing ${\displaystyle \lambda ={\frac {t}{\sum _{k=1}^{n}c_{k}^{2}}}}$, we have that

${\displaystyle \exp \left(\lambda ^{2}\sum _{k=1}^{n}c_{k}^{2}/2-\lambda t\right)=\exp \left(-{\frac {t^{2}}{2\sum _{k=1}^{n}c_{k}^{2}}}\right).}$

Thus, the probability

{\displaystyle {\begin{aligned}\Pr \left[X_{n}-X_{0}\geq t\right]&=\Pr \left[Z_{n}\geq t\right]\\&\leq \exp \left(\lambda ^{2}\sum _{k=1}^{n}c_{k}^{2}/2-\lambda t\right)\\&=\exp \left(-{\frac {t^{2}}{2\sum _{k=1}^{n}c_{k}^{2}}}\right).\end{aligned}}}

The upper tail of Azuma's inequality is proved. By replacing ${\displaystyle X_{i}}$ by ${\displaystyle -X_{i}}$, the lower tail can be treated just as the upper tail. Applying the union bound, Azuma's inequality is proved.


text:
# Topic Modeling for Interpretable Text Classification From EHRs Emil Rijcken, et al.

May 4, 2022

## 1. Introduction

Inpatient violence at psychiatry departments is a common and severe problem (van Leeuwen and Harte, 2017). Typical adverse reactions that victims (professionals) face include emotional reactions, symptoms of post-traumatic stress disorder, and a negative impact on work functioning. Therefore, it is vital to assess the risk of a patient showing violent behavior and take preventive measures. The psychiatry department of the Utrecht Medical Center Utrecht uses questionnaires to predict the likelihood of patients becoming violent. However, filling out these forms is time-consuming and partly subjective. Instead, automated machine-learning approaches based on existing patient information could overcome the time burden and help make more objective predictions. Various automated text classification approaches utilizing clinical notes in the electronic health record allow for more accurate predictions than the questionnaires (Menger et al., 2018a; Mosteiro et al., 2021). In addition to accurate predictions, clinical providers and other decision-makers in healthcare consider the interpretability of model predictions as a priority for implementation and utilization. As machine learning applications are increasingly being integrated into various parts of the continuum of patient care, the need for prediction explanation is imperative (Ahmad et al., 2018). Yet, an intuitive understanding of the automated text classification approaches’ inner workings is currently missing, as the clinical notes are represented numerically by large dense matrices with unknown semantic meaning.

A more intuitive and potentially interpretable approach is text classification through topic modeling, where clinical notes can be represented as a collection of topics. To do so, a topic model is trained on all the written notes to find k topics. Each topic consists of the n most likely words associated with that topic and weights for each word. After training the topic model, all the documents associated with one patient can be represented by a k-length vector in which each cell indicates the extent to which that topic appears in the text. The assumption is that if the generated topics are well interpretable, the model’s decision making is more explainable. Several authors have focused on text classification through topic modeling in health care (Rumshisky et al., 2016; Wang et al., 2019). They use Latent Dirichlet Allocation (LDA) (Blei et al., 2003). Yet, many other topic modeling algorithms exist and selecting a model is not straightforward. A topic modeling algorithm for text classification should be selected based on predictive performance and interpretability. If a model performs well on predictions but is not interpretable, then there is no added value for our analysis in using topic models for this task. Similarly, if the predictive performance is low, but the interpretability is high, topic models should not be used for classification. We note that, to the best of our knowledge, no previous work focuses on both the predictive performance and interpretability of topic models for text classification.

In this article, we train seventeen different topic models and use their topic embeddings as input for text classification (violence prediction). Then, we analyze how each model’s interpretability compares to its predictive value. From this analysis, we make the following contributions:

1. We are the first to analyze both the predictive performance and topic modeling interpretability.

2. We compare 17 topic modeling algorithms based on both criteria.

3. We present considerations that can be used for the selection of a topic model for text classification.

The outline of the article is as follows. In Section 2, we describe how topic models work, how they can be used for text classification, how different algorithms relate to one another and which measures are used for evaluation. In Section 3, we describe our comparison methodology and the data set that we used. In Section 4, we provide tables and show graphs to illustrate how different topic modeling algorithms compare to each other. In Section 5, we discuss our findings, its implications and we conclude the work in Section 6.

## 2. Topic Modeling Algorithms

We compare different topic modeling algorithms based on their interpretability and predictive performance for text classification. In this section, we describe the task of text classification, followed by a description of topic models. Then, we discuss the best-known topic modeling algorithms and discuss how these have been used for text classification.

### 2.1. Text Classification

Classification models are a set of techniques that map input data (in the feature space) to a fixed set of output labels (Flach, 2012). Text classification is the task of assigning such a label to a text. Typically, a ML text classification pipeline contains two steps:

1. representation step,

2. classification step.

In the first step, a text file is transformed from a string into a numeric representation, called an embedding. The classification algorithm in the next step then calculates the most likely label based on the embedding. The choice of the technique depends on various aspects such as the number of features, the size of the data set and whether a technique should be interpretable. Typically, classification models are considered to be interpretable if they can indicate the weights that have been assigned to each input feature. Amongst classification models, the subset of commonly used interpretable models include linear regression, logistic regression, decision trees, fuzzy systems, and association rules (Guillaume, 2001; Alonso et al., 2015).

#### 2.1.1. Representation Techniques

Early approaches for representing texts numerically used the bag-of-words approach (BOW) to represent each word as a one-hot-encoding (Jurafsky and Martin, 2009). BOW suffers from two significant limitations: (i) it is hard to scale, (ii) it only considers the presence of a word in a text and not the word’s location. Therefore, it does not capture syntactic information.

Neural embeddings such as Word2Vec (Mikolov et al., 2013) do not suffer from BOW’s limitations and have been used widely ever since being introduced in 2013. Through neural embeddings, words are represented as dense vectors in a high-dimensional space such that semantically similar words are located close to each other. Since WordsVec’s introduction, several neural embedding approaches have been used for text classification, such as BERT (Devlin et al., 2018), Doc2Vec (Le and Mikolov, 2014), Glove (Pennington et al., 2014), and ELMO (Peters et al., 2018). These neural models have improved the performance of text classification significantly. However, relatively little is known about the information captured by these embeddings’ features. Therefore, there is still little understanding of the classification decisions in the subsequent step. Alternatively, the topics trained by topic models could serve as features for text classification. These topics are better interpretable than the features in neural representations and could help understand text classification decisions better.

### 2.2. Topic Models

Topic models are a group of unsupervised natural language processing algorithms that calculate two quantities:

1. P(Wi|Tk)- the probability of word i given topic k,

2. P(Tk|Dj)- the probability of topic k given document j,

with:

i word index i∈{1, 2, 3, …, M},

j document index j∈{1, 2, 3, …, N},

k topic index k∈{1, 2, 3, …, C},

M the number of unique words in the data set,

N the number of documents in the data set,

C the number of topics.

The top-n words with the highest probability per topic are typically taken to represent a topic. Topic models aim to find topics in which these top-n words in each topic are coherent with each other so that the topic is interpretable and a common theme can be derived. Using topic embeddings for text classification, each input document is transformed into a vector of size C. Each cell indicates the extent to which the document belongs to a topic. After predictions are made for each input text, interpretable classification algorithms can reveal which topics were most important for performing classifications.

### 2.3. Topic Modeling Algorithms

We compare a set of state-of-the-art topic modeling algorithms as defined in Terragni et al. (2021) supplemented with topic modeling algorithms we have developed in an earlier study (Rijcken et al., 2021). The different methods can be divided into two categories; methods based on dimensionality reduction and methods based on the Dirichlet distribution.

#### 2.3.1. Dimensionality Reduction Methods

The algorithms based on dimensionality reduction all start with a document-term matrix A. This could be a simple bag-of-words representation, but typically a weighting mechanism such as tf-idf is applied. The algorithms based on dimensionality reduction are the following.

##### 2.3.1.1. NMF

One of the oldest methods is non-negative matrix factorization (NMF) (Févotte and Idier, 2011). Using matrix A, NMF returns two matrices W & H. Since the vectors of the decomposed representations are non-negative, their coefficients are non-negative as well. W contains the found topics (topics × words) and H contains the coefficients (documents × topics). Then, NMF modifies W and H‘s initial values so that its product approaches A.

##### 2.3.1.2. LSI

Other foundational work on topic modeling is latent semantic indexing (LSI) which uses singular value decomposition for dimensionality reduction on matrix A (Landauer et al., 1998). SVD’s output is a decomposition of A, such that A = UΣVT. In this case, U emerges as the document-topic matrix P(Tk|Dj), V becomes the term-topic matrix P(Wi|Tk) and Σ contains singular values in its diagonal.

##### 2.3.1.3. FLSA

Similar to LSA, fuzzy latent semantic analysis (FLSA) starts with matrix A and uses singular value decomposition for dimensionality reduction (Karami et al., 2018). FLSA hypothesizes that singular value decomposition projects words into a lower dimensional space in a meaningful way, such that words that are semantically related are located nearby each other. FLSA takes the U matrix from singular value decomposition (number of singular values × number of documents), then performs fuzzy c-means clustering (Bezdek, 2013) to find different topics and lastly uses Bayes’ theorem and linear algebra to find the two output matrices.

##### 2.3.1.4. FLSA-W

Since FLSA works with the U matrix, which gives singular values for each document, the clustering is based on documents. Yet, topics are distributions over words and therefore clustering words seems to make more sense. Therefore, FLSA-W clusters on the V matrix instead of U, hence by clustering on words directly.

##### 2.3.1.5. FLSA-V

While FLSA and FLSA-W implicitly assume that the projection to a lower dimensional space occurs in a meaningful way, there is no explicit step guarantying it. FLSA-V uses a projection method similar to multi-dimensional scaling (Borg and Groenen, 2005) for embedding the words into a lower dimensional manifold such that similar words (based on co-occurrence) are placed close together on the manifold (Van Eck and Waltman, 2010). Then, the algorithm performs similar steps as FLSA-W to find the topics. We note that the projection step is very memory intensive and the implementation we need (VOSviewer software, Van Eck and Waltman, 2010) ran into memory issues with large corpuses and require heavy pruning to perform its mapping.

#### 2.3.2. Dirichlet-Based Models

##### 2.3.2.1. LDA

Underlying the class of dimensionality reduction methods that includes the prior models is the “BOW assumption,” which states that the order of words in a document can be neglected. The irrelevance of order also holds for documents, as it does not matter in what order documents occur in a corpus for a topic model to be trained. De Finetti’s representation theorem (De Finetti, 2017) establishes that any collection of exchangeable random variables has a representation as a mixture distribution. Thus, to consider exchangeable representations for words and documents, mixture models that capture the exchangeability of both should be used. This line of thought paves the way to Latent Dirichlet Allocation (LDA) (Blei et al., 2003), which is the best-known topic modeling algorithm on which multiple other topic models are based. LDA posits that each document can be seen as a probability distribution over topics and that each topic can be seen as a probability distribution over words. From a Dirichlet distribution, which is a multivariate generalization of the beta distribution, a random sample is drawn to represent the topic distribution. Then, a random sample is selected from another Dirichlet distribution to represent the word distribution.

##### 2.3.2.2. ProdLDA and NeuralLDA

Although the posterior distribution is intractable for exact inference, many approximate inference algorithms can be considered for LDA. Popular methods are mean-field methods and collapsed Gibbs sampling (Porteous et al., 2008). However, both of these methods require a rederivation of the inference method when applied to new topic models, which can be time-consuming. This drawback has been the basis for black-box inference methods, which require only very limited and easy to compute information from the model and can be applied automatically to new models (Srivastava and Sutton, 2017). Autoencoding variational Bayes (AEVB) is a natural choice for topic models as it trains an inference network (Dayan et al., 1995); a neural network that directly maps the BOW representation of a document onto a continuous latent representation. A decoder network then reconstructs the BOW by generating its words from the latent document representation (Kingma and Welling, 2014). ProdLDA and NeuralLDA are the first topic modeling algorithms that use AEVB inference methods. In ProdLDA, the distribution over individual words is a product of experts (it models a probability distribution by combining the output from several simpler distributions) rather than the mixture model used in NeuralLDA.

##### 2.3.2.3. ETM

Another problem with LDA is dealing with large vocabularies. To fit good topic models, practitioners must severely prune their vocabularies, typically done by removing the most and least frequent words. To this end, the embedded topic model (ETM) is proposed (Dieng et al., 2020). ETM is a generative model of documents that combines traditional topic models with word embeddings. The ETM models each word with a categorical distribution whose natural parameter is the inner product between the word’s embedding and an embedding of its assigned topic.

##### 2.3.2.4. CTM

The topic models described above should all be trained on unilingual datasets. However, many data sets (e.g., reviews, forums, news, etc.) exist in multiple languages in parallel. They cover similar content, but the linguistic differences make it impossible to use traditional, BOW-based topic models. Models have to be either unilingual or suffer from a vast but highly sparse vocabulary. Both issues can be addressed with transfer learning. The cross-lingual contextualized topic model (CTM), a zero-shot cross-lingual topic model, learns topics in one language and predicts them for unseen documents in different languages. CTM extends ProdLDA and is trained with input document representations that account for word-order and contextual information, overcoming one of the main limitations of the BOW models (Bianchi et al., 2020).

##### 2.3.2.5. HDP

A different topic modeling algorithm based on the Dirichlet distribution is the Hierarchical Dirichlet Process (HDP), which is a Bayesian non-parametric model that can be used to model mixed-membership data with a potentially infinite number of components. In contrast to all the algorithms discussed in this section, HDP is the only algorithm that determines the number of topics itself (rather than being set by the user). Given a document collection, posterior inference is used to determine the number of topics needed and to characterize their distributions (Wang et al., 2011).

## 3. Study Design

In this section, we provide the details of our comparative study. We describe first the dataset that we have used, followed by the training of the topic models. Then, we explain the classifier we used. Finally, we provide details of our comparison and evaluation methodology,

### 3.2. Training Topic Models

For the comparison of topic models, we have used the OCTIS Python package (Terragni et al., 2021) and FuzzyTM. In total, we train and compare 17 different algorithms: LDA, NeuralLDA, ProdLDA, NMF, CTM, ETM, LSI, HDP, and three variations for each FLSA, FLSA-W, and FLSA-V. The three variations for the FLSA-based algorithms differ in the fuzzy clustering algorithms used. We apply fuzzy c-means clustering (Bezdek, 2013), FST-PSO clustering (Nobile et al., 2018; Fuchs et al., 2019), and Gustafson-Kessel clustering (Gustafson and Kessel, 1979). Since the number of topics can influence a topic model’s coherence significantly (Rijcken et al., 2021), we train all the topics models with five to 100 topics in steps of five. Since HDP automatically selects the number of topics, we did not include this in the grid search for number of topics. To account for randomness in topic model initialization, we run each combination of topic models with the number of topics ten times. Consequently, we trained a total of 3,210 topic models (16 algorithms with 20 models plus the HDP model, make a total of 3,210 topic models).

### 3.3. Classification Model

We use two different approaches to create a topic embedding for each document. For the first approach, we include all the words of a topic’s distribution and use the vectors from P(T|D) for the classification of each document. We found 20 words to be most interpretable in previous research (Rijcken et al., 2021). For the second approach, we use a topic embedding approach based on the top n words per topic, since topics are typically represented by the top-n words. Hence, we also use n = 20 in this paper. For each topic, the probabilities associated with the words that are present in both the document and the topic’s top-20 words are aggregated.

There are many machine learning methods that can be used for classification. One of the most popular and simplest models for binary prediction is logistic regression. In this paper, we use logistic regression with 10-fold cross validation as the prediction model because of its simplicity and fast training time. A visual impression of the modeling pipeline is depicted in Figure 1.

Figure 1. Visual representation of the modeling pipeline per algorithm.

### 3.4. Evaluation

The evaluation of the topic models depends on the evaluation goals, which are operationalized through various metrics. In this paper, we consider the quality and the prediction performance of the topic model obtained by using the topic model as the criteria along which we evaluate different algorithms. The ideal way for evaluating the quality of a topic model is human evaluation. Various methods have been suggested for this purpose (Chang et al., 2009). However, human evaluation is costly in terms of effort and is not feasible with a large number of models. Since we are training and comparing 3,210 models, we use quantitative measures for comparison. In particular, we use an interpretability score and classification performance as the aspects along which our comparison is made. In this section, we explain the definition of these metrics.

#### Interpretability Score

Interpretability is an abstract concept that could be considered along a number of aspects. From the perspective of modeling from EHR data, our interactions with the clinicians have shown that two aspects are very important. Firstly, the words within each topic (intra-topic assessment) must be semantically related. We use the coherence score (cv) to quantify this. Secondly, different topics should focus on different themes and be diverse; for this, we use the diversity score (inter-topic assessment). Then, we formulate the interpretability score as the product between coherence and diversity, similar to Dieng et al. (2020).

Amongst the quantitative measures for intra-topic assessment, such as perplexity or held-out likelihood, methods that are based on Normalized Pointwise Mutual Information (NPMI) correlate best with human interpretation (Lau et al., 2014). One measure that incorporates NPMI is the coherence score. This score indicates how well words support each other and the score can be divided into four dimensions: the segmentation of words, the calculation of probabilities, the confirmation measure and the aggregation of the topic scores. Röder et al. (2015) tested each possible combination on six open data sets and compared it to human evaluation. Based on this extensive setup, cv was found to correlate highest with human evaluation, amongst all the coherence scores. With cv, the Normalized Pointwise Mutual Information (2) is calculated for the combination of all the top-n words in a topic. For the calculation of the NPMI, a sliding window of size 110 is used to calculate the probabilities. Then, the arithmetic mean is calculated to aggregate the scores for different topics.

The coherence score ranges between zero and one, where one means perfect coherence and zero means no coherence whatsoever. Since the coherence score focuses on the support of words within topics, it only focuses on intra-topic quality and ignores inter-topic quality.

A measure for inter-topic quality is topic diversity (Dieng et al., 2020), which measures the unique words in a topic model as a proportion to the total number of words (3). Mathematically, we calculate the topic diversity as follows. Let W* be the set of top-n words that have been identified for C topics. Then, the diversity score D is defined as

If the topic diversity equals one, different topics do not share any common words, whereas a value of

$\frac{1}{C}$

indicates that all topics contain the same n words.

#### Predictive Performance

To assess the predictive performance of the topic models, we use both the area under the ROC curve (AUC) (Fawcett, 2006) and the area under the Kappa curve (AUK) (Kaymak et al., 2012). The AUC is one of the most commonly used scalars for ranking model performance and was used in previous work as well (Mosteiro et al., 2020), (Menger et al., 2018a; Mosteiro et al., 2021). The AUC is independent of class priors, but it ignores misclassification costs. For this problem of violence risk assessment, misclassification costs may be asymmetric since having false positives is less problematic than having false negatives. The AUK is based on Cohen’s Kappa (Cohen, 1960) and corrects a model’s accuracy for chance agreement. The main difference between AUC and AUK is that AUK is more sensitive to class imbalance than AUC.

## 4. Results

Figure 2 shows the performance (AUC) against the interpretability index for the trained topic models. Figure 3 shows the same, but the predictive performance is measured by the AUK for both the top-20 words and the entire topic distribution. The subscript of each performance metric indicates the number of words considered for the prediction: 20 means the top 20 words only and all means the entire topic distribution is considered. The patterns in Figures 2, 3 look similar because the Kappa curve is a nonlinear transformation of the ROC curve, but there are also differences. For example, LSI results are clearly separated from LDA results according to AUC and interpretability, but the separation is much smaller when considering AUK. This is because AUK indicates that the performance of LSI and LDA models is more similar than what is indicated by AUC.

Figure 2. Model interpretability vs. predictive performance per trained model, as measured by the AUC_20 (only the top 20 words per topic are considered.).

Figure 3. Two graphs showing how a model’s interpretability relates to its predictive performance, as measured by the AUK per trained model. (A) Shows predictions based on a topics first 20 words only, while (B) takes an entire topics’ distribution into account.

Therefore, we will focus on the AUC only for the rest of this analysis. From the graphs, it can be seen that there is no correlation between a model’s interpretability and predictive power. Also, no model outperforms other models for both indicators, for all parameter settings. When basing the predictions on the top 20 words per topic only, FLSA-W (with fcm clustering) and ProdlDA seem to perform best. ProdLDA has many instances with the highest predictive performance (and average interpretability) and a few instances with the highest interpretability (and suboptimal predictive performance). In contrast, almost all instances of FLSA-W have high predictive performance and high interpretability, but no instance has a maximum for either of the variables. It seems that FLSA-W operates at a different trade-off point between performance and interpretability than ProdLDA.

Figure 4 shows for each model the effect of the number of topics interpretability. Each data point in this graph is the average of ten models trained with that setting. We only show each FLSA model with its best clustering method for clarity. For each FLSA model, we selected the clustering method that scored highest on interpretability on the most number of topics amongst the other clustering methods. To allow for comparison, we keep these settings for the following graphs. Except for the lowest number of topics, FLSA-W (with FCM clustering) scores best on interpretability on all numbers of topics. Since the interpretability consists of both the coherence- and the diversity score, both give relevant insights. Figure 5 shows the graphs for these variables. It can be seen that LDA scores the highest on topic coherence and the second-lowest on diversity. This means that the words in the topics support each other but that many topics share most of their words. FLSA-W has almost a perfect diversity score for all topics, and its coherence score is average. ProdLDA’s coherence score is slightly higher than LDA, but its diversity is much lower and decreases as the number of topics increase.

Figure 4. The effect of number of topics on the Interpretability—each data point is a mean score based on 10 runs.

Figure 5. The effect of number of topics on the coherence, based on the top 20 words (A) and diversity (B)—each data point is a mean score based on 10 runs.

Figure 6 shows the effect of different number of topics on the predictive performance. Note that for the FLSA-based models the clustering methods with the highest interpretability scores are shown only. Since the interpretability and predictive performances do not correlate, these models do not necessarily have the highest predictive performance. The graph shows that some models’ predictive performance is better when the top-20 words are considered only (CTM, FLSA-W, FLSA-V, ProdLDA, and NeuralLDA). In contrast, other models perform better when the entire topic distribution is considered (LDA, LSI, NMF). ProdLDA has the highest predictive performance based on the top 20 words only, whereas LSI has the highest predictive power based on the entire topic distribution.

Figure 6. The effect of number of topics on AUC. (A) Shows predictions based on 20 words only and (B) shows predictions based on the entire topic distribution—each data point is a mean score based on 10 runs.

## 5. Discussion

We study the behavior of different topic modeling algorithms based on their interpretability and predictive performance. LDA was used as a topic embedding in earlier text classification approaches with topic embeddings. However, Figure 2 shows that LDA has the lowest interpretability and predictive performance amongst all topic models. Although LDA has high coherence scores, many topics contain the same words, and therefore the interpretability is low. Our results show that selecting a topic model for text classification is not straightforward as no model outperforms the other models both in interpretability and predictive performance. If the interpretability needs to be maximized, FLSA-W is the new preferred model based on the interpretability index, whereas ProdLDA or LSI are preferred for maximal predictive performance.

Whether ProdLDA or LSI are preferred depends on the number of words per topic to base the predictions on. We argue that for the sake of interpretability, predictions based on a topic’s top-n (20 in our case) words are preferred over the ones based on the entire distribution on two counts. Firstly, we use topic embeddings for interpretable text classification. It is more intuitive to interpret a set of n words, than it is to interpret complete distributions where all distributions contain the same words, but the probabilities per word vary. Secondly, no meaningful coherence score can be calculated on a full distribution as the coherence considers the words of a topic and not the probability. If the full topic distribution is taken, the coherence score would be the same for all topic models. Note that, the best predictive performance of the LSI model, based on all words, performs almost on par (with the AUC slightly below 0.8) with the best predictive performance in earlier work (Mosteiro et al., 2021), and hence, we recommend considering topic embeddings for future text classification approaches is reasonable.

Surprisingly, Figure 2 which is based on all models, shows no correlation between model interpretability and predictive performance. Figure 7 shows the same data as Figure 2 but zoomed in on FLSA_W_FCM and FLSA_W_GK. We observe a positive correlation between the two variables for these two models. In contrast, ETM, NMF, LSI, LDA, FLSA_W_fst_pso, FLSA_V_fst_pso, FLSA_V_fcm show a slightly negative correlation between interpretability and predictive performance. The lack of correlation between these two variables raises the question of what information the classifier uses for its decisions. If words in topics do not support each other, then a topic is considered noisy. Yet, the predictive performance of models is reasonably high, implying there might be some tension between topic coherence and the prediction ability of the models.

Figure 7. Interpretability vs. AUC_20 zoomed in FLSA_W_FCM and FLSA_W_GK shows a positive correlation between interpretability and predictive performance – each data point represents a trained model.

A limitation of our work is that we work with a private, specific and imbalanced dataset with relatively long texts. Therefore, it is unknown whether our results can be extended to other datasets. Another limitation is that we formulate interpretability as the product between a topic’s coherence and diversity, based on recent work (Dieng et al., 2020). However, coherence does not always correlate with human interpretation (Rijcken et al., 2021). Furthermore, human evaluations could shine more lights on the topic interpretability, but this is infeasible in our current setup due to the high number of topic models that we have trained (3,210). Lastly, interpretability cannot be reduced to a single number as it is a complex concept, but using a single metric can serve as a proxy for topic comparison at large scale.

## 6. Conclusion

There are many applications of text classification based on electronic health records in the clinical domain. For these tasks, classification interpretability is imperative. Using topic modeling algorithms as topic embeddings for text classification might make a model more explainable. Therefore, this work studies both the topic’s interpretability and predictive performance for interpretable text classification. Comparing all models, we have not found a model that outperforms the other models both on interpretability and on predictive performance. Based on our findings, the FLSA-W (fcm) seems to be the best model for interpretability, whereas ProdLDA seems the best choice for predictive performance. However, this finding is based on one dataset only, and future work should assess the generalizability to other datasets. We found no correlation between a model’s interpretability and predictive performance. More specifically, we observed that some topic models’ predictive performance correlate positively with interpretability, whereas others show an inverse correlation. Also, we found that some models’ predictions are better when the entire topic distribution is used, whereas others score better with the top 20 words only. This work demonstrates that selecting a topic modeling algorithm for text classification is not straightforward and requires careful consideration. Future work will investigate based on which information classifiers make their decisions. This insight could explain why different models’ predictive performance correlates differently with interpretability and why for some models, predictions are better when based on the entire distribution and others are better when based on the top-n words only. Since we assess a topic’s interpretability quantitatively, future work should also focus on qualitatively assessing a topic’s interpretability. If topics are found to be interpretable based on the qualitive assessment, the decisions made by the text classification algorithm are more interpretable. With interpretable algorithms, we are one step closer to implementing automated methods for violence risk assessment and other text classification tasks in the mental health setting.

## Data Availability Statement

The datasets presented in this article are not readily available because this is a dataset with pseudonymized clinical notes from the EHR. Requests to access the datasets should be directed to [email protected]

## Author Contributions

ER and UK planned the experiment. The experiment was carried out by ER. PM supported with the coding. The manuscript was written by ER, with support from UK, FS, MS, and KZ. The dataset was provided by FS. All authors contributed to the article and approved the submitted version.

## Conflict of Interest

The authors declare that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest.

## Publisher’s Note

All claims expressed in this article are solely those of the authors and do not necessarily represent those of their affiliated organizations, or those of the publisher, the editors and the reviewers. Any product that may be evaluated in this article, or claim that may be made by its manufacturer, is not guaranteed or endorsed by the publisher.

## Acknowledgments

We acknowledge the COmputing VIsits DAta (COVIDA) funding provided by the strategic alliance of TU/e, WUR, UU, and UMC Utrecht.

format: plain


text:
# How do you find the derivative of sin ^2 (2x) + sin (2x+1) ?

Mar 8, 2016

You can find it like this:

#### Explanation:

$f \left(x\right) = {\sin}^{2} \left(2 x\right) + \sin \left(2 x + 1\right)$

Applying the chain rule successively:

$f ' \left(x\right) = 2 {\left[\sin \left(2 x\right)\right]}^{1} \times \cos \left(2 x\right) \times 2 + \left[\cos \left(2 x + 1\right) \times 2\right]$

$\therefore f ' \left(x\right) = 4 \sin \left(2 x\right) \cos \left(2 x\right) + 2 \cos \left(2 x + 1\right)$


text:
• anonymous
Find all the integral solutions of the equation $$8y + 11x + 17 =xy$$.
Mathematics

Looking for something else?

Not the answer you are looking for? Search for more explanations.


text:
Cantera  2.1.2
TortuosityBruggeman Class Reference

Base case to handle tortuosity corrections for diffusive transport in porous media using the Bruggeman exponential approximation. More...

#include <TortuosityBruggeman.h>

Inheritance diagram for TortuosityBruggeman:
[legend]
Collaboration diagram for TortuosityBruggeman:
[legend]

## Public Member Functions

TortuosityBruggeman (doublereal setPower=1.5)
Default constructor uses Bruggeman exponent of 1.5. More...

TortuosityBruggeman (const TortuosityBruggeman &right)
Copy Constructor. More...

TortuosityBruggemanoperator= (const TortuosityBruggeman &right)
Assignment operator. More...

virtual TortuosityBaseduplMyselfAsTortuosityBase () const
Duplication operator. More...

virtual doublereal tortuosityFactor (doublereal porosity)
The tortuosity factor models the effective increase in the diffusive transport length. More...

virtual doublereal McMillanFactor (doublereal porosity)
The McMillan number is the ratio of the flux-like variable to the value it would have without porous flow. More...

Public Member Functions inherited from TortuosityBase
TortuosityBase ()
Default constructor uses Bruggeman exponent of 1.5. More...

TortuosityBase (const TortuosityBase &right)
Copy Constructor. More...

virtual ~TortuosityBase ()
Default destructor for TortuosityBase. More...

TortuosityBaseoperator= (const TortuosityBase &right)
Assignment operator. More...

## Protected Attributes

doublereal expBrug_
Bruggeman exponent: power to which the tortuosity depends on the volume fraction. More...

## Detailed Description

Base case to handle tortuosity corrections for diffusive transport in porous media using the Bruggeman exponential approximation.

Class to compute the increase in diffusive path length associated with tortuous path diffusion through, for example, porous media. This base class implementation relates tortuosity to volume fraction through a power-law relationship that goes back to Bruggeman. The exponent is referred to as the Bruggeman exponent.

Note that the total diffusional flux is generally written as

$\frac{ \phi C_T D_i \nabla X_i }{ \tau^2 }$

where $$\phi$$ is the volume fraction of the transported phase, $$\tau$$ is referred to as the tortuosity. (Other variables are $$C_T$$, the total concentration, $$D_i$$, the diffusion coefficient, and $$X_i$$, the mole fraction with Fickian transport assumed.)

The tortuosity comes into play in conjunction the the

Definition at line 44 of file TortuosityBruggeman.h.

## Constructor & Destructor Documentation

 TortuosityBruggeman ( doublereal setPower = 1.5 )

Default constructor uses Bruggeman exponent of 1.5.

Parameters
 setPower Exponent in the Bruggeman factor. The default is 1.5

Definition at line 21 of file TortuosityBruggeman.cpp.

Referenced by TortuosityBruggeman::duplMyselfAsTortuosityBase().

 TortuosityBruggeman ( const TortuosityBruggeman & right )

Copy Constructor.

Parameters
 right Object to be copied

Definition at line 31 of file TortuosityBruggeman.cpp.

## Member Function Documentation

 TortuosityBruggeman & operator= ( const TortuosityBruggeman & right )

Assignment operator.

Parameters
 right Object to be copied

Definition at line 42 of file TortuosityBruggeman.cpp.

References TortuosityBruggeman::expBrug_, and TortuosityBase::operator=().

 TortuosityBase * duplMyselfAsTortuosityBase ( ) const
virtual

Duplication operator.

Returns
Returns a pointer to a duplicate of the current object given a base class pointer

Reimplemented from TortuosityBase.

Definition at line 59 of file TortuosityBruggeman.cpp.

References TortuosityBruggeman::TortuosityBruggeman().

 doublereal tortuosityFactor ( doublereal porosity )
virtual

The tortuosity factor models the effective increase in the diffusive transport length.

This method returns $$1/\tau^2$$ in the description of the flux

$$C_T D_i \nabla X_i / \tau^2$$.

Reimplemented from TortuosityBase.

Definition at line 72 of file TortuosityBruggeman.cpp.

References TortuosityBruggeman::expBrug_.

 doublereal McMillanFactor ( doublereal porosity )
virtual

The McMillan number is the ratio of the flux-like variable to the value it would have without porous flow.

The McMillan number combines the effect of tortuosity and volume fraction of the transported phase. The net flux observed is then the product of the McMillan number and the non-porous transport rate. For a conductivity in a non-porous media, $$\kappa_0$$, the conductivity in the porous media would be $$\kappa = (\rm McMillan) \kappa_0$$.

Reimplemented from TortuosityBase.

Definition at line 86 of file TortuosityBruggeman.cpp.

References TortuosityBruggeman::expBrug_.

## Member Data Documentation

 doublereal expBrug_
protected

Bruggeman exponent: power to which the tortuosity depends on the volume fraction.

Definition at line 99 of file TortuosityBruggeman.h.

The documentation for this class was generated from the following files:


text:
# [SOLVED]Expected value of steps

#### MATHias

##### New member
Hello,

I would like to ask, if I am right with my computation.

Let´s have a set of integers from 0 to 12. We start at 0 and we can go to 1 with the probability 1. From 1 we can go to 1 or back to 0, both with probability 0.5. When we start at zero, how many steps (exp. number of them) do we need to go until 12?

My way of solving:

We start at 0 ... there is only one possibity - to go to the 1 with probability 1
From 1, we can go to the 0 (P=$\frac{1}{2}$) or to the 2 (P=$\frac{1}{2}$)
From 2, we can go back to the 1(P=$\frac{1}{2}$), or forwards to the 3(P=$\frac{1}{2}$) ... but when we start at 0, there is the probability to reach 3(P=${\frac{1}{2}}^{2}$).
etc.

So, I created a binomial distribution:
From 0 to 1: 1 step; prob. 1 ... 1*1
From 0 to 2: 2 steps; prob. ${12 \choose 1}*\frac{1}{2}^{1}*{\frac{1}{2}}^{11}$
From 0 to 3: 3 steps; prob. ${12 \choose 2}*{\frac{1}{2}}^{2}*{\frac{1}{2}}^{10}$
...
From 0 to 11: 11 steps; prob. ${12 \choose 10}*{\frac{1}{2}}^{10}*{\frac{1}{2}}^{2}$
From 0 to 12: 12 steps; prob. ${12 \choose 11}*{\frac{1}{2}}^{11}*{\frac{1}{2}}^{1}$

And now, to get the whole expected value, I need to sum all the expected values:
$1*1+12*2(steps)*\frac{1}{2048}+66*3\frac{1}{2048}+220*4\frac{1}{2048}+495*5\frac{1}{2048}+792*6*\frac{1}{2048}+924*7*\frac{1}{2048}+792*8*\frac{1}{2048}+495*9*\frac{1}{2048}+220*10*\frac{1}{2048}+66*11*\frac{1}{2048}+12*12*\frac{1}{2048}$.

The sum is 15353/1024 = 14.9932 steps. I think it is too low number. Can I ask, where I am not doing right?

Thank you a lot.

Have a nice day.

Last edited:

#### Country Boy

##### Well-known member
MHB Math Helper
You could, of course, go from 0 directly to 12 in exactly 12 steps! The probability of that is $$(1/2)^{11}$$. Or, you could, exactly once, go a step back. In that case, ignoring the first step from 0 to 1, you would have 13 steps, "x" steps up to that point, then one step back, then one step to get back to that point, then the remaining 13- x steps for a total x+ 2+ 13- x= 13 steps. The probability of that is $$(1/2)^{13}$$. Now do the same if we go back twice: either at two different steps or twice at the same step. Each step backwards adds 2 steps to the total so going back twice gives a total of 15 steps. And those steps have probability 1/2 so the probability is $$(1/2)^{15}$$.

In general, there can be any even number of steps or, ignoring the first step, any odd number of steps. For 2n+ 1 steps The probability is $$(1/2)^{2n+1}$$. The expected value is given by the infinite sum $$\sum_{n= 0}^\infty(2n+1)(1/2)^{2n+1}$$. To sum that factor out a 1/2 so it becomes $$\frac{1}{2}\sum_{n=0}^\infty (2n+1)(1/2)^{2n}$$. Notice that $$(2n+1)x^{2n}$$ is the derivative of $$x^{2n+1}$$ so we can do $$\sum_{n=0}^\inf (2n+1)x^{2n}$$ as the derivative of $$\sum_{n=0}^\infty x^{2n+ 1}= x\sum_{n=0}^\infty (x^2)^n$$. That last sum is a geometric sum which has a simple closed form: $$x\frac{1}{1- x^2}$$ as long as |x|< 1. Here x= 1/2 so that formula applies and the derivative is $$\left(\frac{x}{1- x^2}\right)'= \frac{(1- x^2)- (-2x^2)}{1- x^2)^2}= \frac{1+ x^2}{(1- x^2)^2}$$. For x= 1/2 that is $$\frac{1+ 1/4}{(1- 1/4)^2}= \frac{\frac{3}{4}}{\frac{9}{16}}= \frac{3}{4}\frac{16}{9}= \frac{4}{3}$$.

#### Opalg

##### MHB Oldtimer
Staff member
This is an example of an absorbing Markov chain. By calculating the fundamental matrix for this problem, I found that in order to reach level 12 you have to spend an average of 2 steps at level 11, an average of 4 steps at level 10, 6 steps at level 9 and so on (two extra steps for each level as you go down) till you get to 20 steps at level 2, 22 steps at level 1 and 12 steps at level 0 (12 rather than 24 because from level 0 you have to go back to level 1). Therefore the expected total number of steps to reach level 12 is $2+4+6+8 + \ldots + 22 + 12 = 144$ (considerably more than 14.9932!).

Last edited:

#### MATHias

##### New member
Yeah, I see. I had expected more complicated theory in that. Sometimes, it is just easier to draw a graphics to see that. Thanks a lot to both of you.


text:
##### Exercise4

We have seen how a matrix transformation can perform a geometric operation; now we would like to find a matrix transformation that undoes that operation.

1. Suppose that $$T:\real^2\to\real^2$$ is the matrix transformation that rotates vectors by $$90^\circ\text{.}$$ Find a matrix transformation $$S:\real^2\to\real^2$$ that undoes the rotation; that is, $$S$$ takes $$T(\xvec)$$ back into $$\xvec$$ so that $$S\circ T(\xvec) = \xvec\text{.}$$ Think geometrically about what the transformation $$S$$ should be and then verify it algebraically.

We say that $$S$$ is the inverse of $$T$$ and we will write it as $$T^{-1}\text{.}$$

2. Verify algebraically that the reflection $$R:\real^2\to\real^2$$ across the line $$y=x$$ is its own inverse; that is, $$R^{-1} = R\text{.}$$

3. The matrix transformation $$T:\real^2\to\real^2$$ defined by the matrix

\begin{equation*} A=\left[\begin{array}{rr} 1\amp 1 \\ 0 \amp 1\\ \end{array}\right] \end{equation*}

is called a shear. Find the inverse of $$T\text{.}$$

4. Describe the geometric effect of the matrix transformation defined by

\begin{equation*} A=\left[\begin{array}{rr} \frac12 \amp 0 \\ 0 \amp 3\\ \end{array}\right] \end{equation*}

and then find its inverse.

in-context


text:
# 4. Simple Skewness

Week
Week 02
Description
Problems
Module
This lecture is based on the problem called “Simple Skewness” (8VC Venture Cup 2016 - Elimination Round, Codeforces; Problem E), and you can find a link to it here.
In this problem we are trying to find a subset which maximizes the difference between the mean and the median! You can find the explanation that this lecture is based on over at Petr’s blog.
We claim that for arrays of even size with non-negative skewness, you can remove the larger of the two middle elements to ensure that you get to an array with an odd number elements whose skewness is no less than in the original array. This can be shown with the following computation, which I skipped in class.

Recall that the simple skewness of a set of numbers is defined as the difference between the mean and the median of .
Claim. Let be a set of integers with non-negative simple-skewness, and let be the upper middle element, i.e, the -th element if the elements of are written in sorted order. We claim that the simple skewness of the set is at least the simple skewness of the original set .
Proof (version 1; from this comment).
Let be the mean, let and be the center elements, and let be the median.
By the assumption that has non-negative skewness, we have that .
Now, after dropping , the median decreases to by , which is .
The mean decreases to , which is a decrease by . Since (given that is even), we have that:
and by the assumption that , we have that:
.
Thus, the mean decreases by at most as much as the median, as desired.
(To see that this indeed implies the claim, see the slightly more elaborate explanation below.)
Proof (version 2, in the search of a more visual/intuitive approach).
Let’s establish some notation. Using to denote the mean of a set, to denote the median of a set, and to denote the simple skewness of a set, we have:
and
We want to prove that:
under the assumption that:
Let and denote the -th and -th elements of , respectively, when the elements of are listed in sorted order. Then the assumption above translates to:
Notice that , and since , we know that the mean decreases when we “drop ” from , i.e, .
So rewriting what we want to prove:
in other words, the claim above is equivalent to saying the following:
dropping from decreases the median by at least as much as it decreases the mean, assuming the mean is at least as large as the median,
and showing this will imply the claim.
Let’s work out what these decreases amount to. Let denote the sum of all elements in except for and . First, consider the change of mean:
Simplifying further, we have:
On the other hand, consider the change of median:
Now let us write , which is the sum of all the integers in , in terms of , as follows:
where is the sum of for all such that and is the sum of for all such that .
Observe that by our assumption that:
we have the following:
Let’s now go back to what we wanted to show: the decrease in the median is at least the decrease in the mean, substituting :
But this simplifies to:
Since (recall that is even), we see that the above is equivalent to:
which is indeed true from the assumption that the mean is at least the median, as shown above. 🥳
Remark. Do we really need the assumption that the simple skewness of is non-negative to begin with? It turns out that yes, we do! Without this assumption the statement may not be true, here's a counter example (h/t: Harshil Mittal): and . Then but . I am not sure if a weaker version of the claim holds without the assumption; i.e, does there always exist some element whose removal preserves (i.e, does not decrease) the simple skewness of the original set?

If you have either a visual proof for the claim made or some ideas for this more general question, please join the conversation I’ve opened on Twitter inspired by this situation here.
The code discussed in the video can be found here.


text: The diagram shows a right-angled isosceles triangle $XYZ$ which circumscribes a square $PQRS$. What is the ratio of the area of square $PQRS$ to the area of the triangle $XYZ$?