text:
# New paper “A GSOS for Attribute-based Communication”

The short paper A GSOS for Attribute-based Communication by Matteo Paier and myself, has been accepted to EXPRESS/SOS, the Combined 26th International Workshop on Expressiveness in Concurrency and 16th Workshop on Structural Operational Semantics.

Abstract: We propose a new GSOS semantics fo AbC, a calculus for attribute-based communication. This semantics is simpler than the previous ones, but as much as expressive; in fact, we will show that there is a precise equivalence. The new semantics will be useful for simplifying bisimulation proofs, and it is preparatory to the definition of a bialgebraic semantics for AbC.


text:
# Covariant derivative of stress-energy tensor

hi, I understand that Tab,b=0 because the change in density equals the negative divergence, but why do the christoffel symbols vanish for Tab;b=0?

Related Special and General Relativity News on Phys.org
Ben Niehoff
Gold Member
They don't. Why would you think that?

I think your first equation came from flat space, because it is not true in curved space.

WannabeNewton
$\triangledown _{\mu }T^{\mu \nu } = 0$ can be gotten from $\triangledown_{\mu }G^{\mu \nu } = 0$ which is a consequence of the second bianchi identity. You also know that $T^{\mu \nu }, _{\mu } = 0$ but what you can do is say that locally this is the same thing as $T^{\mu \nu }; _{\mu } = 0$ and if this is true for some coordinate system it will be true for all coordinate systems.

format: plain


text:
DeepAI

Stochastic Linear Bandits with Hidden Low Rank Structure

High-dimensional representations often have a lower dimensional underlying structure. This is particularly the case in many decision making settings. For example, when the representation of actions is generated from a deep neural network, it is reasonable to expect a low-rank structure whereas conventional structures like sparsity are not valid anymore. Subspace recovery methods, such as Principle Component Analysis (PCA) can find the underlying low-rank structures in the feature space and reduce the complexity of the learning tasks. In this work, we propose Projected Stochastic Linear Bandit (PSLB), an algorithm for high dimensional stochastic linear bandits (SLB) when the representation of actions has an underlying low-dimensional subspace structure. PSLB deploys PCA based projection to iteratively find the low rank structure in SLBs. We show that deploying projection methods assures dimensionality reduction and results in a tighter regret upper bound that is in terms of the dimensionality of the subspace and its properties, rather than the dimensionality of the ambient space. We modify the image classification task into the SLB setting and empirically show that, when a pre-trained DNN provides the high dimensional feature representations, deploying PSLB results in significant reduction of regret and faster convergence to an accurate model compared to state-of-art algorithm.

• 15 publications
• 52 publications
• 169 publications
• 43 publications
07/17/2017

Non-Linear Subspace Clustering with Learned Low-Rank Kernels

In this paper, we present a kernel subspace clustering method that can h...
01/08/2019

Bilinear Bandits with Low-rank Structure

We introduce the bilinear bandit problem with low-rank structure where a...
06/18/2020

Precise expressions for random projections: Low-rank approximation and randomized Newton

It is often desirable to reduce the dimensionality of a large dataset by...
05/06/2020

Low-Rank Nonlinear Decoding of μ-ECoG from the Primary Auditory Cortex

This paper considers the problem of neural decoding from parallel neural...
03/06/2021

Low-Rank Isomap Algorithm

The Isomap is a well-known nonlinear dimensionality reduction method tha...
09/05/2017

Linear Optimal Low Rank Projection for High-Dimensional Multi-Class Data

Classification of individual samples into one or more categories is crit...
05/14/2019

Transition Subspace Learning based Least Squares Regression for Image Classification

Only learning one projection matrix from original samples to the corresp...

1 Introduction

Stochastic linear bandit (SLB) is a class of sequential decision-making under uncertainty where an agent sequentially chooses actions from very large action sets. At each round, the agent applies its action, and as a response, the environment emits a stochastic reward whose expected value is an unknown linear function of the action. The agent’s goal is to collect as much reward as possible over the course of interactions.

In SLB, the actions are represented as

-dimensional vectors, and the agent maintains limited information about the unknown linear function of reward. Through the course of interaction, the agent implicitly or explicitly constructs the model of the environment. It dedicates the decisions to not only maximize the current reward but also explore other actions to build a better estimation of the unknown linear function and guarantee higher future rewards. This is known as the

exploration vs. exploitation trade-off.

The lack of oracle knowledge of the true environment model causes the agent to make mistakes by picking sub-optimal actions during the exploration. While the agent examines actions in the decision set, its committed mistakes accumulate. The aim of the agent is to design a strategy to minimize the cumulative cost of these mistakes, known as regret. One promising approach to minimize the regret is through utilizing the optimism in the face of uncertainty (OFU) principle first proposed by Lai & Robbins (1985). OFU

based algorithms estimate the environment model up to its confidence interval and construct a plausible set of models within that interval. Among those models in the plausible set, they choose the most optimistic one and follow the optimal behavior suggested by the selected model for the next round of decision making.

For general SLB problems, Abbasi-Yadkori et al. (2011) deploy the OFU principle, propose OFUL algorithm, and for -dimensional SLB, derive a regret upper bound of which matches the lower bound up to a log factor. These regret bounds in high dimensional problems especially when and are about the same order are not practically tolerable. Fortunately, real-world problems usually are not arbitrary and may contain hidden low-dimensional structures. For example in classical recommendation systems, each item is represented by a large and highly detailed hand-engineered feature vector; therefore is intractably large. In these problems, not all the features are helpful for the recommendation task. For instance, the height of goods such as a pen is not a relevant feature for its recommendation while this feature is valuable for furnitures. Therefore the true underlying linear function in SLBs is highly sparse. Abbasi-Yadkori et al. (2012) show how to exploit this additional structure and design a practical algorithm with regret of where is the sparsity level of the true underlying linear function. Under slightly stronger assumptions, Carpentier & Munos (2012) show the theory of compressed sensing can provide a tighter bound of .

The contemporary success of Deep Neural Networks (DNN) in representation learning enables classical machine learning methods to provide significant advancements in many machine learning problems, e.g., classification and regression tasks

(LeCun et al., 1998). DNNs convolve the raw features of the input and construct new feature representations which replace the hand-engineered feature vectors in many real-world sequential decision making applications, e.g., recommendation systems. However, when a DNN provides the feature representations, one cannot see a sparse structure.

Dimension reduction and subspace recovery form the core of unsupervised learning methods and principal component analysis (PCA) is the main technique for linear dimension reduction

(Pearson, 1901; Eckart & Young, 1936). At each round of SLB, the agent chooses an action and receives the reward corresponding to that action. Therefore, the chosen action is assigned a supervised reward signal while other actions in the decision set remain unsupervised. Even though the primary motivation in the SLB framework is decision-making within a large and stochastic decision set, the majority of prior works do not exploit possible hidden structures in these sets. For example, Abbasi-Yadkori et al. (2011) only utilizes supervised actions, the actions selected by the algorithm, to construct the environment model. It ignores all other unsupervised actions in the decision set. On the contrary, large number of actions in the decision sets can be useful in reducing the dimension of the problem and simplifying the learning problem.

Contributions:  In this paper, we deploy unsupervised subspace recovery using PCA to exploit the massive number of unsupervised actions which are observed in the decision sets of SLB and reduce the dimensionality and the complexity of SLBs. We propose PSLB for SLBs and show that if there exists an -dimensional subspace structure such that the actions live in a perturbed region around this subspace, deploying PSLB improves the regret upper bound to . Here represents the difficulty of subspace recovery as a function of the structure of the problem. If learning the subspace is hard, e.g., the eigengap is small to analyze in a reasonable amount of samples, actions are widely distributed in the orthogonal dimensions of the subspace due to perturbation or , then using projection approaches are not remedial. On the other hand, if underlying subspace is identifiable, i.e., large number of actions are available from the decision sets in each round, the eigengap is significant or , then using subspace recovery provides faster learning of the underlying linear function; thus, smaller regret.

We adapt the image classification tasks on MNIST (LeCun et al., 1998), CIFAR-10 (Krizhevsky & Hinton, 2009)

and ImageNet

(Krizhevsky et al., 2012) datasets to the SLB framework and apply both PSLB and OFUL on these datasets. We observe that there exists a low dimensional subspace in the feature space when a pre-trained DNN produces the -dimensional feature vectors. We empirically show that using subspace recovery PSLB learns the underlying model significantly faster than OFUL and provides orders of magnitude smaller regret in SLBs obtained from MNIST, CIFAR-10, and ImageNet datasets.

2 Preliminaries

For any positive integer , denotes the set . The Euclidean norm of a vector is denoted by . The spectral norm of matrix is denoted by , ie., . denotes the Moore-Penrose inverse of matrix . For any symmetric and positive semi-definite matrix , let denote the norm of a vector defined as . The

-th eigenvalue of a symmetric matrix

is denoted by , where . The largest and smallest eigenvalue of are denoted as and , respectively. denotes identity matrix. If is a column vector then is a matrix whose columns are whereas if is a scalar then is a column vector whose elements are . defines the multiset summation operation over the sets .

Model:

Let be the total number of rounds. At each round , the agent is given a decision set with actions, . Let be an orthonormal matrix with , where defines a -dimensional subspace in . Consider a zero meantrue action vector, , such that for all and . Let be zero mean random vectors which are uncorrelated with true action vectors, i.e., for all and . Each action is generated as follows,

 ^xt,i=xt,i+ψt,i. (1)

This model states that each in is a perturbed version of the true underlying . Denote the covariance matrix of by . Notice that is rank-. Perturbation vectors, , are assumed to be isotropic, thus covariance matrix . Let and . We will make a boundedness assumption on and .

Assumption 1 (Bounded Action and Perturbation Vectors).

There exists finite constants, and , such that for all and ,

 ∥xt,i∥22≤dxλ+,∥ψt,i∥22≤dψσ2.

Both and can be dependent on or and they can be interpreted as the effective dimensions of the corresponding vectors.

At each round , the agent chooses an action, and observes a reward such that

 rt=(P^Xt)Tθ∗+ηt∀t∈[T] (2)

where is the projection matrix for the -dimensional subspace , is the unknown parameter vector and is the random noise at round . Notice that since , therefore, .111The reward generative model of is equivalent to where contains the randomness in as well as the perturbations due to . Consider as any filtration of -algebras such that for any , is measurable and is measurable.

Assumption 2 (Subgaussian Noise).

For all , is conditionally R-sub-Gaussian where is a fixed constant, ie. .

This implies that or equivalently . The goal of the agent is to maximize the total expected reward accumulated in rounds, . The oracle’s strategy with the knowledge of at each round is . We evaluate the agent’s performance against the oracle performance. Define regret as the difference between expected reward of the oracle and the agent,

 RT\coloneqqT∑t=1^X∗Ttθ∗−T∑t=1^XTtθ∗=T∑t=1(X∗t−^Xt)Tθ∗. (3)

The agent aims to minimize this quantity over time. In the setting described above, the agent is assumed to know that there exists a -dimensional subspace of in which true action vectors and the unknown parameter vector lie. Finally, we define some quantities about the structure of the problem for all :

 gx=λ+λ−,gψ=σ2λ−,Γ=2gψ+4√gxgψ (4) α\medop=max(dx,dψ),nδ\medop=4α(Γ√log2dδ\medop+√2gxlogmδ)2

3 Overview of Pslb

We propose PSLB, a SLB algorithm which employs subspace recovery to extract information from the unsupervised data accumulated in the SLB. During the course of interaction, the agent constructs the confidence set of the underlying model with and without subspace recovery, then takes the intersection of these two sets. Among the plausible models in this set, the agent deploys OFU principle and follows the optimal action of the most optimistic model. The pseudocode of PSLB is given in Algorithm  1. PSLB consists of 4 key elements: warm-up, subspace estimation, creating confidence sets and acting optimistically. In the following, we will discuss each of them briefly.

3.1 Warm-Up

The decision set at each round , , has a finite number of actions. The algorithm needs to acquire enough samples of action vectors to reliably estimate the hidden subspace. The process of acquiring sufficient samples is considered as the warm-up period. The duration of the warm-up period, , can be chosen in many ways. We set based on the theoretical analysis outlined in Section 4.1. The crux of this choice is to provide a theoretical guarantee of convergence to the underlying subspace. In other words, PSLB collects samples until it has some confidence on the recovered subspace. This idea is considered in more detail in Section 3.2. Note that warm-up periods are implicitly assumed in most SLB algorithms since the given bounds are not meaningful for short periods of time.

3.2 Subspace Estimation

At each round, the algorithm predicts the -dimensional subspace that the true action vectors belong, using the action vectors collected up to that round. In particular, at round , the algorithm uses PCA over action vectors observed so far, . It calculates which is the matrix of top eigenvectors of , thus is the predicted -dimensional subspace. Then, is used to create the estimated projection matrix associated to this subspace, .

As the agent observes more action vectors, the estimated projection matrix becomes more accurate. The accuracy of is measured by the projection error . As more action vectors are collected, shrinks. Since is not known, cannot be calculated directly. Thus, PSLB calculates a high-probability upper bound on the projection error. Using the derived bound, PSLB deploys confidence in the subspace estimation and construct the set of plausible projection matrices where and both lie in with high probability. The construction of is reliant on the structural properties of the problem and the number of samples . We analyze these properties in Section 4.1.

3.3 Confidence Set Construction

At each round, PSLB creates two confidence sets for the model parameter . First, it tries to exploit a possible -dimensional hidden subspace structure. Thus, it searches for a high probability confidence set, , that lies around the estimated subspace at round . Using the history of action-reward pairs, the algorithm solves a regularized least squares problem in the estimated subspace and obtains , the estimated parameter vector in . Then it creates the confidence set around , such that with high probability.

Second, PSLB searches for a high probability confidence set in the ambient space without having subspace recovery. It deploys the confidence set generation subroutine of OFUL by Abbasi-Yadkori et al. (2011). Using the history of action-reward pairs, the algorithm solves another regularized least squares problem but this time in the ambient space and obtains . PSLB then creates the confidence set centered around such that with high probability. Finally, PSLB takes the intersection of constructed confidence sets to create the main confidence set, . still contains with high probability. With this operation, PSLB provides a new perspective that if there exists an easily recoverable -dimensional subspace, it exploits that structure to get lower regret than OFUL can solely achieve. If it fails to detect such structure or the confidence set is looser than what OFUL provides, then it still provides the same regret as OFUL.

3.4 Optimistic Action

For the final step in round , the algorithm chooses an optimistic triplet from the confidence sets created and the current decision set which jointly maximizes the reward:

 (~Pt,^Xt,~θt)=argmax(P′,x,θ)∈Cp,t×Dt×Ct(P′x)Tθ (5)

4 Theoretical Analysis of Pslb

In this section we first state the upper regret bound of PSLB which is the main result of the paper. Then we analyze the components that build up to the result. In order to get a meaningful bound, we assume that the expected rewards are bounded. Recalling the quantities defined in (4), define such that

 Υ=O(αΓ2√mK(λ−+σ2)). (6)

It represents the difficulty of subspace recovery in terms structural properties of SLB setting, and it is analyzed in Section 4.3. Using , the theorem below states the regret upper bound of PSLB.

Theorem 1 (Regret Upper Bound of Pslb).

Fix any . Assume that Assumptions 1 and 2 hold. Also assume that for all , . Then, with probability at least , the regret of PSLB satisfies

 Rt≤min{˜O(Υ√t),˜O(d√t)}. (7)

The proof of the theorem involves two main pieces: the projection error analysis and the construction of projected confidence sets. They are analyzed in Sections 4.1 and 4.2 respectively. Finally, in Section 4.3 their role in the proof of Theorem 1 is explained and the meaning of the result is discussed.

4.1 Projection Error Analysis

Consider the matrix where

th singular value is denoted by

, such that . Extending the definition of inner products of two vectors to subspaces and using Courant-Fischer-Weyl minimax principle, one can define th principal angle between and via

 cosΘi(span(V),span(^Vt))=σi(^VTtV).

Using the analysis in Akhiezer & Glazman (2013) it can be seen that:

 ∥^Pt−P∥2 =√λmax(Im−(^VTtV)T(^VTtV)) =√1−σ2m(^VTtV)=sinΘm (8)

where is the largest principal angle between the column spans of and . Thus, bounding the projection error between two projection matrices is equivalent to bounding the sine of the largest principal angle between the subspaces that they project. In light of this relation, one can use the Davis-Kahan theorem (Davis & Kahan, 1970) to bound the projection error. The exact theorem statement can be found in Section A in the Supplementary Material. Informally, the theorem considers a symmetric matrix and its’ perturbed version and bounds the sine of the largest principal angle caused by this perturbation. Using Davis-Kahan theorem, following lemma bounds the finite sample projection error.

Lemma 2 (Finite Sample Projection Error).

Fix any . Let . Suppose Assumption 1 holds. Then with probability at least , ,

 ∥^Pt−P∥2≤ϕδ√t, where ϕδ=2Γ√αKlog2dδ. (9)

The lemma and it’s proof are along the same lines of Corollary 2.9 of Vaswani & Narayanamurthy (2017). However, we improve the bound on the projection error by using the Matrix Chernoff Inequality (Tropp, 2015) and provide the precise problem dependent quantities in the bound which are required for defining the minimum number of samples for the warm-up period and the construction of confidence sets for . Note that as discussed in Section 3.2, (9) defines the confidence set for all . The general version of the lemma and the details of the proof are given in Section A of the Supplementary Material, but here we provide a proof sketch.

Up to round , the agent observes action vectors in total within the decision sets. Using PCA, PSLB estimates an -dimensional subspace spanned by top eigenvectors of the sample covariance matrix of action vectors and obtain the projection matrix for that subspace. In order to derive Lemma 2, we first carefully pick two symmetric matrices such that the span of their first eigenvectors are equivalent to subspaces that and project to. Using Davis-Kahan theorem with matrix concentration inequalities provided by Tropp (2015), we derive the finite sample projection error bound.

Lemma 2 is key to defining the warm-up period duration. Due to equivalence in (8), , . Therefore, any projection error bound greater than 1 is vacuous. We pick such that with high probability, we obtain theoretically non-trivial bound on projection error. With the given choice of , the bound on the projection error in (9) becomes less than 1 when . After , PSLB starts to produce non-trivial confidence sets around . However, note that can be significantly big for problems that have structure that is hard to recover, e.g. having linear in .

Lemma 2 also brings several important intuitions about the subspace estimation problem in terms of the problem structure. Recalling the definition of in (4), as decreases, the projection error shrinks since the underlying subspace becomes more distinguishable. Conversely, as diverges from 1, it becomes harder to recover the underlying -dimensional subspace. Additionally, since is the maximum of the effective dimensions of the true action vector and the perturbation vector, having large makes the subspace recovery harder and the projection error bound looser, whereas observing more action vectors, in each round produces tighter bound on . The effects of these structural properties on the subspace estimation translate to confidence set construction and ultimately to regret upper bound.

4.2 Projected Confidence Sets

In this section, we analyze the construction of and . For any round , define . At round , let for . The rewards obtained up to round is denoted as . At round , after estimating the projection matrix associated with the underlying subspace, PSLB tries to find , an estimate of , while believing that lives within the estimated subspace. Therefore, is the solution to the following Tikhonov-regularized least squares problem with regularization parameters and ,

 θt=argminθ∥(^Pt^Xt−1)Tθ−rt−1∥22+λ∥^Ptθ∥22.

Notice that regularization is applied along the estimated subspace. Solving for gives . Define such that for all and , and let . The following theorem gives the construction of projected confidence set, , which is an ellipsoid centered around which contains with high probability.

Theorem 3 (Projected Confidence Set Construction).

Fix any . Suppose Assumptions 1 & 2 hold, and and , . If then, with probability at least , , lies in the set

 Cm,t ={θ∈Rd:∥θt−θ∥At≤βt,δ}, where βt,δ =R√2log(1δ)+mlog(1+tL2mλ) +LSϕδ√γmlog(1+tL2mλ)+S√λ. (10)

The detailed proof and a general version of the theorem are given in Section B of the Supplementary Material. We will highlight the key aspects in here. The overall proof follows a similar machinery used by Abbasi-Yadkori et al. (2011). Specifically, the first term of in (10) is derived similarly by using the self-normalized tail inequality. However, since at each round PSLB projects the past actions to an estimated -dimensional subspace to estimate , is replaced by in the bound. While enjoying the benefit of projection, this construction of the confidence set suffers from the finite sample projection error, i.e., uncertainty in the subspace estimation. This effect is observed via second term in (10). The second term involves the confidence bound for the estimated projection matrix, . This is critical in determining the tightness of the confidence set on . As discussed in Section 4.1, reflects the difficulty of subspace recovery of the given problem and it depends on the underlying structure of the problem and SLB. This shows that as estimating the underlying subspace gets more difficult, having a projection based approach in the construction of the confidence sets on provides looser bounds.

In order to tolerate the possible difficulty of subspace recovery, PSLB also constructs , which is the confidence set for without having subspace recovery. The construction of follows OFUL by Abbasi-Yadkori et al. (2011). Let . The algorithm tries to find which is the -regularized least squares estimate of in the ambient space. Thus, . Construction of is done under the same assumptions of Theorem 3, such that with probability at least , lies in the set

 Cd,t ={θ∈Rd:∥^θt−θ∥Zt≤Ωt,δ}where Ωt,δ =R√2log(1δ)+dlog(1+tL2mλ)+S√λ.

The search for an optimistic parameter vector happens in the intersection of and . Notice that with probability at least . Optimistically choosing the triplet, , within the described confidence sets gives PSLB a way to tolerate the possibility of failure in recovering an underlying structure. If confidence set is loose or PSLB is not able to recover an underlying structure, then provides the useful confidence set to obtain desirable learning behavior.

4.3 Regret Analysis

Now that the confidence set constructions and the decision making procedures of PSLB are explained, it only remains to analyze the regret of PSLB. Using the intersection of and as the confidence set at round , gives PSLB the ability to obtain the lowest possible instantaneous regret among both confidence sets. Therefore, the regret of PSLB is upper bounded by the minimum of the regret upper bounds on the individual strategies. Using only is equivalent to following OFUL and the regret analysis can be found in Abbasi-Yadkori et al. (2011). The regret analysis of using only the projected confidence set is the main contribution of this work. It follows the standard regret decomposition into instantaneous regret components. However, due to having different estimated projection matrices in each round, the derivation of the bound uses a different strategy involving the Matrix Chernoff Inequality (Tropp, 2015). The detailed analysis of the regret upper bound and the proof can be found in Section C of the Supplementary Material. Here we elaborate more on the nature of the regret obtained by using projected confidence sets only, i.e. first term in Theorem 1, and discuss the effect of in particular.

is the reflection of the finite sample projection error at the beginning of the algorithm. It captures the difficulty of subspace recovery based on the structural properties of the problem and determines the regret of deploying projection based methods in SLBs. Recall that is the maximum of the effective dimensions of the true action vector and the perturbation vector. Depending on the structure of the problem, can be , e.g., the perturbation can be effective in many dimensions, which prevents the projection error from shrinking; thus, causes resulting in regret. The eigengap within the true action vectors and the eigengap between the true action vectors and the perturbation vectors are critical factors that determine the identifiability of the hidden subspace. As increases, the subspace recovery becomes harder since the effect of perturbation increases. Conversely, as increases, the underlying subspace becomes easier to identify. These effects are significant on the regret of PSLB and they are captured by in . Moreover, having finite samples to estimate the subspace affects the regret bound through . Due to the nature of SLB, this is unavoidable and it scales the final regret by . Overall, with all these elements, represents the hardness of using PCA based methods in dimensionality reduction in SLBs.

Theorem 1 states that if the underlying structure is easily recoverable, e.g. , then using PCA based dimension reduction and construction of confidence sets provide substantially better regret upper bound for large . If that is not the case, then due to the best of the both worlds approach provided by PSLB, the agent obtains the best possible regret upper bound. Note that the bound for using only is a worst case bound and as we present in Section 5, in practice PSLB can give significantly better results.

5 Experiments

In the experiments, we study MNIST, CIFAR-10 and ImageNet datasets and use them to create the decision sets for the SLB setting. A simple 5-layer CNN, a pre-trained ResNet-18 and a pre-trained ResNet-50 are deployed respectively for MNIST, CIFAR-10 and ImageNet. Before training, we modify the architecture of the representation layer (the layer before the final layer) to make it suitable for the SLB study and obtain decision sets for each image.

Consider a standard network whose dimension of the representation layer is . Therefore, the final layer for class classification is fully connected and it is a matrix that outputs numbers to be used for classification. In this study, instead of having a final layer of matrix, we construct the final layer as a -dimensional vector and make the feature representation layer a dimensional vector. We treat this vector as the concatenation of -dimensional contexts i.e., . The final -dimensional layer is of the SLB

, where the logit for each class is computed as an inner product of the class context

and . We train these architectures for different values using cross entropy loss. Here we provide results for MNIST and CIFAR-10 with and ImageNet with .

Removing the final layer, the resulting trained networks are used to generate the feature representations of each image for each class which produces the decision sets at each time step of SLB. Since MNIST and CIFAR-10 have 10 classes, in each decision set we obtain 10 action vectors where each of them are segments in the representation layer. On the other hand, from the ImageNet dataset we get 1000 actions per decision set due to 1000 classes in the datasets. In the SLB setting, the agent receives a reward of 1 if it chooses the right action, which is the segment in the representation layer corresponding to correct label according to trained network, and 0 otherwise. We apply both PSLB and OFUL on these SLBs. We measure the regret by counting the number of mistakes each algorithm makes. To come up with the optimistic choice of action at each time step, both of these algorithms requires solving an inner optimization problem. To mitigate the burden of these computation costs, we sample many models from the confidence sets and choose the most optimistic model among the sampled ones.

Through computing PCA of the empirical covariance matrix of the action vectors, surprisingly we found that projecting action vectors onto the -dimensional subspace defined by the dominant eigenvector is sufficient for these datasets in the SLB setting; thus, . During the experiments PSLB tried to recover a -dimensional subspace using the action vectors collected. We present the regrets obtained by PSLB and OFUL for MNIST, CIFAR-10 and ImageNet in Figure (a)a(b)b(c)c respectively. With the help of subspace recovery and projection, PSLB provides a massive reduction in the dimensionality of the SLB problem and immediately estimates a fairly accurate model for . On the other hand, OFUL naively tries to sample from all dimensions in order to learn . This difference yields orders of magnitude improvement in regret. During the SLB experiment, we also sample the optimistic models that are chosen by PSLB and OFUL. We use these models to test the model accuracy of the algorithms, i.e. perform classification over all images in dataset. The optimistic model accuracy comparisons are depicted in Figure (d)d(e)e(f)f. These portray the learning behavior of PSLB and OFUL. Using projection, PSLB learns the underlying linear model in the first few rounds, whereas OFUL suffers from high-dimension of SLB framework and lack of knowledge besides chosen action-reward pairs. We extend these experiments for settings with and which can be found in Section D.

6 Related Work

The primary class of partial information problems is the multi-arm bandit (MAB). Robbins (1985) introduces the standard stochastic MAB and Lai & Robbins (1985) studies the asymptotic property of learning algorithms on this class. Stochastic MABs are a special case of SLB when the arms representations are orthogonal to each other. For finite sample regime, Auer et al. (2002) deploys the principle of OFU and provide finite sample guarantee for MABs. Auer (2002) deploys the same principle to provide regret guarantee for MABs with the linear pay-off. This principle is realized as the primary approach even for more general problems such as Linear Quadratic systems (Abbasi-Yadkori & Szepesvári, 2011)

(Jaksch et al., 2010).

The study of linear bandit problems extends to various algorithms and environment settings (Dani et al., 2008; Rusmevichientong & Tsitsiklis, 2010; Li et al., 2010). Kleinberg et al. (2010) studies the class of problems when the decision set changes time to time, while Dani et al. (2008) studies this problem when the decision set provides a set of fixed actions. Further analysis in the area extend these approaches to classes where there are more structures in the problem setup. In traditional decision-making problems, where hand engineered feature representations are provided, sparsity in the linear function is a valid structure. Sparsity, as the key in high-dimensional conventional structured linear bandits, conveys series of successes in classical settings (Abbasi-Yadkori et al., 2012; Carpentier & Munos, 2012). In recommendations systems, where a set of users and items are given, Gopalan et al. (2016) consider the low-rank structure of the user-item preference matrix and provide an algorithm which exploits this further structure.

To the best of our knowledge, there are no hidden low-dimensional subspace assumptions on actions and/or unknown weight vector in literature for SLB. On the other hand, subspace recovery and dimension reduction problems are well studied in the literature. Several linear and nonlinear dimension reduction methods have been proposed such as PCA (Pearson, 1901)

(Hyvärinen & Oja, 2000), random projections (Candes & Tao, 2006) and non-convex robust PCA (Netrapalli et al., 2014). Among the linear dimension reduction techniques, PCA is the simplest, yet most widely used method. Analysis of PCA based methods mostly focus on the asymptotic results  (Anderson et al., 1963; Jain et al., 2016). However, in the settings like SLB with finite number of arms, it is necessary to have finite sample guarantees for the application of PCA. In the literature, among few finite sample PCA works, Nadler (2008) provides finite sample guarantees for one-dimensional PCA, whereas Vaswani & Narayanamurthy (2017) extends it to larger dimensions with various noise models.

7 Conclusion

In this paper, we study a linear subspace structure in the action set of an SLB problem. We deploy PCA based projection to exploit the immense number of unsupervised actions in the decision sets and learn the underlying subspace. We proposed PSLB, a SLB algorithm which utilizes the subspace estimated through PCA to improve the regret upper bound of SLB problems. If such structure does not exist or is hard to recover, then the PSLB reduces to the standard SLB algorithm, OFUL. We empirically study MNIST, CIFAR-10 and ImageNet datasets to create SLB framework from image classification tasks. We test the performance of PSLB versus OFUL in the SLB setting created. We show that when DNNs produce features of the actions, a significantly low dimensional structure is observed. Due to this structure, we showed that PSLB substantially outperforms OFUL and converges to an accurate model while OFUL still struggles to sample in high dimensions to learn the underlying parameter vector.

In this work, we studied the class of linear subspace structures. In the future work, we plan to extend this line of study to the general class of low dimensional manifold structured problems. Bora et al. (2017) peruse a similar approach for compression problems. While optimism is the primary approach in the theoretical analyses of SLB

s, it mainly poses a computationally intractable internal optimization problem. An alternative method is Thompson sampling, a practical algorithm for

SLBs. In future work, we plan to deploy Thompson sampling and mitigate the computational complexity of PSLB.

References

• Abbasi-Yadkori & Szepesvári (2011) Abbasi-Yadkori, Y. and Szepesvári, C. Regret bounds for the adaptive control of linear quadratic systems. In Proceedings of the 24th Annual Conference on Learning Theory, pp. 1–26, 2011.
• Abbasi-Yadkori et al. (2011) Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pp. 2312–2320, 2011.
• Abbasi-Yadkori et al. (2012) Abbasi-Yadkori, Y., Pal, D., and Szepesvari, C. Online-to-confidence-set conversions and application to sparse stochastic bandits. In Artificial Intelligence and Statistics, pp. 1–9, 2012.
• Akhiezer & Glazman (2013) Akhiezer, N. I. and Glazman, I. M. Theory of linear operators in Hilbert space. Courier Corporation, 2013.
• Anderson et al. (1963) Anderson, T. W. et al. Asymptotic theory for principal component analysis. Annals of Mathematical Statistics, 34(1):122–148, 1963.
• Auer (2002) Auer, P. Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research, 3(Nov):397–422, 2002.
• Auer et al. (2002) Auer, P., Cesa-Bianchi, N., and Fischer, P. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235–256, 2002.
• Bora et al. (2017) Bora, A., Jalal, A., Price, E., and Dimakis, A. G. Compressed sensing using generative models. arXiv preprint arXiv:1703.03208, 2017.
• Candes & Tao (2006) Candes, E. J. and Tao, T. Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE transactions on information theory, 52(12):5406–5425, 2006.
• Carpentier & Munos (2012) Carpentier, A. and Munos, R. Bandit theory meets compressed sensing for high dimensional stochastic linear bandit. In Artificial Intelligence and Statistics, pp. 190–198, 2012.
• Dani et al. (2008) Dani, V., Hayes, T. P., and Kakade, S. M. Stochastic linear optimization under bandit feedback. 2008.
• Davis & Kahan (1970) Davis, C. and Kahan, W. M. The rotation of eigenvectors by a perturbation. iii. SIAM Journal on Numerical Analysis, 7(1):1–46, 1970.
• Eckart & Young (1936) Eckart, C. and Young, G. The approximation of one matrix by another of lower rank. Psychometrika, 1(3):211–218, 1936.
• Freedman (1975) Freedman, D. A. On tail probabilities for martingales. the Annals of Probability, pp. 100–118, 1975.
• Gopalan et al. (2016) Gopalan, A., Maillard, O.-A., and Zaki, M. Low-rank bandits with latent mixtures. arXiv preprint arXiv:1609.01508, 2016.
• Hyvärinen & Oja (2000) Hyvärinen, A. and Oja, E. Independent component analysis: algorithms and applications. Neural networks, 13(4-5):411–430, 2000.
• Jain et al. (2016) Jain, P., Jin, C., Kakade, S. M., Netrapalli, P., and Sidford, A. Streaming pca: Matching matrix bernstein and near-optimal finite sample guarantees for oja’s algorithm. In Conference on Learning Theory, pp. 1147–1164, 2016.
• Jaksch et al. (2010) Jaksch, T., Ortner, R., and Auer, P.

Near-optimal regret bounds for reinforcement learning.

Journal of Machine Learning Research, 11(Apr):1563–1600, 2010.
• Kleinberg et al. (2010) Kleinberg, R., Niculescu-Mizil, A., and Sharma, Y. Regret bounds for sleeping experts and bandits. Machine learning, 80(2-3):245–272, 2010.
• Krizhevsky & Hinton (2009) Krizhevsky, A. and Hinton, G. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
• Krizhevsky et al. (2012) Krizhevsky, A., Sutskever, I., and Hinton, G. E.

Imagenet classification with deep convolutional neural networks.

In Advances in neural information processing systems, pp. 1097–1105, 2012.
• Lai & Robbins (1985) Lai, T. L. and Robbins, H. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4–22, 1985.
• LeCun et al. (1998) LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998.
• Li et al. (2010) Li, L., Chu, W., Langford, J., and Schapire, R. E. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661–670. ACM, 2010.
• Nadler (2008) Nadler, B. Finite sample approximation results for principal component analysis: A matrix perturbation approach. The Annals of Statistics, 36(6):2791–2817, 2008.
• Netrapalli et al. (2014) Netrapalli, P., Niranjan, U., Sanghavi, S., Anandkumar, A., and Jain, P. Non-convex robust pca. In Advances in Neural Information Processing Systems, pp. 1107–1115, 2014.
• Pearson (1901) Pearson, K. On lines and planes of closest fit to systems of points in space. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 2(11):559–572, 1901.
• Robbins (1985) Robbins, H. Some aspects of the sequential design of experiments. In Herbert Robbins Selected Papers, pp. 169–177. Springer, 1985.
• Rusmevichientong & Tsitsiklis (2010) Rusmevichientong, P. and Tsitsiklis, J. N. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395–411, 2010.
• Tropp (2015) Tropp, J. A. An introduction to matrix concentration inequalities. Foundations and Trends® in Machine Learning, 8(1-2):1–230, 2015.
• Vaswani & Narayanamurthy (2017) Vaswani, N. and Narayanamurthy, P. Finite sample guarantees for pca in non-isotropic and data-dependent noise. In Communication, Control, and Computing (Allerton), 2017 55th Annual Allerton Conference on, pp. 783–789. IEEE, 2017.

Appendix A Projection Error Analysis, Proof of Lemma 2

In this section, we provide the general version of Lemma 2 with the proof details. As stated in the main text, in order to bound the projection error, we will use Davis-Kahan theorem which states the following:

Theorem 4 ((Davis & Kahan, 1970)).

Let be symmetric matrices, such that . The eigenvalues of and are and respectively. Define the eigendecompositions of and :

 S=[UUo][Λ00Λo][UUo]T
 ^S=[^U^Uo][^Λ00^Λo][^U^Uo]T

where and are diagonal matrices with first eigenvalues of and respectively. and denote the corresponding eigenvectors. Define

 δ\coloneqqinf{|^λ−λ|:λ∈[λm,λ1],^λ∈(−∞,^λm+1]}.

If , then , sine of the largest principal angle between the column spans of and , can be upper bounded as

 sinΘm≤∥^SU−UΛ∥2δ=∥^SU−UΛ∥2|λm−^λm+1|. (11)

Notice that in order to use Davis-Kahan theorem in our setting, we need to pick 2 symmetric matrices and such that their first eigenvectors has the same span with the subspaces that and project to. Followed by these choices, in order to get a non-trivial bound we require a significant eigengap between and , due to denominator in (11). We use the following matrix concentration inequalities to maintain an eigengap with high probability.

Theorem 5 (Matrix Chernoff Inequality; (Tropp, 2015)).

Consider a finite sequence of independent, random, symmetric matrices in . Assume that and

for each index k. Introduce the random matrix

. Let denote the minimum eigenvalue of the expectation ,

 μmin=λmin(E[Y])=λmin(∑kE[Xk]).

Then,

 Pr[λmin(Y)≤ϵμmin]≤dexp(−(1−ϵ)2μmin2L)for ϵ∈[0,1).
Theorem 6 (Corollary of Matrix Bernstein; (Tropp, 2015)).

Consider a set of i.i.d. realization of a random matrix , as . If is bounded,

almost surely, with second moment of

 m2(R)=max{∥E[RRT]∥2,∥E[RTR]∥2}.

Then, for all ,

 Pr[∥1nn∑i=1Ri−E[R]∥2≥t]≤(d1+d2)exp(−nt2/2m2(R)+2Lt/3)

Define . Now that we have the required machinery, we present general version of Lemma 2.

Lemma 7.

Fix any . Suppose that Assumption 1 holds. Then with probability at least ,

 ∥^Pt−P∥2≤Φt,δ,∀t≥tw,δ,

where

 Φt,δ=Γ√αtKlog2dδ1−√2dxgxtKlogmδ−Γ√αtKlog2dδ. (12)
Proof.

We set and where . Let U be the top eigenvectors of S. Notice that and is the matrix of top eigenvectors of . Therefore, one can apply Theorem 4 with given choices of and , to bound . Since ,

 ∥^Pt−P∥2≤∥(^S−S)V∥2λm(S)−λm+1(^S)(1)≤∥(^S−S)V∥2λm(S)−∥^S−S∥2(2)≤∥E[^S−S]V∥2+∥^S−S−E[^S−S]∥2λm(S)−∥E[^S−S]∥2−∥^S−S−E[^S−S]∥2

where (1) follows from Weyl’s inequality and the fact that is rank , , and (2) is due to triangle inequality. With the given choices of and and Assumption 1, we have the following:

 λm(S)≥λm(1nn∑i=1xixTi)+λmin(VTΣψV)=λm(1nn∑i=1xixTi)+λmin(σ2Im)=λm(1nn∑i=1xixTi)+σ2 ^S−S=1nn∑i=1ψiψTi+1nn∑i=1xiψTi+1nn∑i=1ψixTi−VVTΣψVVT ∥E[^S−S]∥2=∥σ2Id−σ2P∥2=σ2E[^S−S]V=ΣψV−VVTΣψV=V⊥VT⊥ΣψV=0 ^S−S−E[^S−S]=1nn∑i=1ψiψTi−Σψ+1nn∑i=1xiψTi+1nn∑i=1ψixTi.

Inserting these expressions we get,

 ∥^Pt−P∥2≤∥1n∑ni=1ψiψTi−Σψ+1n∑ni=1xiψTi+1n∑ni=1ψixTi∥2λm(1n∑ni=1xixTi)−∥1n∑ni=1ψiψTi−Σψ+1n∑ni=1xiψTi+1n∑ni=1ψixTi∥2 (13)

We first bound . From Assumption 1, for all and from the model properties, . Using Theorem 5, one can get that

 (14)

Now we consider . From triangle inequality we have,

We will consider each term on the right hand side separately. If Assumption 1 holds, then we have:

 E[ψiψTi] =Σψ ∥ψiψTi∥2 ≤d


text:
# the triangle mania

Level pending

there is an isosceles triangle. the length of the equal sides is 13 cm. Find its base

×

Problem Loading...

Note Loading...

Set Loading...


text:
jernplate8

2020-11-06

Use transformations to sketch the graph of the function.

Nathaniel Kramer

Step 1

Remember that: When we reflect the graph of $y=f\left(x\right)$ in the y-axis, we get the graph for $y=f\left(-x\right)$
We will start the graph of the standard function $y={2}^{x}$ (represented by blue dashed curve)
Reflect the graph of $y={2}^{x}$ in the y-axis, to get the graph for $y={2}^{-x}$ (represented by black solid curve)

Step 2
Remember that: When we shift the graph of $y=f\left(x\right)$ by k units upwards, we get the graph for
Shift the graph of $y={2}^{-x}$ by 1 unit upwards, to get the graph for (represented by red solid curve).
The graph for $y={2}^{-x}$ is represented by black dashed curve.

Do you have a similar question?


text:
# Why insert menu shortcuts sometime run other actions? [duplicate]

I am new in Mathematica. I am wondering, why insert menu shortcuts, like ctrl + ^, or ctrl + _ sometimes result in another action, e.g. "find on page", or "open a new Notebook"?

I really didn't change any settings. Mathematica 10.

Thanks

Edit: Switching the keyboard language helps, but for a short time.

Edit2: Even ctrl +s, ctrl +c, ctrl+v sometimes result in another action, although in other applications, like Microsoft Word, Visual Studio or Matlab, everything works well.

Edit3: I noticed this "feature" long time ago. Restarting PC/Mathematica doesn't help.

## marked as duplicate by MarcoB, ilian, Sjoerd C. de Vries, Jens, dr.blochwaveAug 7 '15 at 6:58

• Even ctrl+v sometimes doesn't work properly. I don't have any hotkey programs running – Mikhail Genkin Aug 6 '15 at 19:28


text:
# Resolution and incomplete Knowledge Base

Assume I have an incomplete knowledge base, for example:

(rich(dave), poor(dave))  // dave is either poor or rich

(not rich(dave), not poor(dave))  // dave is not poor and rich at the same time.

My questions are: 1. If I do resolution on the above clauses, will I get the empty clause? and 2. If Yes, Does that mean my knowledge base is inconsistent?

-

## migrated from cstheory.stackexchange.comNov 5 '12 at 16:45

This question came from our site for theoretical computer scientists and researchers in related fields.

All the resolution tutorials I have found only resolve one predicate at a time, and I don't know how to handle the above. – Aida T. Nov 5 '12 at 2:27

The theory is not inconsistent and trivially admits two different models :

• a first one in which dave is rich but not poor;
• a second one in which dave is poor but not rich.

You're maybe confusing the "empty clause" which contains no literal, thus being always false, with the "true clause" which contains both a literal and its negation, thus being always true. Applying resolution leads to the "true clause" resolvent, not the "empty clause".

-
Thank you. Does this mean in resolution, ALWAYS one predicate is resolved in each step, right? – Aida T. Nov 17 '12 at 17:47
Understanding "resolved" as "deleted" : yes. en.wikipedia.org/wiki/… – Romuald Nov 18 '12 at 19:20


text:
# Scalar multiplication

Scalar multiplication in the Euclidean plane: the vector w is multiplied by the number 2 and the vector v by the number -1

The scalar multiplication , also called S multiplication or scalar multiplication , is an outer two-digit link between a scalar and a vector that is required in the definition of vector spaces . The scalars are the elements of the body over which the vector space is defined. The analog connection in modules is also called scalar multiplication.

The result of a scalar multiplication is a correspondingly scaled vector . In the illustrative case of Euclidean vector spaces , the scalar multiplication extends or shortens the length of the vector by the specified factor. In the case of negative scalars, the direction of the vector is also reversed. A special form of such scaling is normalization . Here, a vector is multiplied by the reciprocal of its length (generally its norm ), resulting in a unit vector with length (or norm) one.

## definition

If there is a vector space over the body , then the scalar multiplication is a two-digit operation ${\ displaystyle V}$ ${\ displaystyle K}$

${\ displaystyle \ odot \ colon K \ times V \ to V}$,

which, by definition of the vector space, is mixed associative and distributive , i.e. fulfills the following properties for all vectors and all scalars : ${\ displaystyle u, v \ in V}$${\ displaystyle \ alpha, \ beta \ in K}$

• ${\ displaystyle \ alpha \ odot (\ beta \ odot v) = (\ alpha \ cdot \ beta) \ odot v}$
• ${\ displaystyle \ alpha \ odot (u \ oplus v) = \ alpha \ odot u \ oplus \ alpha \ odot v}$
• ${\ displaystyle (\ alpha + \ beta) \ odot v = \ alpha \ odot v \ oplus \ beta \ odot v}$

In addition, the neutrality of the single element of the body applies : ${\ displaystyle 1}$

• ${\ displaystyle 1 \ odot v = v}$.

Here refers to the vector addition in as well , and each addition and multiplication in the body . Is often both the vector addition, and for the body adding the plus sign and both the scalar multiplication, and for the body multiplying the mark is used. This convention will also be followed later in this article to make it easier to read. The multiplication symbol is often left out and you write briefly instead of and instead of . ${\ displaystyle \ oplus}$${\ displaystyle V}$${\ displaystyle +}$${\ displaystyle \ cdot}$${\ displaystyle K}$ ${\ displaystyle +}$ ${\ displaystyle \ cdot}$${\ displaystyle \ alpha \ beta}$${\ displaystyle \ alpha \ cdot \ beta}$${\ displaystyle \ alpha v}$${\ displaystyle \ alpha \ cdot v}$

## properties

### neutrality

Designates the zero element of the body and the zero vector of the vector space, then applies to all vectors${\ displaystyle 0_ {K} \ in K}$${\ displaystyle 0_ {V} \ in V}$${\ displaystyle v \ in V}$

${\ displaystyle 0_ {K} \ cdot v = 0_ {V}}$,

because it is true with the second distributive law

${\ displaystyle 0_ {K} \ cdot v + 0_ {K} \ cdot v = (0_ {K} + 0_ {K}) \ cdot v = 0_ {K} \ cdot v}$

and therefore must be the zero vector. The same applies to all scalars${\ displaystyle 0_ {K} \ cdot v}$${\ displaystyle \ alpha \ in K}$

${\ displaystyle \ alpha \ cdot 0_ {V} = 0_ {V}}$,

because it holds with the first distributive law

${\ displaystyle \ alpha \ cdot 0_ {V} + \ alpha \ cdot 0_ {V} = \ alpha \ cdot (0_ {V} + 0_ {V}) = \ alpha \ cdot 0_ {V}}$

and therefore the zero vector must also be here . Overall you get that ${\ displaystyle \ alpha \ cdot 0_ {V}}$

${\ displaystyle \ alpha \ cdot v = 0_ {V} \ Leftrightarrow \ alpha = 0_ {K} ~ {\ text {or}} ~ v = 0_ {V}}$,

because it follows either or and then , where the multiplicative inverse element is to. ${\ displaystyle \ alpha \ cdot v = 0_ {V}}$${\ displaystyle \ alpha = 0_ {K}}$${\ displaystyle \ alpha \ neq 0_ {K}}$${\ displaystyle v = \ alpha ^ {- 1} \ cdot 0_ {V} = 0_ {V}}$${\ displaystyle \ alpha ^ {- 1}}$${\ displaystyle \ alpha}$

### Inverse

If now denotes the additively inverse element to the unity element and the inverse vector to , then applies ${\ displaystyle -1}$${\ displaystyle 1}$${\ displaystyle -v}$${\ displaystyle v}$

${\ displaystyle (-1) \ cdot v = -v}$,

because with the neutrality of one one obtains

${\ displaystyle 0_ {K} = 0_ {K} \ cdot v = (1-1) \ cdot v = 1 \ cdot v + (- 1) \ cdot v = v + (- 1) \ cdot v}$

and so the inverse vector is too . If the additively inverse element is generally closed , then applies ${\ displaystyle (-1) \ cdot v}$${\ displaystyle v}$${\ displaystyle - \ alpha}$${\ displaystyle \ alpha}$

${\ displaystyle (- \ alpha) \ cdot v = - (\ alpha \ cdot v) = \ alpha \ cdot (-v)}$,

because with one gets through the mixed associative law ${\ displaystyle \ beta = -1}$

${\ displaystyle (- \ alpha) \ cdot v = (\ beta \ alpha) \ cdot v = \ beta \ cdot (\ alpha \ cdot v) = - (\ alpha \ cdot v)}$

as well as with the commutativity of the multiplication of two scalars

${\ displaystyle (- \ alpha) \ cdot v = (\ alpha \ beta) \ cdot v = \ alpha \ cdot (\ beta \ cdot v) = \ alpha \ cdot (-v)}$.

## Examples

### Coordinate vectors

If the coordinate space and a coordinate vector , then the multiplication with a scalar is defined component-wise as follows: ${\ displaystyle V = K ^ {n}}$${\ displaystyle v = (v_ {1}, \ ldots, v_ {n}) ^ {T} \ in K ^ {n}}$${\ displaystyle \ alpha \ in K}$

${\ displaystyle \ alpha \ cdot v = \ alpha \ cdot {\ begin {pmatrix} v_ {1} \\\ vdots \\ v_ {n} \ end {pmatrix}} = {\ begin {pmatrix} \ alpha \ cdot v_ {1} \\\ vdots \\\ alpha \ cdot v_ {n} \ end {pmatrix}}}$.

In scalar multiplication, each component of the vector is therefore multiplied by the scalar. In three-dimensional Euclidean space , for example, one obtains ${\ displaystyle \ mathbb {R} ^ {3}}$

${\ displaystyle 3 \ cdot {\ begin {pmatrix} \, 1 \, \\ 4 \\ 2 \ end {pmatrix}} = {\ begin {pmatrix} \, 3 \ cdot 1 \, \\ 3 \ cdot 4 \\ 3 \ cdot 2 \ end {pmatrix}} = {\ begin {pmatrix} \, 3 \, \\ 12 \\ 6 \ end {pmatrix}}}$.

### Matrices

If the matrix space and a matrix , the multiplication with a scalar is also defined component-wise: ${\ displaystyle V = K ^ {m \ times n}}$${\ displaystyle A = (a_ {ij}) \ in K ^ {m \ times n}}$${\ displaystyle \ alpha \ in K}$

${\ displaystyle \ alpha \ cdot A = \ alpha \ cdot {\ begin {pmatrix} a_ {11} & \ ldots & a_ {1n} \\\ vdots & \ ddots & \ vdots \\ a_ {m1} & \ ldots & a_ {mn} \ end {pmatrix}} = {\ begin {pmatrix} \ alpha \ cdot a_ {11} & \ ldots & \ alpha \ cdot a_ {1n} \\\ vdots & \ ddots & \ vdots \\\ alpha \ cdot a_ {m1} & \ ldots & \ alpha \ cdot a_ {mn} \ end {pmatrix}}}$.

With scalar multiplication, each entry in the matrix is multiplied by the scalar. For example, one obtains for a real matrix ${\ displaystyle (2 \ times 2)}$

${\ displaystyle 3 \ times {\ begin {pmatrix} 1 & 2 \\ 4 & 3 \ end {pmatrix}} = {\ begin {pmatrix} 3 \ times 1 & 3 \ times 2 \\ 3 \ times 4 & 3 \ times 3 \ end {pmatrix} } = {\ begin {pmatrix} 3 & 6 \\ 12 & 9 \ end {pmatrix}}}$.

### Polynomials

If the vector space of the polynomials in the variable with coefficients is from a field , then the multiplication of a polynomial with a scalar is again defined component-wise: ${\ displaystyle V = K [X]}$${\ displaystyle X}$${\ displaystyle K}$${\ displaystyle P \ in K [X]}$${\ displaystyle \ alpha \ in K}$

${\ displaystyle \ alpha P = \ alpha (a_ {0} + a_ {1} X + \ dotsb + a_ {n} X ^ {n}) = (\ alpha a_ {0}) + (\ alpha a_ {1} ) X + \ dotsb + (\ alpha a_ {n}) X ^ {n}}$.

For example, the scalar multiplication of the real polynomial function with the number gives the polynomial ${\ displaystyle p (x) = x ^ {n} -x}$${\ displaystyle 3}$

${\ displaystyle (3p) (x) = 3 (x ^ {n} -x) = 3x ^ {n} -3x}$.

### Functions

If a linear function space and a function from a non-empty set into a vector space , then the result of the scalar multiplication of such a function by a scalar is defined as the function ${\ displaystyle V = F (\ Omega, W)}$${\ displaystyle f \ in F (\ Omega, W)}$ ${\ displaystyle \ Omega}$${\ displaystyle W}$${\ displaystyle \ alpha \ in K}$

${\ displaystyle \ alpha f \ colon \ Omega \ to W, \ quad x \ mapsto (\ alpha f) (x) = \ alpha \ cdot f (x)}$.

For example, if one considers the vector space of the linear real functions of the form , then one obtains the function by scalar multiplication with a real number${\ displaystyle f (x) = ax + b}$${\ displaystyle c}$

${\ displaystyle (cf) (x) = c \ cdot f (x) = c \ cdot (ax + b) = cax + cb}$.

With the scalar multiplication, each function value is scaled by the factor . ${\ displaystyle c}$


text:
When I was growing up, everybody expected the world to eventually go up in flames.

I mean, this was during the heyday of the Cold War. Had you asked any adult in the mid-1960s, anywhere in North America or Europe, if the world would survive without nuclear Armageddon to the year 2000, most would have said, not a chance. Even Star Trek predicted a global conflict sometime in the mid-1990s.

Yet here we are, in 2019, and the world is still in one piece. (Yes, despite the efforts of certain, ahem, notable persons. But allow me not to go there at this time.)

And we no longer seem to be concerned with civil defense. But back in the 1950s, 1960s, that was not the case. In the “duck and cover” era, civil defense was very important.

And thus it came to be that Canada’s Emergency Measures Organization even commissioned illustrations that show well-known Ottawa landmarks turned into ruin by war.

The images of the Chateau Laurier, Parliament’s Peace Tower, and the War Memorial appear uncannily realistic. Almost photographic in quality, they could serve as storyboard images for a post-apocalyptic computer game.

Much as I like computer games like that, such as the Fallout or Metro series, I hope we never get to see in reality what these images depict.

There really was a 1958 episode of a television Western (an episode titled The End of the World, of the series Trackdown), in which a character named Trump, a con artist, proposes to build an impenetrable wall to protect a town’s inhabitants.

Snopes confirms: the episode is real. In fact, the full episode is available on YouTube.

I almost forgot: a couple of months ago, I was interviewed over the telephone by a journalist who wanted to know my thoughts about one of my favorite moments in manned space exploration: The Apollo 8 “Genesis” moment, the reading of the opening verses of the Old Testament, on Christmas Day, 1968, by the astronauts of Apollo 8 as their spacecraft emerged from behind the Moon.

Today, something reminded me of this interview and I did a quick search. Lo and behold, there it is: My words, printed in The Boston Globe on December 23, 2018:

“It was a beautiful moment, and Genesis is part of our Western cultural heritage,” said Viktor Toth, an atheist and a senior research fellow at Carleton University in Ottawa, Canada, who played the lead role in the investigation of the Pioneer Anomaly, the mysterious acceleration of the Pioneer 10 and 11 spacecrafts in deep space. “This was an awe-inspiring thing: Human beings for the first time cut off from the Earth, and then they reemerged and saw the Earth again. The message was entirely appropriate.”

Though shortened, this pretty accurately reflects what I actually said during that roughly 10-minute conversation with the journalist.

Today, I answered a question on Quora about the nature of $$c$$, the speed of light, as it appears in the one equation everyone knows, $$E=mc^2.$$

I explained that it is best viewed as a conversion factor between our units of length and time. These units are accidents of history. There is nothing fundamental in Nature about one ten millionth the distance from the poles to the equator of the Earth (the original definition of the meter) or about one 86,400th the length of the Earth’s mean solar day. These units are what they are, in part, because we learned to measure length and time long before we learned that they are aspects of the same thing, spacetime.

And nothing stops us from using units such as light-seconds and seconds to measure space and time; in such units, the value of the speed of light would be just 1, and consequently, it could be dropped from equations altogether. This is precisely what theoretical physicists often do.

But then… I commented that something very similar takes place in aviation, where different units are used to measure horizontal distance (nautical miles, nmi) and altitude (feet, ft). So if you were to calculate the kinetic energy of an airplane (measuring its speed in nmi/s) and its potential energy (measuring the altitude, as well as the gravitational acceleration, in ft) you would need the ft/nmi conversion factor of 6076.12, squared, to convert between the two resulting units of energy.

As I was writing this answer, though, I stumbled upon a blog entry that discussed the crazy, mixed up units of measure still in use worldwide in aviation. Furlongs per fortnight may pretty much be the only unit that is not used, as just about every other unit of measure pops up, confusing poor pilots everywhere: Meters, feet, kilometers, nautical miles, statute miles, kilograms, pounds, millibars, hectopascals, inches of mercury… you name it, it’s there.

Part of the reason, of course, is the fact that America, alone among industrialized nations, managed to stick to its archaic system of measurements. Which is another historical accident, really. A lot had to do with the timing: metric transition was supposed to take place in the 1970s, governed by a presidential executive order signed by Gerald Ford. But the American economy was in a downturn, many Americans felt the nation under siege, the customary units worked well, and there was a conservative-populist pushback against the metric system… so by 1982, Ronald Reagan disbanded the Metric Board and the transition to metric was officially over. (Or not. The metric system continues to gain ground, whether it is used to measure bullets or Aspirin, soft drinks or street drugs.)

Yet another example similar to the metric system is the historical accident that created the employer-funded healthcare system in the United States that American continue to cling to, even as most (all?) other advanced industrial nations transitioned to something more modern, some variant of a single-payer universal healthcare system. It happened in the 1920s, when a Texas hospital managed to strike a deal with public school teachers in Dallas: For 50 cents a month, the hospital picked up the tab of their hospital visits. This arrangement became very popular during the Great Depression when hospitals lost patients who could not afford their hospital care anymore. The idea came to be known as Blue Cross. And that’s how the modern American healthcare system was born.

As I was reading this chain of Web articles, taking me on a tour from Einstein’s $$E=mc^2$$ to employer-funded healthcare in America, I was reminded of a 40-year old British TV series, Connections, created by science historian James Burke. Burke found similar, often uncanny connections between seemingly unrelated topics in history, particularly the history of science and technology.

One hundred years ago today, at 11 AM Paris time (the eleventh hour of the eleventh day of the eleventh month), the War to End All Wars itself ended.

We know what happened in the century that followed. Communism. Fascism. Totalitarianism. Another World War. The Holocaust. Invasion and civil war in China. Nuclear bombs dropped in anger. The Cold War. Korea. Colonial and post-colonial wars like Vietnam.

Yet there is hope that we are becoming wiser. The world as a whole has been largely peaceful for 73 years. No more world wars, no more wars between major powers. Nuclear weapons, so far, proved to be peacemakers instead of annihilating civilization. More people live in peace, have their basic rights respected, have access to a basic education, safe drinking water, basic health care and sufficient nutrition than ever before.

But… When I was in my 20s, politicians in power were all leaders who have seen war. Leaders who were less interested in winning wars than in avoiding them. Put the likes of Kennedy or Khrushchev, Nixon or Brezhnev, even Stalin in a room, and while they might have disagreed on just about everything, they would have agreed on this one.

Not anymore. Our fearless leaders today have not experienced war. Therefore, they may no longer consider avoiding major war a supreme imperative. And when I listen to the rhetoric of Trump, Putin, even French President Macron when he speaks in favor of a joint European army, I realize that for these leaders, war is no longer something they fear, but rather, something they are confident they can win.

Which is why it is especially important to celebrate November 11, 1918, for what it really is: The end of a nightmare. A nightmare in which even the victors weren’t truly victorious, as they all lost a lot and gained very little. A nightmare that ended decades of peace and prosperity and plunged the world into decades of darkness. For the peace that followed was an uneasy one: instead of a safer world, communism was born and the seeds of fascism were sown in 1917-18.

An interesting article appeared on the Web site of BBC News today.

It describes a US president who is anti-immigration, who has a proclivity for conspiracy theories, and who appoints his own daughter to a prominent role in the White House.

But no, it is not Donald J. Trump. It is Millard Fillmore, who became the 13th president of the United States after the death of Zachary Taylor, under whom Fillmore served as Vice-President.

One of the least known among US presidents perhaps, Fillmore nonetheless played a role in the destruction of the Whig Party and the subsequent rise of the Republican Party and their 1860 nominee for President, Abraham Lincoln. It was also under Fillmore’s presidency that the controversial Compromise of 1850 was accomplished. Whether it postponed the Civil War or was a contributing cause remains a subject of debate to this day.

Fillmore’s political career collapsed after his one term. The Whig Party, already in tatters, did not nominate him in 1852. His life was afflicted by tragedies, as he lost his wife and his only daughter in rapid succession shortly after leaving office.

Uncanny similarities notwithstanding, there are also significant differences between Fillmore and Trump. Though described by Queen Victoria as the handsomest man she had ever seen, Fillmore was no rich playboy; he was born in poverty, and he was worried about making a living after leaving the White House, as he was not independently wealthy. And he was certainly a more humble man than Trump: He refused to accept an honorary doctorate from Oxford, stating that he had no “literary or scientific attainment” that would justify the diploma. Besides, his lack of a classical education meant that he spoke no Latin, yet “no man should accept a degree he cannot read”. Somehow, I doubt that such considerations would prevent the 45th president from accepting such an honor.

In 1856, Fillmore again ran for the presidency as the candidate of the newly formed American Party, but only carried the state of Maryland. He died in 1874.

Bashing Trump is a favorite pastime of mine and that of many of my friends. To be sure, there are plenty of reasons to despise the man: His obvious racism, misogyny, narcissism, nepotism, corruption, his authoritarian tendencies, just to name a few.

But putting the focus on these characteristics leads us to miss a very important point. As a Republican president, Trump delivers. He does precisely what his base (who did elect him, after all) were hoping for. Putting conservative justices on the Supreme Court, who might reverse Roe v. Wade and other landmark “liberal” decisions? Check. Sabotaging Obamacare? Check. Making a stand against immigration? Check. A protectionist economic policy? Check. Standing up even against the Republican establishment in Washington? Check.

Trump’s base, by the way, also happen to distrust liberal democracy, and may not be adverse to a more authoritarian, strongman-style rule, so long as it is their strongman. As such, they are far less alarmed by the ease with which Trump gets along with other strongmen and the difficulty he has with the leaders of liberal democracies that are America’s traditional allies. This may even be seen as part of his “alpha male” personality, a sign of his strength.

So even if we take the hatemongering, Islamophobia, racism and other unsavory factors out of the equation, Trump is to many a dream come true: He is delivering precisely what they hoped to see from a Republican president.

And it is because of this that they are willing to turn a blind eye to Trump’s personal shortcomings. It may appear hypocritical, but ultimately, it’s just good old political pragmatism.

For this reason, I think it is deeply misguided to focus on the failings of Trump. This visceral reaction to Trump’s personality does not resonate with his base. If anything, it strengthens their perception that their political opposition is a bunch of disloyal losers: unpatriotic liberals who would rather see the man they despise fail, even if it harms America. (That conservatives behaved exactly like this in their opposition to Obama may not cross their minds. In fact, the very fact that they themselves behaved in this manner may be a reason why they so easily believe that their liberal opposition is no different.)

Is left-wing populism the answer? Supporters of Bernie Sanders undoubtedly think so. But I have my doubts. Why would left-wing populism be any better than its right-wing counterpart? In both cases, we end up with leaders who are dilettantes and demagogues. The problem these days (and this issue is not confined within the borders of America; look at Europe, or look right here, at the Canadian province of Ontario) is the collapse of the center. The end of fact-based governance by an increasingly despised technocratic “elite”.

The irony of it is that this liberal world order, for all its failings, kept the world together with no major conflict for the past 70-odd years, a golden age of possibly unprecedented growth and prosperity. (And not just in the first world; just look at global statistics of life expectancy, literacy rates, and other measures that show just how much life improved throughout much of the planet since 1945.) Yet not only is it rejected, it is rejected most vehemently by those who benefited from it the most.

There was another, similar golden era of near unprecedented growth and prosperity: The second half of the 19th century, all the way up to 1914. Yet even as more and more thinkers were convinced that the era of wars between major powers is a thing of the past, the world was heading towards the disaster called the Great War, which plunged the world into chaos, destroyed the prevailing world order, created the circumstances for the rise of the twin evils of communism and fascism, and eventually led to a second world war and the industrial-scale mass murder of the Holocaust.

I don’t know where the world is heading today, but I admit I think about 1914 a lot.

Here is a sobering statistic based on some Gallup data. The only president ever who was more popular among same party followers than Trump was… George W. Bush.

Yes. More popular than JFK, Ike, Obama or Reagan, 500 days into the presidency.

Then again, this chart may reflect a disease that goes deeper than Trump: the continuing ideological polarization of America. Here are the same figures, this time in chronological order:

The trend seems unmistakable. After WW2, voters were, it appears, more skeptical. Presidents were approved based on their deeds more than their party affiliation. This appears to have changed in the past 70 years. Now, party affiliation matters more.

Then again… What if Truman, Ford, Carter, G. W. Bush are all outliers? After all, in all their cases the circumstances were unusual, exceptional even. Take them out and what we are left with is a pretty steady approval rating in the vicinity of 80%, give or take.

I don’t know. With a data set of only 13 data points, throwing four away as outliers is a bit excessive.

When I was a teenager, the classic novel, The Count of Monte Cristo by Alexandre Dumas, was one of my favorites.

And one of my favorite chapters in that book was a chapter with an uncanny (not to mention unusually long) title: “How a Gardener May Get Rid of the Dormice that Eat His Peaches”. In it, Dumas describes a classic hack: exploiting the human in the system. By bribing an operator of France’s early optical telegraph network, the book’s protagonist is able to plant a false message, which ultimately contributes to the downfall of one of his mortal enemies. In short: a targeted cyberattack on a telecommunications network.

What I did not know, however, is that this chapter may have been inspired by real life events. About ten years before Dumas published his novel, the brothers François and Louis* Blanc managed to hack the telegraph network in a manner even more sophisticated than the hack described in Dumas’s book. Yes, the real-life hack relied on bribing operators, too, but it also involved a case of steganography: inserting a coded message that would piggyback on the original telegraph transmission. Not only did the scheme succeed, like any good hack it remained in place and undetected for two years. And when it was finally detected, the Blanc brothers were charged but never convicted; there were, after all, no laws on the books back in the 1830s against misuse of data networks.

*Well, that’s what Wikipedia tells me. It appears that the twins are misidentified as Francois and Joseph in several English-language publications. Francois was later known as The Magician of Monte Carlo, a casino that he owned and where he first introduced the single-0 style roulette wheel.

I admit I never expected to see this:

I admit I despise both gentlemen in this picture, albeit for different reasons.

However… if this meeting has a positive outcome, I will cheer when they are both awarded the Nobel peace prize.

The more I learn about ancient China, the more my respect grows for the Middle Kingdom and its amazing history.

Here is something written by a 9th century Muslim traveler, Abu Zayd al-Sirafi, who visited China during the Tang Dynasty, in 850 A.D. or thereabouts. I found a modern translation that I first came across so incredible, I searched for corroboration. I then came across this 1733 English translation (if I interpret the cover page correctly, by an unnamed English translator using a French translation from the Arabic by Eusebius Renaudot).

Here is how this 1733 text describes China’s social safety net. (And if you are left wondering if perhaps the traveler mistakenly traveled into the future, visiting a late 20th, early 21st century welfare state, you are not alone):

“The Chinese have a Stone ten Cubits high, erected in the public Squares, and on this Stone are graved the Names of all sorts of Medicines, with the exact rates of each; and when the poor stand in need of any Relief from Physic, they go to the Treasury, where they receive the Price each Medicine is rated at.

“There is no Land Tax in China; they only levy so much per Head, according to the Wealth and Possessions of the Subject. When a Male Child is born, his Name is immediately entered into the King’s Books, and when this Child has attained his eighteenth Year, he begins to pay for his Head; but they demand it not of the Man who has seen his eightieth Year; on the contrary he receives a Gratification, by way of Pension, from the public Treasury; and in doing this, the Chinese say, That they give him this Gratification in his old days, in acknowledgment for what they receiv’d of him when he was young.

“There are Schools in every Town for teaching the Poor and their Children to write and read, and the Masters are paid at the public Charge.”

This text was written nearly 1,200 years ago. It took another millennium before public education become the norm in more developed European nations, and at least another century before various forms of social security and public health institutions took root.

I am beginning to appreciate more and more why the Middle Kingdom viewed the period loosely demarcated by the Opium Wars of the 1850s and the Japanese occupation of the 1930s and 1940s as the Century of Humiliation; and why it might appear to many that the recent rise of China as an economic superpower only means a return to the way things were always supposed to be, the way things have been for several millennia preceding the rapid rise of Europe a few centuries ago.

Not too long ago (OK, well, 30 years… it doesn’t feel that long anymore) there was another genius on the news: the Genius of the Carpathians, Romanian dictator Nicolae Ceausescu.

Here is a joke from that era that, no doubt, could be adapted to fit the “very stable genius”, too.

The US president, the General Secretary of the Soviet communist party, the Pope and Ceausescu are flying somewhere on a plane. Suddenly, the pilot enters the compartment and says, “Gentleman, I have bad news. This airplane is about to crash and we only have four parachutes.”

Immediately, the US president yells, “I am the leader of the free world, I must survive!”, grabs a parachute and jumps.

He is followed by the Soviet leader, who yells, “I am the leader of the worldwide socialist revolution. I must survive!”, grabs another parachute and jumps.

Next comes Ceausescu: “I am the Genius of the Carpathians! I must survive!”, grabs the next parachute and jumps.

The Pope and the pilot remain. The Pope looks at the pilot and says, “My son, I am old and lived a full life. Your whole life is ahead of you. Please take that parachute. I’ll pray for your survival.” The pilot responds, “No need to worry, Holy Father, we have two parachutes left. The Genius of the Carpathians grabbed the fire extinguisher.”

100 years ago today, as war was raging in Europe, the city of Halifax went up in flames in what remains one of the largest non-nuclear man-made explosions in history.

What began as a series of navigational errors resulted in a collision of two ships in Halifax Harbor, one of which was full of explosives. This ship caught fire and as its crew fled, the burning vessel drifted towards the city. It eventually exploded.

The destroyed Exhibition Building in Halifax, NS, also known as the location where the last body form the explosion was recovered two years later.

By the time it was all over, nearly 2,000 people were dead with many more injured. A large number of people lost their eyesight, as they were watching the harbor from indoors through glass windowpanes. These were shattered by the supersonic shock front of the explosion, the shards turning into shrapnel.

A Mi’kmaq community across the harbor was also destroyed, never to be rebuilt. Many of the residents were killed, while others were housed in segregated shelters, and ultimately dispersed throughout the province.

In between being sick with a cold and being hopelessly behind with my TODO list, I almost forgot. Today was an remarkable anniversary.

It was 100 years ago today that the Great October Socialist Revolution (which happened on October 25 according to the Julian calendar, which was still in use in Russia in 1917) achieved victory in St. Petersburg and the Utopian communist Soviet state was born.

Sadly, the Utopian dreams did not last very long. In between its inability to govern without violence and the threats, both internal and external, that the fledgling communist state faced, it quickly turned to a less Utopian interpretation of Marx’s dream: The “dictatorship of the proletariat”, one-party rule in a totalitarian police state.

Nonetheless… when I was little, growing up in then-communist Hungary behind the Iron Curtain, the Soviet Union seemed eternal. Its successes were spectacular, including how it prevailed against the Nazi war machine in the Great Patriotic War and also how it rushed to the forefront of many areas in engineering and the sciences, including the first orbital spacecraft and the first manned spaceflight.

Alas, the Soviet Union proved less eternal than anyone thought. It was done in by an incompetent, ultraconservative octogenarian leadership and the inherent failures and weaknesses of its command economy. Less than 75 years after it was created, the Soviet Union ceased to exist. The red flag over the Kremlin was taken down, and the Soviet federation itself broke up into its constituent states.

And now here we are, on the 100th anniversary of the Great October Socialist Revolution, and barely anyone remembers. There are no broadcasts of military parades from Moscow’s Red Square. Not even a brief commemoration in the evening local news on the CBC, or on CNN in between their analysis of Trump’s Asia trip and the results of tonight’s interim elections. If Russia is mentioned at all, it’s only in the context of the Mueller investigation. The revolution that shook the world in 1917 and shaped the world for three quarters of a century afterwards seems mostly forgotten.

Heck, I almost forgot to blog about it.

The recent dramatic rise in the number of North Korean missile launches, combined with their successful test of a thermonuclear weapon and their announcement (so far, unverified) that they now have the capability to mount a weapon on top of an intercontinental ballistic missile, in combination with a US president who has a demonstrated willingness to “go rogue”, raises the very real possibility of an armed conflict between the United States and North Korea. A conflict that can quickly and uncontrollably escalate.

And it may all be based on a giant misunderstanding.

The almost unanimous opinion in the West appears to be that the DPRK is a rogue regime. That its megalomaniac dictator finds self-gratification in the building of nuclear missles. And that he represents a direct threat, a clear and present danger to the United States.

But what if this is not the case? What if the DPRK leadership is, ahem, rational?

Rational, that is, but based on a biased, distorted interpretation of the facts.

What if they genuinely believe that it is their regime that is being threatened by the United States? That nuclear weapons represent the only security guarantee against a rogue imperialist superpower?

And what if they actually believe their own propaganda version of history, namely that back during the Korean War, it was the DPRK army, under the leadership of its Great Leader, that defeated America, rather than Mao’s China achieving a stalemate? Or that it was indeed the United States that attacked the peace-loving DPRK instead of the DPRK launching a war against its southern neighbor?

These biases lead to the rational conclusion that, on the one hand, the threats faced by the DPRK are very real and thus a nuclear deterrent is essential; and that, on the other hand, bellicose talk can help remind the United States of a supposedly humiliating defeat and deter it from further aggression.

If this is the case, the proper response is negotiation: credible security guarantees offered to North Korea, tangible proof that there is no intent to attack. Threats, such as those uttered by Trump just a few minutes ago while speaking to the UN General Assembly, achieve the exact opposite: they reinforce North Korean beliefs that the American threat is real and imminent. Far from deterring them from pursuing a nuclear weapons program, it prompts them to accelerate their efforts.

And the almost inevitable outcome of the escalation of this war of words is real war. And when that happens, the proverbial excrement can quickly hit the ventilator. China may choose to get involved; reluctantly, perhaps, but they may believe that getting involved is the lesser of two evils. But that involvement can quickly result in direct conflict between China and the United States, or US allies like Japan. And if by any chance Russia chooses to get involved as well, the situation can quickly escalate into an unintended world conflict.

Cannot happen? Think again. 103 years ago this year, a major European power decided to launch a limited military strike to punish a rogue power, a supporter of terrorism, indirectly responsible for a high-profile political assassination. Within weeks, much of the world was embroiled in a conflict that nobody wanted, nobody believed in, and nobody knew how to win, how to end, or how to get out of. The Great War, the interregnum that followed including the rise of Nazism, the second World War and the rise of authoritarian communism worldwide cost, at the very least, 100 million lives. An experience I’d rather not see repeated, especially not with nuclear weapons involved.

Remember what radio used to be like, especially shortwave?

Many stations had an interval signal. This signal, usually just a few musical notes, was played whenever the station would otherwise be silent (e.g., between the end of a program and the time signal at the top of the hour.) I remember many an interval signal fondly.

But one of them, I just cannot identify. Namely this one:

Bugs the devil out of me.

It is well known that the despicable Biff Tannen character from the Back to the Future movies was based on a certain real-life despicable mogul by the name of Donald J. Trump. In particular, the “rich Biff” of 1985, having established a casino and real estate empire after receiving a sports almanac from the future back in 1955, was modeled after everyone’s favorite Trump.

In light of this and today’s historic events, it is only appropriate to imagine how the real-life Biff, I mean Trump, would have fared in one of the movies’ iconic scenes:

I hate manure…

Yes, I know it is more than a little crass to share this tweet. Even so, it is far less distasteful than the many racist caricatures that followed Obama’s inauguration and frankly, it makes it a lot easier to deal with this historic day.

I really have no words to describe how I feel about today. But a picture is worth a thousand words.

I just finished listening to Obama’s farewell address.

Now why do I have the feeling that this may be the very last time in my life that I’ll be hearing an American President preach goodness and decency instead of contempt and hate? Uplifting thoughts instead of fear and loathing?

Meanwhile, there appears to be a multitude of clowns on the Interwebs who think repealing Obamacare is okay, because they are insured through the Affordable Care Act:

What can I say? Enjoy your improved healthcare starting next month, folks. Glad I live in pinko commie Canada where we have had decent (albeit far from perfect) medicare for half a century. Of course once Trump, along with his BFF Putin, manage to blow up the world, none of this will matter anymore.

Last night, after I watched the final episode of an amazing Brazilian television series, 3% (yes, that’s the title) on Netflix, I felt compelled to listen to the immortal song Aquarela do Brasil, especially the Geoff Muldaur version that was the title song for Terry Gilliam’s film Brazil.

As I was listening to the song, I realized that along with Vera Lynn’s We’ll Meet Again, it’s one of the songs I’d like to listen to when the world comes to an end.

Runner-ups include Nena’s 99 Luftballons and Anita Kelsey’s version (known from the film Dark City) of Sway (¿Quién será?)

As to why I am thinking about the end of the world…


text:
# If $\Sigma \models \phi$, then for some finite $\Delta \subset\Sigma$, $\Delta \models \phi$.

This is an easy consequence (Doets calls it Compactness Theorem (version 2)) in Kees Doets' Basic Model theory:

Let $$\Sigma$$ a set of sentences and $$\phi$$ a sentence.

If $$\Sigma \models \phi$$, then for some finite $$\Delta \subset\Sigma$$, $$\Delta \models \phi$$.

"If $$\phi$$ does not logically follow from some $$\Delta \subset \Sigma$$, then the set $$\Sigma \cup \{\neg \phi\}$$ is finitely satisfiable and therefore, by compactness, satisfiable."

How do we know that $$\Sigma \cup \{\neg \phi\}$$ is finitely satisfiable?

From the fact that $$\phi$$ does not logically follow from some $$\Delta$$, we know that $$\neg \phi$$ follows from every $$\Delta \subset \Sigma$$. But how does this imply that there's a model for every finite subset of the set of sentences?

First, a quick comment. Your statement "From the fact that $$\varphi$$ does not logically follow from some $$\Delta$$, we know that $$\neg\varphi$$ follows from every $$\Delta\subseteq \Sigma$$." is incorrect: when $$A$$ is a set of sentences, "$$A\not\models b$$" is different from "$$A\models\neg b$$." We could have $$b$$ be independent of $$A$$ - that is, $$A\not\models b$$ and $$A\not\models\neg b$$.

What is true is that since $$\varphi$$ isn't entailed by any finite $$\Delta\subseteq\Sigma$$, $$\neg\varphi$$ must be compatible with every finite $$\Delta\subseteq\Sigma$$ in the sense that, for every $$\Delta\subseteq\Sigma$$, the set $$\Delta\cup\{\neg\varphi\}$$ will be satisfiable. (It's arguably more natural to say "consistent with" instead of "compatible with," but consistency is a syntactic property which isn't needed in this purely semantic question, so I want to avoid using language which might bring in confusion.)

This is in fact the crux of the problem!

Saying "$$\Sigma\cup\{\neg\varphi\}$$ is finitely satisfiable" just means "$$\Delta\cup\{\neg\varphi\}$$ is satisfiable for every finite $$\Delta\subseteq\Sigma$$." But "$$\Delta\cup\{\neg\varphi\}$$ is satisfiable" just means "there is some model of $$\Delta\cup\{\neg\varphi\}$$," which is to say $$\Delta\not\models\varphi$$ ("$$\Delta\models\varphi$$" means exactly "every model of $$\Delta$$ satisfies $$\varphi$$," which can't be true if there is some model of $$\Delta\cup\{\neg\varphi\}$$).

All that is to say that the statement "$$\Sigma\cup\{\neg\varphi\}$$ is finitely satisfiable" is equivalent to "For every finite $$\Delta\subseteq\Sigma$$, we have $$\Delta\not\models\varphi$$." But this latter statement is precisely our hypothesis "$$\varphi$$ does not logically follow from some [finite] $$\Delta\subseteq\Sigma$$!"

Note that the phrase "logically follow from" could confuse things here: it's meant in the semantic sense ($$\models$$), not the syntactic sense ($$\vdash$$).

If $$\Sigma\vDash\phi$$, then there is a proof of $$\Sigma\vdash\phi$$ (completeness), and since that proof is a finite object it mentions at most finitely many of the axioms of $$\Sigma$$. Therefore the same proof proves $$\Delta\vdash\phi$$ for some finite $$\Delta\subseteq\Sigma$$, and thus $$\Delta\vDash\phi$$ (soundness).

• @HenningMakholm You're probably already familiar with this, but just in case: the semantic proof of compactness that really clicked for me - before the ultraproduct proof - was the fact that you can make Henkinization purely semantic. Let $\models_{fin}$ be the "finitary satisfaction relation," $A\models_{fin}b$ iff $D\models b$ for some finite $D\subseteq A$. We now proceed as usual, with $\models_{fin}$ in place of $\vdash$, and everything goes through basically unchanged. I also like this argument because it gives a(n interestingly, completely ahistorical) "story" for completeness: (cont'd) Dec 8, 2018 at 20:54
• in light of the coincidence of $\models$ with $\models_{fin}$, since the latter is finitary it's reasonable to hope that it is in fact computably enumerable. To find an appropriate $\vdash$, we now just look carefully through the proof that $\models_{fin}$ is all of $\models$, and each time we use a property of $\models_{fin}$ we get a corresponding proof rule. Of course, this isn't how it happened, but it's a natural enough story that I found it very helpful in learning the proof theoretic side of things: that the semantic result led naturally to the syntactic conjecture and ultimate success. Dec 8, 2018 at 20:57
• @HenningMakholm Comment 2 happens after comment 1. The "in light of" is following the proof of the compactness theorem above. My point is that, having proved compactness, it's now natural to look for a proof notion making the completeness theorem true; and having proved compactness specifically in the Henkin style, this becomes very straightforward. Dec 9, 2018 at 1:17
• Everything after "I also like" is not part of the proof of compactness, but an afterthought. Dec 9, 2018 at 1:17
• @AtticusStonestrom Yup, that tends to be exactly how I explain it. So far I've had good results, but to be fair I've only taught rather limited audiences with this so far. May 25, 2021 at 2:11

Every $$\Delta$$ finite have $$\Delta\vDash\lnot\varphi$$, so every model of $$\Delta$$ is a model of $$\Delta\cup\{\lnot\varphi\}$$, and there is a model for every $$\Delta$$, namely, the model of $$\Sigma$$

• So does Doets assume that $\Sigma$ has a model?
– Mike
Dec 8, 2018 at 20:32
• If there is no model to $\Sigma$, there is finite deduction sequence that proves contradiction, take $\Delta$ be all the elements of $\Sigma$ that appear in that sequence and you got a finite subset of $\Sigma$ that proves $\varphi$
– ℋolo
Dec 8, 2018 at 20:35
• @Holo "If there is no model to $\Sigma$, there is finite deduction sequence that proves contradiction" This uses the completeness theorem, which is overkill here. Dec 8, 2018 at 20:38
• @NoahSchweber that is true.. but this is the easiest way to look at this(at least the easiest from the ways I know)
– ℋolo
Dec 8, 2018 at 20:50
• @Holo I disagree - $\vdash$ isn't needed at all, this is just a direct application of the basic definition of $\models$. Dec 8, 2018 at 20:51