text:
Author
Last Commit
Feb. 20, 2019
Created
Jun. 29, 2017

# Neural Machine Translation (seq2seq) Tutorial

Authors: Thang Luong, Eugene Brevdo, Rui Zhao (Google Research Blogpost, Github)

This version of the tutorial requires TensorFlow Nightly. For using the stable TensorFlow versions, please consider other branches such as tf-1.4.

If make use of this codebase for your research, please cite this.

# Introduction

Sequence-to-sequence (seq2seq) models (Sutskever et al., 2014, Cho et al., 2014) have enjoyed great success in a variety of tasks such as machine translation, speech recognition, and text summarization. This tutorial gives readers a full understanding of seq2seq models and shows how to build a competitive seq2seq model from scratch. We focus on the task of Neural Machine Translation (NMT) which was the very first testbed for seq2seq models with wild success. The included code is lightweight, high-quality, production-ready, and incorporated with the latest research ideas. We achieve this goal by:

1. Using the recent decoder / attention wrapper API, TensorFlow 1.2 data iterator
2. Incorporating our strong expertise in building recurrent and seq2seq models
3. Providing tips and tricks for building the very best NMT models and replicating Google’s NMT (GNMT) system.

We believe that it is important to provide benchmarks that people can easily replicate. As a result, we have provided full experimental results and pretrained our models on the following publicly available datasets:

1. Small-scale: English-Vietnamese parallel corpus of TED talks (133K sentence pairs) provided by the IWSLT Evaluation Campaign.
2. Large-scale: German-English parallel corpus (4.5M sentence pairs) provided by the WMT Evaluation Campaign.

We first build up some basic knowledge about seq2seq models for NMT, explaining how to build and train a vanilla NMT model. The second part will go into details of building a competitive NMT model with attention mechanism. We then discuss tips and tricks to build the best possible NMT models (both in speed and translation quality) such as TensorFlow best practices (batching, bucketing), bidirectional RNNs, beam search, as well as scaling up to multiple GPUs using GNMT attention.

# Basic

## Background on Neural Machine Translation

Back in the old days, traditional phrase-based translation systems performed their task by breaking up source sentences into multiple chunks and then translated them phrase-by-phrase. This led to disfluency in the translation outputs and was not quite like how we, humans, translate. We read the entire source sentence, understand its meaning, and then produce a translation. Neural Machine Translation (NMT) mimics that!

Figure 1. Encoder-decoder architecture – example of a general approach for NMT. An encoder converts a source sentence into a "meaning" vector which is passed through a decoder to produce a translation.

Specifically, an NMT system first reads the source sentence using an encoder to build a "thought" vector, a sequence of numbers that represents the sentence meaning; a decoder, then, processes the sentence vector to emit a translation, as illustrated in Figure 1. This is often referred to as the encoder-decoder architecture. In this manner, NMT addresses the local translation problem in the traditional phrase-based approach: it can capture long-range dependencies in languages, e.g., gender agreements; syntax structures; etc., and produce much more fluent translations as demonstrated by Google Neural Machine Translation systems.

NMT models vary in terms of their exact architectures. A natural choice for sequential data is the recurrent neural network (RNN), used by most NMT models. Usually an RNN is used for both the encoder and decoder. The RNN models, however, differ in terms of: (a) directionality – unidirectional or bidirectional; (b) depth – single- or multi-layer; and (c) type – often either a vanilla RNN, a Long Short-term Memory (LSTM), or a gated recurrent unit (GRU). Interested readers can find more information about RNNs and LSTM on this blog post.

In this tutorial, we consider as examples a deep multi-layer RNN which is unidirectional and uses LSTM as a recurrent unit. We show an example of such a model in Figure 2. In this example, we build a model to translate a source sentence "I am a student" into a target sentence "Je suis étudiant". At a high level, the NMT model consists of two recurrent neural networks: the encoder RNN simply consumes the input source words without making any prediction; the decoder, on the other hand, processes the target sentence while predicting the next words.

Figure 2. Neural machine translation – example of a deep recurrent architecture proposed by for translating a source sentence "I am a student" into a target sentence "Je suis étudiant". Here, "<s>" marks the start of the decoding process while "</s>" tells the decoder to stop.

## Installing the Tutorial

To install this tutorial, you need to have TensorFlow installed on your system. This tutorial requires TensorFlow Nightly. To install TensorFlow, follow the installation instructions here.

Once TensorFlow is installed, you can download the source code of this tutorial by running:

git clone https://github.com/tensorflow/nmt/

## Training – How to build our first NMT system

Let's first dive into the heart of building an NMT model with concrete code snippets through which we will explain Figure 2 in more detail. We defer data preparation and the full code to later. This part refers to file model.py.

At the bottom layer, the encoder and decoder RNNs receive as input the following: first, the source sentence, then a boundary marker "<s>" which indicates the transition from the encoding to the decoding mode, and the target sentence. For training, we will feed the system with the following tensors, which are in time-major format and contain word indices:

• encoder_inputs [max_encoder_time, batch_size]: source input words.
• decoder_inputs [max_decoder_time, batch_size]: target input words.
• decoder_outputs [max_decoder_time, batch_size]: target output words, these are decoder_inputs shifted to the left by one time step with an end-of-sentence tag appended on the right.

Here for efficiency, we train with multiple sentences (batch_size) at once. Testing is slightly different, so we will discuss it later.

### Embedding

Given the categorical nature of words, the model must first look up the source and target embeddings to retrieve the corresponding word representations. For this embedding layer to work, a vocabulary is first chosen for each language. Usually, a vocabulary size V is selected, and only the most frequent V words are treated as unique. All other words are converted to an "unknown" token and all get the same embedding. The embedding weights, one set per language, are usually learned during training.

# Embedding
embedding_encoder = variable_scope.get_variable(
"embedding_encoder", [src_vocab_size, embedding_size], ...)
# Look up embedding:
#   encoder_inputs: [max_time, batch_size]
#   encoder_emb_inp: [max_time, batch_size, embedding_size]
encoder_emb_inp = embedding_ops.embedding_lookup(
embedding_encoder, encoder_inputs)

Similarly, we can build embedding_decoder and decoder_emb_inp. Note that one can choose to initialize embedding weights with pretrained word representations such as word2vec or Glove vectors. In general, given a large amount of training data we can learn these embeddings from scratch.

### Encoder

Once retrieved, the word embeddings are then fed as input into the main network, which consists of two multi-layer RNNs – an encoder for the source language and a decoder for the target language. These two RNNs, in principle, can share the same weights; however, in practice, we often use two different RNN parameters (such models do a better job when fitting large training datasets). The encoder RNN uses zero vectors as its starting states and is built as follows:

# Build RNN cell
encoder_cell = tf.nn.rnn_cell.BasicLSTMCell(num_units)

# Run Dynamic RNN
#   encoder_outputs: [max_time, batch_size, num_units]
#   encoder_state: [batch_size, num_units]
encoder_outputs, encoder_state = tf.nn.dynamic_rnn(
encoder_cell, encoder_emb_inp,
sequence_length=source_sequence_length, time_major=True)

Note that sentences have different lengths to avoid wasting computation, we tell dynamic_rnn the exact source sentence lengths through source_sequence_length. Since our input is time major, we set time_major=True. Here, we build only a single layer LSTM, encoder_cell. We will describe how to build multi-layer LSTMs, add dropout, and use attention in a later section.

### Decoder

The decoder also needs to have access to the source information, and one simple way to achieve that is to initialize it with the last hidden state of the encoder, encoder_state. In Figure 2, we pass the hidden state at the source word "student" to the decoder side.

# Build RNN cell
decoder_cell = tf.nn.rnn_cell.BasicLSTMCell(num_units)
# Helper
helper = tf.contrib.seq2seq.TrainingHelper(
decoder_emb_inp, decoder_lengths, time_major=True)
# Decoder
decoder = tf.contrib.seq2seq.BasicDecoder(
decoder_cell, helper, encoder_state,
output_layer=projection_layer)
# Dynamic decoding
outputs, _ = tf.contrib.seq2seq.dynamic_decode(decoder, ...)
logits = outputs.rnn_output

Here, the core part of this code is the BasicDecoder object, decoder, which receives decoder_cell (similar to encoder_cell), a helper, and the previous encoder_state as inputs. By separating out decoders and helpers, we can reuse different codebases, e.g., TrainingHelper can be substituted with GreedyEmbeddingHelper to do greedy decoding. See more in helper.py.

Lastly, we haven't mentioned projection_layer which is a dense matrix to turn the top hidden states to logit vectors of dimension V. We illustrate this process at the top of Figure 2.

projection_layer = layers_core.Dense(
tgt_vocab_size, use_bias=False)

### Loss

Given the logits above, we are now ready to compute our training loss:

crossent = tf.nn.sparse_softmax_cross_entropy_with_logits(
labels=decoder_outputs, logits=logits)
train_loss = (tf.reduce_sum(crossent * target_weights) /
batch_size)

Here, target_weights is a zero-one matrix of the same size as decoder_outputs. It masks padding positions outside of the target sequence lengths with values 0.

Important note: It's worth pointing out that we divide the loss by batch_size, so our hyperparameters are "invariant" to batch_size. Some people divide the loss by (batch_size * num_time_steps), which plays down the errors made on short sentences. More subtly, our hyperparameters (applied to the former way) can't be used for the latter way. For example, if both approaches use SGD with a learning of 1.0, the latter approach effectively uses a much smaller learning rate of 1 / num_time_steps.

We have now defined the forward pass of our NMT model. Computing the backpropagation pass is just a matter of a few lines of code:

# Calculate and clip gradients
params = tf.trainable_variables()
gradients, max_gradient_norm)

One of the important steps in training RNNs is gradient clipping. Here, we clip by the global norm. The max value, max_gradient_norm, is often set to a value like 5 or 1. The last step is selecting the optimizer. The Adam optimizer is a common choice. We also select a learning rate. The value of learning_rate can is usually in the range 0.0001 to 0.001; and can be set to decrease as training progresses.

# Optimization
zip(clipped_gradients, params))

In our own experiments, we use standard SGD (tf.train.GradientDescentOptimizer) with a decreasing learning rate schedule, which yields better performance. See the benchmarks.

## Hands-on – Let's train an NMT model

Let's train our very first NMT model, translating from Vietnamese to English! The entry point of our code is nmt.py.

We will use a small-scale parallel corpus of TED talks (133K training examples) for this exercise. All data we used here can be found at: https://nlp.stanford.edu/projects/nmt/. We will use tst2012 as our dev dataset, and tst2013 as our test dataset.

Run the following command to download the data for training NMT model:
nmt/scripts/download_iwslt15.sh /tmp/nmt_data

Run the following command to start the training:

mkdir /tmp/nmt_model
python -m nmt.nmt \
--src=vi --tgt=en \
--vocab_prefix=/tmp/nmt_data/vocab  \
--train_prefix=/tmp/nmt_data/train \
--dev_prefix=/tmp/nmt_data/tst2012  \
--test_prefix=/tmp/nmt_data/tst2013 \
--out_dir=/tmp/nmt_model \
--num_train_steps=12000 \
--steps_per_stats=100 \
--num_layers=2 \
--num_units=128 \
--dropout=0.2 \
--metrics=bleu

The above command trains a 2-layer LSTM seq2seq model with 128-dim hidden units and embeddings for 12 epochs. We use a dropout value of 0.2 (keep probability 0.8). If no error, we should see logs similar to the below with decreasing perplexity values as we train.

# First evaluation, global step 0
eval dev: perplexity 17193.66
eval test: perplexity 17193.27
# Start epoch 0, step 0, lr 1, Tue Apr 25 23:17:41 2017
sample train data:
src_reverse: </s> </s> Điều đó , dĩ nhiên , là câu chuyện trích ra từ học thuyết của Karl Marx .
ref: That , of course , was the <unk> distilled from the theories of Karl Marx . </s> </s> </s>
epoch 0 step 100 lr 1 step-time 0.89s wps 5.78K ppl 1568.62 bleu 0.00
epoch 0 step 200 lr 1 step-time 0.94s wps 5.91K ppl 524.11 bleu 0.00
epoch 0 step 300 lr 1 step-time 0.96s wps 5.80K ppl 340.05 bleu 0.00
epoch 0 step 400 lr 1 step-time 1.02s wps 6.06K ppl 277.61 bleu 0.00
epoch 0 step 500 lr 1 step-time 0.95s wps 5.89K ppl 205.85 bleu 0.00

See train.py for more details.

We can start Tensorboard to view the summary of the model during training:

tensorboard --port 22222 --logdir /tmp/nmt_model/

Training the reverse direction from English and Vietnamese can be done simply by changing:
--src=en --tgt=vi

## Inference – How to generate translations

While you're training your NMT models (and once you have trained models), you can obtain translations given previously unseen source sentences. This process is called inference. There is a clear distinction between training and inference (testing): at inference time, we only have access to the source sentence, i.e., encoder_inputs. There are many ways to perform decoding. Decoding methods include greedy, sampling, and beam-search decoding. Here, we will discuss the greedy decoding strategy.

The idea is simple and we illustrate it in Figure 3:

1. We still encode the source sentence in the same way as during training to obtain an encoder_state, and this encoder_state is used to initialize the decoder.
2. The decoding (translation) process is started as soon as the decoder receives a starting symbol "<s>" (refer as tgt_sos_id in our code);
3. For each timestep on the decoder side, we treat the RNN's output as a set of logits. We choose the most likely word, the id associated with the maximum logit value, as the emitted word (this is the "greedy" behavior). For example in Figure 3, the word "moi" has the highest translation probability in the first decoding step. We then feed this word as input to the next timestep.
4. The process continues until the end-of-sentence marker "</s>" is produced as an output symbol (refer as tgt_eos_id in our code).

Figure 3. Greedy decoding – example of how a trained NMT model produces a translation for a source sentence "Je suis étudiant" using greedy search.

Step 3 is what makes inference different from training. Instead of always feeding the correct target words as an input, inference uses words predicted by the model. Here's the code to achieve greedy decoding. It is very similar to the training decoder.

# Helper
helper = tf.contrib.seq2seq.GreedyEmbeddingHelper(
embedding_decoder,
tf.fill([batch_size], tgt_sos_id), tgt_eos_id)

# Decoder
decoder = tf.contrib.seq2seq.BasicDecoder(
decoder_cell, helper, encoder_state,
output_layer=projection_layer)
# Dynamic decoding
outputs, _ = tf.contrib.seq2seq.dynamic_decode(
decoder, maximum_iterations=maximum_iterations)
translations = outputs.sample_id

Here, we use GreedyEmbeddingHelper instead of TrainingHelper. Since we do not know the target sequence lengths in advance, we use maximum_iterations to limit the translation lengths. One heuristic is to decode up to two times the source sentence lengths.

maximum_iterations = tf.round(tf.reduce_max(source_sequence_length) * 2)

Having trained a model, we can now create an inference file and translate some sentences:

cat > /tmp/my_infer_file.vi
# (copy and paste some sentences from /tmp/nmt_data/tst2013.vi)

python -m nmt.nmt \
--out_dir=/tmp/nmt_model \
--inference_input_file=/tmp/my_infer_file.vi \
--inference_output_file=/tmp/nmt_model/output_infer

cat /tmp/nmt_model/output_infer # To view the inference as output

Note the above commands can also be run while the model is still being trained as long as there exists a training checkpoint. See inference.py for more details.

# Intermediate

Having gone through the most basic seq2seq model, let's get more advanced! To build state-of-the-art neural machine translation systems, we will need more "secret sauce": the attention mechanism, which was first introduced by Bahdanau et al., 2015, then later refined by Luong et al., 2015 and others. The key idea of the attention mechanism is to establish direct short-cut connections between the target and the source by paying "attention" to relevant source content as we translate. A nice byproduct of the attention mechanism is an easy-to-visualize alignment matrix between the source and target sentences (as shown in Figure 4).

Figure 4. Attention visualization – example of the alignments between source and target sentences. Image is taken from (Bahdanau et al., 2015).

Remember that in the vanilla seq2seq model, we pass the last source state from the encoder to the decoder when starting the decoding process. This works well for short and medium-length sentences; however, for long sentences, the single fixed-size hidden state becomes an information bottleneck. Instead of discarding all of the hidden states computed in the source RNN, the attention mechanism provides an approach that allows the decoder to peek at them (treating them as a dynamic memory of the source information). By doing so, the attention mechanism improves the translation of longer sentences. Nowadays, attention mechanisms are the defacto standard and have been successfully applied to many other tasks (including image caption generation, speech recognition, and text summarization).

## Background on the Attention Mechanism

We now describe an instance of the attention mechanism proposed in (Luong et al., 2015), which has been used in several state-of-the-art systems including open-source toolkits such as OpenNMT and in the TF seq2seq API in this tutorial. We will also provide connections to other variants of the attention mechanism.

Figure 5. Attention mechanism – example of an attention-based NMT system as described in (Luong et al., 2015) . We highlight in detail the first step of the attention computation. For clarity, we don't show the embedding and projection layers in Figure (2).

As illustrated in Figure 5, the attention computation happens at every decoder time step. It consists of the following stages:

1. The current target hidden state is compared with all source states to derive attention weights (can be visualized as in Figure 4).
2. Based on the attention weights we compute a context vector as the weighted average of the source states.
3. Combine the context vector with the current target hidden state to yield the final attention vector
4. The attention vector is fed as an input to the next time step (input feeding). The first three steps can be summarized by the equations below:

Here, the function score is used to compared the target hidden state $$h_t$$ with each of the source hidden states $$\overline{h}_s$$, and the result is normalized to produced attention weights (a distribution over source positions). There are various choices of the scoring function; popular scoring functions include the multiplicative and additive forms given in Eq. (4). Once computed, the attention vector $$a_t$$ is used to derive the softmax logit and loss. This is similar to the target hidden state at the top layer of a vanilla seq2seq model. The function f can also take other forms.

Various implementations of attention mechanisms can be found in attention_wrapper.py.

What matters in the attention mechanism?

As hinted in the above equations, there are many different attention variants. These variants depend on the form of the scoring function and the attention function, and on whether the previous state $$h_{t-1}$$ is used instead of $$h_t$$ in the scoring function as originally suggested in (Bahdanau et al., 2015). Empirically, we found that only certain choices matter. First, the basic form of attention, i.e., direct connections between target and source, needs to be present. Second, it's important to feed the attention vector to the next timestep to inform the network about past attention decisions as demonstrated in (Luong et al., 2015). Lastly, choices of the scoring function can often result in different performance. See more in the benchmark results section.

## Attention Wrapper API

In our implementation of the AttentionWrapper, we borrow some terminology from (Weston et al., 2015) in their work on memory networks. Instead of having readable & writable memory, the attention mechanism presented in this tutorial is a read-only memory. Specifically, the set of source hidden states (or their transformed versions, e.g., $$W\overline{h}_s$$ in Luong's scoring style or $$W_2\overline{h}_s$$ in Bahdanau's scoring style) is referred to as the "memory". At each time step, we use the current target hidden state as a "query" to decide on which parts of the memory to read. Usually, the query needs to be compared with keys corresponding to individual memory slots. In the above presentation of the attention mechanism, we happen to use the set of source hidden states (or their transformed versions, e.g., $$W_1h_t$$ in Bahdanau's scoring style) as "keys". One can be inspired by this memory-network terminology to derive other forms of attention!

Thanks to the attention wrapper, extending our vanilla seq2seq code with attention is trivial. This part refers to file attention_model.py

First, we need to define an attention mechanism, e.g., from (Luong et al., 2015):

# attention_states: [batch_size, max_time, num_units]
attention_states = tf.transpose(encoder_outputs, [1, 0, 2])

# Create an attention mechanism
attention_mechanism = tf.contrib.seq2seq.LuongAttention(
num_units, attention_states,
memory_sequence_length=source_sequence_length)

In the previous Encoder section, encoder_outputs is the set of all source hidden states at the top layer and has the shape of [max_time, batch_size, num_units] (since we use dynamic_rnn with time_major set to True for efficiency). For the attention mechanism, we need to make sure the "memory" passed in is batch major, so we need to transpose attention_states. We pass source_sequence_length to the attention mechanism to ensure that the attention weights are properly normalized (over non-padding positions only).

Having defined an attention mechanism, we use AttentionWrapper to wrap the decoding cell:

decoder_cell = tf.contrib.seq2seq.AttentionWrapper(
decoder_cell, attention_mechanism,
attention_layer_size=num_units)

The rest of the code is almost the same as in the Section Decoder!

## Hands-on – building an attention-based NMT model

To enable attention, we need to use one of luong, scaled_luong, bahdanau or normed_bahdanau as the value of the attention flag during training. The flag specifies which attention mechanism we are going to use. In addition, we need to create a new directory for the attention model, so we don't reuse the previously trained basic NMT model.

Run the following command to start the training:

mkdir /tmp/nmt_attention_model

python -m nmt.nmt \
--attention=scaled_luong \
--src=vi --tgt=en \
--vocab_prefix=/tmp/nmt_data/vocab  \
--train_prefix=/tmp/nmt_data/train \
--dev_prefix=/tmp/nmt_data/tst2012  \
--test_prefix=/tmp/nmt_data/tst2013 \
--out_dir=/tmp/nmt_attention_model \
--num_train_steps=12000 \
--steps_per_stats=100 \
--num_layers=2 \
--num_units=128 \
--dropout=0.2 \
--metrics=bleu

After training, we can use the same inference command with the new out_dir for inference:

python -m nmt.nmt \
--out_dir=/tmp/nmt_attention_model \
--inference_input_file=/tmp/my_infer_file.vi \
--inference_output_file=/tmp/nmt_attention_model/output_infer

# Tips & Tricks

## Building Training, Eval, and Inference Graphs

When building a machine learning model in TensorFlow, it's often best to build three separate graphs:

• The Training graph, which:

• Batches, buckets, and possibly subsamples input data from a set of files/external inputs.
• Includes the forward and backprop ops.
• Constructs the optimizer, and adds the training op.
• The Eval graph, which:

• Batches and buckets input data from a set of files/external inputs.
• Includes the training forward ops, and additional evaluation ops that aren't used for training.
• The Inference graph, which:

• May not batch input data.
• Does not subsample or bucket input data.
• Reads input data from placeholders (data can be fed directly to the graph via feed_dict or from a C++ TensorFlow serving binary).
• Includes a subset of the model forward ops, and possibly additional special inputs/outputs for storing state between session.run calls.

Building separate graphs has several benefits:

• The inference graph is usually very different from the other two, so it makes sense to build it separately.
• The eval graph becomes simpler since it no longer has all the additional backprop ops.
• Data feeding can be implemented separately for each graph.
• Variable reuse is much simpler. For example, in the eval graph there's no need to reopen variable scopes with reuse=True just because the Training model created these variables already. So the same code can be reused without sprinkling reuse= arguments everywhere.
• In distributed training, it is commonplace to have separate workers perform training, eval, and inference. These need to build their own graphs anyway. So building the system this way prepares you for distributed training.

The primary source of complexity becomes how to share Variables across the three graphs in a single machine setting. This is solved by using a separate session for each graph. The training session periodically saves checkpoints, and the eval session and the infer session restore parameters from checkpoints. The example below shows the main differences between the two approaches.

Before: Three models in a single graph and sharing a single Session

with tf.variable_scope('root'):
train_inputs = tf.placeholder()
train_op, loss = BuildTrainModel(train_inputs)
initializer = tf.global_variables_initializer()

with tf.variable_scope('root', reuse=True):
eval_inputs = tf.placeholder()
eval_loss = BuildEvalModel(eval_inputs)

with tf.variable_scope('root', reuse=True):
infer_inputs = tf.placeholder()
inference_output = BuildInferenceModel(infer_inputs)

sess = tf.Session()

sess.run(initializer)

for i in itertools.count():
train_input_data = ...
sess.run([loss, train_op], feed_dict={train_inputs: train_input_data})

if i % EVAL_STEPS == 0:
while data_to_eval:
eval_input_data = ...
sess.run([eval_loss], feed_dict={eval_inputs: eval_input_data})

if i % INFER_STEPS == 0:
sess.run(inference_output, feed_dict={infer_inputs: infer_input_data})

After: Three models in three graphs, with three Sessions sharing the same Variables

train_graph = tf.Graph()
eval_graph = tf.Graph()
infer_graph = tf.Graph()

with train_graph.as_default():
train_iterator = ...
train_model = BuildTrainModel(train_iterator)
initializer = tf.global_variables_initializer()

with eval_graph.as_default():
eval_iterator = ...
eval_model = BuildEvalModel(eval_iterator)

with infer_graph.as_default():
infer_iterator, infer_inputs = ...
infer_model = BuildInferenceModel(infer_iterator)

checkpoints_path = "/tmp/model/checkpoints"

train_sess = tf.Session(graph=train_graph)
eval_sess = tf.Session(graph=eval_graph)
infer_sess = tf.Session(graph=infer_graph)

train_sess.run(initializer)
train_sess.run(train_iterator.initializer)

for i in itertools.count():

train_model.train(train_sess)

if i % EVAL_STEPS == 0:
checkpoint_path = train_model.saver.save(train_sess, checkpoints_path, global_step=i)
eval_model.saver.restore(eval_sess, checkpoint_path)
eval_sess.run(eval_iterator.initializer)
while data_to_eval:
eval_model.eval(eval_sess)

if i % INFER_STEPS == 0:
checkpoint_path = train_model.saver.save(train_sess, checkpoints_path, global_step=i)
infer_model.saver.restore(infer_sess, checkpoint_path)
infer_sess.run(infer_iterator.initializer, feed_dict={infer_inputs: infer_input_data})
while data_to_infer:
infer_model.infer(infer_sess)

Notice how the latter approach is "ready" to be converted to a distributed version.

One other difference in the new approach is that instead of using feed_dicts to feed data at each session.run call (and thereby performing our own batching, bucketing, and manipulating of data), we use stateful iterator objects. These iterators make the input pipeline much easier in both the single-machine and distributed setting. We will cover the new input data pipeline (as introduced in TensorFlow 1.2) in the next section.

## Data Input Pipeline

Prior to TensorFlow 1.2, users had two options for feeding data to the TensorFlow training and eval pipelines:

1. Feed data directly via feed_dict at each training session.run call.
2. Use the queueing mechanisms in tf.train (e.g. tf.train.batch) and tf.contrib.train.
3. Use helpers from a higher level framework like tf.contrib.learn or tf.contrib.slim (which effectively use #2).

The first approach is easier for users who aren't familiar with TensorFlow or need to do exotic input modification (i.e., their own minibatch queueing) that can only be done in Python. The second and third approaches are more standard but a little less flexible; they also require starting multiple python threads (queue runners). Furthermore, if used incorrectly queues can lead to deadlocks or opaque error messages. Nevertheless, queues are significantly more efficient than using feed_dict and are the standard for both single-machine and distributed training.

Starting in TensorFlow 1.2, there is a new system available for reading data into TensorFlow models: dataset iterators, as found in the tf.data module. Data iterators are flexible, easy to reason about and to manipulate, and provide efficiency and multithreading by leveraging the TensorFlow C++ runtime.

A dataset can be created from a batch data Tensor, a filename, or a Tensor containing multiple filenames. Some examples:

# Training dataset consists of multiple files.
train_dataset = tf.data.TextLineDataset(train_files)

# Evaluation dataset uses a single file, but we may
# point to a different file for each evaluation round.
eval_file = tf.placeholder(tf.string, shape=())
eval_dataset = tf.data.TextLineDataset(eval_file)

# For inference, feed input data to the dataset directly via feed_dict.
infer_batch = tf.placeholder(tf.string, shape=(num_infer_examples,))
infer_dataset = tf.data.Dataset.from_tensor_slices(infer_batch)

All datasets can be treated similarly via input processing. This includes reading and cleaning the data, bucketing (in the case of training and eval), filtering, and batching.

To convert each sentence into vectors of word strings, for example, we use the dataset map transformation:

dataset = dataset.map(lambda string: tf.string_split([string]).values)

We can then switch each sentence vector into a tuple containing both the vector and its dynamic length:

dataset = dataset.map(lambda words: (words, tf.size(words))

Finally, we can perform a vocabulary lookup on each sentence. Given a lookup table object table, this map converts the first tuple elements from a vector of strings to a vector of integers.

dataset = dataset.map(lambda words, size: (table.lookup(words), size))

Joining two datasets is also easy. If two files contain line-by-line translations of each other and each one is read into its own dataset, then a new dataset containing the tuples of the zipped lines can be created via:

source_target_dataset = tf.data.Dataset.zip((source_dataset, target_dataset))

Batching of variable-length sentences is straightforward. The following transformation batches batch_size elements from source_target_dataset, and respectively pads the source and target vectors to the length of the longest source and target vector in each batch.

batched_dataset = source_target_dataset.padded_batch(
batch_size,
padded_shapes=((tf.TensorShape([None]),  # source vectors of unknown size
tf.TensorShape([])),     # size(source)
(tf.TensorShape([None]),  # target vectors of unknown size
tf.TensorShape([]))),    # size(target)
0),          # size(source) -- unused
(tgt_eos_id,  # target vectors padded on the right with tgt_eos_id
0)))         # size(target) -- unused

Values emitted from this dataset will be nested tuples whose tensors have a leftmost dimension of size batch_size. The structure will be:

• iterator[0][0] has the batched and padded source sentence matrices.
• iterator[0][1] has the batched source size vectors.
• iterator[1][0] has the batched and padded target sentence matrices.
• iterator[1][1] has the batched target size vectors.

Finally, bucketing that batches similarly-sized source sentences together is also possible. Please see the file utils/iterator_utils.py for more details and the full implementation.

Reading data from a Dataset requires three lines of code: create the iterator, get its values, and initialize it.

batched_iterator = batched_dataset.make_initializable_iterator()

((source, source_lengths), (target, target_lengths)) = batched_iterator.get_next()

# At initialization time.
session.run(batched_iterator.initializer, feed_dict={...})

Once the iterator is initialized, every session.run call that accesses source or target tensors will request the next minibatch from the underlying dataset.

## Other details for better NMT models

### Bidirectional RNNs

Bidirectionality on the encoder side generally gives better performance (with some degradation in speed as more layers are used). Here, we give a simplified example of how to build an encoder with a single bidirectional layer:

# Construct forward and backward cells
forward_cell = tf.nn.rnn_cell.BasicLSTMCell(num_units)
backward_cell = tf.nn.rnn_cell.BasicLSTMCell(num_units)

bi_outputs, encoder_state = tf.nn.bidirectional_dynamic_rnn(
forward_cell, backward_cell, encoder_emb_inp,
sequence_length=source_sequence_length, time_major=True)
encoder_outputs = tf.concat(bi_outputs, -1)

The variables encoder_outputs and encoder_state can be used in the same way as in Section Encoder. Note that, for multiple bidirectional layers, we need to manipulate the encoder_state a bit, see model.py, method _build_bidirectional_rnn() for more details.

### Beam search

While greedy decoding can give us quite reasonable translation quality, a beam search decoder can further boost performance. The idea of beam search is to better explore the search space of all possible translations by keeping around a small set of top candidates as we translate. The size of the beam is called beam width; a minimal beam width of, say size 10, is generally sufficient. For more information, we refer readers to Section 7.2.3 of Neubig, (2017). Here's an example of how beam search can be done:

# Replicate encoder infos beam_width times
decoder_initial_state = tf.contrib.seq2seq.tile_batch(
encoder_state, multiplier=hparams.beam_width)

# Define a beam-search decoder
decoder = tf.contrib.seq2seq.BeamSearchDecoder(
cell=decoder_cell,
embedding=embedding_decoder,
start_tokens=start_tokens,
end_token=end_token,
initial_state=decoder_initial_state,
beam_width=beam_width,
output_layer=projection_layer,
length_penalty_weight=0.0,
coverage_penalty_weight=0.0)

# Dynamic decoding
outputs, _ = tf.contrib.seq2seq.dynamic_decode(decoder, ...)

Note that the same dynamic_decode() API call is used, similar to the Section Decoder. Once decoded, we can access the translations as follows:

translations = outputs.predicted_ids
# Make sure translations shape is [batch_size, beam_width, time]
if self.time_major:
translations = tf.transpose(translations, perm=[1, 2, 0])

See model.py, method _build_decoder() for more details.

### Hyperparameters

There are several hyperparameters that can lead to additional performances. Here, we list some based on our own experience [ Disclaimers: others might not agree on things we wrote! ].

Optimizer: while Adam can lead to reasonable results for "unfamiliar" architectures, SGD with scheduling will generally lead to better performance if you can train with SGD.

Attention: Bahdanau-style attention often requires bidirectionality on the encoder side to work well; whereas Luong-style attention tends to work well for different settings. For this tutorial code, we recommend using the two improved variants of Luong & Bahdanau-style attentions: scaled_luong & normed bahdanau.

### Multi-GPU training

Training a NMT model may take several days. Placing different RNN layers on different GPUs can improve the training speed. Here’s an example to create RNN layers on multiple GPUs.

cells = []
for i in range(num_layers):
cells.append(tf.contrib.rnn.DeviceWrapper(
tf.contrib.rnn.LSTMCell(num_units),
"/gpu:%d" % (num_layers % num_gpus)))
cell = tf.contrib.rnn.MultiRNNCell(cells)

In addition, we need to enable the colocate_gradients_with_ops option in tf.gradients to parallelize the gradients computation.

You may notice the speed improvement of the attention based NMT model is very small as the number of GPUs increases. One major drawback of the standard attention architecture is using the top (final) layer’s output to query attention at each time step. That means each decoding step must wait its previous step completely finished; hence, we can’t parallelize the decoding process by simply placing RNN layers on multiple GPUs.

The GNMT attention architecture parallelizes the decoder's computation by using the bottom (first) layer’s output to query attention. Therefore, each decoding step can start as soon as its previous step's first layer and attention computation finished. We implemented the architecture in GNMTAttentionMultiCell, a subclass of tf.contrib.rnn.MultiRNNCell. Here’s an example of how to create a decoder cell with the GNMTAttentionMultiCell.

cells = []
for i in range(num_layers):
cells.append(tf.contrib.rnn.DeviceWrapper(
tf.contrib.rnn.LSTMCell(num_units),
"/gpu:%d" % (num_layers % num_gpus)))
attention_cell = cells.pop(0)
attention_cell = tf.contrib.seq2seq.AttentionWrapper(
attention_cell,
attention_mechanism,
output_attention=False,)
cell = GNMTAttentionMultiCell(attention_cell, cells)

# Benchmarks

## IWSLT English-Vietnamese

Training details. We train 2-layer LSTMs of 512 units with bidirectional encoder (i.e., 1 bidirectional layers for the encoder), embedding dim is 512. LuongAttention (scale=True) is used together with dropout keep_prob of 0.8. All parameters are uniformly. We use SGD with learning rate 1.0 as follows: train for 12K steps (~ 12 epochs); after 8K steps, we start halving learning rate every 1K step.

Results.

Below are the averaged results of 2 models (model 1, model 2).
We measure the translation quality in terms of BLEU scores (Papineni et al., 2002).

Systems tst2012 (dev) test2013 (test)
NMT (greedy) 23.2 25.5
NMT (beam=10) 23.8 26.1
(Luong & Manning, 2015) - 23.3

Training Speed: (0.37s step-time, 15.3K wps) on K40m & (0.17s step-time, 32.2K wps) on TitanX.
Here, step-time means the time taken to run one mini-batch (of size 128). For wps, we count words on both the source and target.

## WMT German-English

Training details. Our training hyperparameters are similar to the English-Vietnamese experiments except for the following details. The data is split into subword units using BPE (32K operations). We train 4-layer LSTMs of 1024 units with bidirectional encoder (i.e., 2 bidirectional layers for the encoder), embedding dim is 1024. We train for 350K steps (~ 10 epochs); after 170K steps, we start halving learning rate every 17K step.

Results.

The first 2 rows are the averaged results of 2 models (model 1, model 2). Results in the third row is with GNMT attention (model) ; trained with 4 GPUs.

Systems newstest2013 (dev) newstest2015
NMT (greedy) 27.1 27.6
NMT (beam=10) 28.0 28.9
NMT + GNMT attention (beam=10) 29.0 29.9
WMT SOTA - 29.3

These results show that our code builds strong baseline systems for NMT.
(Note that WMT systems generally utilize a huge amount monolingual data which we currently do not.)

Training Speed: (2.1s step-time, 3.4K wps) on Nvidia K40m & (0.7s step-time, 8.7K wps) on Nvidia TitanX for standard models.
To see the speed-ups with GNMT attention, we benchmark on K40m only:

Systems 1 gpu 4 gpus 8 gpus
NMT (4 layers) 2.2s, 3.4K 1.9s, 3.9K -
NMT (8 layers) 3.5s, 2.0K - 2.9s, 2.4K
NMT + GNMT attention (4 layers) 2.6s, 2.8K 1.7s, 4.3K -
NMT + GNMT attention (8 layers) 4.2s, 1.7K - 1.9s, 3.8K

These results show that without GNMT attention, the gains from using multiple gpus are minimal.
With GNMT attention, we obtain from 50%-100% speed-ups with multiple gpus.

## WMT English-German — Full Comparison

The first 2 rows are our models with GNMT attention: model 1 (4 layers), model 2 (8 layers).

Systems newstest2014 newstest2015
Ours — NMT + GNMT attention (4 layers) 23.7 26.5
Ours — NMT + GNMT attention (8 layers) 24.4 27.6
WMT SOTA 20.6 24.9
OpenNMT (Klein et al., 2017) 19.3 -
tf-seq2seq (Britz et al., 2017) 22.2 25.2
GNMT (Wu et al., 2016) 24.6 -

The above results show our models are very competitive among models of similar architectures.
[Note that OpenNMT uses smaller models and the current best result (as of this writing) is 28.4 obtained by the Transformer network (Vaswani et al., 2017) which has a significantly different architecture.]

## Standard HParams

We have provided a set of standard hparams for using pre-trained checkpoint for inference or training NMT architectures used in the Benchmark.

We will use the WMT16 German-English data, you can download the data by the following command.

nmt/scripts/wmt16_en_de.sh /tmp/wmt16

Here is an example command for loading the pre-trained GNMT WMT German-English checkpoint for inference.

python -m nmt.nmt \
--src=de --tgt=en \
--ckpt=/path/to/checkpoint/translate.ckpt \
--hparams_path=nmt/standard_hparams/wmt16_gnmt_4_layer.json \
--out_dir=/tmp/deen_gnmt \
--vocab_prefix=/tmp/wmt16/vocab.bpe.32000 \
--inference_input_file=/tmp/wmt16/newstest2014.tok.bpe.32000.de \
--inference_output_file=/tmp/deen_gnmt/output_infer \
--inference_ref_file=/tmp/wmt16/newstest2014.tok.bpe.32000.en

Here is an example command for training the GNMT WMT German-English model.

python -m nmt.nmt \
--src=de --tgt=en \
--hparams_path=nmt/standard_hparams/wmt16_gnmt_4_layer.json \
--out_dir=/tmp/deen_gnmt \
--vocab_prefix=/tmp/wmt16/vocab.bpe.32000 \
--train_prefix=/tmp/wmt16/train.tok.clean.bpe.32000 \
--dev_prefix=/tmp/wmt16/newstest2013.tok.bpe.32000 \
--test_prefix=/tmp/wmt16/newstest2015.tok.bpe.32000

# Other resources

For deeper reading on Neural Machine Translation and sequence-to-sequence models, we highly recommend the following materials by Luong, Cho, Manning, (2016); Luong, (2016); and Neubig, (2017).

There's a wide variety of tools for building seq2seq models, so we pick one per language:
Stanford NMT https://nlp.stanford.edu/projects/nmt/ [Matlab]
Nemantus https://github.com/rsennrich/nematus [Theano]
OpenNMT http://opennmt.net/ [Torch]
OpenNMT-py https://github.com/OpenNMT/OpenNMT-py [PyTorch]

# Acknowledgment

We would like to thank Denny Britz, Anna Goldie, Derek Murray, and Cinjon Resnick for their work bringing new features to TensorFlow and the seq2seq library. Additional thanks go to Lukasz Kaiser for the initial help on the seq2seq codebase; Quoc Le for the suggestion to replicate GNMT; Yonghui Wu and Zhifeng Chen for details on the GNMT systems; as well as the Google Brain team for their support and feedback!

# BibTex

@article{luong17,
author  = {Minh{-}Thang Luong and Eugene Brevdo and Rui Zhao},
title   = {Neural Machine Translation (seq2seq) Tutorial},
journal = {https://github.com/tensorflow/nmt},
year    = {2017},
}


text:
# Batteries in series vs parallel

As fa as I understand it, two identicle batteries in parallel will give double the amperage than just one battery and two batteries in series will give double the voltage. If my understanding is correct, what is the reason for this.

Any help is appreciated

The series voltage doubles because batteries make a potential difference between their terminals. So let's assume 2 AA batteries with a nominal 1.5V difference between their terminals. One battery itself makes a difference of 1.5V. Connecting another in series, it adds another 1.5V difference, relative to the 1.5V difference the other has already made.

To say two identical batteries in parallel doubles the current is a little misleading, because the current that flows through the batteries is determined largely by the load attached to them. If they are attached to a high resistance, very little current will flow. Attached to a low resistance, a high amount of current will flow.

Taking this to the limit, what happens if we attach a battery to a zero resistance? Does an unlimited current flow? Not in practice, because the chemical reactions in the battery can only happen so fast. Electrical engineers model the underlying chemistry as an "internal resistance", as if there's an imaginary resistor in series with the battery. This puts an upper limit on the current a battery can supply.

With two batteries in parallel, you have twice the battery plate area able to react. The same thing can be accomplished with a different battery size, such as using C cells instead of AA cells.

Or as an electrical engineer would put it, the internal resistance of each battery is in parallel. That halves the effective internal resistance, and thus doubles the current that the battery could supply into a zero-resistance load.

Of course in practice batteries aren't used to power zero-resistance loads, since that would just mean a dead battery. Rather, the objective is typically to make the battery's internal resistance much lower than the resistance of the load, such that that the battery's internal resistance is negligible.

Each battery has some chemical energy in it which can be converted into electrical energy.

Assume that the batteries are ideal, the voltage of each battery is $V$ and the current through each battery is $I$.

For a series combination of batteries the electrical energy delivered by the batteries in a time $t$ is $(2V)(I)t$ and for a parallel arrangement it is $(V)(2I)t$.

You now compare this with one battery where the energy delivered is $VIt$.

In some applications you need to increase the voltage and so you put the batteries in series whilst in other application where there is a large current drain you put the batteries in parallel.

If the batteries are non ideal and have an internal resistance then putting the batteries in parallel reduces their effective internal resistance and so allows a larger maximum current to flow.
So two batteries in parallel both of which have the same internal resistance can produce twice the maximum current of one battery.

Powering electric motors is one application where batteries in model cars are often put in parallel.

format: plain


text:
I was trying to add an additional header for every new page of my CV (2nd page and onward), but unfortunately everything I tried ended in a failure.

I've tried editing "moderncvstyleclassic.sty" and adding a new command similar to \makecvtitle command. I'm new to latex, so probably I just messed code somewhere.

\firstname{John}
\familyname{Doe}

(...) %personal info

\begin{document}

\makecvtitle % Print the CV title, so for the 1st page I don't need a new header

(...) %some info here

\clearpage

\end{document}

I was looking to add black/gray color header with fonts 18/16 like:

John Doe                                                         Curriculum Vitae

• You should provide us with something to work with, just so it's easier to get started. Do so by constructing a minimal working example (MWE). – Werner Jun 12 '14 at 6:17
• Did you mean adding something like this? – Kwydin Jun 12 '14 at 11:30
• moderncv uses fancyhdr to setup headers and footers, are you trying to accomplish something that can be done with fancyhdr? If so you can use the fancyhdr macros directly in you document to setup the header/footer styles – Bordaigorl Jun 12 '14 at 11:42
• Ok now I'm confused, I've tried using \chead (since I used \cfoot already) but it gave me an error then and that's why I was looking for another solution with headers, now I've found out about \lhead, \rhead (those are which I needed with a small editing for fonts and color), so I've tried using \chead again and now it works ... – Kwydin Jun 12 '14 at 12:47

@Bordaigorl Thx for hinting me in the right direction.

The problem was so simple that it's kinda stupid. So, sorry for taking your time.

I was looking for something like this:

\firstname{John}
\familyname{Doe}

(...) %personal info

\begin{document}

\makecvtitle % Print the CV title, so for the 1st page I don't need a new header

(...) %some info here

\clearpage


text:
# Joining lists with some common elements in average case

What are some ways of commutatively combining a pair of lists to produce a list comprised of elements from the pair of inputs, with no duplicates, with time complexity better than $O(n \log(n))$? Suppose we have the following inputs

$a = [5, 1, 6, 8]$

$b = [8, 4, 5, 2, 10]$

We would like to commutatively combine $a$ and $b$ to produce a list with no duplicate elements (i.e. if F denotes a function that satisfies the aforementioned criteria, then $\forall x, y \quad F(x, y) = F(y, x)$). One possible valid output is $c = [1, 2, 4, 5, 6, 8, 10]$ - since the output doesn't have to be sorted, any permutation of $c$ is just as valid (although consistency would be nice). The most obvious naïve algorithm concatenates the two lists, then removes duplicates, then sorts the result in $O(n \log(n))$ time.

Is there a commonly used name for this kind of problem, and where can I find literature about it?

• Are you asking for a way to compute the union of two lists? Aug 16 '11 at 9:12
• I don't think this is a research level question. Aug 16 '11 at 10:21
• Even ignoring the commutativity requirement, the problem of eliminating duplicate elements is called duplicate elimination, and has a lower bound of n log n in the comparison model. More precisely, it's $n \log n - \sum_i n_i \log n_i$ where $n_i$ is the multiplicity of the $i^{\text{th}}$ element. See Munro, I., Spira, P.: Sorting and searching in multisets. SIAM Journal on Computing 5 (1976) 1-8 Aug 16 '11 at 11:46
• If the input sequences are possibly not sorted, then I don't see what's the point of saying you have two sequences. Aug 16 '11 at 13:35
• To the asker: Please edit the question to clarify whether the input sequences are already sorted or not. −1 for this ambiguity. Aug 16 '11 at 14:51

Yes and no.

Set interaction is one of the problems specifically studied in Ben-Or's seminal paper on lower bounds for algebraic decision and computation trees. The problem is formally defined as follows: Given two sets of n numbers, is their intersection empty? Equivelently, does their union have exactly 2n elements? Ben-or proves a lower bound of Ω(n log n) for this problem. If the sets have diffent sizes n>m, the lower bound becomes Ω(n log m), but this only beats the naive O(n log n) bound if m is subpolynomial in n.

On the other hand, if your list elements are integers, you can solve the problem in o(n log n) time using fast integer-RAM sorting algorithms. For reasonable word sizes, I believe the fastest integer sorting algorithm runs in $O(n \sqrt{\log \log n})$ expected time [Han and Thorup, FOCS 2002].

• I ignored the phrase "average case" in the title, because it didn't appear in the question itself. Aug 20 '11 at 22:41

I'm not sure I understand the question completely. Do you want an algorithm that, given two sorted sequences each containing no duplicates, outputs a new sorted sequence containing every item in either of the input sequences and also no duplicates?

If so, you can represent the larger sequence as a special type of tree (a finger tree), then merge the sequences in $O(i \lg (k/i))$ merges, where $i$ is the size of the smaller sequence and $k$ is the size of the larger sequence. I think this is asymptotically optimal in the pointer machine model.

• I don't think the OP is assuming the original sequences are sorted. Aug 16 '11 at 11:41
• If the lists are sorted, then you just merge them (no need for fancy trees). Aug 16 '11 at 13:34
• @Radu GRIGore: Yes, but then you may make O(k) comparisons, which is not so great if i is small. Aug 16 '11 at 14:40
• Can you build the finger tree faster than O(k)? Aug 16 '11 at 14:59
• @Radu GRIGore - Not really, or at least not helpfully in this case, but the survey I linked from Brodal explains why this merge time may be useful in any case See sections 11.5.2 and 11.5.4. Aug 17 '11 at 0:46
def F(a,b):
M = max(max(a),max(b))
C = BitArray of size M
FOR x in a:
C[x] = 1
FOR y in b:
C[y] = 1
FOR z in range(0,M):
IF C[z] == 1:
c.append(z)
return c

Nice qualities:

1. This function is $O(n)$.
2. It preserves order.

Non-nice qualities:

1. If input is $a = [100000000000], b=[0]$ you will regret using it.

So if numbers in the lists are uniformly and densely distributed between $0$ and $M$ then this will work fine otherwise not using it will be wise.

But again the complexity is $O(n)$ and this is theoretical cs website.

• I don't think the last one works. Aug 16 '11 at 16:31
• @Kaveh You are right. It doesn't. I tried to implement it just now. Needs many modifications. Thanks! Aug 16 '11 at 16:53


text:
# Tag Info

### Evolving artificial neural networks for solving NP problems

Given that neural nets are good at interpolation (but poor at extrapolation), for a given use case it suffices to solve a few billion large problems and feed them to a sufficiently large net. In some ...
• 3,912

### Evolving artificial neural networks for solving NP problems

Even if P $\neq$ NP, that says nothing about average case complexity. That for any algorithm for solving a NP complete problem must have at least some instances where it takes more than polynomial ...
1 vote

### What does "Temporal extent" mean?

It's just the ordinary meaning of the words extent and resolution, only applied to time instead of space. You can think of space-time as a kind of a continuous block, instead of just thinking of time ...
1 vote

### What is meant by the term "prior" in machine learning

In Bayesian statistics, a "prior" represents the beliefs we have before observing some data. Then, after we observe some data, we update our beliefs; those updated beliefs are called the &...
• 141k

### What is meant by the term "prior" in machine learning

It's roughly any pre-training choices you encode into your model In machine learning a prior is, according to the book "Deep Learning" by Goodfellow, Bengio, and Courville, a probability ...
• 101
1 vote

### Is there a good rule of thumb for regularization constants?

Cross-validation is simple and easy to implement. Rather than inventing something new, which might be dubious, I recommend you use cross-validation. It works. There are no formulas for the ...
• 141k


text:
# Custom string-to-int converter

I have written the following function:

#include <iostream>
#include <utility>
#include <string>
#include <string_view>
#include <limits>
#include <optional>
#include <stdexcept>

std::optional<int> isInteger( const std::string_view token, const std::pair<int, int> acceptableRange =
std::pair<int, int>( std::numeric_limits<int>::min( ), std::numeric_limits<int>::max( ) ) ) noexcept;

// source file

std::optional<int> isInteger( const std::string_view token, const std::pair<int, int> acceptableRange ) noexcept
{
if ( token.empty( ) )
{
return { }; // not convertible
}

try
{
std::size_t pos { 0 };

const int result_integer { std::stoi( std::string{ token }, &pos, 10 ) };

const auto& [ minAcceptableValue, maxAcceptableValue ] { acceptableRange };

if ( pos == token.length( ) && ( result_integer <= maxAcceptableValue && result_integer >= minAcceptableValue ) )
{
return result_integer; // convertible, this is the happy ending
}
else
{
return { }; // not convertible
}
}
catch ( const std::invalid_argument& ia ) { return { }; } // not convertible
catch ( const std::out_of_range& oor ) { return { }; } // not convertible
catch ( const std::length_error& le ) { return { }; } // not convertible
catch ( const std::bad_alloc& ba ) { return { }; } // not convertible
}

// call site

int main( )
{
const std::string str { "12" };
const std::pair<int, int> acceptableRange { std::make_pair<int, int>( 0, 50 ) };

const std::optional<int> tempInteger { isInteger( str, acceptableRange ) };

if ( tempInteger ) { std::cout << "Converted value: " << tempInteger.value( ) << '\n'; }
else { std::cout << "Conversion failed" << '\n'; }
}

The above function converts any string_view to an int if possible, otherwise returns an empty std::optional. I thought that returning an empty optional acts as an error code and informs the caller of the failure. So there isn't any need to let it throw and then handle the exceptions in the call site. I think that stack unwinding is unnecessary in this case.

I have a few questions:

1. Is this function good in terms of performance? Or should I use an alternative from another library? If so, then what can be the alternative?
2. Does it cover all the edge cases? I have tested it with many different (valid and invalid) inputs but it never failed.
3. Is it good that it's handling the possible exceptions inside its scope?
4. I declared it noexcept and this decreased the size of the executable (just a little). Do you recommend doing this for this function since no exception will escape its body?

Also I use GCC v11.2 (just in case you need to know).

1. Wrapping a convenience wrapper in a convenience wrapper is generally just wasteful. Instead of calling std::stol(), go directly for std::strtol().

• No need to convert to a std::string, which is potentially expensive and can fail.
Instead, after trimming yourself, reject if too long, otherwise copy into a fixed-length buffer and add terminator.

• No need to catch any exceptions, as the wrapper adding them is avoided.

2. As an aside, if you want to catch all exceptions and treat them equally, use the catch-all catch(...). Even if you don't forget any, writing them out and verifying is just tedious, and potentially bloats your executable. The compiler is unlikely to figure out you are really catching all possible exceptions, and thus the superfluous runtime type checks stay.

3. Marking all functions which cannot throw by design (in contrast to those which do so by happenstance) noexcept is a good idea. It spells the contract out for users and lets the compiler take advantage too.

4. CV-qualifiers on parameters in pure declarations (not definitions) are just noise, as they have no effect on the functions signature.

5. I'm really not sold on packing the maximum and minimum into a pair, instead of passing them individually.

If you use pre-C++17 with a back-ported replacement for std::string_view, this code might be of interest:

auto trim(std::string_view s) noexcept {
auto space = [](unsigned char c){ return std::isspace(c); };
while (!s.empty() && space(s.front()))
s.remove_prefix(1);
while (!s.empty() && space(s.back()))
s.remove_suffix(1);
return s;
}

std::optional<int> parseInteger(std::string_view s, int min, int max) noexcept {
s = trim(s);
constexpr size_t nBuffer = std::numeric_limits<int>::digits / 3 + 3;
if (!s.size() || s.size() >= nBuffer)
return {};
char buffer[nBuffer];
std::copy(s.begin(), s.end(), buffer);
nBuffer[s.size()] = 0;
char* end;
long r = std::strtol(buffer, &end, 10);
if (end - buffer != s.size() || r < min || r > max)
return {};
return r;
}

1. Since C++17, you can use std::from_chars() for the parsing, which while a bit more basic, is also more amenable to fitting into your own code however you want. It avoids copying and even results in shorter code:
std::optional<int> parseInteger(std::string_view s, int min, int max) noexcept {
s = trim(s);
if (!s.size())
return {};
if (s.size() > 1 && s[0] == '+' && s[1] != '-')
s.remove_prefix(1);
int r;
auto result = std::from_chars(s.begin(), s.end(), r, 10);
if (result.ec || result.ptr != s.end() || r < min || r > max)
return {};
return r;
}

• Comments are not for extended discussion; this conversation has been moved to chat. Jan 30 at 6:10

The name isInteger is curious. It suggests that the function is a predicate (i.e. returns a bool). I would go with something like toInteger or asInteger.

Some of the includes need to be present in the header file:

#include <limits>
#include <optional>
#include <string_view>
#include <utility>

And others in the implementation:

#include <stdexcept>
#include <string>

<iostream> is only needed by the main() function, not by any of the code under review.

Since the function is declared noexcept, I think this is one of the few cases where I'd accept catch (...) - all exceptions should result in an empty optional being returned.

I'd reformat the very long condition, and perhaps change the if { return } else { return } to not use else:

    const auto& [ min, max ] { acceptableRange };
if (pos != token.length()) {
return {};
}
if (result_integer > max || result_integer < min) {
return {};
}
return result_integer;

This looks very much like a function that ought to be a template, perhaps with a couple of if constexpr branches to deal with signed and unsigned integers, and perhaps also floating-point types (with a rename to toNumber()).

• Yes, I am thinking about making it a function template. However, I'm not that experienced with templates. I am not sure how I can handle unsigned too. Jan 28 at 11:26
• Unsigned types would be similar, but you'd use std::stoul() family instead. Or std::from_chars(), which will work better in a template, because it's already generic. Jan 28 at 13:27
• @TobySpeight std::from_chars() is not actually generic. But there are overloads for all the integer and floating types, which has about the same effect. Jan 28 at 21:13
• @Toby Speight I posted my final solution as an answer. Take a look at it if you would like to. Jan 29 at 15:24

Thanks to @Toby Speight and @Deduplicator I came up with a very compelling solution.

Here is my solution:

// header file

std::optional<int> to_integer( std::string_view token, const std::pair<int, int> acceptableRange =
{ std::numeric_limits<int>::min( ), std::numeric_limits<int>::max( ) } ) noexcept;

// source file

std::optional<int> to_integer( std::string_view token, const std::pair<int, int> acceptableRange ) noexcept
{
if ( token.empty( ) )
{
return { };
}

if ( token.size( ) > 1 && token[ 0 ] == '+' && token[ 1 ] != '-' ) { token.remove_prefix( 1 ); }

int value { };
const auto [ ptr, ec ] { std::from_chars( token.begin( ), token.end( ), value, 10 ) };

const auto& [ minAcceptableValue, maxAcceptableValue ] { acceptableRange };

if ( ec != std::errc( ) || ptr != token.end( ) ||
value < minAcceptableValue || value > maxAcceptableValue ) { return { }; }

return value;
}

The execution speed improvement ranges between ~20% to ~1450% depending on the input string. Also, the above solution slightly reduced the size of the executable.

This solution does not involve work with std::string and exceptions, thus the result is performance gain and probably a smaller memory footprint.

• 1. const-qualifying the pair in the header just confuses the matter. 2. Initializing value is at best an insignificant pessimization. 3. Your modified code no longer ignores leading nor trailing whitespace. Jan 29 at 16:09
• @Deduplicator Yes, I didn't include the trim function since I have a tokenize function which takes a string_view of user input and returns a vector containing tokens of type std::string (which do not have white space anymore). Then another function passes those tokens one by one to to_integer. Jan 29 at 16:26
• @Deduplicator So I should not initialize the value to get better performance? Is it safe to keep it uninitialized? Jan 29 at 16:27
• You only use it iff from_chars signals success. Leaving it uninitialized might marginally increase efficiency, or might change nothing, depending on the compiler. Jan 29 at 16:43
• cv-qualifiers on function-parameters have no impact on function signature. Thus, they are only relevant for the definition, where they only impact the body (and ctor-init-list for ctors). Jan 29 at 18:00


text:
$$\require{cancel}$$

1: Units and Measurement

The thumbnail image is of the Whirlpool Galaxy, which we examine in the first section of this chapter. Galaxies are as immense as atoms are small, yet the same laws of physics describe both, along with all the rest of nature—an indication of the underlying unity in the universe. The laws of physics are surprisingly few, implying an underlying simplicity to nature’s apparent complexity. In this text, you learn about the laws of physics. Galaxies and atoms may seem far removed from your daily life, but as you begin to explore this broad-ranging subject, you may soon come to realize that physics plays a much larger role in your life than you first thought, no matter your life goals or career choice.

• 1.1: Prelude to Units and Measurement
The laws of physics are surprisingly few, implying an underlying simplicity to nature’s apparent complexity. In this text, you learn about the laws of physics. Galaxies and atoms may seem far removed from your daily life, but as you begin to explore this broad-ranging subject, you may soon come to realize that physics plays a much larger role in your life than you first thought, no matter your life goals or career choice.
• 1.2: The Scope and Scale of Physics
Physics is about trying to find the simple laws that describe all natural phenomena. It operates on a vast range of scales involving length, mass, and time. Scientists attempt to describe the world by formulating models, theories, and laws. They utilize orders of magnitudes of numbers to track and compare phenomena occurring on particular scales.
• 1.3: Units and Standards
Systems of units are constructed from a small number of fundamental units, which are defined by accurate and precise measurements of conventionally chosen base quantities. Two commonly used systems of units are English units and SI units. SI units are a metric system of units, meaning values can be calculated by factors of 10. The SI base units of length, mass, and time are the meter (m), kilogram (kg), and second (s), respectively.
• 1.4: Unit Conversion
Multiplication by conversion factors allows for quantities to change units. The operation must be done in such a way that the units you want to get rid of are canceled and the units you want to end up with remain. Units obey the rules of algebra so, for example, if a unit is squared two factors are needed to cancel it.
• 1.5: Dimensional Analysis
The dimension of a physical quantity is just an expression of the base quantities from which it is derived. All equations expressing physical laws or principles must be dimensionally consistent. This fact can be used as an aid in remembering physical laws, as a way to check whether claimed relationships between physical quantities are possible, and even to derive new physical laws.
• 1.6: Estimates and Fermi Calculations
An estimate is a rough educated guess at the value of a physical quantity based on prior experience and sound physical reasoning. Some strategies that may help when making an estimate are as follows: 1) Get big lengths from smaller lengths. 2) Get areas and volumes from lengths. 3) Get masses from volumes and densities. 4) If all else fails, bound it. One “sig. fig.” is fine. 5) Ask yourself: Does this make any sense?
• 1.7: Significant Figures
Accuracy of a measured value refers to how close a measurement is to an accepted reference value. Precision of measured values refers to how close the agreement is between repeated measurements. Significant figures express the precision of a measuring tool. When performing mathematical operations with measured values, there are rules to standardize the precision of the final answer.
• 1.8: Solving Problems in Physics
The three stages of the process for solving physics problems used in this textmap are as follows: 1)Strategy: Determine which physical principles are involved and develop a strategy for using them to solve the problem. 2) Solution: Do the math necessary to obtain a numerical solution with the correct units. 3) Significance: Check the solution to make sure it makes sense and assess its significance.
• 1.A: Units and Measurement (Answers)
• 1.E: Units and Measurement (Exercises)
• 1.S: Units and Measurement (Summary)

Thumbnail: This image might be showing any number of things. It might be a whirlpool in a tank of water or perhaps a collage of paint and shiny beads done for art class. Without knowing the size of the object in units we all recognize, such as meters or inches, it is difficult to know what we’re looking at. In fact, this image shows the Whirlpool Galaxy (and its companion galaxy), which is about 60,000 light-years in diameter (about 6 × 1017 km across). (credit: S. Beckwith (STScI) Hubble Heritage Team, (STScI/AURA), ESA, NASA)

• Samuel J. Ling (Truman State University), Jeff Sanny (Loyola Marymount University), and Bill Moebs with many contributing authors. This work is licensed by OpenStax University Physics under a Creative Commons Attribution License (by 4.0).


text:
# Is there an NLP or text classification method for word order and pre-specification of terms?

I'm fairly new to NLP and text classification world, and so far I haven't been able to find the answer to the following problem:

I have text entries for a large number of observations. My goal is to classify (supervised) by text into one of two outcomes. However, the text I'm looking to classify has phrases where ordering matters, especially when it comes to negation prior to the word. Are there robust methods that allow for this accommodation of strings and negation terms prior to strings?

Ideally, the method would also allow me to specify a priori which terms that are already known to denote an observation as having a specific classification, but then learn beyond those terms how to classify.


text:
# sbi clerk :: reasoning :: test 8

## Home sbi clerk / reasoning Questions and Answers

1.  Directions(Q.1 to Q.5 ):

How many such pairs of letters are there in the word ’LABOUR’ each of which has as many letters between them in the word (in both forward and backward directions) as they have between them in the English alphabetical series ?

a

None

b

One

c

Two

d

Three

e

More than three

 Answer : Option C Explanation :

2.  What should come next in the letter series given below ?
Z Z Y Z Y X Z Y X W Z Y X
W V Z Y X W V U Z Y X W V
U T Z Y X W V U T

a

U

b

Z

c

R

d

T

e

None of these

 Answer : Option E Explanation :

3.  In a class of 20 students, Mridul’s rank is 12th from the top and Veena’s rank is 17th from the bottom. If Rohan’s rank is exactly between Mridul and Veenna’ rank, what is Rohan’s rank from the top ?

a

9th

b

8th

c

10th

d

7th

e

Cannot be determined

 Answer : Option B Explanation : Veena’s rank from the top = 20 – 17 + 1 = 4th Therefore, Rohan’s rank from the top = $\frac{{\left( {12 + 4} \right)}}{2} = 8{\rm{th}}$

4.  How many meaningful English words can be formed with the letters ’EWF’ using all the letters only once in each word ?

a

None

b

One

c

Two

d

Three

e

More than three

 Answer : Option B Explanation : Meaningful Word $\Rightarrow$ FEW

5.  Four of the following five are alike in a certain way and hence form a group. Which of the following does not belong to that group ?

a

Tyre

b

Speed

c

Clutch

d

Brake

e

Gear

 Answer : Option B Explanation : Except speed, all others are different parts of automobile.

6.  Directions(Q.6 to Q.10 ):
Study the following information carefully and answer the given questions.
Eight friends L, M, N, O, P, Q, R and S are sitting around a circle facing the centre. There are equal number of males and females in the group. No two females are immediate neighbours of each other. N is a male and N sits third to the right of R. O is a female and O is not an immediate neighbour of N. P sits second to the left of O. S sits fourth to the right of L and S is not an immediate neighbour of R. Q is a female.

What is Q’s position with respect to O ?

a

Immediate right

b

Third to the right

c

Third to the left

d

Fourth to the left

e

Fifth to the right

 Answer : Option D Explanation : Q is fourth to the left or right of O.

7.  If all the eight friends are made to sit alphabetically in the clockwise direction starting from L, positions of how many will remain unchanged (excluding L)?

a

None

b

One

c

Two

d

Three

e

Four

 Answer : Option B Explanation :

8.  Which of the following is true about M ?

a

M sits third to the right of Q

b

M sits second to the right of L

c

M is a male

d

M sits to the immediate left of O

e

None of these

 Answer : Option C Explanation : M sits third to the left of Q. M sits second to the left of L. M is a male. M sits to the immediate right of O.

9.  Which of the following represent the females in the group ?

a

O, P, Q, S

b

Q, R, P, O

c

Q, L, M, O

d

O, M, Q, R

e

None of these

 Answer : Option B Explanation : The females in the group are : O, P, Q and R.

10.  Four of the following five are alike in a certain way based on their seating positions in the above arrangement and so form a group. Which is the one that does not belong to the group ?

a

LO

b

NL

c

OP

d

PQ

e

MS

 Answer : Option A Explanation : Except in LO, in all others the first person is second to the right of the second person.

11.  Directions(Q.11 to Q.15 ):
In each of the questions below, two statements are given followed by two conclusions numbered I and II. You have to take the two statements to be true even if they seem to be at variance from the commonly known facts and then decide which of the given conclusions logically follows from the given statements disregarding commonly known facts and Give answer

Statements :
All tents are cabins.
All cabins are houses.
Conclusions :
I. All tents are houses.
II. All houses are tents.

a

if only conclusion I follows.

b

if only conclusion II follows.

c

if either conclusion I or conclusion II follows

d

if neither conclusion I nor conclusion II follows.

e

if both conclusions I and II follow.

 Answer : Option A Explanation : (i) All tents are cabins $\Rightarrow$ Universal Affirmative (A-type). (ii) Some watches are rings $\Rightarrow$ Particular Affirmative (I-type). (iii) No string is a basket.$\; \Rightarrow$ Universal Negative (E-type). (iv) Some strings are not baskets $\Rightarrow$ Particular Negative (O type). A + A $\Rightarrow$ A-type of Conclusion “All tents are houses.” This is Conclusion I.

12.  Statements :
All watches are shoes.
Some watches are rings.
Conclusions :
I. Some rings are shoes.
II. All rings are shoes.

a

if only conclusion I follows.

b

if only conclusion II follows.

c

if either conclusion I or conclusion II follows

d

if neither conclusion I nor conclusion II follows.

e

if both conclusions I and II follow.

 Answer : Option A Explanation : (i) All tents are cabins $\Rightarrow$ Universal Affirmative (A-type). (ii) Some watches are rings $\Rightarrow$ Particular Affirmative (I-type). (iii) No string is a basket.$\; \Rightarrow$ Universal Negative (E-type). (iv) Some strings are not baskets $\Rightarrow$ Particular Negative (O type). I + A $\Rightarrow$ I-type of Conclusion “Some rings are shoes.” This is Conclusion I.

13.  Statements :
All purses are strings.
No string is a basket.
Conclusions :
I. No purse is a basket.
II. At least some purses are baskets.

a

if only conclusion I follows.

b

if only conclusion II follows.

c

if either conclusion I or conclusion II follows

d

if neither conclusion I nor conclusion II follows.

e

if both conclusions I and II follow.

 Answer : Option A Explanation : (i) All tents are cabins $\Rightarrow$ Universal Affirmative (A-type). (ii) Some watches are rings $\Rightarrow$ Particular Affirmative (I-type). (iii) No string is a basket.$\; \Rightarrow$ Universal Negative (E-type). (iv) Some strings are not baskets $\Rightarrow$ Particular Negative (O type). A + E $\Rightarrow$ E-type of Conclusion “No purse is a basket.” This is Conclusion I.

14.  Statements :
Some weathers are rains.
Some summers are weathers.
Conclusions :
I. At least some summers are rains.
II. At least some weathers are summers.

a

if only conclusion I follows.

b

if only conclusion II follows.

c

if either conclusion I or conclusion II follows

d

if neither conclusion I nor conclusion II follows.

e

if both conclusions I and II follow.

 Answer : Option B Explanation : (i) All tents are cabins $\Rightarrow$ Universal Affirmative (A-type). (ii) Some watches are rings $\Rightarrow$ Particular Affirmative (I-type). (iii) No string is a basket.$\; \Rightarrow$ Universal Negative (E-type). (iv) Some strings are not baskets $\Rightarrow$ Particular Negative (O type). Both the Premises are Particular Affirmative (I-type). No Conclusion follows from the two Particular Premises. Conclusion II is Converse of the second Premise.

15.  Statements :
Some glasses are tablets.
All machines are tablets.
Conclusions :
I. All tablets being machines is a possibility.
II. All machines being glasses is a possibility.

a

if only conclusion I follows.

b

if only conclusion II follows.

c

if either conclusion I or conclusion II follows

d

if neither conclusion I nor conclusion II follows.

e

if both conclusions I and II follow.

 Answer : Option D Explanation : (i) All tents are cabins $\Rightarrow$ Universal Affirmative (A-type). (ii) Some watches are rings $\Rightarrow$ Particular Affirmative (I-type). (iii) No string is a basket.$\; \Rightarrow$ Universal Negative (E-type). (iv) Some strings are not baskets $\Rightarrow$ Particular Negative (O type). A + I $\Rightarrow$ No Conclusion


text:
# Calculating number of independent trials needed for event to occur at least n times

Event occurs with probability $p$ every trial. What is the number $k$ of independent trials needed for event to occur no less than $N$ times with probability $q$ ?

What I've managed to express so far is probability $q$ through $p$ and $N$ (is this correct?):

$q = p^{k} + C^{k-1}_{k}p^{k-1}(1-p) + ... + C^{N}_{k}p^{N}(1-p)^{k-N}$

But would like to know how to analytically express what I need (I can solve it with numeric methods, ofc).

-
Small correction. You are very rarely going to be able to get equality to hold, so you should look for for when $q$ is greater than or equal to the expression on the right. Also, you have an $n$ when you mean to have $N$. Finally, and almost completely off topic, when you have a variable that only takes integer values, it is a somewhat standard convention to use one of the variables $i,j,k, \ell, m$, or $n$ (or $N$, in some cases). Seeing $p^x$ and then realizing that $x$ has to be an integer made me twitch for a few seconds. – Aaron Oct 17 '12 at 10:01
@Aaron: Thanks, corrected the problems. And it is indeed obvious that matching probabilities with equality operator wouldn't make much sense. – Violet Giraffe Oct 17 '12 at 10:13
Small correction to my comment. I wrote greater where I meant less than. I hope no great confusion arose. Also, thank you for changing the $x$'s to $k$'s. The formula looks a lot less confusing when I casually glance at it. – Aaron Oct 17 '12 at 10:48

This is not a solution, per se, but rather a heuristic you can use to narrow your search for the smallest number of trials you need. I do not think that there is an analytic solution, but rather just a large scale approximation which is quite useful.

Your trials can be viewed as a random variables which take the value $1$ with probability $p$ and the value $0$ with probability $1-p$. These have expected value $p$ and variance $p(1-p)$. By the central limit theorem, the sum of $k$ independent trials (i.e., the number of successful trials you've had) will be approximately normally distributed, with mean $kp$ and variance $kp(1-p)$. We want the probability that we have at least $N$ successes to be $q$ or greater. We can phrase this in terms of the standard error function.

Let $\mathcal N(\mu,\sigma^2)$ denote a normally distributed random variable with mean $\mu$ and variance $\sigma^2$. We want
$$q=P(\mathcal N(kp,kp(1-p))>N)=P(\mathcal N(0,kp(1-p))>N-kp)=P\left(\mathcal N(0,kp(1-p))>\frac{N-kp}{\sqrt{kp(1-p)}}\right).$$

However, $P(\mathcal N(0,1)>x)=\frac{1}{2}-\frac{1}{2}\operatorname{erf}(x/\sqrt{2})$, so we need to solve

$$\operatorname{erf}^{-1}(1-2q)=\frac{N-kp}{\sqrt{2kp(1-p)}}.$$

The left hand side is a constant which can be computed easily using many different computer packages. This reduces the problem to something more computationally feasible than computing the sum in the problem for various values of $k$.

-
Did you mean "take value 1 with probability p and value 0 with probability 1-p"? – Violet Giraffe Oct 17 '12 at 10:46
Yes. I have no idea how what I wrote ended up there. Fixing. – Aaron Oct 17 '12 at 10:49
Thanks, very interesting thinking! – Violet Giraffe Oct 17 '12 at 11:03

There's still something wrong with your formula; there's an $x$ that hasn't been introduced. Going by the text, you want

$$\sum_{j=N}^k\binom kjp^j(1-p)^{k-j}\;.$$

You're unlikely to find a closed form for this, since for $p=1/2$ this is proportional to a sum over the lower argument of a binomial coefficient, for which no closed form is known. See also Asymptotics for a partial sum of binomial coefficients.

-
Corrected the mysterious $x$ – Violet Giraffe Oct 17 '12 at 10:35


text:
# Some questions concerning the size of proper classes in ZFC

For some formulae $\phi(x)$ it can be proved from the axioms of ZFC, that there is no set $X$ with $(x)x\in X \equiv \phi(x)$. Thus the collection $\lbrace x\ |\ \phi(x)\rbrace$ is a proper class.

Furthermore, there is no set $Y$ that is in bijection with such a collection, right? Thus, every proper class must be in some sense larger than any set, right? ("too large to be a set")

For two formulae $\phi(x)$, $\psi(x)$, one of them defining a proper class, it may be possible two show that $(x) \phi(x) \equiv \psi(x)$. This means a) that also the second collection is a proper class, and b) that the two have equal size in some sense.

Can the notion of size of proper classes (or equipollency) be made precise? Is it possible that two proper classes do not have equal size in this sense? Would it thus follow, that there are smaller and larger proper classes? Or do all proper classes have the same size (of $V$)?

And - finally - can the size of $V$ be characterized? To talk at large, maybe like this (if sense of $P(V)$ could be made): $V$ is so large such that $|V| = |P(V)|$ (which never holds for sets)? (This would admittedly be counter-intuitive, since the discrepancy between $|X|$ and $|P(X)|$ grows with $|X|$.)

-
The descrepancy between $|X|$ and $|P(X)|$ only provably grows with $|X|$ for finite $X$. For infinite $|X|$, just about anything is possible (but not everything!). In particular, it can be the case that the generalized continuum hypothesis holds - that $|P(X)|$ is the very next size after $|X|$ for all infinite $|X|$. – Jason DeVito Feb 21 '11 at 16:06
But at least |X| < |P(X)| holds for all sets X, doesn't it? – Hans Stricker Feb 21 '11 at 16:08
You can say a bit more than that: you can say that |X|<|Y| implies |P(X)| <= |P(Y)| and you can add one minor technical condition about the cofinality of the power set, but (roughly) other than that, anything goes. – Steven Stadnicki Feb 22 '11 at 2:54

This question was asked at MO a while ago. Below I quote the relevant part of my answer. But let me add some comments.

In ZFC (proper) classes are not actual objects, we only treat them formally, and they are really just short-cuts for formulas (with parameters), i.e., we identify formulas $\phi(x)$ with the collection of sets that satisfy $\phi$.

This makes talking of relations between classes somewhat awkward. Arturo's nice answer, for example, indicates how one can make sense of, say, a bijection between two classes. A bit more formally, if $X$ is the class of $x$ such that $\phi(x)$ and $Y$ is the class of $y$ such that $\psi(y)$, then a bijection between $X$ and $Y$ is a class $Z$ given by a formula $\rho(x,y)$ such that:

1. For any $x,y,z$, if $\rho(x,y)$ and $\rho(x,z)$ then $y=z$.
2. Similarly, for any $x,y,z$, if$\rho(x,y)$ and $\rho(z,y)$, then $x=z$.
3. For any $x,y$, $\rho(x,y)$ implies that $\phi(x)$ and $\psi(y)$ holds.
4. For any $x$ such that $\phi(x)$ there is a $y$ such that $\rho(x,y)$.
5. And, for any $y$ such that $\psi(y)$, there is an $x$ such that $\rho(x,y)$.

This awkwardness also makes it impossible to develop an appropriate theory of classes. For example, the natural question: "Are $X$ and $Y$ pf the same size?" cannot even be asked in ZFC. Of, course, if there is a $\rho$ as above, then we can say that they have the same size, as witnessed by $Z$, and if there is no such $\rho$, outside of ZFC we can say that thy don't have the same size, but all we can do in ZFC is to say, of any given formula $\rho$, that $\rho$ does not define a bijection between $X$ and $Y$.

Of course, equipotency is only an example of what we cannot discuss freely about classes. Thus when interested in proper classes, we move from ZFC to other theories. There are (at least) two natural extensions of ZFC where classes can be treated as formal objects. One is NBG (Von Neumann-Bernays-Goedel). Here, the objects are classes, and sets are classes that belong to other classes. $Z$ is a bijection between $X$ and $Y$ iff $A$ is a function, its domain is $X$ and its range is $Y$ (just as with sets). NBG is usually preferred because it is a conservative extension of ZFC; in a sense, all we have done is to allow references to classes without changing what we mean by "set" in any way. Formally, any theorem of NBG that only mentions sets is a theorem of ZFC. And our interpretation of classes as given by formulas gives us a way of extending any model of ZFC to one of NBG.

The fact that NBG is conservative over ZFC is in a sense a serious limitation, as we limit the notion of class somewhat artificially. When discussing elementary embedding formulations of large cardinal axioms (something very common in modern set theory), for example, the discussion can be carried out in NBG, but not in the smoothest possible fashion. In technical terms, the comprehension axiom in NBG is predicative, but it is hard to justify this when we are allowing proper classes at all.

The most natural extension of ZFC to treat proper classes is Morse-Kelley (MK). Here, comprehension is unrestricted, so it is more natural to combine classes into new ones by usual operations. The cost of this is that MK is not a conservative extension of ZFC. In fact, MK can prove the consistency of NBG (and therefore of ZFC). That being said, to discuss equipotency of classes, MK seems the appropriate framework.

Here is what I said in the MO post mentioned above:

In extensions of set theory where classes are allowed (not just formally as in ZFC, but as actual objects as in MK or GB), sometimes it is suggested to add an axiom (due to Von Neumann, I believe) stating that any two classes are in bijection with one another. Under this axiom, the "cardinality" of a proper class would be ORD, the class of all ordinals. (By the way, by class forcing, given any proper class, one can add a bijection between the class and ORD without adding sets, so this assumption bears no implications for set theory proper.)

Without assuming Von Neumann's axiom, or the axiom of choice, I know of no sensible way of making sense of this notion, as now we could have some proper classes that are "thinner" than others, or even incomparable. Of course, we could study models where this happens (for example, work in ZF, assume there is a strong inaccessible $\kappa$, and consider $V_\kappa$ as the universe of sets, and $Def(V_\kappa)$ in Gödel's sense (or even $V_{\kappa+1}$) as the collection of classes).

Let me expand on this a bit. I argue in ZFC as this is the best known framework of the three mentioned above:

First, class forcing allows us to add a bijection between $V$ and $ORD$ without adding sets. Essentially, what we do is to "thread" through the class of bijections between sets and ordinals. In the resulting extension, we have added no sets, but we have a new class $G$. The resulting structure $(V,G,\in)$ is a model of the strong version of ZFC where we allow $G$ to appear as a predicate in instances of the replacement axiom. Also, any proper class $A$ here (in the sense of "definable by a formula") is also in bijection with the ordinals, and such a bijection is easily definable from $A$ and $G$.

This shows that the assumption that all classes have the same size is completely harmless: No new theorems of ZFC can be proved by adding this assumption.

The model we obtain is not a "natural" model of NBG, though, since G is not definable.

Arturo's suggestion ($V=L$) gives us models where bijections between classes and the ordinals are definable. It has the disadvantage that V=L is quite limiting. As I mentioned in the comments to his answer, there is an alternative: We can assume $G$ definable. This is because, over any model of ZFC, we can force to obtain a new model where $V=HOD$ (on the other hand, once $V\ne L$ we cannot force to have the equality back).

$HOD$ is the class of hereditarily ordinal definable sets. This means that $x\in HOD$ implies that $x\subset HOD$, and that to be in HOD, $x$ must be definable from ordinal parameters. Of course $V=L$ implies $V=HOD$, but $HOD$ is compatible with all known large cardinals, while $L$ is not. Moreover, $HOD$ carries a definable well-ordering (in order type ORD), so if $V=HOD$, then any proper class is in bijection with the ordinals. Moreover, $V=HOD$ is equivalent to the statement that there is a (definable) bijection between $V$ and $ORD$. So, at least in ZFC, this characterizes in a natural way when all proper classes have the same size (and it is really the only way that "sizes of proper classes" can be freely discussed in ZFC).

Finally, it is consistent that $V\ne HOD$, in which case $V$ and $ORD$ have different cardinality in the ZFC sense defined above, and in fact one can arrange that there are incomparable "sizes" of proper classes.

-
Thanks for the extended (and better than mine) answer. – Arturo Magidin Feb 21 '11 at 19:14
Definitely! If I had seen it, I would have marked it as a favorite question, but I didn't. Thus, I didn't have seen it. – Hans Stricker Feb 21 '11 at 19:44

Specifically, in an August 2006 post in sci.math, Herman Rubin said that if $\mathbf{V}=\mathbf{L}$ (Goedel's Constructible Universe), then every proper class is equipollent to (bijectable with) the class of all ordinals, hence equipollent with one another, so you only have a single "size" of proper classes.

However, he also said that there are models of ZFC with different versions of the Axiom of Choice for proper classes and in some of these not all proper classes are equipollent (even if you assume the Axiom of Choice for sets).

For completeness: what do we mean by equipollency of proper classes? Goedel defined equivalence of proper classes as follows: For proper classes $X$ and $Y$, $X\sim Y$ if and only if there exists $Z$ such that:

1. $Z$ is a relation (contained in $\mathbf{V}^2$);
2. $Z$ is twice unary ($Z$ is single-valued, and so is its inverse);
3. The domain of $Z$ is $X$; and
4. The domain of the inverse of $Z$ is $Y$.

One model where all proper classes are equipollent is when we assume the "Axiom of Global Choice", which states that there exists a unary relation $A$ such that for all nonempty sets $X$, there exists $y\in X$ such that $(X,y)\in A$. This is given by Goedel in his paper on the consistency of AC and GCH with ZF. It implies that any class is equipollent to an initial segment of the ordinals, and since any proper initial segment of the ordinals is a set, a proper class must be equipollent to the proper class of all ordinals, giving the result that all proper classes are equipollent.

-
Do I understand correctly: equivalence of proper classes depends on the existence of a set Z? – Hans Stricker Feb 21 '11 at 16:26
@Hans: The referred $Z$ is a class. – Asaf Karagila Feb 21 '11 at 16:36
@Hans: No, $Z$ is a proper class. Joel Hamkins has addressed this issue elsewhere on this site. More generally than V=L, what you need is precisely that V=HOD, the class of hereditarily ordinal definable sets. – Andrés E. Caicedo Feb 21 '11 at 16:37
@Andres: Do you mean this response? math.stackexchange.com/questions/9037/… If so, I'll add a link to the answer. – Arturo Magidin Feb 21 '11 at 16:41
Hi Arturo, I think... (Joel may have said something else in comments to another question as well). In any case: The point is: V=HOD gives a global (definable) well-ordering of the universe (in order type ORD). From this it follows that any proper class is in bijection with the ordinals. And, in ZF, V=HOD is equivalent to the existence of such bijection. (Part of the issue here is technical: In ZF, proper classes are given by formulas (with parameters). In other set theories like MK where proper classes need not be definable, a well-ordering of V does not imply V=HOD.) – Andrés E. Caicedo Feb 21 '11 at 16:50


text:
## Theory and numerics for multi-term periodic delay differential equations: small solutions and their detection

Neville J. Ford and Patricia M. Lumb

### Abstract

In this paper we consider scalar linear periodic delay differential equations of the form $x'(t)=\sum_{j=0}^{m}b_j(t)x(t-jw), x(t)=\phi(t) \mbox{ for } t \in [0,mw), \mbox{ } t\ge mw \quad (\ddagger) \label{ddagger}$ where $b_j$, $j=0,..., m$ are continuous periodic functions with period $w$. We summarise a theoretical treatment that analyses whether the equation has small solutions. We consider discrete equations that arise when a numerical method with fixed step-size is applied to approximate the solution to ($\ddagger$) and we develop a corresponding theory. Our results show that small solutions can be detected reliably by the numerical scheme. We conclude with some numerical examples.

Full Text (PDF) [393 KB]

### Key words

delay differential equations, small solutions, super-exponential solutions, numerical methods

### AMS subject classifications

34K28, 65P99, 37N30

< Back


text:
These data come from the years 1976-1982 in the Panel Study of Income Dynamics (PSID), with information about the demographics and earnings of 595 individuals.

WageData

## Format

A data frame with 4165 rows and 14 variables:

id

Unique identifier for each survey respondent

t

A number corresponding to each wave of the survey, 1 through 7

wks

Weeks worked in the past year

lwage

Natural logarithm of earnings in the past year

union

Binary indicator whether respondent is a member of union (1 = union member)

ms

Binary indicator for whether respondent is married (1 = married)

occ

Binary indicator for whether respondent is a blue collar (= 0) or white collar (= 1) worker.

ind

Binary indicator for whether respondent works in manufacturing (= 1)

south

Binary indicator for whether respondent lives in the South (= 1)

smsa

Binary indicator for whether respondent lives in a standard metropolitan area (SMSA; = 1)

fem

Binary indicator for whether respondent is female (= 1)

blk

Binary indicator for whether respondent is African-American (= 1)

ed

Years of education

exp

Years in the workforce.

## Source

These data are all over the place. This particular file was downloaded from Richard Williams at http://www3.nd.edu/~rwilliam/statafiles/wages.dta, though he doesn't claim ownership of these data.

The data were shared as a supplement to Baltagi (2005) at http://www.wiley.com/legacy/wileychi/baltagi3e/data_sets.html.

They were also shared as a supplement to Greene (2008) at http://pages.stern.nyu.edu/~wgreene/Text/Edition6/tablelist6.htm.

The data are also available in numerous other locations, including in slightly different formats as Wages in the plm package and PSID7682 in the AER package.


text:
# Useful series for limit comparison test

I already know the harmonic series ($1/n$, which diverges) and following the link, $1/n^2$ that converges.

What other useful series could you teach me, or perhaps some general advice? Any website/resource is very welcome also, since most of my search for them reveals only the harmonic one and not much more. (I know how to execute the test!).

Have a nice day!

-
Standard series for which convergence is known are: geometric series; $p$-series; any series that corresponds to an improper integral whose convergence you know; powers over factorials (e.g., $\frac{2^n}{n!}$), etc. The more series you figure out, the more you'll have in your portfolio to use for comparisons. – Arturo Magidin Feb 17 '11 at 19:28
Thanks for your share Arturo! – Qosmo Feb 17 '11 at 19:47

There is the generalization of what you put above, the so called $p$-series. Let $p\in \mathbb{R}$, then $$\sum_{n=1}^\infty \frac{1}{n^p}$$ converges if and only if $p>1$. This can be proven using the integral test mentioned by Shai Covo.

Also of interest are alternating series, such as $$\sum_{n=1}^\infty \frac{(-1)^n}{\sqrt{n}}$$ since there are good tests to see if they converge. (The above sum converges) Specifically, the alternating series test tells us that if we have a sequence $a_n$ with

(1) $a_n\cdot a_{n+1} <0$ for every $n$ (it alternates signs)

(2) $|a_{n+1}|\leq |a_n|$

(3) $\lim_{n\rightarrow \infty} a_n =0$

Then $\sum_{n=1}^\infty a_n$ converges. This then brings up the topic of Conditional and Absolute convergence. For a generalization of the alternating series test, see Dirichlets Test. (This test allows us to give the conditions of convergence for series such as $\sum_{n=1}^\infty a_n \sin (n)$)

Hope that helps,

-

General advice: consider the integral test for convergence. As an exercise, apply it to the series $\sum\limits_{n = 2}^\infty {\frac{1}{{n(\log n)^\alpha }}}$, $\alpha > 0$ fixed. For which $\alpha$ does the series coverge?

Another very useful test is the alternating series test. See also convergence tests.

-
Sorry to ruin your answer. We don't cover integral test in our course. :( – Qosmo Feb 17 '11 at 19:46