text:
# Vector Representations of Words

In this tutorial we look at the word2vec model by Mikolov et al. This model is used for learning vector representations of words, called "word embeddings".

## Highlights

This tutorial is meant to highlight the interesting, substantive parts of building a word2vec model in TensorFlow.

• We start by giving the motivation for why we would want to represent words as vectors.
• We look at the intuition behind the model and how it is trained (with a splash of math for good measure).
• We also show a simple implementation of the model in TensorFlow.
• Finally, we look at ways to make the naive version scale better.

We walk through the code later during the tutorial, but if you'd prefer to dive straight in, feel free to look at the minimalistic implementation in tensorflow/examples/tutorials/word2vec/word2vec_basic.py This basic example contains the code needed to download some data, train on it a bit and visualize the result. Once you get comfortable with reading and running the basic version, you can graduate to models/tutorials/embedding/word2vec.py which is a more serious implementation that showcases some more advanced TensorFlow principles about how to efficiently use threads to move data into a text model, how to checkpoint during training, etc.

But first, let's look at why we would want to learn word embeddings in the first place. Feel free to skip this section if you're an Embedding Pro and you'd just like to get your hands dirty with the details.

## Motivation: Why Learn Word Embeddings?

Image and audio processing systems work with rich, high-dimensional datasets encoded as vectors of the individual raw pixel-intensities for image data, or e.g. power spectral density coefficients for audio data. For tasks like object or speech recognition we know that all the information required to successfully perform the task is encoded in the data (because humans can perform these tasks from the raw data). However, natural language processing systems traditionally treat words as discrete atomic symbols, and therefore 'cat' may be represented as Id537 and 'dog' as Id143. These encodings are arbitrary, and provide no useful information to the system regarding the relationships that may exist between the individual symbols. This means that the model can leverage very little of what it has learned about 'cats' when it is processing data about 'dogs' (such that they are both animals, four-legged, pets, etc.). Representing words as unique, discrete ids furthermore leads to data sparsity, and usually means that we may need more data in order to successfully train statistical models. Using vector representations can overcome some of these obstacles.

Vector space models (VSMs) represent (embed) words in a continuous vector space where semantically similar words are mapped to nearby points ('are embedded nearby each other'). VSMs have a long, rich history in NLP, but all methods depend in some way or another on the Distributional Hypothesis, which states that words that appear in the same contexts share semantic meaning. The different approaches that leverage this principle can be divided into two categories: count-based methods (e.g. Latent Semantic Analysis), and predictive methods (e.g. neural probabilistic language models).

This distinction is elaborated in much more detail by Baroni et al., but in a nutshell: Count-based methods compute the statistics of how often some word co-occurs with its neighbor words in a large text corpus, and then map these count-statistics down to a small, dense vector for each word. Predictive models directly try to predict a word from its neighbors in terms of learned small, dense embedding vectors (considered parameters of the model).

Word2vec is a particularly computationally-efficient predictive model for learning word embeddings from raw text. It comes in two flavors, the Continuous Bag-of-Words model (CBOW) and the Skip-Gram model (Section 3.1 and 3.2 in Mikolov et al.). Algorithmically, these models are similar, except that CBOW predicts target words (e.g. 'mat') from source context words ('the cat sits on the'), while the skip-gram does the inverse and predicts source context-words from the target words. This inversion might seem like an arbitrary choice, but statistically it has the effect that CBOW smoothes over a lot of the distributional information (by treating an entire context as one observation). For the most part, this turns out to be a useful thing for smaller datasets. However, skip-gram treats each context-target pair as a new observation, and this tends to do better when we have larger datasets. We will focus on the skip-gram model in the rest of this tutorial.

## Scaling up with Noise-Contrastive Training

Neural probabilistic language models are traditionally trained using the maximum likelihood (ML) principle to maximize the probability of the next word $$w_t$$ (for "target") given the previous words $$h$$ (for "history") in terms of a softmax function,

\begin{align} P(w_t | h) &= \text{softmax} (\text{score} (w_t, h)) \\ &= \frac{\exp \{ \text{score} (w_t, h) \} } {\sum_\text{Word w' in Vocab} \exp \{ \text{score} (w', h) \} } \end{align}

where $$\text{score} (w_t, h)$$ computes the compatibility of word $$w_t$$ with the context $$h$$ (a dot product is commonly used). We train this model by maximizing its log-likelihood on the training set, i.e. by maximizing

\begin{align} J_\text{ML} &= \log P(w_t | h) \\ &= \text{score} (w_t, h) - \log \left( \sum_\text{Word w' in Vocab} \exp \{ \text{score} (w', h) \} \right). \end{align}

This yields a properly normalized probabilistic model for language modeling. However this is very expensive, because we need to compute and normalize each probability using the score for all other $$V$$ words $$w'$$ in the current context $$h$$, at every training step.

On the other hand, for feature learning in word2vec we do not need a full probabilistic model. The CBOW and skip-gram models are instead trained using a binary classification objective (logistic regression) to discriminate the real target words $$w_t$$ from $$k$$ imaginary (noise) words $$\tilde w$$, in the same context. We illustrate this below for a CBOW model. For skip-gram the direction is simply inverted.

Mathematically, the objective (for each example) is to maximize

$$J_\text{NEG} = \log Q_\theta(D=1 |w_t, h) + k \mathop{\mathbb{E}}_{\tilde w \sim P_\text{noise}} \left[ \log Q_\theta(D = 0 |\tilde w, h) \right]$$

where $$Q_\theta(D=1 | w, h)$$ is the binary logistic regression probability under the model of seeing the word $$w$$ in the context $$h$$ in the dataset $$D$$, calculated in terms of the learned embedding vectors $$\theta$$. In practice we approximate the expectation by drawing $$k$$ contrastive words from the noise distribution (i.e. we compute a Monte Carlo average).

This objective is maximized when the model assigns high probabilities to the real words, and low probabilities to noise words. Technically, this is called Negative Sampling, and there is good mathematical motivation for using this loss function: The updates it proposes approximate the updates of the softmax function in the limit. But computationally it is especially appealing because computing the loss function now scales only with the number of noise words that we select ($$k$$), and not all words in the vocabulary ($$V$$). This makes it much faster to train. We will actually make use of the very similar noise-contrastive estimation (NCE) loss, for which TensorFlow has a handy helper function tf.nn.nce_loss().

Let's get an intuitive feel for how this would work in practice!

## The Skip-gram Model

As an example, let's consider the dataset

the quick brown fox jumped over the lazy dog

We first form a dataset of words and the contexts in which they appear. We could define 'context' in any way that makes sense, and in fact people have looked at syntactic contexts (i.e. the syntactic dependents of the current target word, see e.g. Levy et al.), words-to-the-left of the target, words-to-the-right of the target, etc. For now, let's stick to the vanilla definition and define 'context' as the window of words to the left and to the right of a target word. Using a window size of 1, we then have the dataset

([the, brown], quick), ([quick, fox], brown), ([brown, jumped], fox), ...

of (context, target) pairs. Recall that skip-gram inverts contexts and targets, and tries to predict each context word from its target word, so the task becomes to predict 'the' and 'brown' from 'quick', 'quick' and 'fox' from 'brown', etc. Therefore our dataset becomes

(quick, the), (quick, brown), (brown, quick), (brown, fox), ...

of (input, output) pairs. The objective function is defined over the entire dataset, but we typically optimize this with stochastic gradient descent (SGD) using one example at a time (or a 'minibatch' of batch_size examples, where typically 16 <= batch_size <= 512). So let's look at one step of this process.

Let's imagine at training step $$t$$ we observe the first training case above, where the goal is to predict the from quick. We select num_noise number of noisy (contrastive) examples by drawing from some noise distribution, typically the unigram distribution, $$P(w)$$. For simplicity let's say num_noise=1 and we select sheep as a noisy example. Next we compute the loss for this pair of observed and noisy examples, i.e. the objective at time step $$t$$ becomes

$$J^{(t)}_\text{NEG} = \log Q_\theta(D=1 | \text{the, quick}) + \log(Q_\theta(D=0 | \text{sheep, quick}))$$

The goal is to make an update to the embedding parameters $$\theta$$ to improve (in this case, maximize) this objective function. We do this by deriving the gradient of the loss with respect to the embedding parameters $$\theta$$, i.e. $$\frac{\partial}{\partial \theta} J_\text{NEG}$$ (luckily TensorFlow provides easy helper functions for doing this!). We then perform an update to the embeddings by taking a small step in the direction of the gradient. When this process is repeated over the entire training set, this has the effect of 'moving' the embedding vectors around for each word until the model is successful at discriminating real words from noise words.

We can visualize the learned vectors by projecting them down to 2 dimensions using for instance something like the t-SNE dimensionality reduction technique. When we inspect these visualizations it becomes apparent that the vectors capture some general, and in fact quite useful, semantic information about words and their relationships to one another. It was very interesting when we first discovered that certain directions in the induced vector space specialize towards certain semantic relationships, e.g. male-female, verb tense and even country-capital relationships between words, as illustrated in the figure below (see also for example Mikolov et al., 2013).

This explains why these vectors are also useful as features for many canonical NLP prediction tasks, such as part-of-speech tagging or named entity recognition (see for example the original work by Collobert et al., 2011 (pdf), or follow-up work by Turian et al., 2010).

But for now, let's just use them to draw pretty pictures!

## Building the Graph

This is all about embeddings, so let's define our embedding matrix. This is just a big random matrix to start. We'll initialize the values to be uniform in the unit cube.

embeddings = tf.Variable(
tf.random_uniform([vocabulary_size, embedding_size], -1.0, 1.0))

The noise-contrastive estimation loss is defined in terms of a logistic regression model. For this, we need to define the weights and biases for each word in the vocabulary (also called the output weights as opposed to the input embeddings). So let's define that.

nce_weights = tf.Variable(
tf.truncated_normal([vocabulary_size, embedding_size],
stddev=1.0 / math.sqrt(embedding_size)))
nce_biases = tf.Variable(tf.zeros([vocabulary_size]))

Now that we have the parameters in place, we can define our skip-gram model graph. For simplicity, let's suppose we've already integerized our text corpus with a vocabulary so that each word is represented as an integer (see tensorflow/examples/tutorials/word2vec/word2vec_basic.py for the details). The skip-gram model takes two inputs. One is a batch full of integers representing the source context words, the other is for the target words. Let's create placeholder nodes for these inputs, so that we can feed in data later.

# Placeholders for inputs
train_inputs = tf.placeholder(tf.int32, shape=[batch_size])
train_labels = tf.placeholder(tf.int32, shape=[batch_size, 1])

Now what we need to do is look up the vector for each of the source words in the batch. TensorFlow has handy helpers that make this easy.

embed = tf.nn.embedding_lookup(embeddings, train_inputs)

Ok, now that we have the embeddings for each word, we'd like to try to predict the target word using the noise-contrastive training objective.

# Compute the NCE loss, using a sample of the negative labels each time.
loss = tf.reduce_mean(
tf.nn.nce_loss(weights=nce_weights,
biases=nce_biases,
labels=train_labels,
inputs=embed,
num_sampled=num_sampled,
num_classes=vocabulary_size))

Now that we have a loss node, we need to add the nodes required to compute gradients and update the parameters, etc. For this we will use stochastic gradient descent, and TensorFlow has handy helpers to make this easy as well.

# We use the SGD optimizer.

## Training the Model

Training the model is then as simple as using a feed_dict to push data into the placeholders and calling tf.Session.run with this new data in a loop.

for inputs, labels in generate_batch(...):
feed_dict = {train_inputs: inputs, train_labels: labels}
_, cur_loss = session.run([optimizer, loss], feed_dict=feed_dict)

See the full example code in tensorflow/examples/tutorials/word2vec/word2vec_basic.py.

## Visualizing the Learned Embeddings

After training has finished we can visualize the learned embeddings using t-SNE.

Et voila! As expected, words that are similar end up clustering nearby each other. For a more heavyweight implementation of word2vec that showcases more of the advanced features of TensorFlow, see the implementation in models/tutorials/embedding/word2vec.py.

## Evaluating Embeddings: Analogical Reasoning

Embeddings are useful for a wide variety of prediction tasks in NLP. Short of training a full-blown part-of-speech model or named-entity model, one simple way to evaluate embeddings is to directly use them to predict syntactic and semantic relationships like king is to queen as father is to ?. This is called analogical reasoning and the task was introduced by Mikolov and colleagues . Download the dataset for this task from download.tensorflow.org.

To see how we do this evaluation, have a look at the build_eval_graph() and eval() functions in models/tutorials/embedding/word2vec.py.

The choice of hyperparameters can strongly influence the accuracy on this task. To achieve state-of-the-art performance on this task requires training over a very large dataset, carefully tuning the hyperparameters and making use of tricks like subsampling the data, which is out of the scope of this tutorial.

## Optimizing the Implementation

Our vanilla implementation showcases the flexibility of TensorFlow. For example, changing the training objective is as simple as swapping out the call to tf.nn.nce_loss() for an off-the-shelf alternative such as tf.nn.sampled_softmax_loss(). If you have a new idea for a loss function, you can manually write an expression for the new objective in TensorFlow and let the optimizer compute its derivatives. This flexibility is invaluable in the exploratory phase of machine learning model development, where we are trying out several different ideas and iterating quickly.

Once you have a model structure you're satisfied with, it may be worth optimizing your implementation to run more efficiently (and cover more data in less time). For example, the naive code we used in this tutorial would suffer compromised speed because we use Python for reading and feeding data items -- each of which require very little work on the TensorFlow back-end. If you find your model is seriously bottlenecked on input data, you may want to implement a custom data reader for your problem, as described in New Data Formats. For the case of Skip-Gram modeling, we've actually already done this for you as an example in models/tutorials/embedding/word2vec.py.

If your model is no longer I/O bound but you want still more performance, you can take things further by writing your own TensorFlow Ops, as described in Adding a New Op. Again we've provided an example of this for the Skip-Gram case models/tutorials/embedding/word2vec_optimized.py. Feel free to benchmark these against each other to measure performance improvements at each stage.

## Conclusion

In this tutorial we covered the word2vec model, a computationally efficient model for learning word embeddings. We motivated why embeddings are useful, discussed efficient training techniques and showed how to implement all of this in TensorFlow. Overall, we hope that this has show-cased how TensorFlow affords you the flexibility you need for early experimentation, and the control you later need for bespoke optimized implementation.


text:
Dalia S.

The admission fee at an amusement park is $1.50 for children and$ 4.00 for adults. On a certain day, 223 people entered the park, and the admission fees collected totaled \$622 . How many children and how many adults were admitted?
Number of children=?

By:

Tutor
New to Wyzant

An experienced,patient & hardworking tutor

Dalia S.

how did you solve for the equations to get x and y?
if you re arrange the equation you get 1.5x=622-4y, how do you get x from here? do you simply substitute the variable with 223?
Report

09/10/14

SURENDRA K.

Hello Dalai,

Multiply the first equation by 4 giving you ----
4x+4y= 892
1.5x+4y=622
Subtract the two equations

2.5x=270
x=270/2.5=108
Substitute back to get y

Hope that helps you
Report

09/10/14

## Still looking for help? Get the right answer, fast.

Get a free answer to a quick problem.
Most questions answered within 4 hours.

#### OR

Choose an expert and meet online. No packages or subscriptions, pay only for the time you need.

format: plain


text:
# I'm supposed to load some packages BEFORE the document class?

So I was reading Fixing LaTeX2e and it has several examples of the form

\RequirePackage{fixltx2e}
\documentclass...

What? I thought documentclass always went right at the top. Are there other situations I should require a package before documentclass?

• I don't think this will be a very "big list"... :-D Not that I'm an expert, but I can't think of any others besides nag and hyphsubst. – Paul Gessler Dec 29 '14 at 23:03
• @PaulGessler Isn't fix-cm one? – cfr Dec 29 '14 at 23:34
• @cfr could be; I've never used it. I only listed the ones I knew of. – Paul Gessler Dec 29 '14 at 23:52
• @PaulGessler I had no idea what to tag it, sorry about that. I expected someone to edit it to the right one. Best Practices perhaps? – Canageek Jan 1 '15 at 4:27

Generally the use for package loading is with \usepackage after \documentclass but fixltx2e is essentially a list of unrelated fixes that should really be in the format and so potentially could include commands that a document class file wants to use, so ought to be fixed before that are used. Actually given the current set of fixes in fixltx2e and the typical commands used in a class file, using it at the start of the preamble with \usepackage is usually safe enough.

As noted in comments fix-cm (which is actually generated from the same source file) is similar in that it changes the font settings for the standard OT1 cm fonts and so ought to be loaded before the document class if that class does any typesetting (including trial typesetting in box registers to measure things) so not just visible typeset output.

• May I misunderstood that Joseph Wright advised to use \RequirePackage{fixltx2e} before \documentclass... ? – jotagah Dec 30 '14 at 1:01
• @jotagah no as I say here it is best to use fixltx2e before \documentclass. – David Carlisle Dec 30 '14 at 1:44
• @DavidCarlisle Shouldn't any sane document class load it before anything else anyway? – jubobs Dec 30 '14 at 1:57
• @Jubobs no that removes choice from the end user. the (current) design is that the fixes are not put in the format so that by default existing documents are not changed. For the same reason none of the standard classes load it by default. – David Carlisle Dec 30 '14 at 2:10

Only a too long comment about:

I thought \documentclass always went right at the top.

Not necessarily, beside \RequirePackage{}, that could be needed to load the package before the macros contained in the .cls file, many (not all) commands works above \documentclass. For example (It is a proof of concept, not a recommendation!) this is a functional code:

\def\mymacro{Some macro make this text. }
\newcommand\thistoo{This too. }
\title{My title}
\author{Me}
\date{\today}

\documentclass{article}
\begin{document}
\maketitle
Hello, Word. \mymacro
\thistoo
\end{document}

In fact, you can have a working main.tex file without a \documentclass, as this can be loaded from a subdocument:

\input{pre-preamble}
\begin{document}
\TEST
\lipsum[1-10]
\end{document}

Where pre-preamble.tex could be some like:

% pre-preamble.tex
\def\TEST{A test. }
\documentclass[twocolumn]{article}
\usepackage{lipsum}


text:
Econometrics

You are currently browsing the archive for the Econometrics category.

A non-technical guide to the dueling Seattle minimum wage studies

Over the past couple of weeks two studies of the effects of Seattle’s recent minimum wage hikes have been released: one from some researchers at the University of Washington, the other from researchers at Berkeley.  The results have widely been interpreted, including by the authors of one of the studies, as wildly inconsistent.  This post presents a non-technical guide to the problems associated with attempting to estimate the effects of the minimum wage, the statistical methods used in both papers, and how to interpret the results (spoiler: the results are actually not in conflict).

A simple exposition of local average treatment effects

This post presents a simple explanation of the concept of “local average treatment effects” in the context of instrumental variables estimation.  I borrow shamelessly from the somewhat more advanced presentation in Imbens and Wooldridge’s lecture notes, which is a good place to look for further reading.

The basic idea underlying LATE is to acknowledge that different people (or different units more generally) generally have different causal effects for any given “treatment,” broadly defined.  It is common to talk about “the” causal effect of, say, education on earnings, or interest rates on growth, or pharmaceuticals on health, but if different people respond differently to education or to medical treatments and different countries respond differently to macroeconomic interventions, it’s not clear what we mean by “the” causal effect.  We can still talk coherently about distributions of causal effects, though, and we may be interested in estimated various averages of those causal effects.  Local average treatment effects (LATEs) are one such average.

For concreteness, let’s suppose the government decides to lend a hand to empirical researchers by implementing the following goofy policy: a randomly selected group of high school kids are randomized to get an offer of either $0 or$5,000 to acquire a college degree.  We wish to use this natural experiment to estimate “the” effect of getting a college degree on, say, wages.  We collect data on all these folks comprised of: a dummy variable $Z_i$ which equals one if person $i$ was offered \$5,000 and zero if they were offered zero, a dummy variable $D_i$ which indicates the student actually received a college degree, and wages, $y_i$.

Inequality, poverty, and health: Comments on the Globe’s coverage

Canada’s Globe and Mail newspaper has been running a series of articles on income inequality. This post presents some comments on the coverage of income inequality and health in Wealth begets health: Why universal medical care only goes so far by André Picard.

I make three points. First, that the article is much more consistent with the literature if one reads “poverty” every time the article uses the word “inequality.” Second, that the fact that income and health are correlated across people or across regions does not tell us that income causes health. And finally, that the research does suggest that decreasing poverty will increase health, but that we should not expect substantial reductions in health care expenditures as a result. I close with some notes on policy implications.

U.S. voters more likely to support marijuana legalization than non-voters

Much has been made of a recent Gallup poll showing a majority of Americans now support marijuana legalization. But if a majority support legalization, why do politicians seem so reluctant to support drug law reform?

One explanation for this puzzle is that Americans who vote are less likely to support legalization than those who do not vote. Voters tend to be older, and possibly have other characteristics which are associated with opposition to drug policy reform.

GMM and its application outside finance

The 2013 Nobel prize in economics was won by Fama, Shiller, and some other dude, according to most media accounts. Fama and Shiller were pretty easy to explain: one of them is at Chicago and is associated with a theory called “efficient markets,” so he’s the free market guy. Shiller criticized the Chicago guy, so we know where to put him on the political spectrum. But this third guy, Hansen, well, he’s at Chicago, but he does some sort of theoretical econometrics, so if we’re the Guardian we’ll just assume he’s “ultra-conservative” and then ignore him, or if we’re anyone else we’ll skip to just ignoring him (even the Economist gives up, complaining they can’t explain his work without “writing all sorts of equations in our newspaper.”) This post attempts to provide a relatively gentle, albeit with all sorts of equations, introduction to part of the third guys’s research, focusing on applications in causal modeling in microeconomics rather than the examples from finance or macroeconomics.

Tags: , ,

Remarks on Chen and Pearl on causality in econometrics textbooks

Bryant Chen and Judea Pearl have published a interesting piece in which they critically examine the discussions (or lack thereof) of causal interpretations of regression models in six econometrics textbooks. In this post, I provide brief assessments of the discussion of causality in nine additional econometrics texts of various levels and vintages, and close with a few remarks about causality in textbooks from the perspective of someone who does, and teaches, applied econometrics. Like Chen and Pearl, I find some of these textbooks provide weak or misleading discussion of causality, but I also find one very good and one excellent discussion in relatively recent texts. I argue that the discussion of causality in econometrics textbooks appears to be improving over time, and that the oral tradition in economics is not well-reflected in econometrics textbooks.

The Chen and Pearl paper has been around for a while in working paper form and recently came out in the Real World Economics Review, also available here from the authors with much clearer typesetting.

The additional textbooks I discuss below are: Amemiya (1985), Kmenta (1986), Davidson and MacKinnon (1993), Gujarati (1999), Hayashi (2000), Wooldridge (2002), Davidson and MacKinnon (2004), Deilman (2005), and Cameron and Trivedi (2005).

« Older entries


text:
# Faster R-CNN Explained for Object Detection Tasks

2 years ago   •   16 min read

This article gives a review of the Faster R-CNN model developed by a group of researchers at Microsoft. Faster R-CNN is a deep convolutional network used for object detection, that appears to the user as a single, end-to-end, unified network. The network can accurately and quickly predict the locations of different objects. In order to truly understand Faster R-CNN, we must also do a quick overview of the networks that it evolved from, namely R-CNN and Fast R-CNN.

The article starts by quickly reviewing the region-based CNN (R-CNN), which is the first trial towards building an object detection model that extracts features using a pre-trained CNN. Next, Fast R-CNN is quickly reviewed, which is faster than the R-CNN but unfortunately neglects how the region proposals are generated. This is later solved by the Faster R-CNN, which builds a region-proposal network that can generate region proposals that are fed to the detection model (Fast R-CNN) to inspect for objects.

• Overview of the Object Detection Pipeline
• R-CNN Review
• Fast R-CNN Overview
• Faster R-CNN
• Main Contributions
• Region Proposal Network (RPN)
• Anchors
• Objectness Score
• Feature Sharing between RPN and Fast R-CNN
• Training Faster R-CNN
• Alternating Training
• Approximate Joint Training
• Non-Approximate Joint Training
• Drawbacks
• Conclusion
• References

Let's get started.

Bring this project to life

## Overview of the Object Detection Pipeline

Traditional object detection techniques follow the 3 major steps given in the figure below. The first step involves generating several region proposals. These region proposals are candidates that might have objects within them. The number of these regions is usually in the several thousands, e.g. 2,000 or more. Examples of some algorithms that generate region proposals are Selective Search and EdgeBoxes.

From each region proposal, a fixed-length feature vector is extracted using various image descriptors like the histogram of oriented gradients (HOG), for example. This feature vector is critical to the success of the object detectors. The vector should adequately describe an object even if it varies due to some transformation, like scale or translation.

The feature vector is then used to assign each region proposal to either the background class or to one of the object classes. As the number of classes increases, the complexity of building a model that can differentiate between all of these objects increases. One of the popular models used for classifying the region proposals is the support vector machine (SVM).

This quick overview is enough to understand the basics of the region-based convolutional neural network (R-CNN).

## R-CNN Quick Overview

In 2014, a group of researchers at UC Berkely developed a deep convolutional network called R-CNN (short for region-based convolutional neural network) $[1]$ that can detect 80 different types of objects in images.

Compared to the generic pipeline of the object detection techniques shown in the previous figure, the main contribution of R-CNN $[1]$ is just extracting the features based on a convolutional neural network (CNN). Other than this, everything is similar to the generic object detection pipeline. The next figure shows the working of the R-CNN model.

The R-CNN consists of 3 main modules:

1. The first module generates 2,000 region proposals using the Selective Search algorithm.
2. After being resized to a fixed pre-defined size, the second module extracts a feature vector of length 4,096 from each region proposal.
3. The third module uses a pre-trained SVM algorithm to classify the region proposal to either the background or one of the object classes.

The R-CNN model has some drawbacks:

• It is a multi-stage model, where each stage is an independent component. Thus, it cannot be trained end-to-end.
• It caches the extracted features from the pre-trained CNN on the disk to later train the SVMs. This requires hundreds of gigabytes of storage.
• R-CNN depends on the Selective Search algorithm for generating region proposals, which takes a lot of time. Moreover, this algorithm cannot be customized to the detection problem.
• Each region proposal is fed independently to the CNN for feature extraction. This makes it impossible to run R-CNN in real-time.

As an extension of the R-CNN model, the Fast R-CNN model is proposed $[2]$ to overcome some limitations. A quick overview of Fast R-CNN is given in the next section.

## Fast R-CNN Quick Overview

Fast R-CNN $[2]$ is an object detector that was developed solely by Ross Girshick, a Facebook AI researcher and a former Microsoft Researcher. Fast R-CNN overcomes several issues in R-CNN. As its name suggests, one advantage of the Fast R-CNN over R-CNN is its speed.

Here is a summary of the main contributions in $[2]$:

1. Proposed a new layer called ROI Pooling that extracts equal-length feature vectors from all proposals (i.e. ROIs) in the same image.
2. Compared to R-CNN, which has multiple stages (region proposal generation, feature extraction, and classification using SVM), Faster R-CNN builds a network that has only a single stage.
3. Faster R-CNN shares computations (i.e. convolutional layer calculations) across all proposals (i.e. ROIs) rather than doing the calculations for each proposal independently. This is done by using the new ROI Pooling layer, which makes Fast R-CNN faster than R-CNN.
4. Fast R-CNN does not cache the extracted features and thus does not need so much disk storage compared to R-CNN, which needs hundreds of gigabytes.
5. Fast R-CNN is more accurate than R-CNN.

The general architecture of Fast R-CNN is shown below. The model consists of a single-stage, compared to the 3 stages in R-CNN. It just accepts an image as an input and returns the class probabilities and bounding boxes of the detected objects.

The feature map from the last convolutional layer is fed to an ROI Pooling layer. The reason is to extract a fixed-length feature vector from each region proposal. The GIF below shows how the ROI Pooling layer works.

Simply put, the ROI Pooling layer works by splitting each region proposal into a grid of cells. The max pooling operation is applied to each cell in the grid to return a single value. All values from all cells represent the feature vector. If the grid size is 2×2, then the feature vector length is 4.

The extracted feature vector using the ROI Pooling is then passed to some FC layers. The output of the last FC layer is split into 2 branches:

1. Softmax layer to predict the class scores
2. FC layer to predict the bounding boxes of the detected objects

In R-CNN, each region proposal is fed to the model independently from the other region proposals. This means that if a single region takes S seconds to be processed, then N regions take S*N seconds. The Fast R-CNN is faster than the R-CNN as it shares computations across multiple proposals.

R-CNN $[1]$ samples a single ROI from each image, compared to Fast R-CNN $[2]$ that samples multiple ROIs from the same image. For example, R-CNN selects a batch of 128 regions from 128 different images. Thus, the total processing time is 128*S seconds.

For Faster R-CNN, the batch of 128 regions may be selected from just 2 images (64 regions per image). When regions are sampled from the same image, then their convolutional layer computations are shared, and this reduces the time. So, the processing time drops to 2*S. However, sampling multiple regions from the same image degrades the performance as all regions are correlated.

Despite the advantages of the Fast R-CNN model, there is a critical drawback as it depends on the time-consuming Selective Search algorithm to generate region proposals. The Selective Search method cannot be customized on a specific object detection task. Thus, it may not be accurate enough to detect all target objects in the dataset.

In the next section, Faster R-CNN $[3]$ is introduced. Faster R-CNN builds a network for generating region proposals.

## Faster R-CNN

Faster R-CNN $[3]$ is an extension of Fast R-CNN $[2]$. As its name suggests, Faster R-CNN is faster than Fast R-CNN thanks to the region proposal network (RPN).

### Main Contributions

The main contributions in this paper are $[3]$:

1. Proposing region proposal network (RPN) which is a fully convolutional network that generates proposals with various scales and aspect ratios. The RPN implements the terminology of neural network with attention to tell the object detection (Fast R-CNN) where to look.
2. Rather than using pyramids of images (i.e. multiple instances of the image but at different scales) or pyramids of filters (i.e. multiple filters with different sizes), this paper introduced the concept of anchor boxes. An anchor box is a reference box of a specific scale and aspect ratio. With multiple reference anchor boxes, then multiple scales and aspect ratios exist for the single region. This can be thought of as a pyramid of reference anchor boxes. Each region is then mapped to each reference anchor box, and thus detecting objects at different scales and aspect ratios.
3. The convolutional computations are shared across the RPN and the Fast R-CNN. This reduces the computational time.

The architecture of Faster R-CNN is shown in the next figure. It consists of 2 modules:

1. RPN: For generating region proposals.
2. Fast R-CNN: For detecting objects in the proposed regions.

The RPN module is responsible for generating region proposals. It applies the concept of attention in neural networks, so it guides the Fast R-CNN detection module to where to look for objects in the image.

Note how the convolutional layers (e.g. computations) are shared across both the RPN and the Fast R-CNN modules.

The Faster R-CNN works as follows:

• The RPN generates region proposals.
• For all region proposals in the image, a fixed-length feature vector is extracted from each region using the ROI Pooling layer $[2]$.
• The extracted feature vectors are then classified using the Fast R-CNN.
• The class scores of the detected objects in addition to their bounding-boxes are returned.

### Region Proposal Network (RPN)

The R-CNN and Fast R-CNN models depend on the Selective Search algorithm for generating region proposals. Each proposal is fed to a pre-trained CNN for classification. This paper $[3]$ proposed a network called region proposal network (RPN) that can produce the region proposals. This has some advantages:

1. The region proposals are now generated using a network that could be trained and customized according to the detection task.
2. Because the proposals are generated using a network, this can be trained end-to-end to be customized on the detection task. Thus, it produces better region proposals compared to generic methods like Selective Search and EdgeBoxes.
3. The RPN processes the image using the same convolutional layers used in the Fast R-CNN detection network. Thus, the RPN does not take extra time to produce the proposals compared to the algorithms like Selective Search.
4. Due to sharing the same convolutional layers, the RPN and the Fast R-CNN can be merged/unified into a single network. Thus, training is done only once.

The RPN works on the output feature map returned from the last convolutional layer shared with the Fast R-CNN. This is shown in the next figure. Based on a rectangular window of size nxn, a sliding window passes through the feature map. For each window, several candidate region proposals are generated. These proposals are not the final proposals as they will be filtered based on their "objectness score" (explained below).

### Anchor

According to the next figure, the feature map of the last shared convolution layer is passed through a rectangular sliding window of size nxn, where n=3 for the VGG-16 net. For each window, K region proposals are generated. Each proposal is parametrized according to a reference box which is called an anchor box. The 2 parameters of the anchor boxes are:

1. Scale
2. Aspect Ratio

Generally, there are 3 scales and 3 aspect ratios and thus there is a total of K=9 anchor boxes. But K may be different than 9. In other words, K regions are produced from each region proposal, where each of the K regions varies in either the scale or the aspect ratio.  Some of the anchor variations are shown in the next figure.

Using reference anchors (i.e. anchor boxes), a single image at a single scale is used while being able to offer scale-invariant object detectors, as the anchors exist at different scales. This avoids using multiple images or filters. The multi-scale anchors are key to share features across the RPN and the Fast R-CNN detection network.

For each nxn region proposal, a feature vector (of length 256 for ZF net and 512 for the VGG-16 net) is extracted. This vector is then fed to 2 sibling fully-connected layers:

1. The first FC layer is named cls, and represents a binary classifier that generates the objectness score for each region proposal (i.e. whether the region contains an object, or is part of the background).
2. The second FC layer is named reg which returns a 4-D vector defining the bounding box of the region.

The first FC layer (i.e. binary classifier) has 2 outputs. The first is for classifying the region as a background, and the second is for classifying the region as an object. The next section discusses how the objectness score is assigned to each anchor and how it is used to produce the classification label.

### Objectness Score

The cls layer outputs a vector of 2 elements for each region proposal. If the first element is 1 and the second element is 0, then the region proposal is classified as background. If the second element is 1 and the first element is 0, then the region represents an object.

For training the RPN, each anchor is given a positive or negative objectness score based on the Intersection-over-Union (IoU).

The IoU is the ratio between the area of intersection between the anchor box and the ground-truth box to the area of union of the 2 boxes. The IoU ranges from 0.0 to 1.0. When there is no intersection, the IoU is 0.0. As the 2 boxes get closer to each other, the IoU increases until reaching 1.0 (when the 2 boxes are 100% identical).

The next 4 conditions use the IoU to determine whether a positive or a negative objectness score is assigned to an anchor:

1. An anchor that has an IoU overlap higher than 0.7 with any ground-truth box is given a positive objectness label.
2. If there is no anchor with an IoU overlap higher than 0.7, then assign a positive label to the anchor(s) with the highest IoU overlap with a ground-truth box.
3. A negative objectness score is assigned to a non-positive anchor when the IoU overlap for all ground-truth boxes is less than 0.3. A negative objectness score means the anchor is classified as background.
4. Anchors that are neither positive nor negative do not contribute to the training objective.

I was confused by the second and third conditions when I was first reading the paper. So, let's give more clarification.

Assume there are 3 region proposals associated with 3 anchors, where their IoU scores with 3 ground-truth boxes are listed below. Because there is an anchor with an IoU score of 0.9, which is higher than 0.7, it is assigned a positive objectness score with that ground-truth box, and negative to all other boxes.

0.9, 0.55, 0.1

Here is the result of classifying the anchors:

positive, negative, negative

The second condition means that when no anchor has an IoU overlap score higher than 0.7, then search for the anchor with the highest IoU and assign it a positive objectness score. It is expected that the maximum IoU score is less than or equal to 0.7, but the confusing part is that the paper did not mention a minimum value of the IoU score.

It is expected that the minimum value should be 0.5. So, if an anchor box has an IoU score that is greater than 0.5 but less than or equal to 0.7, then assign it a positive objectness score.

Assume that the IoU scores of an anchor are listed below. Because the highest IoU score is the second one with a value of 0.55, it falls under the second condition. Thus, it is assigned a positive objectness score.

0.2, 0.55, 0.1

Here is the result of classifying the anchors:

negative, positive, negative

The third condition specifies that when the IoU scores of an anchor with all ground-truth boxes are less than 0.3, then this anchor is assigned a negative objectness score. For the next IoU scores, the anchor is given a negative score for the 3 cases because all of the IoU scores are less than 0.3.

0.2, 0.25, 0.1

Here is the result of classifying the anchors:

negative, negative, negative

According to the fourth condition, when an anchor has an IoU score that is greater than or equal to 0.3 but less than or equal to 0.5, it is neither classified as positive nor negative. This anchor is not used in training the classifier.

For the following IoU scores the anchor is not assigned any label, as all of the scores are between 0.3 and 0.5 (inclusive).

0.4, 0.43, 0.45

The next equation summarizes the 4 conditions.

Note that the first condition (0.7 < IoU) is usually sufficient to label an anchor as positive (i.e. contains an object) but the authors preferred to mention the second condition (0.5 < IoU <= 0.7) for the rare cases where there is no region with an IoU of 0.7.

### Feature Sharing between RPN and Fast R-CNN

The 2 modules in the Fast R-CNN architecture, namely the RPN and Fast R-CNN, are independent networks. Each of them can be trained separately. In contrast, for Faster R-CNN it is possible to build a unified network in which the RPN and Fast R-CNN are trained at once.

The core idea is that both the RPN and Fast R-CNN share the same convolutional layers. These layers exist only once but are used in the 2 networks. It is possible to call it layer sharing or feature sharing. Remember that the anchors $[3]$ are what makes it possible to share the features/layers between the 2 modules in the Faster R-CNN.

### Training Faster R-CNN

The Faster R-CNN paper $[3]$ mentioned 3 different ways to train both the RPN and Fast R-CNN while sharing the convolutional layers:

1. Alternating Training
2. Approximate Joint Training
3. Non-Approximate Joint Training

#### Alternating Training

The first method is called alternating training, in which the RPN is first trained to generate region proposals. The weights of the shared convolutional layers are initialized based on a pre-trained model on ImageNet. The other weights of the RPN are initialized randomly.

After the RPN produces the boxes of the region proposals, the weights of both the RPN and the shared convolutional layers are tuned.

The generated proposals by the RPN are used to train the Fast R-CNN module. In this case, the weights of the shared convolutional layers are initialized with the tuned weights by the RPN. The other Fast R-CNN weights are initialized randomly. While the Fast R-CNN is trained, both the weights of Fast R-CNN and the shared layers are tuned. The tuned weights in the shared layers are again used to train the RPN, and the process repeats.

According to $[3]$, alternating training is the preferred way to train the 2 modules and is applied in all experiments.

#### Approximate Joint Training

The second method is called approximate joint training, in which both the RPN and Fast R-CNN are regarded as a single network, not 2 separate modules. In this case, the region proposals are produced by the RPN.

Without updating the weights of neither the RPN nor the shared layers, the proposals are fed directly to the Fast R-CNN which detects the objects' locations. Only after the Fast R-CNN produces its outputs are the weights in the Faster R-CNN tuned.

Because the weights of the RPN and the shared layers are not updated after the region proposals are generated, the weights' gradients with respect to the region proposals are ignored. This reduces the accuracy of this method compared to the first method (even if the results are close). On the other hand, the training time is reduced by about 25-50%.

#### Non-Approximate Joint Training

In the approximate joint training method, an RoI Warping layer is used to allow the weights' gradients with respect to the proposed bounding boxes to be calculated.

### Drawbacks

One drawback of Faster R-CNN is that the RPN is trained where all anchors in the mini-batch, of size 256, are extracted from a single image. Because all samples from a single image may be correlated (i.e. their features are similar), the network may take a lot of time until reaching convergence.

As an extension to Faster R-CNN $[3]$, the Mask R-CNN model includes another branch that returns a mask for each detected object.

## Conclusion

This article reviewed a deep convolutional neural network used for object detection called Faster R-CNN, which accurately detects and classifies objects in images.

The article started by reviewing the generic steps of any object detection model. It then quickly reviewed how the R-CNN and Fast R-CNN models work in order to have an idea of what challenges Faster R-CNN is conquering.

Faster R-CNN is a single-stage model that is trained end-to-end. It uses a novel region proposal network (RPN) for generating region proposals, which save time compared to traditional algorithms like Selective Search. It uses the ROI Pooling layer to extract a fixed-length feature vector from each region proposal.

One drawback we saw of Faster R-CNN is that for the RPN, all anchors in the mini-batch are extracted from a single image. Because all samples from a single image may be correlated (i.e. their features are similar), the network may take a lot of time until reaching convergence.

That being said, Faster R-CNN is a state of the art object detection model. Mask R-CNN has since been built off of Faster R-CNN to return object masks for each detected object.


text:
### Mode Switching Algorithms

After running an experiment using sequences of modes (for contacting sampled households), I've been thinking about how to decide when to switch modes. In our experiment, we had a specified time when the switch would occur (after 5 weeks of the first mode, switch to the second mode).

It seems like better "switching" rules should be possible. Ideally, we would want to identify some best mode as quickly as possible. The amount of time it might take to determine this would vary across sampled cases.

The hard part is that we generally have very little feedback. We don't get a lot of information back from failed attempts. For example, a letter doesn't generally generate much feedback other than an interview occurred, it didn't occur, or the letter was returned. It might be that interviewer-administered modes are more promising for this kind of tailoring, since they do generally obtain more feedback.

### "Responsive Design" and "Adaptive Design"

My dissertation was entitled "Adaptive Survey Design to Reduce Nonresponse Bias." I had been working for several years on "responsive designs" before that. As I was preparing my dissertation, I really saw "adaptive" design as a subset of responsive design.

Since then, I've seen both terms used in different places. As both terms are relatively new, there is likely to be confusion about the meanings. I thought I might offer my understanding of the terms, for what it's worth.

The term "responsive design" was developed by Groves and Heeringa (2006). They coined the term, so I think their definition is the one that should be used. They defined "responsive design" in the following way:

1. Preidentify a set of design features that affect cost and error tradeoffs.
2. Identify indicators for these costs and errors. Monitor these during data collection.
3. Alter the design features based on pre-identified decision rules based on the indi…

### Tailoring vs. Targeting

One of the chapters in a recent book on surveying hard-to-reach populations looks at "targeting and tailoring" survey designs. The chapter references this paper on the use of the terms among those who design health communication. I thought the article was an interesting one. They start by saying that "one way to classify message strategies like tailoring is by the level of specificity with which characteristics of the target audience are reflected in the the communication."

That made sense. There is likely a continuum of specificity ranging from complete non-differentiation across units to nearly individualized. But then the authors break that continuum and try to define a "fundamental" difference between tailoring and targeting. They say targeting is for some subgroup while tailoring is to the characteristics of the individual. That sounds good, but at least for surveys, I'm not sure the distinction holds.

In survey design, what would constitute tail…

### An Experimental Adaptive Contact Strategy

I'm running an experiment on contact methods in a telephone survey. I'm going to present the results of the experiment at the FCSM conference in November. Here's the basic idea.

Multi-level models are fit daily with the household being a grouping factor. The models provide household-specific estimates of the probability of contact for each of four call windows. The predictor variables in this model are the geographic context variables available for an RDD sample.

Let $\mathbf{X_{ij}}$ denote a $k_j \times 1$ vector of demographic variables for the $i^{th}$ person and $j^{th}$ call. The data records are calls. There may be zero, one, or multiple calls to household in each window. The outcome variable is an indicator for whether contact was achieved on the call. This contact indicator is denoted $R_{ijl}$ for the $i^{th}$ person on the $j^{th}$ call to the $l^{th}$ window. Then for each of the four call windows denoted $l$, a separate model is fit where each household is assum…


text:
# Fast calculations using fast-Fourier convolution

Consider an array $$X$$ with shape $$H \times W$$. Let $$Y$$ be the other array of the same shape and $$Z$$ is an array of shape $$h \times w$$.

We want to construct an array $$R$$ of shape $$(H-h + 1, W-w+ 1)$$ by the following rule:

$$\displaystyle R[k, l] = \sum_{i, j} (X[i,j] - Y[i,j])^2 +$$ $$\sum_{i=0}^{h-1}\sum_{j=0}^{w-1}[(X[k + i, l + j] - Z[i, j])^2 - (X[k + i, l + j] - Y[k + i, l + j])^2]$$

So it's better to represent it via the image: we erase some subarray of size $$h \times w$$ in $$X - Y$$, change it by $$X_{h, w} - Z$$ and compute the sum of squares.

Using dynamic programming we can solve it pretty fast, but it's still a time-consuming process. I think that it's possible to calculate such an array using fast Fourier convolutions. But we need to determine convolution arrays to do that.

Any hints?


text:
# Differences

This shows you the differences between the selected revision and the current version of the page.

whitepapers:sequences:1dintegration 2014/09/04 13:40 whitepapers:sequences:1dintegration 2014/09/09 10:31 current
Line 3: Line 3:
===== Integration in One Dimension ===== ===== Integration in One Dimension =====
-Students entering into upper-division physics courses are typically very comfortable with integration as taught in mathematics courses. In physics, there is additional language which accompanies integration as well as greater flexibility in variables. +Students entering into upper-division physics courses are typically familiar and comfortable with integration as taught in mathematics courses. In physics, there is additional language and interpretation which accompany integration. By reintroducing integration early in upper-division courses, many common student difficulties which arise in electricity and magnetism and other physics courses can be addressed.
+
+Students may be encountering new approaches to integration which are not addressed in math courses. For example, [[courses:activities:vfact:vfpederivmach|Internal Energy of the "Derivative Machine"]] may be the first time students have experimentally measured an integral and can be used to encourage fluency between multiple representations of integration such as numerical, graphical, and algebraic representations. Additionally, students typically integrate with respect to the variable of the function such as $x$ in $f(x)=\int_{x_0}^{x_f}(mx+b)dx$. However, oftentimes in physics the resulting function is of a different variable such as $g(m)=\int_{x_0}^{x_f}(mx+b)dx$ which students may not have encountered in previous calculus and introductory physics courses.
+
+This sequence can serve as a quick reintroduction to integration and can likely be completed entirely in less than one hour.
==== Activities ==== ==== Activities ====
-  * **[[courses:activities:vfact:vfpederivmach|Internal Energy of the "Derivative Machine"]]** //(Estimated time: )//:+  * **[[courses:activities:vfact:vfpederivmach|Internal Energy of the "Derivative Machine"]]** //(Estimated time: )//: This small group activity serves as an introduction to experimentally measuring an integral by determining the internal energy, $U$, of a nonlinear system at several locations. Students must choose a point of zero internal energy and then add up, incrementally, the force at each small change in distance by numerical integration.
-  * **1D Rectangular Integration** //(Estimated time: )//: Introduction to language physicists use in integration including chopping, adding/accumulation, boundaries, functions. +  * **1D Rectangular Integration** //(Estimated time: )//: This lecture introduces students to the language which physicists use with regard to integration. This includes the notion of integration as "chopping and adding" and "accumulation" as well as explanations of boundaries and functions as used in physics.
-  * How what you're integrating isn't necessarily the parameter you want to vary after integrating. --Lecture or Homework primarily+  * **Functions** //(Estimated time: )//: This lecture or homework problem addresses how the parameter which the integration is occurring over isn't necessarily the parameter which is varied following the integration. In mathematics, the resulting function from an integral has variables which are the same over which the integration occurred. For example, if integrating over $dx$, the function following the integration will be $f(x)$. However, in physics, often another parameter is varied following the integration, so if integrating over $dx$, the function may be $g(m)$. By addressing this through a homework problem or a lecture, students will have the knowledge to recognize when this occurs in more complex physical problems.

##### Views

New Users

Curriculum

Pedagogy

Institutional Change

Publications


text:
# The product of two consecutive natural numbers is

Let $$Y = n(n+1)$$ for some positive integer $$n$$. Which of the following statements is true?

×


text:
Forbidding Kuratowski Graphs as Immersions

Forbidding Kuratowski Graphs as Immersions

Archontia C. Giannopoulou  Department of Mathematics, National and Kapodistrian University of Athens, Panepistimioupolis, GR-15784, Athens, Greece. Emails: {arcgian,sedthilk}@math.uoa.grSupported by a grant of the Special Account for Research Grants of the National and Kapodistrian University of Athens (project code: 70/4/10311).    Marcin Kamiński Département d’Informatique, Université Libre de Bruxelles, Brussels, Belgium. Email: Marcin.Kaminski@ulb.ac.be    Dimitrios M. Thilikos Co-financed by the European Union (European Social Fund - ESF) and Greek national funds through the Operational Program “Education and Lifelong Learning” of the National Strategic Reference Framework (NSRF) - Research Funding Program: “Thales. Investing in knowledge society through the European Social Fund.”
Abstract

The immersion relation is a partial ordering relation on graphs that is weaker than the topological minor relation in the sense that if a graph contains a graph as a topological minor, then it also contains it as an immersion but not vice versa. Kuratowski graphs, namely and , give a precise characterization of planar graphs when excluded as topological minors. In this note we give a structural characterization of the graphs that exclude Kuratowski graphs as immersions. We prove that they can be constructed by applying consecutive -edge-sums, for , starting from graphs that are planar sub-cubic or of branch-width at most 10.

Keywords: graph immersions, Kuratowski graphs, tree-width, branch-width.

1 Introduction

A famous graph theoretic result is the theorem of Kuratowski which states that a graph is planar if and only if it does not contain and (also known as the Kuratowski graphs) as a topological minor, that is, if and cannot be obtained from the graph by applying vertex and edge removals and edge dissolutions. It is well-known that the topological minor relation defines a (partial) ordering of the class of graphs.

In a similar way, the immersion and the minor orderings can be defined in graphs if instead of vertex dissolutions we ask for edge lifts and edge contractions respectively. (For detailed definitions see Section 2.) Notice here that the topological minor ordering is stronger than the minor and the immersion orderings in the sense that if a graph contains a graph as a topological minor then it also contains it as an immersion and as a minor but the inverse direction does not always hold.

In the celebrated Graph Minors theory, developed by Robertson and Seymour, it was proven that both the immersion and minor orderings are well-quasi-ordered, that is, there are no infinite sets of mutually non-comparable graphs [16, 19] according to these orderings. This result has as a consequence the complete characterization of the graph classes that are closed under taking immersions or minors in terms of forbidden graphs, where a graph class is closed under taking immersions (respectively minors) if for any graph that belongs to the graph class all of its immersions (respectively minors) also belong to the graph class. For example, by an extension of the Kuratowski theorem (also known as Wagner’s theorem), it is also known that a graph is planar if and only if it does not contain and as a minor.

Thus, a question that naturally arises is about the characterization of the structure of a graph that excludes some fixed graph as an immersion or as a minor. While this subject has been extensively studied for the minor ordering (see [6, 20, 18, 15, 9, 2, 3, 13, 17, 22]), the immersion ordering only recently attracted the attention of the research community [10, 4, 8, 1, 12]. In [4], DeVos et al. proved that for every positive integer , every simple graph of minimum degree at least contains the complete graph on vertices as a (strong) immersion and in [7] Ferrara et al., given a graph , provide a lower bound on the minimum degree of any graph in order to ensure that is contained in as an immersion. More recently, in [21], Seymour and Wollan proved a structure theorem for graphs excluding complete graphs as immersions.

In terms of graph colorings, Abu-Khzam and Langston in [1] provide evidence supporting the analog of Hadwiger’s Conjecture according to the immersion ordering, that is, the conjecture stating that if the chromatic number of a graph is at least then contains the complete graph on vertices as an immersion and prove it for . This conjecture is proven for and by Lescure and Meyniel in [14] and by DeVos et al. in [5] independently. The most recent result on colorings is an approximation of the list coloring number on graphs excluding the complete graph as immersion [12].

Finally, in terms of algorithms, in [10], Grohe et al. gave a cubic time algorithm that decides whether a fixed graph is contained in an input graph as immersion and in [8] it was proved that the minimal graphs not belonging to a graph class closed under immersions can be computed when an upper bound on their tree-width and a description of the graph class in Monadic Second Order Logic are given.

In this note we characterize the structure of the graphs that do not contain and as immersions. As these graphs already exclude Kuratowski graphs as topological minors they are already planar. Additionally, we show that they have a more special structure: they can be constructed by repetitively, joining together simpler graphs, starting from either graphs of small decomposability or by planar graphs with maximum degree 3. In particular, we prove that a graph that does not contain neither nor as immersions can be constructed by applying consecutive -edge-sums, for , to graphs that are planar sub-cubic or of branch-width at most 10.

2 Definitions

For every integer , we let . All graphs we consider are finite, undirected, and loopless but may have multiple edges. Given a graph we denote by and its vertex and edge set respectively. Given a set (resp. ), we denote by (resp. ) the graph obtained from if we remove the edges in (resp. the vertices in along with their incident edges). We denote by the set of the connected components of . Given a vertex , we also use the notation . The neighborhood of a vertex , denoted by , is the set of edges in that are adjacent to . We denote by the set of the edges of that are incident to . The degree of a vertex , denoted by , is the number of edges that are incident to it, i.e., . Notice that, as we are dealing with multigraphs, . The minimum degree of a graph , denoted by , is the minimum of the degrees of the vertices of , that is, . A graph is called sub-cubic if all its vertices have degree at most 3. We also denote by the complete graph on vertices and by the complete bipartite graph with vertices in its one part and in the other. Let be a path and . We denote by the sub-path of with end-vertices and . Given two paths and who share a common endpoint , we say that they are well-arranged if their common vertices appear in the same order in both paths.

We say that a graph is a subgraph of a graph if can be obtained from , after removing edges or vertices. An edge cut in a graph is a non-empty set of edges that belong to the same connected component of and such that has more connected components than . If has one more connected component than then we say that is a minimal edge cut. Let be an edge cut of a graph and let be the connected component of containing the edges of . We say that is an internal edge cut if it is minimal and both connected components of contain at least 2 vertices. An edge cut is also called -edge-cut if it has cardinality .

In this paper we mostly deal with lanai graphs, that is graphs that are embedded in the sphere . We call such a graph, along with its embedding, -embeddable graph. Let , be two disjoint cycles in a -embeddable graph . Let also be the open disk of that does not contain points of , . The annulus between and is the set and we denote it by . Notice that is a closed set. If is a collection of cycles of a -embeddible graph . We say that is nested if for every , .

Contractions and minors.

The contraction of an edge from is the removal from of all edges incident to or and the insertion of a new vertex that is made adjacent to all the vertices of such that edges corresponding to the vertices in increase their multiplicity, that is, if there was a vertex , edges joining and and, edges joining and then in the resulting graph there will be edges joining with . Finally, remove any loops resulting from this operation. Given two graphs and , we say that is a contraction of , denoted by , if can be obtained from after a (possibly empty) series of edge contractions. Moreover, is a minor of if is a contraction of some subgraph of .

Topological minors.

A subdivision of a graph is any graph obtained after replacing some of its edges by paths between the same endpoints. A graph is a topological minor of (denoted by ) if contains as a subgraph some subdivision of .

Immersions.

The lift of two edges and to an edge is the operation of removing and from and then adding the edge in the resulting graph. We say that a graph can be (weakly) immersed in a graph (or is an immersion of ), denoted by , if can be obtained from a subgraph of after a (possibly empty) sequence of edge lifts. Equivalently, we say that is an immersion of if there is an injective mapping such that, for every edge of , there is a path from to in and for any two distinct edges of the corresponding paths in are edge-disjoint, that is, they do not share common edges. Additionally, if these paths are internally disjoint from , then we say that is strongly immersed in (or is a strong immersion of ). The injective mapping together with the edge-disjoint paths is called a model of in defined by .

Edge sums.

Let and be graphs, let be vertices of and respectively, and consider a bijection where . We define the -edge sum of and on and as the graph obtained if we take the disjoint union of and , identify with , and then, for each , lift and to a new edge and remove the vertex . (See Figures 1 and 2)

Let be a graph, let be a minimal -edge cut in , and let be the connected component of that contains . Let also and be the two connected components of . We denote by the graph obtained from after contracting all edges of to a single vertex . We say that the graph consisting of the disjoint union of the graphs in is the -split of and we denote it by . Notice that if is connected and is a minimal -edge cut in , then is the result of the -edge sum of the two connected components and of on the vertices and . From Menger’s Theorem we obtain the following.

Observation 2.1.

Let be a positive integer. If is a connected graph that does not contain an internal -edge cut, for some and are distinct vertices such that then there exist edge-disjoint paths from to .

Lemma 2.2.

If is a -immersion free connected graph and is a minimal internal -edge cut in , for then both connected components of are -immersion free.

Proof.

For contradiction assume that is a -immersion free connected graph and one of the connected components of , say , contains or as an immersion, where is a minimal internal -edge cut in , . Assume that is immersed in and let be a model of in . Let also be the newely introduced vertex of . Notice that if and is not an internal vertex of any of the edge-disjoint paths between the vertices in , then is a model of in . As , is a model of in , a contradiction to the hypothesis. Thus, we may assume that either or is an internal vertex in at least one of the edge-disjoint paths between the vertives in . Note that, as neither nor contain vertices of degree , or .

We first exclude the case where , that is, only appears as an internal vertex on the edge-disjoint paths. Observe that, as , belongs to exactly one path in the model defined by . Let and be the neighbors of in . Recall that, by the definition of an internal -split, there are vertices and in such that . Furthermore, as is connected, there exists a -path in . Therefore, be substituting the subpath by the path defined by the union of the edges and the path in we obtain a model of in defined by , a contradiction to the hypothesis.

Thus, the only possible case is that . As and , defines a model of in . Let and be the neighbors of in . We claim that there is a vertex in and edge-disjoint paths from to in , thus proving that there exists a model of in as well, a contradiction to the hypothesis. By the definition of an internal -split, there are vertices and in such that , . Recall that is connected. Therefore, if for every vertex , , contains a path whose endpoints, say and belong to and internally contains the vertex in , say . Then it is easy to verify that satisfies the conditions of the claim. Assume then that there is a vertex of degree at least 3. Let be the graph obtained from after removing all vertices in and adding a new vertex that we make it adjacent to the vertices in . As does not contain an internal -edge cut, , does not contain an internal -edge cut, . Therefore, from Observation 2.1 and the fact that , we obtain that there exist 3 edge-disjoint paths from to in and thus in . This completes the proof of the claim and the lemma follows. ∎

Let and . A -cylinder, denoted by , is the cartesian product of a cycle on vertices and a path on vertices. (See, for example, Figure 3) A -railed annulus in a graph is a pair such that is a collection of nested cycles that are all met by a collection of paths (called rails) in a way that the intersection of a rail and a path is always a (possibly trivial, that is, consisting of only one vertex) path. (See, for example, Figure 3) Notice that given a graph embedded in the sphere and a -cylinder (-railed annulus respectively) of , then any two cycles of the -cylinder (-railed annulus respectively) define an annulus between them.

Branch decompositions.

A branch decomposition of a graph is a pair , where is a ternary tree and is a bijection of the edges of to the leaves of , denoted by . Given a branch decomposition , we define as follows.

Given an edge let and be the trees in Then . The width of a branch decomposition is and the branch-width of a graph , denoted by , is the minimum width over all branch decompositions of . In the case where the width of the branch decomposition is defined to be 0. The following has been proven in [11].

Theorem 2.3.

If is a planar graph and are integers with and then either contains the -cylinder as a minor or has branch-width at most .

We now prove the following.

Lemma 2.4.

If is a planar graph of branch-width at least 11, then contains a (4,4)-railed annulus.

Proof.

Let be a planar graph of branch-width at least 11. Then by Theorem 2.3, contains -cylinder as a minor. By the definition of the minor relation, contains a -railed annulus. ∎

Confluent paths

Let be a graph embedded in some surface and let . We define a disk around as any open disk with the property that each point in is either or belongs to the edges incident to . Let and be two edge-disjoint paths in . We say that and are confluent if for every , that is not an endpoint of or , and for every disk around , one of the connected components of the set does not contain any point of . We also say that a collection of paths is confluent if the paths in it are pairwise confluent.

Moreover, given two edge-disjoint paths and in we say that a vertex that is not an endpoint of or is an overlapping vertex of and if there exists a around such that both connected components of contain points of . For a family of paths , a vertex of a path is called an overlapping vertex of if there exists a path such that is an overlapping vertex of and .

3 Preliminary results on the confluency of paths

Lemma 3.1.

Let be a graph and such that there exist edge-disjoint paths and from to and respectively. If the paths and are not well-arranged then there exist edge-disjoint paths and from to and respectively such that .

Proof.

Let , where is the order that the vertices in appear in and, is the order that they appear in . As the paths are not well-arranged there exists such that . Without loss of generality assume that is the smallest such integer. Without loss of generality assume also that . We define

 P′1 = P1[v,uλ−1]∪P2[uλ−1,uiλ]∪P1[uiλ,v1] P′2 = P2[v,uλ−1]∪P1[uλ−1,uλ]∪P2[uλ,v2].

and observe that and satisfy the desired properties. (For an example, see Figure 4).

Before proceeding to the statement and proof of the next proposition we need the following definition. Given a collection of paths in a graph , we define the function such that is the number of pairs of paths for which is an overlapping vertex. Let

 g(P)=∑x∈⋃P∈PV(P)fP(x).

Notice that for every and thus . Observe also that if and only if is a confluent collection of paths.

Lemma 3.1 allows us to prove the main result of this section. We state the result for general surfaces as the proof for this more general setting does not have any essential difference than the case where is the sphere .

Proposition 3.2.

Let be a positive integer. If is a graph embedded in a surface , and is a collection of edge-disjoint paths from to in , then contains a confluent collection of well-arranged edge-disjoint paths from to where and such that .

Proof.

Let be the spanning subgraph of induced by the edges of the paths in and let be a minimal spanning subgraph of that contains a collection of edge-disjoint paths from to . Let also be the collection of edge-disjoint paths from to in for which is minimum. It is enough to prove that .

For a contradiction, we assume that and we prove that there exists a collection of edge-disjoint paths from to in such that . As , then there exists a path, say , that contains an overlapping vertex . Let be the endpoint of which is different from . Without loss of generality we may assume that is the overlapping vertex of that is closer to in . Then there is a -path such that is an overlapping vertex of and . Let , and for every . As Lemma 3.1 and the edge-minimality of imply that the paths and are well-arranged, we obtain that is a path from to , . Let be . It is easy to verify that is a collection of edge-disjoint paths from to . We will now prove that .

First notice that if , then . Thus, it is enough to prove that . Observe that if and is an overlapping vertex of and then is also an overlapping vertex of and . Furthermore, while is an overlapping vertex in the case where , it is not an overlapping vertex of and . It remains to examine the case where . In other words, we examine the case where one of the paths and , say , is or , and . Let be a disk around and be the two distinct disks contained in the interior of after removing . We distinguish the following cases.

Case 1. is neither an overlapping vertex of and , nor of and (see Figure 5). Then it is easy to see that the same holds for the pairs of paths and and, and . Indeed, notice that for every , intersects exactly one of and . Furthermore, as is an overlapping vertex of and , both paths intersect the same disk. From the observation that , we obtain that is neither an overlapping vertex of and nor of and .

Case 2. is an overlapping vertex of and but not of and , (see Figure 6). Notice that exactly one of the following holds.

• intersects exactly one of the disks or , say . Then intersects and intersects . Therefore, it is easy to see that, is not an overlapping vertex of and anymore but becomes an overlapping vertex of and .

• intersects exactly one of the disks or , say . Then intersects and intersects . Therefore, it is easy to see that remains an overlapping vertex of and and does not become an overlapping vertex of and .

Case 3. is an overlapping vertex of both and and, and (see Figure 7). As above, exactly one of the following holds.

• intersects exactly one of the disks or , say . Then intersects . It follows that is an overlapping vertex of both and and, and

• intersects exactly one of the disks or , say . Then intersects . It follows that is neither an overlapping vertex of and nor of and .

From the above cases we obtain that and therefore , contradicting the choice of . This completes the proof of the Proposition. ∎

4 A decomposition theorem

We prove the following decomposition theorem for -immersion free graphs.

Theorem 4.1.

If is a graph not containing or as an immersion, then can be constructed by applying consecutive -edge sums, for , to graphs that either are sub-cubic or have branch-width at most 10.

Proof.

Observe first that a -immersion-free graph is also -topological-minor-free, therefore, from Kuratowski’s theorem, is planar. Applying Lemma 2.2, we may assume that is a -immersion-free graph without any internal -edge cut, . It is now enough to prove that is either planar sub-cubic or has branch-width at most 10. For a contradiction, we assume that and that contains some vertex of degree . Our aim is to prove that contains as an immersion. First, let be the graph obtained from after subdividing all of its edges once. Notice that contains as an immersion if and only if contains as an immersion. Hence, from now on, we want to find in as an immersion.

From Lemma 2.4 , and thus , contains a -railed annulus as a subgraph. Observe then that also contains as a subgraph a -railed annulus such that the vertex of degree does not belong in the annulus between its cycles (Figure 8 depicts the case where is inside the annulus between the second and the third cycle). We denote by and the nested cycles and by and the rails of the above -railed annulus. Let be the annulus between and . Without loss of generality we may assume that separates from and that is edge-minimal, that is, there is no other annulus such that and .

Let now be the connected components of .

Claim 1.

For every and every , .

Proof of Claim 1.

Indeed, assume the contrary. Then there is a cycle such that and define an annulus with and , a contradiction to the edge-minimality of the annulus . ∎

For every , we denote by and the unique neighbor of in and respectively (whenever they exist). We call the connected components that have both a neighbor in and a neighbor in substantial. Let . That is, is the set of graphs induced by the substantial connected components and their neighbors in the cycles and . Note that every edge of has been subdivided in and thus every edge for which and corresponds to a substantial connected component in .

We now claim that there exist four confluent edge-disjoint paths and from to in . This follows from the facts that does not contain an internal -edge cut, contains at least vertices, combined with Observation 2.1. Moreover, from Proposition 3.2, we may assume that and are confluent.

Let be the subpath of , where is the vertex in whose distance from in is minimum, . Recall that all edges of have been subdivided in . This implies that there exist four (possibly not disjoint) graphs in , say and such that , . We distinguish two cases.

Case 1. The graphs and are vertex-disjoint.
This implies that the endpoints of and are disjoint. Let be the graph induced by the cycles and the paths and let and be confluent edge-disjoint paths from to , , and in such that

1. is minimum, that is, the number of the edges of the paths that is outside of is minimum, and

2. subject to i, is minimum.

Let also be the graph induced by , , , , and . From now on we work towards showing that contains as an immersion. For every we call a connected component of non-trivial if it contains at least an edge.

Claim 2.

For every , contains at most one non-trivial connected component and is an endpoint of .

Proof of Claim 2.

First, notice that any path from to in contains and thus, . Observe now that is a subpath of whose internal vertices do not belong to , thus if belongs to a non-trivial connected component of , then is an endpoint of . We will now prove that any non-trivial connected component of contains . Assume in contrary that there exists a non-trivial connected component of that does not contain . Let be the endpoint of for which is minimum. Let also be the vertex in such that is minimum. Let be the subpath of with endpoints such that is a cycle with . We further assume that the interior of is the open disk that does not contain any vertices of . We will prove that for every path , . As this trivially holds for we will assume that . Observe that, for every , as for every connected component of it holds that . Furthermore, observe that is a separator in . This implies that does not belong to the interior of . Thus, if there is a vertex such that , there is a vertex , a contradiction to the confluency of the paths. We may then replace by , a contradiction to i. ∎

We denote by the endpoint of that is different from if


text:
# \autorows style table with custom columns and dynamic row spanning

I'm trying to create a table environment similar to memoir's \autorow, (in that I can supply contents as a list, along with the number of columns) but with more complex requirements. I need to be able to use a custom column (similar to what I might do with \newcolumntype) so that I can add automatic custom numbering for each cell. I need to be able to specify an explicit width (let's call it x) for the table, and have items added to the table such that if adding at item to a row would cause that row's total length to exceed x, that item is instead added as a as a column-spanning cell in the next row. An item so long that it exceeds x even if placed in the first column should be allowed to overflow, or wrap within that cell/row. Rows should be left aligned. Here's a mock up illustrating the desired results:

I achieved the auto-numbering using the solution to this previous question.

I realize the solution to this is probably very complex; just knowing what approach to use would be a big help, since I expect an explicit solution probably well exceeds what would be reasonable to ask of someone else volunteering their time to write. Of course, if there's some simple solution I've overlooked, fantastic.

• Did you think of taking a look at the tasks package. Another possibility would perhaps be the shortlst package. See examples of its use with some patching I did on this thread. – Bernard Apr 3 '15 at 0:41
• I wouldn't recommend basing any solution on tabu. Avoid it like the plague. – cfr Apr 3 '15 at 1:06

## 1 Answer

As told in comments, avoid tabu for this and use tasks package. Here is an example.

\documentclass{article}
\usepackage[more]{tasks}

% new list-like environment
% \NewTasks[options]{name}[separator](default number of columns)
\NewTasks[style=enumerate,counter-format=tsk[1]),label-width=2ex]{myenumerate}[\item](3)

\usepackage{kantlipsum}% insert text fragments
\begin{document}

\kant[1]

\begin{myenumerate}
\item Added normally
\item two
\item three
\item four
\item*(2) This will occupy two columns as it is bigger
\item! This will occupy three columns as it is very much bigger and bigger This will occupy three columns as it is very much bigger and bigger
\item*(2) Again more columns text Again more columns text Again more columns text
\item eight
\item nine
\end{myenumerate}

\kant[2]

\begin{tasks}[style=enumerate,counter-format=tsk[1]),item-indent=0em,label-width=2ex](3)
\task Added normally
\task two
\task three
\task four
\task*(2) This will occupy two columns as it is bigger
\task! This will occupy three columns as it is very much bigger and bigger This will occupy three columns as it is very much bigger and bigger
\task*(2) Again more columns text Again more columns text Again more columns text
\task eight
\task nine
\end{tasks}

\end{document}

• This is awesome, but is there any way to make the column spanning totally automatic? I'd still have to "pre-check" which items will need to span and add the necessary arguments to each task manually. – Texman Apr 3 '15 at 5:30
• @Texman LaTeX can't know how many columns the text can span by itself. – user11232 Apr 3 '15 at 5:41
• @Kumar This is as good as it gets then. Thanks! – Texman Apr 3 '15 at 5:52


text:
Barbara and Dianne go target shooting. Suppose that each of Barbara’s shots hits a wooden duck target with probability p1

# Barbara and Dianne go target shooting. Suppose that each of Barbara’s shots hits a wooden duck target with probability p1

J
240 points

Barbara and Dianne go target shooting. Suppose that each of Barbara’s shots hits a wooden duck target with probability p1, while each shot of Dianne’s hits it with probability p2. Suppose that they shoot simultaneously at the same target. If the wooden duck is knocked over (indicating that it was hit), what is the probability that

(a) both shots hit the duck?
(b) Barbara’s shot hit the duck?
What independence assumptions have you made?

Barbara and
jeffp

8.7k points

Let,

H be the event that the duck is hit

B be the event that Barbra hit the duck

D be the event that Dianne hit the duck

both shots hit the duck

we want to find

$$P(BD|H)=\frac{P(H|BD)P(BD)}{P(H)}=\frac{P(BD)}{P(H)}$$

the probability P(H) is the probability that at least one person hits the target ie,

$$P(H)=P(BD^c)+P(B^cD)+P(BD)$$

$$=p_1(1-p_2)+(1-p_1)p_2+p_1p_2$$

therefore

$$P(BD|H)=\frac{P(BD)}{P(H)}$$

$$=\frac{p_1p_2}{p_1(1-p_2)+(1-p_1)p_2+p_1p_2}$$

$$=\frac{p_1p_2}{p_1+p_2-p_1p_2}$$

Barbara's shot hit the duck

This happens under two scenarios, Barbara alone hits the duck, or both Barbara and Diane hit the duck. The second scenario was already calculated in part (a). So we have that,

$$P(B|H)=P(BD^c|H)+P(BD|H)$$

we already know $P(BD|H)$, but need to find

$$P(BD^c|H)=\frac{p_1(1-p_2)}{p_1+p_2-p_1p_2}$$

and therefore

$$P(B|H)=P(BD^c|H)+P(BD|H)$$

$$=\frac{p_1p_2}{p_1+p_2-p_1p_2}+\frac{p_1(1-p_2)}{p_1+p_2-p_1p_2}$$

$$=\frac{p_1}{p_1+p_2-p_1p_2}$$

Surround your text in *italics* or **bold**, to write a math equation use, for example, $x^2+2x+1=0$ or $$\beta^2-1=0$$

Use LaTeX to type formulas and markdown to format text. See example.


text:
Lesson Objectives
• Demonstrate the ability to solve a radical equation
• Learn how to solve a radical inequality

## How to Solve a Radical Inequality

Solving radical inequalities can be quite tedious depending on the type of problem that you encounter. The method that is described below is not necessarily the fastest, especially if you have an easy problem. The benefit of this method is that it will work for any scenario.

• Find any domain restrictions
• Replace the inequality symbol with an equality symbol
• Solve the resulting equation
• The solution gives us the critical values or boundaries
• Split the number line up into intervals based on the critical values and domain restrictions
• Test numbers in each interval to obtain your solution set
Example 1: Solve each inequality $$-5\sqrt{2x+12}+ 2 > -18$$ Step 1) Find any domain restrictions:
Set your radicand (2x + 12) as greater than or equal to zero and solve the inequality: $$2x + 12 ≥ 0$$ $$x ≥ -6$$ Step 2) Replace the inequality symbol with an equality symbol and solve the resulting equation: $$-5\sqrt{2x + 12}+ 2=-18$$ $$x=2$$ This solution gives us a boundary. We can use it to split the number line up into three intervals. A region that is less than -6, where no values will work due to the domain restriction. A region that is between -6 and 2, and a region that is greater than 2. For the numbers -6 and 2, we will consider them separately. Step 3) Test numbers in each interval to obtain your solution set:
We know that nothing in interval A (values less than -6) works due to the domain restriction.
For interval B we can test 0: $$-5\sqrt{2(0) + 12}+ 2 > -18$$ $$-5\sqrt{12}+ 2 > -18$$ $$-10\sqrt{3}> -20$$ Since this statement is true, we can conclude that any value from -6 up to but not including 2 will work. 2 is excluded here because we have a non-strict inequality. Testing any value in region C, where values are larger than 2 will result in a false statement. We will report our answer as: $$-6 ≤ x < 2$$ $$[-6, 2)$$

#### Skills Check:

Example #1

Solve each inequality. $$\sqrt{2x - 4}+ 9 ≤ 11$$

A
$$x ≥ 4$$
B
$$2 < x ≤ 4$$
C
$$2 ≤ x ≤ 4$$
D
$$x ≤ 2$$
E
$$x ≤ 2 \hspace{.1em}\text{or}\hspace{.1em}x ≥ 4$$

Example #2

Solve each inequality. $$\sqrt{x + 9}> \sqrt{3 - 2x}$$

A
$$-\frac{3}{2}≤ x < 2$$
B
$$x > \frac{3}{2}$$
C
$$x ≤ -2$$
D
$$-2 < x ≤ \frac{3}{2}$$
E
$$-2 ≤ x < \frac{3}{2}$$

Example #3

Solve each inequality. $$5 + \sqrt{3x - 8}≥ 7$$

A
$$x ≤ \frac{8}{3}$$
B
$$x ≥ \frac{8}{3}$$
C
$$-2 ≤ x ≤ 4$$
D
$$x ≥ 4$$
E
$$x ≤ 4$$


text:
# Are perfect complexes the same as compact objects in D(R) for noncommutative rings?

The Stacks Project proves Thomason's insight that

compact objects of the derived category $$\simeq$$ bounded complexes of finitely generated projective modules

in Section 15.78, but the running conventions of the Stacks Project assume that all rings are commutative.

I believe the insight is originally from the Thomason-Trobaugh paper in the Grothendieck Festschrift, but this paper also works exclusively with commutative rings (and schemes).

What is the situation for non-commutative rings?

First, you can notice that if you have a set of compact objects $$F$$ in a triangulated category $$S$$ such that there's no proper triangulated, coproduct-closed subcategory containing $$F$$, the minimal thick subcategory containing $$F$$ is exactly the subcategory of compact objects. (It's more or less a consequence of the triangulated Brown representability theorem.)
Then if $$T$$ is $$D(R{\operatorname{-mod}})$$, $$R$$ is a compact object in it (since homs from it are zeroth cohomology); the smallest thick subcategory containing $$R$$ is the subcategory of perfect complexes, so by the observation above it is the subcategory of compact objects.