text:
# Algorithms Reference Classification

## Multinomial Logistic Regression

### Description

The MultiLogReg.dml script performs both binomial and multinomial logistic regression. The script is given a dataset $(X, Y)$ where matrix $X$ has $m$ columns and matrix $Y$ has one column; both $X$ and $Y$ have $n$ rows. The rows of $X$ and $Y$ are viewed as a collection of records: $(X, Y) = (x_i, y_i)_{i=1}^n$ where $x_i$ is a numerical vector of explanatory (feature) variables and $y_i$ is a categorical response variable. Each row $x_i$ in $X$ has size $\dim x_i = m$, while its corresponding $y_i$ is an integer that represents the observed response value for record $i$.

The goal of logistic regression is to learn a linear model over the feature vector $x_i$ that can be used to predict how likely each categorical label is expected to be observed as the actual $y_i$. Note that logistic regression predicts more than a label: it predicts the probability for every possible label. The binomial case allows only two possible labels, the multinomial case has no such restriction.

Just as linear regression estimates the mean value $\mu_i$ of a numerical response variable, logistic regression does the same for category label probabilities. In linear regression, the mean of $y_i$ is estimated as a linear combination of the features: $\mu_i = \beta_0 + \beta_1 x_{i,1} + \ldots + \beta_m x_{i,m} = \beta_0 + x_i\beta_{1:m}$. In logistic regression, the label probability has to lie between 0 and 1, so a link function is applied to connect it to $\beta_0 + x_i\beta_{1:m}$. If there are just two possible category labels, for example 0 and 1, the logistic link looks as follows:

$Prob[y_i\,{=}\,1\mid x_i; \beta] \,=\, \frac{e^{\,\beta_0 + x_i\beta_{1:m}}}{1 + e^{\,\beta_0 + x_i\beta_{1:m}}}; \quad Prob[y_i\,{=}\,0\mid x_i; \beta] \,=\, \frac{1}{1 + e^{\,\beta_0 + x_i\beta_{1:m}}}$

Here category label 0 serves as the baseline, and function $\exp(\beta_0 + x_i\beta_{1:m})$ shows how likely we expect to see “$y_i = 1$” in comparison to the baseline. Like in a loaded coin, the predicted odds of seeing 1 versus 0 are $\exp(\beta_0 + x_i\beta_{1:m})$ to 1, with each feature $x_{i,j}$ multiplying its own factor $\exp(\beta_j x_{i,j})$ to the odds. Given a large collection of pairs $(x_i, y_i)$, $i=1\ldots n$, logistic regression seeks to find the $\beta_j$’s that maximize the product of probabilities $Prob[y_i\mid x_i; \beta]$ for actually observed $y_i$-labels (assuming no regularization).

Multinomial logistic regression [Agresti2002] extends this link to $k \geq 3$ possible categories. Again we identify one category as the baseline, for example the $k$-th category. Instead of a coin, here we have a loaded multisided die, one side per category. Each non-baseline category $l = 1\ldots k\,{-}\,1$ has its own vector $(\beta_{0,l}, \beta_{1,l}, \ldots, \beta_{m,l})$ of regression parameters with the intercept, making up a matrix $B$ of size $(m\,{+}\,1)\times(k\,{-}\,1)$. The predicted odds of seeing non-baseline category $l$ versus the baseline $k$ are $\exp\big(\beta_{0,l} + \sum\nolimits_{j=1}^m x_{i,j}\beta_{j,l}\big)$ to 1, and the predicted probabilities are:

$$$l < k: Prob [y_i {=} l \mid x_i; B] \,\,\,{=}\,\,\, \frac{\exp\big(\beta_{0,l} + \sum\nolimits_{j=1}^m x_{i,j}\beta_{j,l}\big)}{1 \,+\, \sum_{l'=1}^{k-1}\exp\big(\beta_{0,l'} + \sum\nolimits_{j=1}^m x_{i,j}\beta_{j,l'}\big)};$$$ $$$Prob [y_i {=} k \mid x_i; B] \,\,\,{=}\,\,\, \frac{1}{1 \,+\, \sum_{l'=1}^{k-1}\exp\big(\beta_{0,l'} + \sum\nolimits_{j=1}^m x_{i,j}\beta_{j,l'}\big)}.$$$

The goal of the regression is to estimate the parameter matrix $B$ from the provided dataset $(X, Y) = (x_i, y_i)_{i=1}^n$ by maximizing the product of $Prob[y_i\mid x_i; B]$ over the observed labels $y_i$. Taking its logarithm, negating, and adding a regularization term gives us a minimization objective:

$$$f(B; X, Y) \,\,=\,\, -\sum_{i=1}^n \,\log Prob[y_i\mid x_i; B] \,+\, \frac{\lambda}{2} \sum_{j=1}^m \sum_{l=1}^{k-1} |\beta_{j,l}|^2 \,\,\to\,\,\min$$$

The optional regularization term is added to mitigate overfitting and degeneracy in the data; to reduce bias, the intercepts $\beta_{0,l}$ are not regularized. Once the $\beta_{j,l}$’s are accurately estimated, we can make predictions about the category label $y$ for a new feature vector $x$ using Eqs. (1) and (2).

#### Table 5

: The Log file for multinomial logistic regression contains the following iteration variables in CSV format, each line containing triple (Name, Iteration#, Value) with Iteration# being 0 for initial values.

Name Meaning
LINEAR_TERM_MIN The minimum value of $X$ %*% $B$, used to check for overflows
LINEAR_TERM_MAX The maximum value of $X$ %*% $B$, used to check for overflows
NUM_CG_ITERS Number of inner (Conj. Gradient) iterations in this outer iteration
IS_TRUST_REACHED $1 = {}$trust region boundary was reached, $0 = {}$otherwise
POINT_STEP_NORM L2-norm of iteration step from old point (matrix $B$) to new point
OBJECTIVE The loss function we minimize (negative regularized log-likelihood)
OBJ_DROP_REAL Reduction in the objective during this iteration, actual value
OBJ_DROP_PRED Reduction in the objective predicted by a quadratic approximation
OBJ_DROP_RATIO Actual-to-predicted reduction ratio, used to update the trust region
IS_POINT_UPDATED $1 = {}$new point accepted; $0 = {}$new point rejected, old point restored
GRADIENT_NORM L2-norm of the loss function gradient (omitted if point is rejected)
RUST_DELTA Updated trust region size, the “delta”

### Details

We estimate the logistic regression parameters via L2-regularized negative log-likelihood minimization (3). The optimization method used in the script closely follows the trust region Newton method for logistic regression described in [Lin2008]. For convenience, let us make some changes in notation:

• Convert the input vector of observed category labels into an indicator matrix $Y$ of size $n \times k$ such that $Y_{i, l} = 1$ if the $i$-th category label is $l$ and $Y_{i, l} = 0$ otherwise.
• Append an extra column of all ones, i.e. $(1, 1, \ldots, 1)^T$, as the $m\,{+}\,1$-st column to the feature matrix $X$ to represent the intercept.
• Append an all-zero column as the $k$-th column to $B$, the matrix of regression parameters, to represent the baseline category.
• Convert the regularization constant $\lambda$ into matrix $\Lambda$ of the same size as $B$, placing 0’s into the $m\,{+}\,1$-st row to disable intercept regularization, and placing $\lambda$’s everywhere else.

Now the ($n\,{\times}\,k$)-matrix of predicted probabilities given by (1) and (2) and the objective function $f$ in (3) have the matrix form

\begin{aligned} P \,\,&=\,\, \exp(XB) \,\,/\,\, \big(\exp(XB)\,1_{k\times k}\big)\\ f \,\,&=\,\, - \,\,{\textstyle\sum} \,\,Y \cdot (X B)\, + \, {\textstyle\sum}\,\log\big(\exp(XB)\,1_{k\times 1}\big) \,+ \, (1/2)\,\, {\textstyle\sum} \,\,\Lambda \cdot B \cdot B\end{aligned}

where operations $\cdot\,$, /, exp, and log are applied cellwise, and $\textstyle\sum$ denotes the sum of all cells in a matrix. The gradient of $f$ with respect to $B$ can be represented as a matrix too:

$\nabla f \,\,=\,\, X^T (P - Y) \,+\, \Lambda \cdot B$

The Hessian $\mathcal{H}$ of $f$ is a tensor, but, fortunately, the conjugate gradient inner loop of the trust region algorithm in [Lin2008] does not need to instantiate it. We only need to multiply $\mathcal{H}$ by ordinary matrices of the same size as $B$ and $\nabla f$, and this can be done in matrix form:

$\mathcal{H}V \,\,=\,\, X^T \big( Q \,-\, P \cdot (Q\,1_{k\times k}) \big) \,+\, \Lambda \cdot V, \,\,\,\,\textrm{where}\,\,\,\,Q \,=\, P \cdot (XV)$

At each Newton iteration (the outer iteration) the minimization algorithm approximates the difference $\varDelta f(S; B) = f(B + S; X, Y) \,-\, f(B; X, Y)$ attained in the objective function after a step $B \mapsto B\,{+}\,S$ by a second-degree formula

$\varDelta f(S; B) \,\,\,\approx\,\,\, (1/2)\,\,{\textstyle\sum}\,\,S \cdot \mathcal{H}S \,+\, {\textstyle\sum}\,\,S\cdot \nabla f$

This approximation is then minimized by trust-region conjugate gradient iterations (the inner iterations) subject to the constraint

$\|S\|_2 \leq \delta$

The trust region size $\delta$ is initialized as $0.5\sqrt{m}\,/ \max_i |x_i|_2$ and updated as described in [Lin2008]. Users can specify the maximum number of the outer and the inner iterations with input parameters moi and mii, respectively. The iterative minimizer terminates successfully if

$\|\nabla f\|_2 < \varepsilon \|\nabla f_{B=0} \|_2$

, where ${\varepsilon}> 0$ is a tolerance supplied by the user via input parameter tol.

### Returns

The estimated regression parameters (the $$.\hat{\beta}_{j, l}$$ ) are populated into a matrix and written to an HDFS file whose path/name was provided as the B input argument. Only the non-baseline categories ($1\leq l \leq k\,{-}\,1$) have their $\hat{\beta}{j, l}$ in the output; to add the baseline category, just append a column of zeros. If icpt=0 in the input command line, no intercepts are used and B has size $m\times (k\,{-}\,1)$; otherwise B has size $(m\,{+}\,1)\times (k\,{-}\,1)$ and the intercepts are in the $m\,{+}\,1$-st row. If icpt=2, then initially the feature columns in $X$ are shifted to mean${} = 0$ and rescaled to variance${} = 1$. After the iterations converge, the $\hat{\beta}{j, l}$’s are rescaled and shifted to work with the original features.

## Support Vector Machines

### Binary-Class Support Vector Machines

#### Binary SVM Description

Support Vector Machines are used to model the relationship between a categorical dependent variable y and one or more explanatory variables denoted X. This implementation learns (and predicts with) a binary class support vector machine (y with domain size 2).

#### Binary SVM Details

Support vector machines learn a classification function by solving the following optimization problem ($L_2$-SVM):

\begin{aligned} &\textrm{argmin}_w& \frac{\lambda}{2} ||w||_2^2 + \sum_i \xi_i^2\\ &\textrm{subject to:}& y_i w^{\top} x_i \geq 1 - \xi_i ~ \forall i\end{aligned}

where $x_i$ is an example from the training set with its label given by $y_i$, $w$ is the vector of parameters and $\lambda$ is the regularization constant specified by the user.

To account for the missing bias term, one may augment the data with a column of constants which is achieved by setting the intercept argument to 1 [Hsieh2008].

This implementation optimizes the primal directly [Chapelle2007]. It uses nonlinear conjugate gradient descent to minimize the objective function coupled with choosing step-sizes by performing one-dimensional Newton minimization in the direction of the gradient.

#### Binary SVM Returns

The learnt weights produced by l2-svm.dml are populated into a single column matrix and written to file on HDFS (see model in section Arguments). The number of rows in this matrix is ncol(X) if intercept was set to 0 during invocation and ncol(X) + 1 otherwise. The bias term, if used, is placed in the last row. Depending on what arguments are provided during invocation, l2-svm-predict.dml may compute one or more of scores, accuracy and confusion matrix in the output format specified.

### Multi-Class Support Vector Machines

#### Multi SVM Description

Support Vector Machines are used to model the relationship between a categorical dependent variable y and one or more explanatory variables denoted X. This implementation supports dependent variables that have domain size greater or equal to 2 and hence is not restricted to binary class labels.

#### Multi SVM Details

Support vector machines learn a classification function by solving the following optimization problem ($L_2$-SVM):

\begin{aligned} &\textrm{argmin}_w& \frac{\lambda}{2} ||w||_2^2 + \sum_i \xi_i^2\\ &\textrm{subject to:}& y_i w^{\top} x_i \geq 1 - \xi_i ~ \forall i\end{aligned}

where $x_i$ is an example from the training set with its label given by $y_i$, $w$ is the vector of parameters and $\lambda$ is the regularization constant specified by the user.

To extend the above formulation (binary class SVM) to the multiclass setting, one standard approach is to learn one binary class SVM per class that separates data belonging to that class from the rest of the training data (one-against-the-rest SVM, see [Scholkopf1995]).

To account for the missing bias term, one may augment the data with a column of constants which is achieved by setting intercept argument to 1 [Hsieh2008].

This implementation optimizes the primal directly [Chapelle2007]. It uses nonlinear conjugate gradient descent to minimize the objective function coupled with choosing step-sizes by performing one-dimensional Newton minimization in the direction of the gradient.

#### Multi SVM Returns

The learnt weights produced by m-svm.dml are populated into a matrix that has as many columns as there are classes in the training data, and written to file provided on HDFS (see model in section Arguments). The number of rows in this matrix is ncol(X) if intercept was set to 0 during invocation and ncol(X) + 1 otherwise. The bias terms, if used, are placed in the last row. Depending on what arguments are provided during invocation, m-svm-predict.dml may compute one or more of scores, accuracy and confusion matrix in the output format specified.

## Naive Bayes

### Naive Bayes Description

Naive Bayes is very simple generative model used for classifying data. This implementation learns a multinomial naive Bayes classifier which is applicable when all features are counts of categorical values.

### Naive Bayes Details

Naive Bayes is a very simple generative classification model. It posits that given the class label, features can be generated independently of each other. More precisely, the (multinomial) naive Bayes model uses the following equation to estimate the joint probability of a feature vector $x$ belonging to class $y$:

$\text{Prob}(y, x) = \pi_y \prod_{i \in x} \theta_{iy}^{n(i,x)}$

where $\pi_y$ denotes the prior probability of class $y$, $i$ denotes a feature present in $x$ with $n(i,x)$ denoting its count and $\theta_{iy}$ denotes the class conditional probability of feature $i$ in class $y$. The usual constraints hold on $\pi$ and $\theta$:

\begin{aligned} && \pi_y \geq 0, ~ \sum_{y \in \mathcal{C}} \pi_y = 1\\ \forall y \in \mathcal{C}: && \theta_{iy} \geq 0, ~ \sum_i \theta_{iy} = 1\end{aligned}

where $\mathcal{C}$ is the set of classes.

Given a fully labeled training dataset, it is possible to learn a naive Bayes model using simple counting (group-by aggregates). To compute the class conditional probabilities, it is usually advisable to avoid setting $\theta_{iy}$ to 0. One way to achieve this is using additive smoothing or Laplace smoothing. Some authors have argued that this should in fact be add-one smoothing. This implementation uses add-one smoothing by default but lets the user specify her/his own constant, if required.

This implementation is sometimes referred to as multinomial naive Bayes. Other flavours of naive Bayes are also popular.

### Naive Bayes Returns

The learnt model produced by naive-bayes.dml is stored in two separate files. The first file stores the class prior (a single-column matrix). The second file stores the class conditional probabilities organized into a matrix with as many rows as there are class labels and as many columns as there are features. Depending on what arguments are provided during invocation, naive-bayes-predict.dml may compute one or more of probabilities, accuracy and confusion matrix in the output format specified.

## Decision Trees

### Decision Trees Description

Decision tree (for classification) is a classifier that is considered more interpretable than other statistical classifiers. This implementation is well-suited to handle large-scale data and builds a (binary) decision tree in parallel.

### Decision Trees Details

Decision trees [BreimanFOS1984] are simple models of classification that, due to their structure, are easy to interpret. Given an example feature vector, each node in the learned tree runs a simple test on it. Based on the result of the test, the example is either diverted to the left subtree or to the right subtree. Once the example reaches a leaf, then the label stored at the leaf is returned as the prediction for the example.

Building a decision tree from a fully labeled training set entails choosing appropriate splitting tests for each internal node in the tree and this is usually performed in a top-down manner. The splitting test (denoted by $s$) requires first choosing a feature $j$ and depending on the type of $j$, either a threshold $\sigma$, in case $j$ is continuous-valued, or a subset of values $S \subseteq \text{Dom}(j)$ where $\text{Dom}(j)$ denotes domain of $j$, in case it is categorical. For continuous-valued features the test is thus of form $x_j < \sigma$ and for categorical features it is of form $x_j \in S$, where $x_j$ denotes the $j$th feature value of feature vector $x$. One way to determine which test to include, is to compare impurities of the tree nodes induced by the test. The node impurity measures the homogeneity of the labels at the node. This implementation supports two commonly used impurity measures (denoted by $\mathcal{I}$): Entropy $\mathcal{E}=\sum_{i=1}^{C}-f_i \log f_i$, as well as Gini impurity $\mathcal{G}=\sum_{i=1}^{C}f_i (1-f_i)$, where $C$ denotes the number of unique labels and $f_i$ is the frequency of label $i$. Once the impurity at the tree nodes has been obtained, the best split is chosen from a set of possible splits that maximizes the information gain at the node, i.e., $\arg\max_{s}\mathcal{IG}(X,s)$, where $\mathcal{IG}(X,s)$ denotes the information gain when the splitting test $s$ partitions the feature matrix $X$. Assuming that $s$ partitions $X$ that contains $N$ feature vectors into $X_\text{left}$ and $X_\text{right}$ each including $N_\text{left}$ and $N_\text{right}$ feature vectors, respectively, $\mathcal{IG}(X,s)$ is given by

$\mathcal{IG}(X,s)=\mathcal{I}(X)-\frac{N_\text{left}}{N}\mathcal{I}(X_\text{left})-\frac{N_\text{right}}{N}\mathcal{I}(X_\text{right})$

where $\mathcal{I}\in{\mathcal{E},\mathcal{G}}$. In the following we discuss the implementation details specific to decision-tree.dml.

Input format. In general implementations of the decision tree algorithm do not require categorical features to be dummy coded. For improved efficiency and reducing the training time, our implementation however assumes dummy coded categorical features and dummy coded class labels.

Tree construction. Learning a decision tree on large-scale data has received some attention in the literature. The current implementation includes logic for choosing tests for multiple nodes that belong to the same level in the decision tree in parallel (breadth-first expansion) and for building entire subtrees under multiple nodes in parallel (depth-first subtree building). Empirically it has been demonstrated that it is advantageous to perform breadth-first expansion for the nodes belonging to the top levels of the tree and to perform depth-first subtree building for nodes belonging to the lower levels of the tree [PandaHBB2009]. The parameter num_samples controls when we switch to depth-first subtree building. Any node in the decision tree that receives $\leq$ num_samples training examples, the subtree under it is built in its entirety in one shot.

Stopping rule and pruning. The splitting of data at the internal nodes stops when at least one the following criteria is satisfied:

• the depth of the internal node reaches the input parameter depth controlling the maximum depth of the learned tree, or
• no candidate split achieves information gain.

This implementation also allows for some automated pruning via the argument num_leaf. If a node receives $\leq$ num_leaf training examples, then a leaf is built in its place.

Continuous-valued features. For a continuous-valued feature $j$ the number of candidate thresholds $\sigma$ to choose from is of the order of the number of examples present in the training set. Since for large-scale data this can result in a large number of candidate thresholds, the user can limit this number via the arguments bins which controls the number of candidate thresholds considered for each continuous-valued feature. For each continuous-valued feature, the implementation computes an equi-height histogram to generate one candidate threshold per equi-height bin.

Categorical features. In order to determine the best value subset to split on in the case of categorical features, this implementation greedily includes values from the feature’s domain until the information gain stops improving. In particular, for a categorical feature $j$ the $|Dom(j)|$ feature values are sorted by impurity and the resulting split candidates $|Dom(j)|-1$ are examined; the sequence of feature values which results in the maximum information gain is then selected.

Description of the model. The learned decision tree is represented in a matrix $M$ that contains at least 6 rows. Each column in the matrix contains the parameters relevant to a single node in the tree. Note that for building the tree model, our implementation splits the feature matrix $X$ into $X_\text{cont}$ containing continuous-valued features and $X_\text{cat}$ containing categorical features. In the following, the continuous-valued (resp. categorical) feature-ids correspond to the indices of the features in $X_\text{cont}$ (resp. $X_\text{cat}$). Moreover, we refer to an internal node as a continuous-valued (categorical) node if the feature that this nodes looks at is continuous-valued (categorical). Below is a description of what each row in the matrix contains.

• Row 1: stores the node-ids. These ids correspond to the node-ids in a complete binary tree.
• Row 2: for internal nodes stores the offsets (the number of columns) in $M$ to the left child, and otherwise 0.
• Row 3: stores the feature index of the feature (id of a continuous-valued feature in $X_\text{cont}$ if the feature is continuous-valued or id of a categorical feature in $X_\text{cat}$ if the feature is categorical) that this node looks at if the node is an internal node, otherwise 0.
• Row 4: store the type of the feature that this node looks at if the node is an internal node: 1 for continuous-valued and 2 for categorical features, otherwise the label this leaf node is supposed to predict.
• Row 5: for the internal nodes contains 1 if the feature chosen for the node is continuous-valued, or the size of the subset of values used for splitting at the node stored in rows 6,7,$\ldots$ if the feature chosen for the node is categorical. For the leaf nodes, Row 5 contains the number of misclassified training examples reaching at this node.
• Row 6,7,$\ldots$: for the internal nodes, row 6 stores the threshold to which the example’s feature value is compared if the feature chosen for this node is continuous-valued, otherwise if the feature chosen for this node is categorical rows 6,7,$\ldots$ store the value subset chosen for the node. For the leaf nodes, row 6 contains 1 if the node is impure and the number of training examples at the node is greater than num_leaf, otherwise 0.

As an example, Figure 2 shows a decision tree with $5$ nodes and its matrix representation.

#### Figure 2

Figure 2: (a) An example tree and its (b) matrix representation. $x$ denotes an example and $x_j$ is the value of the $j$th continuous-valued (resp. categorical) feature in $X_\text{cont}$ (resp. $X_\text{cat}$). In this example all leaf nodes are pure and no training example is misclassified.

(a)

(b)

Col 1 Col 2 Col 3 Col 4 Col 5
Row 1 1 2 3 6 7
Row 2 1 0 1 0 0
Row 3 3 0 5 0 0
Row 4 1 1 2 2 1
Row 5 1 0 2 0 0
Row 6 0.45 0 2 0 0
Row 7     3

### Decision Trees Returns

The matrix corresponding to the learned model as well as the training accuracy (if requested) is written to a file in the format specified. See details where the structure of the model matrix is described. Recall that in our implementation $X$ is split into $X_\text{cont}$ and $X_\text{cat}$. If requested, the mappings of the continuous-valued feature-ids in $X_\text{cont}$ (stored at S_map) and the categorical feature-ids in $X_\text{cat}$ (stored at C_map) to the global feature-ids in $X$ will be provided. Depending on what arguments are provided during invocation, the decision-tree-predict.dml script may compute one or more of predictions, accuracy and confusion matrix in the requested output format.

## Random Forests

### Random Forests Description

Random forest is one of the most successful machine learning methods for classification and regression. It is an ensemble learning method that creates a model composed of a set of tree models. This implementation is well-suited to handle large-scale data and builds a random forest model for classification in parallel.

### Random Forests Details

Random forests [Breiman2001] are learning algorithms for ensembles of decision trees. The main idea is to build a number of decision trees on bootstrapped training samples, i.e., by taking repeatedly samples from a (single) training set. Moreover, instead of considering all the features when building the trees only a random subset of the features—typically $\approx \sqrt{D}$, where $D$ is the number of features—is chosen each time a split test at a tree node is performed. This procedure decorrelates the trees and makes it less prone to overfitting. To build decision trees we utilize the techniques discussed in Decision Trees and proposed in [PandaHBB2009]; the implementation details are similar to those of the decision trees script. Below we review some features of our implementation which differ from decision-tree.dml.

Bootstrapped sampling. Each decision tree is fitted to a bootstrapped training set sampled with replacement (WR). To improve efficiency, we generate $N$ sample counts according to a Poisson distribution with parameter subsamp_rate, where $N$ denotes the total number of training points. These sample counts approximate WR sampling when $N$ is large enough and are generated upfront for each decision tree.

Bagging. Decision trees suffer from high variance resulting in different models whenever trained on a random subsets of the data points. Bagging is a general-purpose method to reduce the variance of a statistical learning method like decision trees. In the context of decision trees (for classification), for a given test feature vector the prediction is computed by taking a majority vote: the overall prediction is the most commonly occurring class among all the tree predictions.

Out-Of-Bag error estimation. Note that each bagged tree in a random forest model is trained on a subset (around $\frac{2}{3}$) of the observations (i.e., feature vectors). The remaining ($\frac{1}{3}$ of the) observations not used for training is called the Out-Of-Bag (OOB) observations. This gives us a straightforward way to estimate the test error: to predict the class label of each test observation $i$ we use the trees in which $i$ was OOB. Our random-forest-predict.dml script provides the OOB error estimate for a given training set if requested.

Description of the model. Similar to decision trees, the learned random forest model is presented in a matrix $M$ with at least 7 rows. The information stored in the model is similar to that of decision trees with the difference that the tree-ids are stored in the second row and rows $2,3,\ldots$ from the decision tree model are shifted by one. See Decision Trees for a description of the model.

### Random Forests Returns

The matrix corresponding to the learned model is written to a file in the format specified. See Decision Trees where the details about the structure of the model matrix is described. Similar to decision-tree.dml, $X$ is split into $X_\text{cont}$ and $X_\text{cat}$. If requested, the mappings of the continuous feature-ids in $X_\text{cont}$ (stored at S_map) as well as the categorical feature-ids in $X_\text{cat}$ (stored at C_map) to the global feature-ids in $X$ will be provided. The random-forest-predict.dml script may compute one or more of predictions, accuracy, confusion matrix, and OOB error estimate in the requested output format depending on the input arguments used.


text:
# 4 L is Drawn from a Container Full of Milk and Then is Filled with Water. this Operation is Performed Three More Times. the Ratio of the Quantity of Milk Left in the Container and that of Water is 16 - Mathematics

MCQ

4 L is drawn from a container full of milk and then is filled with water. This operation is performed three more times. The ratio of the quantity of milk left in the container and that of water is 16 : 65. How much milk did the container hold initially?

• 24L

• 12L

• 15L

• 25 L

#### Solution

12 L

Explanation:
According to the formula,
After n operations, the quantity of pure liquid

= ["a"(1 - "b"/"a")^"n"] units

Here, b = 4, n = 4, a = ?
Quantity of milk left in the container after four operations = ["a"(1 - 4/"a")^"n"]L

Then, according to the question,

"Quantity of milk left"/"Quantity of water" = 16/81

⇒ (a[(1-4/a)^4])/a=16/(65+16)=16/81

⇒ (1-4/a)^4=16/81

⇒ 1-4/a=2/3

⇒ 4/a=1/3

∴ a = 12L

Concept: Ratio and Proportion (Entrance Exam)
Is there an error in this question or solution?

format: plain


text:
Le proposte di nuovi seminari vanno inviate al Prof. Sandro Coriasco - sandro.coriasco[AT]unito.it o alla Prof.ssa Vivina Barutello - vivina.barutello[AT]unito.it

E' possibile tenere i seminari, e/o parteciparvi, anche tramite applicativi di web-conferencing, previo accordo con gli organizzatori

# SEMINARI DI ANALISI MATEMATICA

## Evento

Titolo:
The Fisher-KPP problem with doubly nonlinear diffusion
Quando:
11.11.2016 13.30 h
Dove:
Palazzo Campana - Torino
Aula:
Aula S
Relatore:
Dott. Alessandro Audrito
Afferenza:
Dipartimento di Matematica, Università degli Studi di Torino
Proponente:
V. Barutello, S. Coriasco
Locandina:

## Descrizione

The famous Fisher-KPP reaction-diffusion model combines linear diffusion with the typical KPP reaction term, and appears in a number of relevant applications in biology and chemistry. It is remarkable as a mathematical model since it possesses a family of travelling waves that describe the asymptotic behaviour of a large class solutions $$0\le u(x,t)\le 1$$ of the problem posed in the real line. The existence of propagation waves with finite speed has been confirmed in some related models and disproved in others.
We investigate here the corresponding theory when the linear diffusion is replaced by the "slow'' and "fast'' doubly nonlinear diffusion. In the first case, we find travelling waves that represent the wave propagation of more general solutions even when we extend the study to several space dimensions (we show a TW asymptotic behaviour also in the critical case that we call "pseudo-linear'', i.e., when the operator is still nonlinear but has homogeneity one. In the second one, we prove the non-existence of travelling waves while the propagation is exponentially fast in space for large times. Moreover, in the "fast'' diffusion case, we show precise bounds for the level sets of general solutions.

## Sede

Sede:
Palazzo Campana   -   Sito web
Via:
Via Carlo Alberto, 10
Cap:
10123
Città:
Torino
Provincia:
To
Paese:

## Descrizione

Dipartimento di Matematica, Università degli Studi di Torino


text: If you are among those who have struggled the last few years in the aviation industry it may seem hard to give thanks. Lets take a minute to consider a few things.  If you are still in aviation after the hit the industry has taken, you should be giving thanks.  If you still have a job as a pilot or mechanic, you should be giving thanks.  If you still get up in the morning going to a “job” you love, you should be giving thanks.  The fact we still have a country where we have the freedom that we do, you should be giving thanks.  More importantly than any of these things, is the fact that God, the Creator of everything would send HIS Son here to die for our sins, and for that we can truly give thanks.  Psalm 118:1 – O give thanks unto the LORD; for he is good: because his mercy endureth for ever. (KJV)


text:
# Responsivity of photodetector

a) Define the responsivity $\rho$ and quantum efficiency $\eta$ of a photo-detector and show that they are related by

$\rho= (\eta*e*\lambda)/(h c)$

(b) For $0.92 eV$ photons, a photodiode has responsivity $0.35 A/W$. Calculate the quantum efficiency of the photo-diode.

a)

Responsivityis kind of the “total efficiency” of a photo-detector.

Its precise definition: it is the rapport between the output electric current over the input power of photons.

If we multiply the Responsivity with the output Voltage we obtain EXACTLY the total efficiency of the photo-detector.

$\mathbf{\rho =\frac{I(out)}{P(in)}}$

$P(in) =\frac{N}{t}*h\nu =\frac{N}{t}*\frac{h c}{\lambda}$

For $N$ incoming photons there are generated $\eta*N$ electrons. Therefore

$\rho = \frac{\eta*e}{h\nu}=\frac{\eta*e\lambda}{h c}$

b)

If the energy of the incoming photon is $E =(h c)/\lambda= 0.92 eV$ then the quantum efficiency is

$\eta =\frac{h c}{\lambda}*\frac{1}{e}*\rho =0.92*0.35=0.322$


text:
Students can download Maths Chapter 4 Geometry Ex 4.5 Questions and Answers, Notes, Samacheer Kalvi 9th Maths Guide Pdf helps you to revise the complete Tamilnadu State Board New Syllabus, helps students complete homework assignments and to score high marks in board exams.

## Tamilnadu Samacheer Kalvi 9th Maths Solutions Chapter 4 Geometry Ex 4.5

Question 1.
Construct the ΔLMN such that LM = 7.5 cm, MN = 5cm and LN = 8cm. Locate its centroid.
Solution:

Steps for construction:
Step 1: Draw the ΔLMN using the given measurement LM = 7.5 cm, MN = 5cm and LN = 8cm.
Step 2: Construct the perpendicular bisectors of any two sides LM and MN intersect LM at P and MN at Q respectively.
Step 3: Draw the median LQ and PN meet at G.
The point G is the centroid of the given ΔLMN.

Question 2.
Draw and locate the centroid of the triangle ABC where right angle at A, AB = 4cm and AC = 3 cm.
Solution:

Steps for construction:
Step 1: Draw the ΔABC using the given measurement AB = 4cm and AC = 3 cm and ZA = 90°.
Step 2: Construct the perpendicular bisectors of any two sides AB and AC to find the mid-points P and Q of AB and AC.
Step 3: Draw the medians PC and BQ intersect at G.
The point G is the centroid of the given ΔABC.

Question 3.
Draw the ΔABC, where AB = 6cm, ∠B = 110° and AC = 9cm and construct the centroid.
Solution:

Steps for construction:
Step 1: Draw the ΔABC using the given measurement AB = 6cm, AC = 9cm and ∠B =110°.
Step 2: Construct the perpendicular bisectors of any two sides AB and BC to find the mid-points P and Q of AB and BC.
Step 3: Draw the medians PC and AQ intersect at G.
The point G is the centroid of the given ΔABC.

Question 4.
Construct the ΔPQR such that PQ = 5cm, PR = 6cm and ∠QPR = 60° and locate its centroid.
Solution:

Steps for construction:
Step 1 : Draw ΔPQR using the given measurements PQ = 5cm, PR = 6cm and ∠P = 60°.
Step 2 : Construct the perpendicular bisectors of any two sides PQ and QR to find the mid-points of M and N respectively.
Step 3 : Draw the median PN and MR and let them meet at G.
The point G is the centroid of the given ΔPQR.

Question 5.
Draw ΔPQR with sides PQ = 7 cm, QR = 8 cm and PR = 5 cm and construct its Orthocentre.
Solution:

Steps for construction:
Step 1: Draw the ΔPQR with the given measurements.
Step 2: Construct altitudes from any two vertices P and Q to their opposite sides QR and PR respectively.
Step 3: The point of intersection of the altitude H is the orthocentre of the given ΔPQR.

Question 6.
Draw an equilateral triangle of sides 6.5 cm and locate its Orthocentre.
Solution:

Steps for construction:
Step 1: Draw the ΔABC with the given measurements.
Step 2: Construct altitudes from any two vertices A and C to their opposite sides BC and AB respectively.
Step 3: The point of intersection of the altitude H is the orthocentre of the given ΔABC.

Question 7.
Draw ΔABC, where AB = 6 cm, ∠B = 110° and BC = 5 cm and construct its Orthocentre.
Solution:

Steps for construction:
Step 1: Draw the ΔABC with the given measurements.
Step 2: Construct altitudes from any two vertices B and C to their opposite sides AC and BC respectively.
Step 3: The point of intersection of the altitude H is the orthocentre of the given ΔABC.

Question 8.
Draw and locate the Orthocentre of a right triangle PQR where PQ = 4.5 cm, QR = 6 cm and PR = 7.5 cm.
Solution:

Steps for construction:
Step 1: Draw the ΔPQR with the given measures.
Step 2: Construct altitude from any two vertices Q and R to their opposite side PR and PQ respectively.
Step 3: The point of intersection of the altitude H is the orthocentre of the given ΔPQR.


text:
### 直链烷烃近红外光谱的温度效应与应用研究

1. 南开大学化学学院分析科学研究中心 天津市生物传感与分子识别重点实验室 药物化学生物学国家重点实验室天津化学化工协同创新中心 天津 300071
• 投稿日期:2015-10-17 发布日期:2015-12-23
• 通讯作者: 邵学广 E-mail:xshao@nankai.edu.cn
• 基金资助:

项目受国家自然科学基金(No.21475068)和教育部创新团队(IRT13022)资助.

### Effect of Temperature on Near-infrared Spectra of n-Alkanes

Qi Lihua, Cai Wensheng, Shao Xueguang

1. Research Center for Analytical Sciences, College of Chemistry, Nankai University, Tianjin Key Laboratory of Biosensing and Molecular Recognition, State Key Laboratory of Medicinal Chemical Biology, Collaborative Innovation Center of Chemical Science and Engineering (Tianjin), Tianjin 300071, China
• Received:2015-10-17 Published:2015-12-23
• Supported by:

Project supported by the National Natural Science Foundation of China (No. 21475068) and MOE Innovation Team (IRT13022).

Effect of temperature on near-infrared (NIR) spectra has been studied and applied to structural and quantitative analyses. To investigate the effect of temperature on NIR spectra of alkyl organic system, n-alkanes were studied in this work. NIR spectra of pure n-alkanes (hexane to decane), binary (hexane and octane) and ternary (octane, nonane and decane) mixtures were measured. In the experiments, temperature was controlled to change from 60 to 20℃ with a step of ca. 5℃. Comparing the spectra at different temperatures, only a little difference in peak intensity of some bands can be found. Therefore, alternating trilinear decomposition (ATLD) algorithm was adopted to analyze the three-order data matrix. The results show that two spectral loadings are obtained because the influence of temperature on the spectra of terminal ethyl (C2H5) groups differs from that of mid-chain methylene (CH2) groups. Furthermore, the temperature scores of CH2 and C2H5 groups decrease linearly with temperature, implying that the temperature effect can be quantitatively described by a quantitative spectra-temperature relationship (QSTR) model. The QSTR model provides an efficient way to predict the temperature of n-alkane solutions. Good linearity also exists between sample scores and carbon number or the relative content of CH2 and C2H5 groups in the molecules of the n-alkanes. Linear models between the two scores and the relative content of CH2 and C2H5 groups are obtained, respectively, using the least square fitting of the score and the relative contents. The model can be used for prediction of the relative content of CH2 and C2H5 groups in mixtures, which can further be used to estimate the composition of the mixtures. Furthermore, the relationship between the scores and the carbon atom numbers is modeled using multivariate linear regression (MLR). The composition of n-alkane mixtures can also be estimated through the predicted carbon number using the MLR model. These models are validated by binary and ternary mixtures of the n-alkanes. It was indicated that the relative contents of CH2 and C2H5 groups or the carbon atom number can be predicted using the models. Therefore, a new way for quantitative estimation of the composition in n-alkane mixtures was developed using the temperature effect of the near-infrared spectra.


text:
Fun with Integration

Calculus Level 4

Solve your way through the following steps and submit the result of (c) as your answer.

(a) First, prove that for all values of $$n\in\mathbb{R}$$

$\int _{ 0 }^{ 1 }{ (n^{ 2 }x^{ n }+2nx^{ n }+x^{ n }-1) } dx\equiv n.$

The logical reasoning behind this proof will help in parts (b) and (c).

(b) Sketch, on the same axes, the curves representing $$f(x)=16x^3-1$$ and $$x=1.$$

(c) Express $$f(x)$$ in the form $$x^n (n+1)^2-1,$$ and hence, without integrating or making use of any approximations, state the area enclosed between the two curves and the coordinate axes.

Note: This problem can easily be worked out with a calculator, online maths website or by integrating directly. But that will take all the fun out of it! The question is based on the typical calculus A-level syllabus. Please follow the rules and arrive to the answer by following all the below steps chronologically.

×

Problem Loading...

Note Loading...

Set Loading...


text:
# Test: Complex Variables

## 15 Questions MCQ Test RRB JE for Electrical Engineering | Test: Complex Variables

Description
Attempt Test: Complex Variables | 15 questions in 45 minutes | Mock test for GATE preparation | Free important questions MCQ to study RRB JE for Electrical Engineering for GATE Exam | Download free PDF with solutions
QUESTION: 1

### The integration of f (z) = x2 + ixy from A(1, 1) to B(2, 4) along the straight line AB joining the two points is

Solution:

x = at + b, y = ct + d

QUESTION: 2

###

Solution:

We know by the derivative of an analytic function that

QUESTION: 3
Solution:

QUESTION: 4

where c is the upper half of the circle z = 1

Solution:

Given contour c is the circle |z| = 1

QUESTION: 5

Solution:

Let f (z) = cosπz then f(z) is analytic within and on |z| =3, now by Cauchy’s integral formula

QUESTION: 6

Solution:

QUESTION: 7

The value of    around a rectangle with vertices at   is

Solution:

QUESTION: 8

where c is the circle x2 + y2 = 4

Que: The value of f(3) is

Solution:

QUESTION: 9

where c is the circle x2 + y2 = 4

Que: The value of f' (1 - i) is

Solution:

The point (1 - i) lies within circle |z| = 2 ( ... the distance of 1 - i i.e., (1, 1) from the origin is √2 which is less than 2, the radius of the circle).

Let Ø(z) = 3z2 + 7z + 1 then by Cauchy’s integral formula

QUESTION: 10

Expand the given function in Taylor’s series.

Que:

Solution:

QUESTION: 11

Expand the given function in Taylor’s series

Que:

Solution:

QUESTION: 12

Expand the given function in Taylor’s series.

Que:

Solution:

QUESTION: 13

If |z + 1|  < 1, then z-2 is equal to

Solution:

QUESTION: 14

Expand the function   in Laurent’s series for the condition given in question.

Que: 1 < |z| < 2

Solution:

QUESTION: 15

Expand the function   in Laurent’s series for the condition given in question.

Que: |z| > 2

Solution:

 Use Code STAYHOME200 and get INR 200 additional OFF Use Coupon Code


text:
The combinatorial diameter $\operatorname{diam}(P)$ of a polytope $P$ is the maximum shortest path distance between any pair of vertices. In this paper, we provide upper and lower bounds on the combinatorial diameter of a random "spherical" polytope, which is tight to within one factor of dimension when the number of inequalities is large compared to the dimension. More precisely, for an $n$-dimensional polytope $P$ defined by the intersection of $m$ i.i.d.\ half-spaces whose normals are chosen uniformly from the sphere, we show that $\operatorname{diam}(P)$ is $\Omega(n m^{\frac{1}{n-1}})$ and $O(n^2 m^{\frac{1}{n-1}} + n^5 4^n)$ with high probability when $m \geq 2^{\Omega(n)}$. For the upper bound, we first prove that the number of vertices in any fixed two dimensional projection sharply concentrates around its expectation when $m$ is large, where we rely on the $\Theta(n^2 m^{\frac{1}{n-1}})$ bound on the expectation due to Borgwardt [Math. Oper. Res., 1999]. To obtain the diameter upper bound, we stitch these shadows paths'' together over a suitable net using worst-case diameter bounds to connect vertices to the nearest shadow. For the lower bound, we first reduce to lower bounding the diameter of the dual polytope $P^\circ$, corresponding to a random convex hull, by showing the relation $\operatorname{diam}(P) \geq (n-1)(\operatorname{diam}(P^\circ)-2)$. We then prove that the shortest path between any nearly'' antipodal pair vertices of $P^\circ$ has length $\Omega(m^{\frac{1}{n-1}})$.

Networks and Optimization

Bonnet, G.F.Y, Dadush, D.N, Grupel, U, Huiberts, S, & Livshyts, G. (2021). Asymptotic bounds on the combinatorial diameter of random polytopes.


text:
Twilight
Search…
Order/LendTx

# OrderTx

In order to hide the amount in the trader's account, the program separates the pedersen commitment for the initial margin from the original value in the account. Yes, the whole account is locked. Though the knowledge of original value in the account remains with the trader.
The program below performs a range check on the resulting expression from V - IM to prove expr ≥ 0 .
1
p.push(Commitment::blinded(v))
2
.var()
3
.expr()
4
.push(Commitment::blinded(IM))
5
.var()
6
.expr()
7
.neg()
8
9
.range()
10
.drop()
Copied!
The blinding factor used for the Initial Margin would then be revealed to the relayer in order to track the solvency of the positions and create settlement transactions.
The relayer would use the execution price of the trade to generate a delegate locking signature on this Tx and relay it forward to the base layer.

# LendTx

The program for LendTx is similar to OrderTx, and instead of IM, we use the commitment on the Deposit to be locked in the Twilight pool.
1
p.push(Commitment::blinded(v))
2
.var()
3
.expr()
4
.push(Committment::blinded(Deposit)
5
.r#const()
6
.neg()
7
8
.range()
9
.drop()
Copied!
The relayer further executes locking constraints on the transaction where:
$TLV_0*PS=TPS_0*Deposit+Error \\ AND \\TPS_1-TPS_0=PS \\ AND \\ TLV_1-TLV_0=Deposit$
• 0 and 1 subscripts are referring to before and after state of the values
• TLV and TPS are abbreviations for total locked value and total pool share.
• AND is a conjunction constraint
• Error is from the rounding error
1
p.push(Commitment::blinded(TLV0)
2
.var()
3
.dup()
4
.expr()
5
.push(Commitment::blinded(poolShare))
6
.var()
7
.dup()
8
.expr()
9
.roll:2()
10
.mul()
11
.push(Commitment::blinded(TPS0))
12
.var()
13
.dup()
14
.expr()
15
.push(Commitment::blinded(Deposit))
16
.var()
17
.dup()
18
.expr()
19
.roll:2()
20
.mul()
21
.push(Commitment::blinded(Error))
22
.var()
23
.expr()
24
25
.roll:3()
26
.eq()
27
.push(commitment::blinded(TPS1)
28
.var()
29
.expr()
30
.roll:3()
31
.expr()
32
.neg()
33
34
.roll:3()
35
.expr()
36
.eq()
37
.and()
38
.push(Commitment::blinded(TLV1))
39
.var()
40
.expr()
41
.roll:3()
42
.expr()
43
.neg()
44
45
.roll:2()
46
.expr()
47
.eq()
48
.and()
49
.verify()
Copied!
The above program holds true for a positive error. For a negative error, expr for the error is negated.
The relayer would use the deposit amount of the transaction to generate a delegate locking signature and relay it to the base layer.


text:
# 16

Previous  ... Next

## Number

$16$ (sixteen) is:

$2^4$

The $4$th square number after $1$, $4$, $9$:
$16 = 4 \times 4$

The $5$th powerful number after $1$, $4$, $8$, $9$

The $2$nd fourth power after $1$:
$16 = 2 \times 2 \times 2 \times 2$

The $2$nd power of $4$ after $(1)$, $4$:
$16 = 4^2$

The $1$st power of $16$ after the zeroth $1$:
$16 = 16^1$

The $9$th highly abundant number after $1$, $2$, $3$, $4$, $6$, $8$, $10$, $12$:
$\sigma \left({16}\right) = 31$

The $9$th Ulam number after $1$, $2$, $3$, $4$, $6$, $8$, $11$, $13$:
$16 = 3 + 13$

The $1$st square number to be the sum of two triangular numbers in two different ways:
$16 = 10 + 6 = 15 + 1$

The $4$th power of $2$ after $(1)$, $2$, $4$, $8$:
$16 = 2^4$

The $5$th almost perfect number after $1$, $2$, $4$, $8$:
$\sigma \left({16}\right) = 31 = 2 \times 16 - 1$

The $6$th of $35$ integers less than $91$ to which $91$ itself is a Fermat pseudoprime:
$3$, $4$, $9$, $10$, $12$, $16$, $\ldots$

The $8$th even number after $2$, $4$, $6$, $8$, $10$, $12$, $14$ which cannot be expressed as the sum of $2$ composite odd numbers.

The $11$th after $1$, $2$, $4$, $5$, $6$, $8$, $9$, $12$, $13$, $15$ of the $24$ positive integers which cannot be expressed as the sum of distinct non-pythagorean primes.

The $14$th integer $n$ after $0$, $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$, $13$, $14$, $15$ such that $2^n$ contains no zero in its decimal representation:
$2^{16} = 65 \, 536$

The $11$th positive integer after $2$, $3$, $4$, $7$, $8$, $9$, $10$, $11$, $14$, $15$ which cannot be expressed as the sum of distinct pentagonal numbers.

The $4$th square after $1$, $4$, $9$ which has no more than $2$ distinct digits


text:
# Homework Help: Planetary Motion,Feynman Lectures

1. Dec 25, 2009

### @run

1. The problem statement, all variables and given/known data
This question is a part of independent study.
The problem is based on Feynman lectures volume 1,chapter 9,Newton's laws of dynamics,section 9-7 planetary motion. To compute numerically path of motion of a planet around sun using Newtons laws of kinematics and gravitation Feynman took initial conditions as x=0.5,y=0,v(x)=0,v(y)=1.63 & e=0.1.I understand that v(x)=0 and v(y) should have some value initially,but cannot understand why he take the value 1.63 for v(y) and how he computed 1.63.

2. Relevant equations

F = -G*M*m/r^2
r=sqrt(x^2+y^2)
x=x(0) + e* v(x) , v(x) = v(0) + e*a(x) , a(x) = -x/(r^3)
y=y(0) + e* v(y) , v(y) = v(0) + e*a(y) , a(y) = -x/(r^3)

3. The attempt at a solution

1
.x = a cos $, y = b sin$ -------(1)
v(x) = -a(d$/dt) sin$ -------(2),
v(y) = -b(d$/dt) cos$ = -(bx/a)(d$/dt)--------(3) y = 0 means$ = 0, x=a.
so, v(y) = -b(d\$/dt) = -bw
now there is a relation connecting the parameters a,b and e of an ellipse
b*b = a*a(1-e*e).
taking e = 0.8(a guss) value of b is calculated.
If I can calculate w in some way, i can get v(y). Some attempts made using the w*r^2 is conserved.
But couldn't calculate w.
2.
This attempt is made first for understanding that v(y) = 1.63 have any importance.
A simple program in c++ is made and plotted x-y graph.This analysis revealed that 1.63 have importance,then only perfect ellipse will be formed. If v(y) is taken as 0.8 planet will not revolve
around sun,the same thing happens when a value greater than 1.63 is taken ,for example 2.2
Analyis also says that the value of v(y) depend on x.When i take x=1 ,v(y) should have a value
near 1.4.This can be expect naturally because when x value changes from 0.5 to 1 the
gravitational force decreased,so less v(y) required.

Last edited: Dec 26, 2009


text:
# I want to find the covariance for an AR(2) process

I am not sure what the formula is for the covariance of an AR(2) process $$X_t = \phi_1 X_{t−1} + \phi_2 X_{t−2} + \epsilon_t$$ where $\{\epsilon_t\}$ is white noise process (Gaussian) $N(0, \sigma^2)$.

What is the formula for $\text{Cov}(X_t, X_{t-j})$?

• I am asking what is the general formula for covariance, not autocovariance – user7543128 Mar 5 '17 at 0:46
• What does that mean in this context? – Michael R. Chernick Mar 5 '17 at 0:47
• Okay but note that it exists only if the roots of the characteristic polynomial fall outside the unit circle in the complex plane. – Michael R. Chernick Mar 5 '17 at 1:03
• Check out the existing posts on the subject at Cross Validated. You will find either an exact same question or similar ones that will help you. – Richard Hardy Mar 5 '17 at 10:32
• – Christoph Hanck Jun 17 at 14:27

Just use the bilinearity of the covariance function: $$\operatorname{cov}\left(\sum_{i=1}^n a_iX_i, \sum_{j=1}^m b_j Y_j\right) = \sum_{i=1}^n\sum_{j=1}^m a_i b_j(\operatorname{cov}X_i, Y_j)$$ to get \begin{align} \operatorname{cov}(X_t,X_{t-j}) &= \operatorname{cov}(\phi_1X_{t-1}+\phi_2X_{t-2}+\epsilon_t, \phi_1X_{t-j-1}+\phi_2X_{t-j-2}+\epsilon_{t-j})\\ &= \phi_1^2 \operatorname{cov}(X_{t-1},X_{t-j-1}) + \phi_1^2 \operatorname{cov}(X_{t-2},X_{t-j-2})\\ & \quad +\phi_1\phi_2 \operatorname{cov}(X_{t-1},X_{t-j-2}) + \phi_1\phi_2 \operatorname{cov}(X_{t-2},X_{t-j-1}) \end{align} which gives a linear recurrence relationship that you can try and solve for yourself, or read up on how to go about doing so in your book. A very general relationship for time series defined by linear recurrences is that the "output" autocovariance function is given by the convolution of the "input" autocovariance function and the "autocovariance" of the characteristic function of the recurrence: $$C_o = C_i\, \star\, \left(\phi(x)\, \star\, \phi(x^{-1})\right).$$
• For $j>0$, the covariances of $\epsilon_{t-j}$ with $X_{t-1}$ and $X_{t-2}$ are non-zero so your second equation is incorrect. – Jarle Tufto Oct 21 '17 at 8:14


text:
# PSD - Correct Formula for removing Noise

Ok, so finally some things are making sense.

I'm trying to scale the results, which I have done by the following equation:

$$PS_{rms} = \frac{2 \cdot \left |y _{m} \right |^{2}}{ S_{1}^{2} } m = 0.....N/2$$

Where $y_{m} = (re*re+im*im)$

This produces the following:

(Sorry about the axis - I have not had time to do these)

Prior to scaling the results, I got the following:

Essentially, so far, so good (I hope!)

Now I want to remove the noise around the signal, in theory, so that the main peaks are just showing and remove all the peaks that are not. So in theory, I would just be left between points (60 - 80).

I have been trying to read, and, understand the "Section 10: Averaging and overlapping" in this paper: http://www.rssd.esa.int/SP/LISAPATHFINDER/docs/Data_Analysis/GH_FFT.pdf

It assumes that the usual remedy is to take the average of $M$ elements and reduce the standard deviation of the averaged result by a factor of $1 / \sqrt{M}$ however, what would be $M$ in this case? How could I therefore reduce the standard deviation, in order to remove noise from the result of scaling the PSD?

This is the only part to which I am now confused about, I essentially need to reduce the noise levels at the start of the result, and, at the end of the result thus giving me only the important peaks within the signal.


text:
# Converting StringJoin to StringForm inside Hold

Let's say I have a piece of code:

Hold[{code1,
code2}] (*MWE ofc*)

which I want to convert. Each StringJoin[...] should be replaced so I will get:

Hold[{code1, StringForm["asdad  adsd ", testa, testb], code2}]

I have an answer but maybe one may show shorter approach:

Hold[{code1, "asdad " <> ToString[testa] <> " adsd " <> ToString[testb], code2}
] /. HoldPattern[StringJoin[x__]
] :> RuleCondition@(
StringForm[StringJoin @@ (Hold[x] /. _ToString :> ""),
##] & @@ Cases[Hold[x], HoldPattern[ToString[z_]] :> z]
) // InputForm

 Hold[{code1, StringForm["asdad  adsd ", testa, testb], code2}]

Edit: This solution is not perfect. It evauates testa and testb, does not matter in my case but for generality let's assume they may not be evaluated. Also, referring to first of Mr.Wizard's suggestions: StringJoin expressions may appear or different levels too.

-
Should all StringJoin objects be replaced, or only those at level 2, or only certain ones by position? –  Mr.Wizard Jan 17 at 13:54
@Mr.Wizard Let's say we don't know on which level they may appear. But if you have neat solution for the simpler case, I'm lookng forward seeing it too. –  Kuba Jan 17 at 13:57
I was trying to solve this on my own, without reading your solution, but I struggled to get evaluation correct so I looked at your method to see how you had solved it. I discovered that your code does not work properly: testa and testb get evaluated. Is that acceptable? –  Mr.Wizard Jan 17 at 14:22
I think I'm remembering something. Please tell me, what are the Attributes of StringForm on your system? –  Mr.Wizard Jan 17 at 14:34
@Mr.Wizard only Protected. Hmm, it seems they are, I've missed that because it does not make a difference for my purposes. –  Kuba Jan 17 at 14:36

I think that in general, for tasks like this one, tricks like Trott-Strzebonski technique are not the best way, and one really needs expression parsers, which are may be not shorter, but more readable and more extensible. Here is a possible one for your problem:

ClearAll[convert];
SetAttributes[convert, {HoldAll}];
convert[x_List] := Map[convert, Unevaluated[x]];
convert[Hold[{pieces___}]] :=
(Hold[#] &[convert[{pieces}]]) /. convert[x_] :> x;
convert[s_StringJoin] := convertSJ[s];

where the specific converter for StringJoin is:

ClearAll[convertSJ];
SetAttributes[convertSJ, HoldAll];
convertSJ[s_StringJoin] := convertSJ[s, {}];
convertSJ[StringJoin[prev__String, ToString[x_], rest___], {accum___}] :=
convertSJ[StringJoin[prev, "  ", rest], {accum, x}];
convertSJ[s_StringJoin, {accum___}] :=
With[{st = s}, convert[StringForm[st, accum]]];

So that

convert[
Hold[{code1, "asdad " <> ToString[testa] <> " adsd " <> ToString[testb], code2}]
]

(* Hold[{code1, StringForm["asdad    adsd   ", testa, testb], code2}] *)

-
I was about to ask "why" but then I remembered we've been over this before. Frankly I still don't agree, as that convert with all its cases seems more confusing to me than a single replacement rule that caries out a specific action. "Agree to disagree" I guess. –  Mr.Wizard Jan 17 at 15:53
@Mr.Wizard The big advantage of convert is that its rules are composable, which means that, for more complex expressions, it will automatically dispatch to a right rule for a given part, and then combine them all together again. The difference in power between plain rule-based approach and the one based on parsers is pretty much similar to a difference between a parser and a regexp, for string parsing (with a caveat that patterns in M are more powerful than regexps). The more complex the original expression and the transformation rules, the more this difference will show. –  Leonid Shifrin Jan 17 at 16:02
@Mr.Wizard Another reason why I prefer this approach is that in every single rule in convert, I can focus on only what this particular rule should do. In a single rule a-la your solution or others, all these transformations are coupled together by the evaluation control constructs, while in my approach evaluation control does not couple the transformation together. If I want to change that rule later, for example, I don't have to care what else such a change might break. –  Leonid Shifrin Jan 17 at 16:05
@Mr.Wizard Yes, I still think that the parser approach is still superior even in that case, because I find it easier to understand. In most (but not all) cases, I started to view TZ trick as a hack, and when you need something more complicated that what TZ gives out of the box (in terms of evaluation), you need more hacks to make it all work without evaluation leaks. The parser approach is straight-forward: you descend down the expression, transform, and then collect the expression back, with evaluation control taken care of explicitly in each case. –  Leonid Shifrin Jan 17 at 16:16
You have almost convinced me but I still have trouble finding this easy to read. Would you consider posting a self Q&A with a graphical illustration of a simple parser? I think I lack a mental image that allows me to "see" this operation. I hope you understand what I am trying to say. –  Mr.Wizard Jan 17 at 16:27

This is what I came up with. Better? I don't know.

convert =
Block[{StringForm},
SetAttributes[StringForm, HoldRest];
# /. sj_StringJoin :> RuleCondition[
Reap[Unevaluated[sj] /. (t : ToString)[x_] :> (Sow[Hold@x]; "  "), _,
Join @@ #2 &] /. {s_, {_[ex__]}} :> StringForm[s, ex]]
] &;

Test:

start = Hold[{code1, "asdad " <> ToString[testa] <> " adsd " <> ToString[testb], code2}];
{code1, code2} = {0, 0};
testa := 2 + 2
testb := Print["!"]

convert @ start // InputForm

Hold[{code1, StringForm["asdad    adsd   ", testa, testb], code2}]

If we don't need to prevent evaluation of testa and testb, which Kuba's code does not do, we can simplify this considerably:

rule = sj_StringJoin :>
RuleCondition[
StringForm[#, Sequence @@ #2[[1]]] & @@
Reap[Unevaluated[sj] /. ToString :> ((Sow[#]; "  ") &)]
];

start /. rule // InputForm

During evaluation of In[]:= !

Hold[{code1, StringForm["asdad    adsd   ", 4, Null], code2}]

-
This attribute is quite nice, I'm struggling with injection of unevaluated sequence in different way but I got stuck now. :p p.s. to many whitespaces: "  " -> "". Thanks again. –  Kuba Jan 18 at 0:24

An embedded Trott-Strzebonski method-approach. rep[expr, held, from -> to, f] works by:

• holding held symbol (like ToString);
• replacing symbol from with to (like StringJoin -> StringForm), partially evaluating arguments that are not held...
• ...applying function f to arguments not held in from.

It leaves code... and test... parts unevaluated, es expected.

rep[expr_, held_, from_ -> to_, f_] := Block[{z},
expr //. {held -> HoldForm, from -> z} /. (z[y__] :> Block[{},
to @@ MapThread[#1 @@ (#2 /@ #3) &,
{{from, Sequence}, {f, #&}, GatherBy[{y}, Head]}] /; True]) //. HoldForm->held];

{code1, code2} = {11, 22};
testa := (Print@"A"; 2);
testb := (Print@"B"; 4);

rep[expr, ToString, StringJoin -> StringForm, #<>"" &] // InputForm

Hold[{code1, StringForm["asdad  adsd ",
ToString[testa], ToString[testb]], code2}]

It is general enough to deal with other types of replacements:

expr = Hold[{code1, 1 + N@testa + 3 + N@testb, code2}];
rep[expr, N, Plus -> g, f] // InputForm

Hold[{code1, g[f[1] + f[3], N[testa], N[testb]], code2}]

-
@Mr.Wizard, Kuba Please see new version. –  István Zachar Jan 17 at 15:11
The new version does not prevent evaluation of testa and testb, but neither does Kuba's original. My rule code seems a good deal simpler in this case. Also your code has ToString[testa] rather than bare testa, which does not behave the same; consider for example if testa is a "2D" expression. This could be an advantage or a disadvantage depending on what Kuba wants. –  Mr.Wizard Jan 17 at 15:25
@Mr.Wizard Yeah, I've realized that too. For the moment, I don't have time to figure out something clever. If I cannot do better tomorrow, I'll delete it. –  István Zachar Jan 17 at 16:19
@Mr.Wizard Figured out something. –  István Zachar Jan 17 at 16:24