text:
\section{Introduction}
\label{sec:intro}
In this paper we propose a new algorithm related to the regularization path of machine learning problems such as

\begin{equation}
  \label{eq:theta_hat}
  \hat \theta(\lambda) =  \argmin_\theta \mathcal L(\theta) + \lambda R(\theta),
\end{equation}
where $\theta\in\mathbb R^p$ is a vector of model parameters, the loss function $\mathcal L:\mathbb R^p \rightarrow \mathbb R$ is typically convex, and $\lambda\geq 0$ is a penalty constant.
The regularizer $R:\mathbb R^p\rightarrow \mathbb R_+$ is a non-convex function involving the $\ell_0$ pseudo-norm,
\begin{equation}
    ||\theta||_0 = \sum_{j=1}^p I[\theta_j \neq 0]\in \mathbb Z_+ = \{0,1,\dots,p\}
\end{equation}
which counts the number of non-zero entries of the $\theta$ parameter vector ($I$ is the indicator function).
Some typical examples are given in Table~\ref{tab:examples}, which includes best subset regression \citep{Miller2002,Soussen2010}, optimal segmentation \citep{segment-neighborhood,optimal-partitioning}, $k$-means clustering \citep{macqueen1967}, and low-rank matrix factorization \citep{Huang2018}.
For learning it is important to compute not just a single model for one penalty $\lambda$, but also the full regularization path $\{\hat \theta(\lambda)|\lambda \geq 0\}=\{\Theta_1, \Theta_2, \dots, \Theta_{N}\}$. The path is a finite set of $N$ models, i.e. for any $\lambda\geq 0$, we have $\hat \theta(\lambda)=\Theta_k$ for some model size $k\in\{1,\dots, N\}$. To simplify the presentation we limit our discussion to regularizers $R(\Theta_k)=k$ which are equal to model size. More general regularizers, e.g. $R(\Theta_k)=r_k$ for some sequence of increasing values $r_1<\cdots<r_N$, can be handled using a straightforward modification of our proposed algorithm.

One example is best subset regression, which seeks the best $k$ features for a linear regression function.
In this problem there a total of $p$ input features and therefore a set of $N=p+1$ models in the regularization path $\{\Theta_0, \Theta_1,\dots, \Theta_p\}$.
This non-convex problem is NP-hard, so the optimal regularization path can only be computed for low-dimensional problems \citep{Bertsimas2016}.
For high-dimensional problems there are various heuristic algorithms for computing approximate solutions, e.g. greedy forward/backward selection \citep{MallatZhang1993,Davis1994,Miller2002,Schniter2009,Soussen2010}, non-smooth non-convex regularizers \citep{FanLi2001,Zhang2010,Mazumder2011,SparseStep}, and $\ell_1$ regularization/LASSO \citep{Tibshirani1996,Chen1998}.
Each weight vector $\Theta_k\in\mathbb R^p$ in the optimal or approximate regularization path has $k$ non-zero entries, $R(\Theta_k)=||\Theta_k||_0=k$.
The extreme elements correspond to the ordinary least squares solution $\Theta_p$ with all features selected, and the completely regularized solution $\Theta_0$ with no features selected.

Another example is optimal segmentation, which is the maximum likelihood model with $k$ segments ($k-1$ changepoints) for a sequential data set.
In this problem there are $p$ sequence data, and each element $\Theta_k$ of the regularization path has $k\in\{1,\dots,p\}$ distinct segments ($k-1$ changes) along the sequence, i.e. $R(\Theta_k)=1+||D\Theta_k||_0=k$ where $D\in\mathbb R^{p-1\times p}$ is the matrix which returns the difference between adjacent pairs of data in the sequence.
Even though this problem is non-convex, an optimal solution can be computed via dynamic programming algorithms that are log-linear in the number of data, and linear in the number of models \citep{pelt,Maidstone2016}.
There are also several fast heuristic algorithms, including binary segmentation \citep{binary-segmentation,Truong2018}, which computes an approximate regularization path of $N=p$ models in $O(N\log N)$ time on average and $O(N^2)$ in the worst case.
The optimal or approximate regularization path of $N=p$ models $\{\Theta_1, \Theta_2, \dots, \Theta_{p}\}$ has extreme elements $\Theta_1$ with no changes (one common segment/parameter for the entire data sequence) and $\Theta_{p}$ with a change after every data point (a different segment/parameter for each data point).

\begin{table*}[t]
    \centering
    \begin{tabular}{cccc}
        Problem &  Loss  & Regularizer & Model complexity  \\
            \hline
        Best Subset Regression & $||X\theta-y||_2^2$ & $||\theta||_0$ & features selected \\
        Optimal Segmentation & $||\theta-y||^2_2$ & $|| D\theta ||_0$ & segments/changepoints\\
        $k$-means Clustering & $||\theta M - X||_F$ & $||\theta^T \mathbf 1||_0$ & cluster centers\\
        Matrix Factorization & $||U\Diag(\theta) V^T-X||_F$ & $||\theta||_0$ & rank\\[0.1cm]
    \end{tabular}
    \caption{Examples of machine learning problems which use the $\ell_0$ pseudo-norm as a regularizer.}
    \label{tab:examples}
\end{table*}

In this context solving the penalized problem~(\ref{eq:theta_hat}) for a given penalty $\lambda\geq 0$ results in one of the solutions to the corresponding constrained problem,
\begin{equation}
  \label{eq:L_k_theta}
   L_k=\min_{\theta}
      \mathcal L(\theta),
  \text{ subject to } R( \theta) \leq k,
\end{equation}
where $k\in\mathbb Z_+$ is the model size (selected features, changepoints, clusters, etc).
If the loss values $L_1>\dots>L_N$ in a regularization path $\{\Theta_1, \Theta_2, \dots, \Theta_{N}\}$ are known, they can be used to define the model selection function
\begin{equation}
\label{eq:k*}
k_N^*(\lambda) = \argmin_{k\in\{1,\dots, N\} }
\underbrace{L_k + \lambda k}_{f_k(\lambda)}.
\end{equation}
The model selection function~(\ref{eq:k*}) returns the (smallest) model complexity $k$ which is optimal for a given penalty parameter $\lambda$.
In this paper we provide a new formal proof that dynamic programming can be used to compute an exact representation of the model selection function $k^*_N(\lambda)$ in linear $O(N)$ time.

\subsection{Existing algorithms and related work}
The model selection function $k^*_N(\lambda)$ can be trivially evaluated for a single $\lambda$ parameter in linear $O(N)$ time, which yields the solution to (\ref{eq:theta_hat}) via $\hat \theta(\lambda) = \Theta_{k^*_N(\lambda)}$.
However for some learning algorithms we need an exact representation of the model selection function for a full path of penalty $\lambda$ values.
Quadratic $O(N^2)$ time algorithms for computing the full path have been proposed for changepoint detection \citep{Lavielle2005,HOCKING-penalties} and regression \citep{Arlot2009}, but these algorithms are too slow for high-dimensional problems (e.g. full path of binary segmentation models for large data sets, see Section~\ref{sec:empirical-timings}).

The algorithm we propose is similar to the ``convex hull trick'' which is informally described, without any references to the machine learning literature, on a web page
\citep{Convex-hull-trick}.
The novelty of our paper with respect to that previous work is (1)  rigorous formal proofs of the linear time complexity and optimality, (2) explaining the relevance to the machine learning literature, (3) detailed theoretical and empirical comparisons with baseline algorithms.

A final related work is the CROPS algorithm of \citet{crops}, which also
proposes an algorithm that outputs an exact path of solutions for several penalty values. Both papers exploit the structure of the piecewise linear model selection function which relates the constrained and penalized problems. The input to our algorithm is a sequence of constrained models of sizes 1 to $N$, whereas the input to CROPS is an interval of penalty values. In general the two algorithms output different results (partial solution paths).
However in the special case when $N=p$ models are input to our algorithm (all possible models) and the interval $(0,\infty)$ is input to CROPS, then the two algorithms return the same output (the full path).

\subsection{Important definitions}
In this section, we will reference several concepts that are related to our proposed algorithm. Changepoints refer to a sudden deviation from previously recorded values within a given data set. Segments are used to fit each unique block data with an average value line. The model complexity $(k)$ refers to the total amount of unique segments present in a given segmentation model. A regularization path is the path of optimal segmentation models selected for a given range of penalties. Breakpoints represent the penalty value in which the algorithm switches from a previously selected model to a new one based on the evaluation of the model selection function (\ref{eq:k*}).

\subsection{Contributions and organization}

In this paper we propose a new dynamic programming algorithm for computing the model selection function $k^*_N(\lambda)$, and we prove that it computes an exact representation for all penalties $\lambda\geq 0$ (Section~\ref{sec:algorithm}).
Our second contribution is a theoretical analysis of the time complexity of our algorithm, which demonstrates that it is linear $O(N)$ time in the worst case; we also provide a theoretical analysis of previous algorithms in terms of the framework of this paper  (Section~\ref{sec:pseudocode}). Our third contribution is an empirical study of time complexity in several real and synthetic data sets, including a comparison with previous algorithms (Section~\ref{sec:empirical-complexity}). Our final contribution is an empirical study of the prediction accuracy in cross-validation experiments on supervised changepoint detection problems (Section~\ref{sec:accuracy}). The paper concludes with a discussion (Section~\ref{sec:discussion}).

\section{Dynamic programming algorithm}
\label{sec:algorithm}
We propose a dynamic programming algorithm for $N$ decreasing loss values $L_1>\cdots>L_N$; it computes an exact representation of the $k^*_N(\lambda)$ model selection function for all penalties $\lambda\geq 0$.

\subsection{Exact representation of a piecewise constant function using breakpoints}
\label{sec:breakpoints}
Our proposed algorithm recursively computes $k^*_N$ from $k^*_{N-1}$, so is an instance of dynamic programming \citep{bellman}. At each step/iteration $t\in\{1,\dots, N\}$ of the algorithm, the algorithm stores a set of $M_t\in\{1,\dots,t\}$ selectable models,
\begin{equation}
\label{eq:K}
     1=K_{t,1}<K_{t,2}<\cdots<K_{t,M_t}=t.
\end{equation}
The algorithm also stores a corresponding set of breakpoints,
\begin{equation}
    \infty=b_{t,0} > b_{t,1} > \cdots > b_{t,M_t}=0.
\end{equation}
These two sets define for all $t\geq 1$ a recursively computed model selection function,
\begin{equation}
    F_t(\lambda) = \begin{cases}
     K_{t,1} & \text{ if } \lambda\in ( b_{t,1}, b_{t,0} )\\
     &\vdots\\
     K_{t,M_t} & \text{ if } \lambda\in ( b_{t,M_t}, b_{t,M_t-1} )
    \end{cases}
    \label{eq:F_t}
\end{equation}
We prove later (Theorem~\ref{thm:optimal}) that the recursively computed function $F_N$ is identical to $k^*_N$, the desired model selection function~(\ref{eq:k*}). The geometric interpretation of the models $K_{t,i}\in\mathbb Z$ and breakpoints $b_{t,i}\in \mathbb R$ are shown in
Figure~\ref{fig:three-iterations}. Each breakpoint is a penalty value where the min cost (grey segments) changes from one cost function to another (black lines).
\begin{figure*}[!b]
  \centering
  \input{figure-three-iterations}
  \vskip -.5cm
  \caption{Two possible runs of the algorithm for $N=3$ models. \textbf{Left:} at iteration $t=2$, the cost function $f_2(\lambda)$ is minimal (grey curve) for penalties $\lambda<b_{2,1}=c(2,1)$, and $f_1(\lambda)$ is minimal otherwise. \textbf{Middle:} at iteration $t=3$ a small $L_3$ value results in $c(3,2)>b_{2,1}$ so we remove $b_{2,1}$ and $K_{2,2}=2$, because $f_2(\lambda)$ is no longer minimal for any $\lambda$. \textbf{Right:} at iteration $t=3$ a large $L_3$ value results in $c(3,2)<b_{2,1}$ so we keep $b_{2,1}=b_{3,1}$ and store a new breakpoint $c(3,2)=b_{3,2}$.}
  \label{fig:three-iterations}
\end{figure*}
\subsection{Dynamic programming update rules}
\label{sec:updates}
The algorithm starts at the first iteration $t=1$ by initializing $M_1=1$ model with
\begin{equation}
\label{eq:init}
K_{1,1}=1,\, b_{1,1}=0,\, b_{1,0}=\infty,
\end{equation}
which is an exact representation of the first model selection function $F_1$. For all other iterations $t>1$, the algorithm begins by discarding any breakpoints which are no longer necessary, then adds one new breakpoint. In particular it first computes the index $i$ corresponding to the largest model from the previous iteration $t-1$ which is still selected at iteration $t$,
\begin{equation}
    I_t = \max\big\{i\in\{1,\dots,M_{t-1}\} \mid
    c(t, i) < b_{t-1,i-1}
    \big\}.
\label{eq:It}
\end{equation}
The new candidate breakpoint $c(t,i)$ is
the penalty for which the new cost function $f_t$ is equal to a previous function $f_{K_{t-1,i}}$,
\begin{equation}
\label{eq:cti}
     c(t,i) = \frac{L_{K_{t-1,i}} - L_t}{t - K_{t-1,i}}.
\end{equation}

A modification to use more general regularizers involves replacing $t - K_{t-1,i}$ with $r_{t}-r_{K_{t-1,i}}$ in the denominator of equation~(\ref{eq:cti}).

We then compute the number of models selected
at iteration $t$,
\begin{equation}
    M_t = I_t + 1.
\end{equation}
The algorithm stores the new set of models selected at iteration $t$,
\begin{equation}
\label{eq:Kti}
    K_{t,i} = \begin{cases}
    K_{t-1,i} & \text{ for } i\in\{1,\dots, I_t\}\\
    t & \text{ for } i=M_t.
    \end{cases}
\end{equation}
The algorithm also stores the new breakpoint $c(t,I_t)$ along with some of the previous breakpoints,
\begin{equation}
    b_{t,i} = \begin{cases}
    b_{t-1,i} & \text{ for } i\in\{0,\dots, I_{t}-1\}\\
    c(t, I_t) & \text{ for } i=I_t\\
    0 & \text{ for } i=M_t.
    \end{cases}
    \label{eq:bti}
\end{equation}
Once the selected models $K_{t,i}$ and breakpoints $b_{t,i}$ have been recursively computed via (\ref{eq:Kti}--\ref{eq:bti}), the model selection function $F_t$ is defined using equation~(\ref{eq:F_t}).

\subsection{Demonstration of algorithm up to $t=3$}
In this section we provide two example runs of the algorithm.
The initialization creates an exact representation of $k^*_1=F_1$, via one possible model $K_{1,1}=1$ which is selected for all $\lambda$ between the two breakpoints $b_{1,1}=0<\infty=b_{1,0}$. The second iteration computes the candidate breakpoint $c(2,1)$ which is stored in the new breakpoints $b_{2,2}=0<c(2,1)<\infty=b_{2,0}$, along with $M_2=2$ models $K_{2,2}=2>1=K_{2,1}$ (Figure~\ref{fig:three-iterations}, left).

At iteration $t=3$ we first compute the candidate $c(3,2)$ and compare it to the stored breakpoint $b_{2,1}$. If $c(3,2)\geq b_{2,1}$ then $I_3=1$ and so $b_{2,1}$ is removed (Figure~\ref{fig:three-iterations}, middle).
The candidate $c(3,2)$ is also discarded; the new breakpoints $b_{3,2}=0<c(3,1)<\infty=b_{3,0}$ are computed and stored with $M_3=2$ models $K_{3,2}=3>1=K_{3,1}$. Otherwise, $c(3,2)< b_{2,1}$ implies $I_3=2$ and the previous breakpoint $b_{2,1}$ is kept along with the candidate $c(3,2)$  (Figure~\ref{fig:three-iterations}, right). The breakpoints $b_{3,3}=0<c(3,2)<b_{2,1}<\infty=b_{3,0}$ are stored with $M_3=3$ models $K_{3,3}=3>2>1=K_{3,1}$.

\subsection{Recursive update rules are optimal}
Equations~(\ref{eq:K}--\ref{eq:bti}) define a dynamic programming algorithm, because the recursively computed $F_N$ is optimal in the sense of equation~(\ref{eq:k*}), as demonstrated in the following theorem.
\begin{theorem}[Update rules yield the optimal model selection function]
\label{thm:optimal}
The recursively computed function $F_N$~(\ref{eq:F_t}) and the model selection function $k^*_N$~(\ref{eq:k*}) are identical.
\end{theorem}
\begin{proof}
The proof follows from equations~(\ref{eq:K}--\ref{eq:bti}) using induction on $t$. The base case is $t=1$, for which the initialization~(\ref{eq:init}) of the recursively computed function implies $F_1(\lambda) = 1$ for all $\lambda\in (0, \infty)$. Because at iteration $t=1$ there is only one possible model, it is clear that $F_1(\lambda)=k^*_1(\lambda)$ for all $\lambda$.

The proof by induction now assumes that $F_{t-1}(\lambda)=k^*_{t-1}(\lambda)$ for all $\lambda$; we will prove that the same is true for $t$.
The recursive updates (\ref{eq:Kti}--\ref{eq:bti}) imply that
\begin{eqnarray}
F_{t}(\lambda)
&=& \begin{cases}
    K_{t-1,1} & \text{ if } \lambda\in( b_{t-1,1}, b_{t-1,0})\\
    & \vdots\\
    K_{t-1,I_t} & \text{ if } \lambda \in ( c(t,I_t), b_{t-1, I_t-1} )\\
    t & \text{ if } \lambda \in (0, c(t,I_t) )
    \end{cases}\\
&=& \begin{cases}
    F_{t-1}(\lambda) & \text{ if } \lambda > c(t,I_t)\\
    t & \text{ if } \lambda < c(t,I_t)
    \end{cases}
    \label{eq:Ft_minus_one}
\end{eqnarray}
We need to prove that the function above returns the model size $k\in\{1,\dots, t\}$ with min cost $f_k(\lambda)$, for any penalty $\lambda$. Equations~(\ref{eq:It}--\ref{eq:cti}) imply
$K_{t-1,I_t}=F_{t-1}[c(t, I_t)]$ is the min cost model at the penalty $c(t, I_t)$ where the new cost function $f_t$ equals the previous min cost function,
\begin{equation}
    f_t[c(t,I_t)]=f_{K_{t-1,I_t}}[c(t,I_t)] = \min_{k\in\{1,\dots,t-1\}} f_k[c(t,I_t)].
\end{equation}
Because $f_t(\lambda)=L_t+\lambda t$ is a linear function with a larger slope than any of $f_1,\dots,f_{t-1}$, and a smaller intercept $L_t<L_{t-1}<\cdots$, we therefore deduce that $f_t$ is less costly before $c(t,I_t)$, and more costly after:
\begin{equation}
    \begin{cases}
    f_t(\lambda)< \min_{k\in\{1,\dots,t-1\}} f_k(\lambda) & \text{ for all } \lambda < c(t,I_t) \\
    f_t(\lambda)> \min_{k\in\{1,\dots,t-1\}} f_k(\lambda) & \text{ for all } \lambda > c(t,I_t)
    \end{cases}
    \label{eq:ft_greater_less}
\end{equation}
Combining equations~(\ref{eq:Ft_minus_one},\ref{eq:ft_greater_less}) and using the induction hypothesis completes the proof that $F_t(\lambda)=k^*_t(\lambda)=\argmin_{k\in\{1,\dots, t\}} f_t(\lambda)$ for all $\lambda$.
\end{proof}

\section{Theoretical complexity analysis}
\label{sec:pseudocode}

In this section we propose pseudocode that efficiently implements the dynamic programming algorithm, and provide a proof of worst case linear time complexity. We also provide a theoretical analysis of the previous quadratic time algorithm in terms of the framework of this paper.

\subsection{Proposed linear time algorithm}

We propose Algorithm~\ref{algo:dp}, which is pseudocode for equations (\ref{eq:It}--\ref{eq:bti}).
It recursively computes an exact representation of the model selection function $F_N$ in terms of breakpoints $b$ and selected models $K$.

It begins by initializing the model selection function $F_1$ (line~\ref{line:init}).
Then for all $t\in\{2,\dots,N\}$ it recusively computes $F_t$ from $F_{t-1}$.
The first step in the loop (line~\ref{line:solve}) is to call the \textsc{Solve} sub-routine, which computes the number of selected models $M_t$ and the new breakpoint $\lambda=c(t,M_t-1)$. The number of while loop evaluations $w[t]$ can optionally be stored in order to analyze empirical time complexity.
The next step is to store the new model $t$ and new breakpoint $\lambda$ (line~\ref{line:store}), which completes the computation of $F_t$.

\begin{table*}[t]
    \centering

        \begin{tabular}{ccc}
        Algorithm &  Best & Worst  \\
            \hline
        \textbf{This paper}, Algorithm~\ref{algo:dp} & $O(N)$ & $O(N)$\\
        \citep{Arlot2009, HOCKING-penalties}& $O(N)$ & $O(N^2)$ \\
        Always quadratic & $O(N^2)$ & $O(N^2)$
    \end{tabular}
    \caption{Summary of asymptotic time complexity in terms of number of input models, $N$.}
    \label{tab:complexity}
\end{table*}

\begin{algorithm}
\begin{algorithmic}[1]
\STATE Input:
Array of $N$ real numbers $L[1]>\cdots>L[N]$ (decreasing loss values).
\STATE
\label{line:allocate} Allocate: selected models $K\in\mathbb Z^N$, breakpoints $b\in\mathbb R^N$, while loop iterations $w\in\mathbb Z^N$
\STATE \label{line:init} Initialize: number of models $M\gets 1$, breakpoint $b[1]\gets \infty$, selected model $K[1]\gets 1$
\FOR{$t=2$ to $N$}
  \STATE \label{line:solve} $M,\lambda,w[t]\gets\textsc{Solve}(K, b, L, M, t)$
  \STATE \label{line:store} $b[M]\gets \lambda$, $K[M]\gets t$\label{line:K}  // store a new breakpoint
\ENDFOR
\STATE Output: selected models $K[1:M]$, breakpoints $b[1:M]$, while loop iterations $w[2:N]$
\caption{\label{algo:dp}
Dynamic programming for computing exact representation of model selection function}
\end{algorithmic}
\end{algorithm}

In this paper we propose an amortized constant $O(1)$ time implementation of the \textsc{Solve} sub-routine (Algorithm~\ref{algo:proposed-solve}).
It computes $I_t,M_t$ by solving the maximization in equation~(\ref{eq:It}) using a linear search over possible values of the model index $i$.
It starts at the current number of selected models (line~\ref{line:initM}), and then repeatedly tests the criterion from equation~(\ref{eq:It}).
If the current value of the model index $i$ does not satisfy the condition of the while loop (line~\ref{line:while}), then the model index is decremented to remove a breakpoint (line~\ref{line:remove}).
The number of while loop iterations $w_t$ (lines~\ref{line:initM},\ref{line:remove}) can be optionally computed in order to analyze the empirical time complexity of the algorithm.
Even though Algorithm~\ref{algo:proposed-solve} is clearly $O(M)$ in the worst case, in the next section we prove that it is amortized constant $O(1)$ time when used in the context of Algorithm~\ref{algo:dp}. Using this sub-routine therefore results in an overall linear $O(N)$ time complexity for Algorithm~\ref{algo:dp}, in the best and worst case  (Table~\ref{tab:complexity}).

\begin{algorithm}
\begin{algorithmic}[1]
\STATE Input: selected model sizes $K\in\mathbb Z^N$, breakpoints $b\in\mathbb R^N$, loss values $L\in\mathbb R^N$, number of selected models $M\in\mathbb Z$, new model size $t\in\mathbb Z$.
\STATE \label{line:initM} $i\gets M,\  w_t\gets 1$
\WHILE{$\lambda\gets (L[ K[i] ] - L[t])/(t- K[i]) \geq b[i]$}
\label{line:while}
    \STATE \label{line:remove} $i--,\  w_t ++$ // remove a breakpoin
\ENDWHILE
\STATE Output: number of models $i+1$, new breakpoint $\lambda$, number of while loop iterations $w_t$
\caption{\label{algo:proposed-solve}
Proposed \textsc{Solve} sub-routin
}
\end{algorithmic}
\end{algorithm}

\subsection{Previous quadratic algorithms}
\label{sec:quadratic-pseudocode}

In this section we provide a detailed comparison with several previously proposed quadratic algorithms \citep{Arlot2009,HOCKING-penalties}.
In terms of the framework of this paper, these previous algorithms can be interpreted as computing $K_{t,i}, b_{t,i}$ for $t=N$, without computing any of the solutions at the previous iterations $t<N$.
These other algorithms are therefore not performing dynamic programming.
Whereas our algorithm starts at the smallest model size and then updates the model selection function for larger sizes, these other algorithms begin at the largest model size.
In particular they start by initializing the largest model $K_{N,M_N}=N$ and the smallest breakpoint $b_{N,M_N}=0$, then for all $i\in\{M_N-1, \dots, 1\}$ they recursively compute $K_{N,i},b_{N,i}$ from $K_{N,i+1},b_{N,i+1}$.
There are $M_N-1$ iterations of this recursive computation, and each iteration considers $K_{N,i+1}-1$ breakpoints. The overall algorithm is therefore $O(N M_N)$; best case $O(N)$ is when the number of selected models $M_N=2$ is small; worst case $O(N^2)$ is when $M_N=N$ is large (Table~\ref{tab:complexity}). Interestingly, the opposite is true of our algorithm (best case is when $M_N$ is large), as we prove in the next section.

\subsection{Proof of linear time and space complexity}
\label{sec:time-proof}
The overall space complexity of Algorithm~\ref{algo:dp} is clearly $O(N)$, because up to $N$ possible models/breakpoints can be computed.
The time complexity depends on the implementation of the \textsc{Solve} sub-routine (line~\ref{line:solve}).

The computation time of our proposed implementation of the \textsc{Solve} sub-routine (Algorithm~\ref{algo:proposed-solve}) depends on $w_t$, the number of times the while condition is evaluated (line~\ref{line:while}).
In particular, the overall time complexity of Algorithm~\ref{algo:dp} is linear in total number of times the while condition is checked,
\begin{equation}
\label{eq:WN}
    W_N = \sum_{t=2}^N w_t.
\end{equation}
The following result proves that Algorithm~\ref{algo:dp} is overall $O(N)$ time, by bounding the total number of times the while condition is checked.
\begin{theorem}[Best and worst case time complexity]
\label{thm:time-complexity}
For any $N$ inputs to Algorithm~\ref{algo:dp}, the total number of while loop iterations $W_N$ over all calls to Algorithm~\ref{algo:proposed-solve} is bounded: $N-1\leq W_N \leq 2N-3$.
\end{theorem}
\begin{proof}
The proof uses the fact that for all $t\in\{2,\dots, N\}$, we have
\begin{equation}
    \label{eq:model_size_iterations} M_t = 2+M_{t-1}-w_t,
\end{equation}
which follows from the definition of the number of while loop iterations $w_t$ (on line~\ref{line:remove} of Algorithm~\ref{algo:proposed-solve}, every iteration decrements $i$, and therefore $M_t$). The total number of while loop iterations is thus
\begin{eqnarray}
W_N
\label{eq:sum_w} &=& \sum_{t=2}^N w_t = \sum_{t=2}^N 2+M_{t-1} - M_t\\
\label{eq:distribute_sum} &=& 2(N-1)+ \sum_{t=2}^{N} M_{t-1}-\sum_{t=2}^N M_t \\
\label{eq:re_write_sum} &=& 2(N-1)+ \sum_{t=1}^{N-1} M_{t}-\sum_{t=2}^N M_t\\
\label{eq:subtract_two_sums} &=& 2N-2  + M_1 - M_N \\
\label{eq:M1_is_one} &=& 2N-1 - M_N.
\end{eqnarray}
The first two equalities (\ref{eq:sum_w}) follow from the definitions of the number of while loop iterations (\ref{eq:WN}--\ref{eq:model_size_iterations}).
The next equalities come from distributing the sum (\ref{eq:distribute_sum}), then re-writing the second term as a sum from $t=1$ to $N-1$ (\ref{eq:re_write_sum}).
The last equalities come from subtracting the terms in the two sums (\ref{eq:subtract_two_sums}), then using the fact that $M_1=1$ (\ref{eq:M1_is_one}).
The result is obtained using the fact that the number of selectable models is bounded, $2\leq M_N\leq N$.
\end{proof}

The best case of Algorithm~\ref{algo:dp}, $W_N=N-1$ iterations, happens when the number of selected models is large, $M_N=N$; the worst case $W_N=2N-3$ iterations occurs when $M_N=2$.
Because the total number of iterations is always $O(N)$, the \textsc{Solve} sub-routine (Algorithm~\ref{algo:proposed-solve}) is amortized constant $O(1)$ time on average, even though it is linear in the number of models $O(M)$ in the worst case.

\begin{figure}
  \centering
  \input{figure-loss-small-evals}
  \vskip -0.5cm
  \caption{Empirical number of iterations $W_N$ of while loop in Algorithm~\ref{algo:proposed-solve} in synthetic loss values (\textcolor{Rpurple}{violet points}) and loss values from optimal changepoint models of real neuroblastoma data (black points) are linear $O(N)$ in the number of input models $N$, consistent with theoretical upper/lower bounds obtained in Theorem~\ref{thm:time-complexity} (\textcolor{gray}{grey lines}). }
  \label{fig:empirical-iterations}
\end{figure}

\section{Empirical complexity analysis}
\label{sec:empirical-complexity}

\label{sec:empirical-timings}
\begin{figure*}
  \centering
   \includegraphics[height=2.8in]{figure-fullpath-db-binseg.png}
   \includegraphics[height=2.8in]{figure-fullpath-grid-timing.png}

  \vskip -0.5cm
  \caption{The proposed exact linear time algorithm is orders of magnitude faster than the previous exact quadratic time algorithm
  and naïve approximate grid search.
  \textbf{Left:} the two exact algorithms compute the same result, but the proposed linear time algorithm is orders of magnitude faster, even when time to compute loss values via binary segmentation (binseg) is included in the timing (lines/bands for mean/SD over 5 timings).
  \textbf{Right:} when used on loss values from $N=287443$ optimal changepoint models for one genomic data sequence, the proposed exact linear time algorithm is always faster than approximate grid search with at least 10 points (points/segments for mean/SD over 5 timings). }
  \label{fig:empirical-time}
\end{figure*}

In this section we empirically examine the number of iterations of our algorithm, and show that it is overall orders of magnitude faster than previous baselines.

\subsection{Empirical iteration counts are consistent with theoretical bounds}

As discussed in Section~\ref{sec:time-proof}, the time complexity of Algorithm~\ref{algo:dp} is linear $W_N$, the total number of iterations of the while loop in the \textsc{Solve} sub-routine. Here we demonstrate that the theoretical bounds on $W_N$ obtained in Theorem~\ref{thm:time-complexity} are consistent with the number of iterations obtained empirically in real and synthetic data.
First, we considered 1000 real cancer DNA copy number data sets of different sizes $p\in\{2, \dots,869\}$ from R package \texttt{neuroblastoma}.
For each sequence data set $ \mathbf z\in \mathbb R^p$ we used the Pruned Dynamic Programming Algorithm (PDPA) of \citet{pruned-dp-new} to compute a sequence of optimal changepoint models. For each number of segments $k\in\{1,\dots, p\}$ the optimal loss is
\begin{align}
  \label{eq:L_k_cpt}
   L_k=&\ \ \min_{\mathbf \theta\in\mathbb R^p}\
      \sum_{j=1}^p (\theta_j-z_j)^2\\
      \text{subject to} &\ \
      ||D\theta||_0=\sum_{j=1}^{p-1} I[\theta_j\neq \theta_{j+1}]=k-1.
      \nonumber
\end{align}
The PDPA returns a regularization path of $N=p$ models, from $k=1$ segment (no changepoints, $\theta_j=\theta_{j+1}$ for all $j$) to $k=N=p$ segments (change after every data point, $\theta_j\neq\theta_{j+1}$ for all $j$). We used the resulting loss values $L_1>\cdots>L_N$ as input to Algorithm~\ref{algo:dp}. We plotted the number of iterations $W_N$ as a function of data set size $N$ (black points in Figure~\ref{fig:empirical-iterations}), and observed that they always fall between the upper/lower bounds from Theorem~\ref{thm:time-complexity} (grey lines). These results provide empirical evidence that the time complexity of our algorithm is linear $O(N)$ in real data.

Second, we considered two synthetic sequences of loss values, $L_t=N-t$ for all $t\in\{1,\dots,N\}$ (e.g. $L_1=4>3>2>1>0=L_5$ for $N=5$) and $L_t=N-\sqrt{t}$ (e.g. $L_1=4>3.59>3.27>3>2.76=L_5$ for $N=5$). For these loss values we observed a number of iterations
(violet points in Figure~\ref{fig:empirical-iterations}) that always falls on the upper/lower bounds (grey lines), which indicates that these synthetic data achieve the worst/best case. Overall these results provide a convincing empirical validation of our theoretical bounds from Theorem~\ref{thm:time-complexity}.

\subsection{Empirical timings suggest orders of magnitude speedups}

\begin{figure*}[!b]
    \centering
    \input{figure-binseg-quadratic-rigaill}

    \caption{Binary segmentation (step 1) followed by exact model selection (step 2) was run on four synthetic data sequences $x_i$ (panels from left to right).
    Both model selection algorithms (worst case quadratic, and proposed worst case linear time) output the exact path of selected models.
    \textbf{Bottom:} when there are few selected models (first and third columns) the quadratic algorithm achieves its best case linear time complexity; when there are many selected models (second and fourth columns) it achieves the worst case quadratic time complexity.
    \textbf{Top:} total timings over both steps show that the linear time algorithm offers substantial speedups when binary segementation achieves its best-case log-linear time complexity, and there are many selected models (second column).}
    \label{fig:binseg-quadratic-rigaill}
\end{figure*}

Our proposed algorithm takes as input a sequence of $N$ loss values, which must be computed by some other machine learning algorithm. In this section we therefore analyzed our algorithm in the context of a two-step pipeline: (i) compute the $N$ loss values, (ii) compute an exact representation of the model selection function. The overall time complexity of the two-step pipeline is determined by the slower of the two steps. If the first step is at least quadratic, then the pipeline is as well (using either linear or quadratic time model selection in the second step). However if the first step is sub-quadratic, then we expect that our linear time algorithm in the second step should result in speedups.

\paragraph{Simulated data for which proposed linear algorithm results in speedups over previous quadratic algorithm.} For the first step we therefore use the log-linear binary segmentation algorithm, which inputs a data sequence $\mathbf z\in\mathbb R^p$, and computes an approximate solution to (\ref{eq:L_k_cpt}). The binary segmentation algorithm computes the full path of $N=p$ models with corresponding loss values $L_1,\dots, L_N$ in $O(N\log N)$ time on average \citep{binary-segmentation, Truong2018}. For each data set size $N\in\{10^2, \dots, 10^5\}$ we generate synthetic data sequences $z_j = \sin(j)+j/N$, for all $j\in\{1,\dots,N\}$. Figure~\ref{fig:empirical-time} (left) shows timings of binary segmentation alone (binseg), exact model selection algorithms alone (linear, quadratic), and two-step pipelines (binseg.linear, binseg.quadratic), on an Intel T2390 1.86GHz CPU. As expected, our proposed linear time algorithm is orders of magnitude faster than the previous quadratic time algorithm (when run alone, and also in the two-step pipeline). For example, for $N=10^5$ data, the binseg.linear pipeline takes about 3 seconds, whereas binseg.quadratic takes about 2 minutes. More generally, such timings are typical for any data for which binary segmentation runs in log-linear time, and selected models $M_N$ increases with the data set size $N$ (second column of Figure \ref{fig:binseg-quadratic-rigaill}, same as Figure~\ref{fig:empirical-time} left). However, there are other kinds of data for which our approach is no faster than the quadratic baseline (other columns of Figure \ref{fig:binseg-quadratic-rigaill}). For example, when binary segmentation runs in quadratic time, then our linear time model selection algorithm offers no speedups to the overall pipeline (third and fourth columns of Figure \ref{fig:binseg-quadratic-rigaill}). Also, since the previous (worst case quadratic) algorithm achieves its best case linear time complexity when the number of selected models $M_N$ is small/constant, then our proposed algorithm offers no speedups in this case (first columns of Figure \ref{fig:binseg-quadratic-rigaill}). Overall, we have shown that for some data sets, our linear time algorithm provides substantial speedups relative to the previous quadratic time algorithm.

\paragraph{Real data for which proposed linear algorithm is faster than grid search.} Another baseline algorithm for computing a representation of the model selection function is a naïve approximate grid search over $G$ penalties $\lambda$, which takes $O(NG)$ time. We expected this baseline to perform poorly in the context of large $N$ and large $G$, so we performed timings on a large \texttt{chipseq} data set from the UCI repository \citep{uci-ml-repo}. We first computed a regularization path of $N=287,443$ optimal changepoint models for a sequence of $p=1,656,457$ data, and then performed timings of the model selection algorithms on the resulting $N$ loss values.
We observed that our proposed linear time algorithm is always faster than approximate grid search with at least 10 grid points (Figure~\ref{fig:empirical-time}, right).
For example the approximate grid search takes almost 2 minutes for $N=10,000$ grid points, whereas the proposed exact linear time algorithm takes only 27 milliseconds. Overall these data indicate that the proposed linear time algorithm is indeed faster than the two baselines in large data.

\section{Prediction accuracy in supervised changepoint problems}
\label{sec:accuracy}

\begin{figure*}[!b]
  \centering
    \begin{tikzpicture}[->,>=latex,shorten >=1pt,auto,node distance=3cm, thick]
      \node (L) {Label set $\ell$};
      \node (y) [below of=L, node distance=1.5cm] {Interval $y$};
      \node (z) [right of=L] {Sequence $\mathbf z$};
      \node (x) [right of=y] {Features $\mathbf x$};
      \node (f) [below of=x, node distance=1.5cm] {Function $f$};
      \node (l) [right of=x] {Penalty $\lambda$};
      \node (m) [right of=z] {Model $\hat \theta$};
      \path
      (L) edge (y)
      (z) edge [line width=2pt] node [above] {$k^*$} (y)
      (z) edge (x)
      (y) edge (f)
      (x) edge (f)
      (f) edge (l)
      (x) edge (l)
      (l) edge [line width=2pt] node {$k^*$} (m)
      (z) edge (m)
      ;
 \node[rectangle, inner sep=0mm, fit= (L) (l),label=below right: $i$, xshift=28mm] {};
  \node[rectangle, inner sep=5mm,draw=black!100, fit= (L) (l)] {};
    \end{tikzpicture}
  \caption{Computation graph for supervised changepoint detection in labeled sequences $i$. Directed edges start from inputs and end at outputs, e.g. interval $y$ can be computed using labels $\ell$ and sequence $\mathbf z$. Bold edges indicate computations which use the model selection function $k^*$.}
  \label{fig:computation-graph}
\end{figure*}

\begin{figure*}
  \centering
  \includegraphics[width=\textwidth]{figure-chipseq-cv}
  \vskip -0.3cm
  \caption{Prediction accuracy on held-out test data increases as a function of number of points used in approximate grid search algorithm (red line/band); it takes 10--100 grid points to achieve the maximum accuracy in each data set (panels), which is also achieved by the proposed linear time exact algorithm (black point/error bar on right).}
  \label{fig:chipseq-cv}
\end{figure*}

In this section we aim to demonstrate that the proposed exact algorithm results in more accurate predictions than a naïve approximate grid search.
To examine the accuracy of our algorithm, we consider several supervised changepoint detection problems from the UCI \texttt{chipseq} data, which contain labels that indicate presence/absence of changepoints in particular data subsets. Accurate changepoint detection in these data is important in order to characterize active/inactive regions in the human epigenome.

Here we give a brief summary of the supervised learning framework for changepoint detection; for details see \citep{HOCKING-penalties}. Each observation $i$ is represented by a numeric data vector/sequence $\mathbf z_i$ along with a corresponding label set $\ell_i$.
We compute a feature vector $\mathbf x_i$ then learn a penalty function $f(\mathbf x_i)=\log \lambda_i$ which results in a model $\hat \theta(\lambda_i)$. The goal is to learn a function $f$ that results in minimal errors with respect to the labels $\ell_i$ in test data sequences.
In this context there is a model selection function $k_i^*$ which is specific to each data sequence $i$, and is used in two places during the learning and prediction (bold arrows in Figure~\ref{fig:computation-graph}).
First, it is used to compute the interval/output $ y_i=(\underline y_i, \overline y_i)$ of optimal penalty values for each training data sequence $i$, such that predicting $f(\mathbf x_i)=\log\lambda_i\in (\underline y_i, \overline y_i)$ results in minimal label errors. Second, it is used to compute the predicted model $\hat \theta(\lambda_i)$ given a predicted penalty $\lambda_i$.
We learn a linear $f$ by minimizing an L1-regularized cost function \citep{HOCKING-penalties}, using outputs $y_i$ computed by either our exact algorithm or a naïve approximate grid search with a variable number of penalties $\lambda$.

We performed 4-fold cross-validation in five different labeled data sets (panels in Figure~\ref{fig:chipseq-cv}). We observed in each data set that it takes 10--100 penalties $\lambda$ in the grid search to achieve the maximum number of correctly predicted labels, which was also achieved by the proposed exact algorithm. Overall these data provide empirical evidence that, in the context of supervised changepoint detection problems, using an exact representation of the model selection function results in more accurate predictions than using an approximate representation obtained via grid search.

\section{Discussion and conclusions}
\label{sec:discussion}

For learning problems with $\ell_0$ regularization, we proposed a new dynamic programming algorithm for computing an exact representation of the model selection function~(\ref{eq:k*}). By bounding the number of iterations, we proved theoretically that the algorithm is linear time in the worst case. In real and synthetic data we empirically validated these bounds, and showed that the proposed linear time algorithm is orders of magnitude faster than two baselines. We used cross-validation in supervised changepoint detection problems to show that the exact representation provides more accurate predictions than the grid search approximation baseline.

Our algorithm requires no special data structures and can be efficiently implemented using arrays in standard C; our free software implementation is available at \url{https://github.com/tdhock/penaltyLearning/}. For reproducibility we also provide the source code that we used to make the figures at \url{https://github.com/tdhock/changepoint-data-structure}.
For future work we would like to consider selecting models from a partial set $S\subset \{1,\dots,N\}$, and develop an efficient algorithm for updating an exact representation of the corresponding model selection function.

\bibliographystyle{abbrvnat}

redpajama_set_name: RedPajamaArXiv


So here are a couple of extended quotations from Walter Brueggemann's most recent book, Reality, Grief, Hope: Three Urgent Prophetic Tasks. These paragraphs jumped out at me from his middle section on the need for prophetic grief in the face of contemporary suffering, In this he echoes the mourning of Jeremiah and Lamentations in particular.
Here he quotes Richard Beck's The Authenticity of Faith: The Varieties and Illusions of Religious Experience (Abilene, 2012), which is itself an engagement with some of religious faith's most influential critics. Beck's is a slightly surprising use of language (whereby a "healthy soul" and "summer faith" are not exactly to be commended!) but stick with it. There's a crucial point here.
In the face of a suffering and broken world, belief in divine solicitousness and special protection is hard to come by for sick souls. In fact, just the opposite seems to be the case; God is decidedly unhelpful and, rather than providing protection, is allowing suffering to continue, often in ways that leave us trembling in sadness, shock, despair and horror [my emphasis].
These experiences are difficult to face. They infuse life with a sense of existential despair. Even though it might be easier, simply as a matter of coping, to hide our eyes from life (as many do), the sick souls refuse to look away. They refuse the too easy retreat into existentially consoling beliefs. And the price they pay for this is allowing a painful tension to sit at the center of their existence,a belief in a God who is often not present and who often fails to rescue.
…The heathy-minded, according to James, will seek to exit this space as quickly as possible, usually by cracking the faith experience. However, sick souls, being less motivated by a need for comfort, are more likely to linger in this space, perhaps spending their entire lives within this experience. Sick souls would accomplish this by remaining rugged monotheists, refusing to crack God. Sick souls still try to shoulder the full emotional burden of monotheism.
No doubt, people will be oh so hasty to leap to its surrounding verses – before allowing the reality of this felt abandonment to sink in. But that's precisely the problem with what Beck (slightly bizarrely, to be fair) calls 'healthy faith' – it beetles over the pain too fast. And the aftermath is that this leaves those languishing in the dark caverns of depression far behind. Brueggemann is certainly not denying the possibility of hope (that's the topic of his book's final third after all).
Beck describes healthy souls as those who are "feeling queasy about the incarnation" and so flee to easier assurances of a gnostic type, hold to a "higher Christology" that skimps on the embodiment of Jesus, and hold a religion of solace that is without darkness. To that extent, Freud is right about religion. But Beck's research shows that Freud's reductionism simply disregards the "saints of darkness" who seek no such easy consolation and who are resolved to face the evident reality of loss, abandonment, and absence.
I've adapted the quadrilateral diagram and its contrast with what Beck calls the polar model of faith on his excellent blog post here from 2007. Incidentally by communion here he means 'engagement with God'.
I was so surprised when I read your blog about depression. For some reason I have always felt guilt over being a Christian and struggling with depression. I breathed a sigh of relief that there are others who struggle. Thank you most sincerely.
Thanks Mark – really helpful summary and reflections.


text:
Home » FC Goa sack Sergio Lobera, club and coaching staff release statement
FC Goa sack Sergio Lobera, club and coaching staff release statement
By Nehal on 2nd February 2020
Sergio Lobera's time is up at FC Goa
In an extraordinary turn of events, league leaders FC Goa have announced the departure of Head Coach Sergio Lobera and his assistants Jesus Tato and Manuel Sayabera.
FC Goa today has mutually parted ways with coach Sergio Lobera, Jesus Tato and Manuel Sayabera. The club thanks Sergio and his assistants for their services.
Club Statment: https://t.co/ngzbiAUjad pic.twitter.com/G4i3QK0y1g
— FC Goa (@FCGoaOfficial) February 1, 2020
In the statement FC Goa released, the club did not specify the reasons for its decision and insisted the club have "mutually parted ways." FC Goa are currently on top of the ISL, and with three games to go within touching distance of an AFC Champions League spot which makes the decision taken by the management hard to fathom.
Meanwhile, Sergio Lobera released a statement on his Instagram page. Although the statement is mostly PR boilerplate, the coach did mention that they were "really unhappy" about the club letting them go.
https://www.instagram.com/p/B8CLnvHDlPp/
Reports indicate Lobera, assistant coach Jesus Tato and conditioning coach Manuel Sayabera were served termination letters a couple of days ago on Friday afternoon. Sergio's departure has been on the cards for a while with various internal conflicts and issues, but a fall-out with the players nearly a fortnight ago proved to be the final straw.
After Sergio lost the dressing room, the management were left with little choice – they had to make a decision now or risk the discontent within the players disrupting their campaign.
There are also reports which hint at a pay dispute – Sergio Lobera is the highest paid coach in the ISL and he was looking for an improved contract after leading the side to the 2018-19 ISL final where they lost to Bengaluru FC. They also won the Super Cup last season. The FC Goa management have reportedly baulked at the rise in pay and were looking to negotiate with a wage closer to what Sergio was making currently.
Other sources indicate a few more reasons for Lobera's departure:
Courtesy: IFTWC
The news of the termination reached the press before the club could put out a statement. This was largely because Lobera and his staff refused to sign the letters and sought time to consult with their legal advisers.
FC Goa and Sergio Lobera still cannot arrive at an understanding over the termination. Last clause still being negotiated by lawyers from either side. Expecting a joint statement, or another development, later in the evening #ISL #Indianfootball
— Marcus Mergulhao (@MarcusMergulhao) February 1, 2020
Clifford Miranda will be the interim coach while the Technical Director Derrick Pereira will be on the bench and address the press. FC Goa are up against Hyderabad FC next on the fifth of February.
Published in FC Goa, Football in India, Indian Football, Indian Super League, ISL and News
ISL 2019-20 League Winners FC Goa appoint Juan Ferrando as their new manager - THE AWAY END 30th April 2020
[…] FC Goa have announced the appointment of 39-year-old Spanish coach Juan Ferrando as their new manager. The Catalonian was previously Head Coach at Greek club Volos FC and replaces Sergio Lobera who was sacked late into the 2019-20 ISL season. […]
In Excess of xA: An Analysis of FC Goa's 2019-20 season - The Away End 10th October 2020
[…] season coming up in November and scheduled to be held in Goa sees the Gaurs poised for change. With Sergio Lobera leaving the club and a number of key players departing, Goa have signed promising Indian players in Phrangki Buam, […]
Mumbai City FC formally announce Sergio Lobera as their new Head Coach - The Away End 12th October 2020
[…] the appointment of former FC Goa manager Sergio Lobera as their new Head Coach. Lobera was let go by FC Goa under controversial circumstances while the club was on top of the 2019-20 ISL with three games left in the league stage. FC Goa went […]

redpajama_set_name: RedPajamaCommonCrawl


text:
SAS Group's April 2013 traffic figures
SAS Group's capacity (ASK) was up by 10.4% and the Group's traffic (RPK) increased by 1.5%.
The SAS Group's load factor decreased by 6.1 p.u. to 69.5%.
SAS Group carried 2.5 million passengers in April, up 6.5%.
Group market trends, RASK and yield development
The traffic continued to develop as expected during April with number of passengers growing primarily on shorter routes. However, despite good response to the increased capacity, demand did not match and the load was lower, due to the timing of Easter and also due to the launch of 8 European routes since 31 March where demand still is seasonally relatively low.
Currency adjusted yield (Scandinavian Airlines) in March 2013 was down 2.7% versus previous year and RASK was down 3.9%, due to the timing of Easter as expected. In April 2013 the change in yield vs. last year is expected to be positive and the change in RASK to be in line with last year.
Overall, the market demand continues to be good. Despite yield has been somewhat more stable in recent months, the over capacity on certain routes adds uncertainty to the yield and RASK outlook going forward and the SAS Group expects a negative trend for the RASK and yield for the full year 2012/13. The capacity increase for 2012/13 is expected to be approximately 5-6%.


text:
Porn Minus Porn
THE REVIEWS ARE IN
The Critics Are Making Us Blush
It's very rare for a small comedy theater to land on a critic's radar, but Porn Minus Porn is raking in some phenomenal reviews.
The Chicago Reader highly recommends the show, writing, "Each week a cast of ten or so offer readings of two episodes from Cinemax's soft-core series Life on Top, transcribed in stilted, preposterous glory by show creator Ben Bowman, who also acts as host. The dialogue is by turns mundane and overwrought ("I would drag my dick ten miles over hot asphalt to sniff the tire of the garbage truck that took away her panties"), the story lines impenetrable, and the sex— well, who knows? ... It's joyous trash, and since the actors read the scripts cold, the hour feels as spontaneous as the best improv." (more)
Newcity Stage also raved about the show. "The ensemble on stage capitalizes perfectly on the idiotic structures, non-sequiturs and gross clichés that infest porn like bedbugs infest New York City. With lines like, 'That girl was looking at you like a taco bar' or 'How much lubricant do you really need?'/ 'Why limit yourself!!?' it becomes clear that, like most things, when taken slightly out of context (or in this case, when the context/sex is taken out), porn almost becomes poetic, in the same way a pile of trash can become poetic with a black-and-white filter in some haughty Instagram feed." (more)
The Onion A.V. Club showed us major love in their Podmass series. "The script is, as one would expect, ridiculous. What makes it incredibly funny is that, though no one is watching the show for the plot and dialogue, it truly does feel like the writers are trying their hardest to make it clever, and nothing is funnier than bad jokes. The actors who read the script are brilliant in their delivery, playing it straight and highlighting how absurd and abrupt the placement of sex scenes are in the show. ... It's an extremely fun listen with a surprising cliffhanger ending." (more)
Porn Minus Porn has also been featured in Cusp Magazine, The Columbia Chronicle, Under the Gun Theater's news site and The Boiling Point Improv Blog.
If you've seen our show and want to share your opinion, leave a review on the Yelp page for Under the Gun Theater.


Unique Photos Of Kubota Big tool Rack – Through the thousands of Pictures on the net regarding kubota big tool rack, we all choices the best selections using greatest image resolution truly for our readers, and now this photographs is actually considered one of stocks choices inside our best images gallery in relation to Unique Photos Of Kubota Big tool Rack. I am hoping you'll think it's great.
submitted by Stephanie Snyder at 2018-08-08 03:36:07. To find out plenty photograph with Unique Photos Of Kubota Big tool Rack photos gallery remember to comply with this kind of web page link.


I'm not the biggest fan of Autumn, but even I admit that I do like a good dose of the ol' Pumpkin Spice, crunchy leaves under foot and cosy afternoons snuggled up with a nice hot drink and a movie or two. The one thing I struggle with in Autumn is 'transitional' fashion and normally I end up getting it horribly wrong.
If I'm honest I struggle all year around because as much as I want to be "fashionable" I also want to be comfortable AF and you know this girl hasn't got time for faffy outfits and all the accessories under the sun.
Autumn is the one time of year guaranteed to make getting dressed a chore in itself … one minute it can be gorgeous and bright and the next it can look as though I need an ark to get me to the office as opposed to a car.
In Summer I love to get my legs out, even though they are my least favourite body part and despite not being the girliest of girls on the planet I absolutely adore wearing pretty dresses and skirts when the weather is kind enough to allow it.
So when it comes to getting ready in Autumn one minute I can be reaching for the floaty dresses and abandoning them in the floordrobe the next (everyone has a floordrobe right?) … Autumn weather can be so cruel.
COLD SHOULDERS DRESSES … One way that I take Summer fashion with me is by wearing these cutie pies throughout September & October. I love a good cold shoulder dress like this one here from Tobi (I have another from Superdry too that I wore in this post here), especially if they're in a light and floaty material because they add that little extra bit of cover up that you need on the cooler Autumnal days, but still let you feel uber girlie and a little bit boho too.
ALL THE KNITS … I am a massive jumper fan and so far this Autumn I have added several new ones to my collection. In recent years Superdry has been my go to store for good quality knitwear but lately I have found some great ones on ASOS, & Other Stories and also this gorgeous one from Tobi too (seen above). When it is cold and mean outside there is nothing nicer than putting on a nice knitted jumper, keeping warm and feeling all wrapped up.
LAYER IT UP … This is such a great way to take your favourite Summer pieces into Autumn with you. Take this gorgeous white shift dress from Tobi (which coincidentally ended up in the floordrobe at the weekend when the weather looked as though it was about to do a sneaky u-turn) … There is absolutely no needs to leave this behind just because its a little Summery. Teamed with a pair of leather look leggings (I have my eye on these from ASOS) and some statement boots like these ASOS Cianna ones and you can wear those short shift dresses all year round!
I guess in reality there are bits of Autumn that I love and bits that I really don't … just like the other seasons I guess, which just means I best pull on my favourite knit and make the most of the season before Winter hits the UK.
What are your best of Autumn wardrobe (or floordrobe) staples?
*This post has been written in collaboration with Tobi, all thoughts and words are my own.


It is your responsibility to understand the law and to comply with its requirements. The paragraphs above cover the essence of the law, but you may find our Colorado Law page helpful.
SPICE does not provide testing at this time. However we do have some links on our links page that give some testing options.


I am fragrance obsessed and love being able to play around with different scents, tones, layering and discovering new favourites. For me, a fragrance is something I need to have in my life, they can lift your mood, evoke memories, inspire or simply be a conversation starter. When I got the opportunity to spend some time in the vault of Atelier Colognes, I was totally within my element trying out everything I could whilst being told a wonderful story.
Having been surrounded by so many amazing fragrances, I was invited along to be introduced to the latest launch of Pacific Lime.
I am totally new to Atelier Colognes, I have walked past the boutique store in Covent Garden many times, but this was my first visit and I enjoyed absolutely every single part of it. The store itself has quite the historic boutique vibe with the dark wood and strategically placed bottles, which makes you want to try absolutely every single one, it is literally quite the place to visit. The brand came about through a wonderfully romantic story between the founders Christophe and Sylvie who met and fell in love back in 2006 and who wanted to not only keep their brand 100% French made, but also one which tells a story and evokes memories or as they eloquently put it "Memories in a bottle".
Pacific Lime lives within the Sunny Citruses family for Atelier Colognes and it is one which I absolutely loved at first spritz. Think bright lime and coconut perfume, this fragrance is said to tell the story of an unexpected celebration on a dream beach.
The scarlet fuchsia sunset was her only hint to their destination. He had spent months organizing this event in the greatest secrecy. Surrounded by everyone they loved, they savored the moment with joy and excitement. When the doors opened, she recognized the beach of her childhood. Everyone was dazzled by the vibrant colors, the exotic perfumes, and the exhilarating tropical heat. The party could finally begin!
The main ingredients of this unisex fragrance are limes from Mexico, lemon from Italy, coconut from the Philippines, spearmint from America and eucalyptus from China. As you can see, it is quite the story behind a fragrance and it is one which really does grab your attention. It brings about a mixture of sweet, soft and freshness alongside amber and woody notes which bring together all of those fragrances to create summer in a bottle.
What I love the most about this fragrance is the earthy notes mixing with the more zesty notes to give that fresh but sweet scent and ultimately the Lime and the Coconut just blew me away. On the skin, it has one of the best-staying powers I have ever come across for a fragrance, it literally lasts for hours and I don't feel the need to top it up of an evening if I am going out.
Pacific Lime is currently exclusive to Selfridges HERE and the Atelier Cologne Boutique HERE and will launch nationwide in John Lewis in April. Gift Sets are also available and the brand also has a range of candles (which I really want to now try), Reed Diffusers (those too) as well as Bath and Body products. Prices start at £30 increasing price per bottle size.
I haven't noticed this in Covent Garden before, but it looks amazing - bet the scents are as amazing as they sound!
An unexpected celebration on a dream beach. I mean, I can't smell it...but I'm sold!! And that wall of colour just looks so satisfying. Will certainly be checking these guys out when I'm next in London.
They look incredible, and right up my street, the packaging and the scents look beautiful!
I love unisex fragrances. I often forget to put on perfume in the rush of getting ready but I'm loving the fact they have cabdles too.


text:
Five For Fighting "Slice" *Review*
"Have you read my blog today, 300 million little USA's, your doorstep is just a click away, we'll get together one of these days." ~Five For Fighting
If I had to come up with just one word that describes Five for Fighting's newest cd Slice it would be smooth.
Which is the perfect thing for me right now. I have very diverse tastes when it comes to music ranging from traditional church hymns and classical to country to heavy metal screamo rock. Ever since Amber was born though I've been tending to listen to my soft music much more, I guess it's just with a toddler you listen to so much yelling throughout the day that's the last kind of music to listen to!
The music isn't boring though, it's very much "dance worthy" every time the first song starts to play Amber starts dancing, so cute!!! I also love the lyrics of that song, it gives a holler to us bloggers so what's not to love? The second song is dedicated to "the unknown soldier" and of course being a military spouse I love that song and it's one of my favorite songs on the cd.
In the song The Dance you hear the lyrics, "You put the beautiful in life" seriously, what girl would not melt if her man told her that?! So sweet and romantic!
All in all I love the cd. If you're liked his smash single "Superman" at all then you should go get this album! It hits stores on October 13 but you can pre-order it from Amazon by going here right now it's listed for only $9.99 and I think that it would be more than worth that price!
For this review I received a digital copy of the album I reviewed free. These opinions are entirely my own and I will receive no other gain from them.
Filed in: Music, Review • by Nicole • 22 Comments
Serendipity is Sweet
Oh, I didn't know they had a new CD coming out. Glad you posted this 😀
I am going to check them out right now on Amazon.
Wow! I love them!!! Definitely getting their CD now so whoever you did the review for – let them know!
I didn't know you did reviews. That's awesome. You are just all sorts of motivated 🙂
I'm going to go listen to them on itunes…
I really liked it! Thanks for letting us know about them.
Great review! Thanks for telling us about them.
Didnt know he had a New CD
As I am typing this in bed bed..my lil shih tzu is sleeping next to me…HE IS SNORING!!! HAHAHAHAHA!!
His 2000 album America Town went platinum in the U.S. largely because of the success of the song "Superman (It's Not Easy)", which became a song of healing for America following the September 11 attacks in 2001.
Five for Fighting is the stage name of American singer-songwriter John Ondrasik
Ondrasik has also released a DualDisc of his 2004 album which has one side containing The Battle for Everything in its entirety and the other side being a DVD containing bonus footage and Five For Fighting music videos.
Five for Fighting's fourth album, Two Lights, was released on August 1, 2006.
John Ondrasik was born on January 7, 1968 in Los Angeles, a child of a musical family…
In his early years Ondrasik learned the piano.
As a teenager, he learned how to play the guitar and started to write music….
While he also learned to sing opera briefly, he quickly decided that he would like to be a singer/songwriter.
Ondrasik went to college at UCLA and graduated with a degree in applied science and mathematics continuing to pursue music in his spare time.
He adopted the name "Five for Fighting," which is an expression in ice hockey when a player receives a five-minute penalty for fighting.
In December 2008, John Ondrasik announced that his fifth studio album will have an expected release date of early Summer 2009.
Sounds like you're pretty well schooled on this topic. 🙂
I wouldn't have even known if Five for Fighting was the group name or the album name if it hadn't been for this blog.


Futures markets had been pointing to flat or slightly declining prices.
Global dairy prices at the latest Global Dairy Trade (GDT) auction fell 1.3 per cent to US$3487 in a discouraging start to the new season.
Whole milk powder (WMP) prices were down 1.1 per cent to US$3205, though regular grade WMP to ship in August was practically unchanged.
Analysts had been picking either flat or slightly declining prices because of higher volumes being offered, and because premiums of futures over previous GDT have shrunk.
Favourable weather saw a rise in Fonterra's milk collection by 3 per cent during April, but for the 2017-18 season from June to April, New Zealand farmers produced 2 per cent less milk than the year before.
The latest result contrasted with the final auction for the season last month when prices lifted1.9 per cent overall to reach US$3637.
Federated Farmers dairy chairman Chris Lewis said the rise in the value of the New Zealand dollar would contribute to even lower returns, but such factors were sometimes out of the country's control.
Some analysts have been picking the dollar to fall to 65c against the US, but in fact it has recently lifted to just over the 70c mark.
«What with GDT falling slightly and the dollar going up, some accountants will be looking at their balance sheets,» Lewis said.
Farmers were used to spikes and dips in prices, but as long as the overall value remained at the $3300 level, they would be happy.
Most processors had delivered positive farmgate forecasts in recent weeks in the region of $7 per kilogram of milksolids. Lewis sounded a note of caution, saying it was better to under promise and then over deliver.
The most dramatic change in the overnight auction was seen in butter milk powder, which jumped by 17.7 per cent.
AgriHQ pointed out there was a greater volume of WMP on offer than had been forecast. WMP volumes for the auction were lifted 7.6 per cent from forecasts. Buyers bought more WMP than they did at the May 15 event, but they were unwilling to pay more for it.
Butter prices fell 3.5 per cent, anhydrous milkfat was down 1.7 per cent. Skim milk powder prices were up marginally, lifting 0.3 per cent.
Cheddar prices were down 3.6 per cent, lactose lifted 3.9 per cent and rennet casein prices rose 2.7 per cent.


text:
Q: Using Booleans in IEnumerator and coroutines When the game starts the bool ismove is set to true whilst is supposed to be false so that when the coroutines starts, the bool ismove is later on set to true.
(The bool should be false but it automatically sets to true onstart)
Am I calling boolean correctly in this code? Bdw I set the bool public but did not assign it as true or false.
    public void Start()
    {
        rbody = GetComponent<Rigidbody2D>();
        anim = GetComponent<Animator>();
        collectedTusker = 0;
        StartCoroutine(Countdown());
    }

    IEnumerator Countdown()
    {
        ismove = false;
        police.isfollowplayer = false;

        while (count > 0)
        {
            Countdowntext.text = count.ToString();

            yield return new WaitForSeconds(1f);

            count--;
        }

        Countdowntext.text = "GO!";

        yield return new WaitForSeconds(1f);

        //enable player and enemy movement
        ismove = true;
        police.isfollowplayer = true;

        Countdowntext.gameObject.SetActive(false);
    }
    public void FixedUpdate()
    {
        //onstart
        if (police.isfollowplayer == false)
        {
            ismove = false;
        }
        else
        {
            ismove = true;
        }

        //movement condition
        if (ismove == true)
        {
            anim.enabled = true;
            Movement();
            jump();

        }
        else
        {
            //no movement in y and x axis
            rbody.velocity = Vector2.zero;
            isdead = true;
        }
    }

A: You are using ismove in FixedUpdated and in Coroutine.
When you call StartCoroutine(Countdown()); it sets police.isfollowplayer = false; and your FixedUpdate() enters in a if that change ismove to true.
Try avoid using the same variable in Coroutines and Updates or create another bool to tell when is on couroutines.

redpajama_set_name: RedPajamaStackExchange


text:
Thirty-first Dynasty of Egypt
Achaemenid Egypt
Satrapy of the Achaemenid Empire
343 BC–332 BC →
Standard of Cyrus the Great
Western part of the Achaemenid Empire, with the territories of Egypt.[1][2][3][4]
• 343–338 BC Artaxerxes III (first)
• 336–332 BC Darius III (last)
Historical era Achaemenid era
• Conquests of Artaxerxes III 343 BC
• Conquests of Alexander the Great 332 BC
The Thirty-first Dynasty of Egypt (notated Dynasty XXXI, alternatively 31st Dynasty or Dynasty 31), also known as the Second Egyptian Satrapy, was effectively a short-lived province (satrapy) of the Achaemenid Persian Empire between 343 BC to 332 BC. It was founded by Artaxerxes III, the King of Persia, after his reconquest of Egypt and subsequent crowning as Pharaoh of Egypt, and was disestablished upon the conquest of Egypt by Alexander the Great.
The period of the 31st Dynasty was the second occasion in which Persian pharaohs ruled Egypt, hence the term "Second Egyptian Satrapy". Before the 31st Dynasty was founded, Egypt had enjoyed a brief period of independence, during which three indigenous dynasties reigned (the 28th, 29th, and 30th dynasties). The period before this is referred to as the "First Egyptian Satrapy" or the 27th Dynasty (525–404 BC).
1.1 First Egyptian Campaign
1.2 Second Egyptian Campaign
1.3 Satrapal rule in Egypt
3 Coinage
3.1 Achaemenid Egyptian coinage
3.2 Cilician coinage with Achaemenid rulers as Pharaohs
4 Pharaohs of the 31st Dynasty
5 Timeline of the 31st Dynasty (Achaemenid Pharaohs only)
6 Satraps of the 31st Dynasty
First Egyptian Campaign[edit]
In around 351 BC, Artaxerxes embarked on a campaign to recover Egypt, which had revolted under his father, Artaxerxes II. At the same time a rebellion had broken out in Asia Minor, which, being supported by Thebes, threatened to become serious.[5] Levying a vast army, Artaxerxes marched into Egypt, and engaged Nectanebo II. After a year of fighting the Egyptian Pharaoh, Nectanebo inflicted a crushing defeat on the Persians with the support of mercenaries led by the Greek generals Diophantus and Lamius.[6] Artaxerxes was compelled to retreat and postpone his plans to reconquer Egypt.
Second Egyptian Campaign[edit]
Artaxerxes III as Pharaoh, satrapal coinage of Cilicia.[7]
Cylinder seal depicting a Persian king thrusting his lance at an Egyptian pharaoh, while holding four other Egyptian captives on a rope.[8][9][10]
In 343 BC, Artaxerxes, in addition to his 330,000 Persians, had now a force of 14,000 Greeks furnished by the Greek cities of Asia Minor: 4,000 under Mentor, consisting of the troops which he had brought to the aid of Tennes from Egypt; 3,000 sent by Argos; and 1000 from Thebes. He divided these troops into three bodies, and placed at the head of each a Persian and a Greek. The Greek commanders were Lacrates of Thebes, Mentor of Rhodes and Nicostratus of Argos while the Persians were led by Rhossaces, Aristazanes, and Bagoas, the chief of the eunuchs. Nectanebo II resisted with an army of 100,000 of whom 20,000 were Greek mercenaries. Nectanebo II occupied the Nile and its various branches with his large navy. The character of the country, intersected by numerous canals, and full of strongly fortified towns, was in his favour and Nectanebo II might have been expected to offer a prolonged, if not even a successful, resistance. But he lacked good generals, and over-confident in his own powers of command, he found himself out-manoeuvered by the Greek mercenary generals. His forces were eventually defeated by the combined Persian armies at the Battle of Pelusium (343 BC).[11]
Probable portrait of young Artaxerxes IV as Pharaoh, wearing the Pharaonic crown.[7]
After his defeat, Nectanebo hastily fled to Memphis, leaving the fortified towns to be defended by their garrisons. These garrisons consisted of partly Greek and partly Egyptian troops, between whom jealousies and suspicions were easily sown by the Persian leaders. As a result, the Persians were able to rapidly defeat numerous towns across Lower Egypt and were advancing upon Memphis when Nectanebo decided to quit the country and flee southwards to Ethiopia.[11] The Persian army then completely routed the Egyptians and occupied the Lower Delta of the Nile. Following Nectanebo's flight to Ethiopia, all of Egypt submitted to Artaxerxes. The Jews in Egypt were sent either to Babylon or to the south coast of the Caspian Sea, the same location where the Jews of Phoenicia had earlier been sent.
After this victory over the Egyptians, Artaxerxes had the city walls destroyed, started a reign of terror, and set about looting all the temples. Persia gained a significant amount of wealth from this looting. Artaxerxes also imposed high taxes and attempted to weaken Egypt enough that it could never revolt against Persia again. During the 10 years that Persia controlled Egypt, believers in the native religion were persecuted and sacred books were stolen.[12] Before he returned to Persia, he appointed Pherendares as satrap of Egypt. With the wealth gained from his reconquest of Egypt, Artaxerxes was able to amply reward his mercenaries. He then returned to his capital, having successfully completed his invasion and occupation of Egypt.
Satrapal rule in Egypt[edit]
Portrait of Sabaces, Achaemenid satrap of Egypt, from his coinage. Circa 340-333 BC. Achaemenid Egypt.
It is not known who served as satrap after Artaxerxes III, but Pherendates II was an early satrap of Egypt. Under Darius III (336–330 BC) there was Sabaces, who fought and died at Issus and was succeeded by Mazaces. Egyptians also fought at Issus, for example, the nobleman Somtutefnekhet of Heracleopolis, who described on the "Naples stele" how he escaped during the battle against the Greeks and how Arsaphes, the god of his city, protected him and allowed him to return home.
In 332 BC, Mazaces handed over the country to Alexander the Great without a fight. The Achaemenid empire had ended, and for a while Egypt was a satrapy in Alexander's empire. Later the Ptolemies and the Romans successively ruled the Nile valley.
Egyptian Man in a Persian Costume, c. 343-332 BC, 71.139, Brooklyn Museum
Occasionally Egyptians wore foreign costumes and jewelry. The taste for non-Egyptian fashion arose during periods of extensive trade or diplomatic contact with distant courts, or when Egypt was controlled by a foreign power. The Persians, who twice invaded the Nile Valley from their Iranian homeland, dominated Egypt during Dynasty 27 (525–404 BC) and Dynasty 31 (342–332 BC). This statue to the left dates to the later period of Persian rule in Egypt.
The long skirt shown wrapped around this statue's body and tucked in at the upper edge of the garment is typically Persian. The necklace, called a torque, is decorated with images of ibexes, symbols in ancient Persia of agility and sexual prowess. The depiction of this official in Persian dress may have been a demonstration of loyalty to the new rulers.
Coinage[edit]
Achaemenid Egyptian coinage[edit]
Coin of Satrap Sabakes, in imitation of Athenian coinage. Circa 340-333 BC. Achaemenid Egypt.
Coin of Satrap Sabakes. Achaemenid Egypt. Circa 335-333 BC
Cilician coinage with Achaemenid rulers as Pharaohs[edit]
Another similar coin. Mazaios, Satrap of Cilicia, 361/0-334 BC.[7]
Coin of Cilicia 343-332 BC, thought to represent Artaxerxes III on the obverse, and a young Artaxerxes IV on the reverse, both wearing the Pharaonic crown.[13][7]
Pharaohs of the 31st Dynasty[edit]
Name of Pharaoh
Throne Name
Artaxerxes III 343–338 BC Placed Egypt under Persian rule for a second time
Artaxerxes IV 338–336 BC Only reigned in Lower Egypt
Khababash 338–335 BC Senen-setepu-ni-ptah Led a revolt against Persian rule in Upper Egypt, declared himself Pharaoh
Darius III 336–332 BC Upper Egypt returned to Persian control in 335 BC
Timeline of the 31st Dynasty (Achaemenid Pharaohs only)[edit]
Satraps of the 31st Dynasty[edit]
Dynasties of Ancient Egypt
All years are BC
First Dynasty I c. 3150–2890
Second Dynasty II 2890–2686
Old Kingdom
Third Dynasty III 2686–2613
Fourth Dynasty IV 2613–2498
Fifth Dynasty V 2498–2345
Sixth Dynasty VI 2345–2181
First Intermediate
Seventh Dynasty VII spurious
Eighth Dynasty VIII 2181–2160
Ninth Dynasty IX 2160–2130
Tenth Dynasty X 2130–2040
Early Eleventh Dynasty XI 2134–2061
Middle Kingdom
Late Eleventh Dynasty XI 2061–1991
Twelfth Dynasty XII 1991–1803
Thirteenth Dynasty XIII 1803–1649
Fourteenth Dynasty XIV 1705–1690
Second Intermediate
Fifteenth Dynasty XV 1674–1535
Sixteenth Dynasty XVI 1660–1600
Abydos Dynasty 1650–1600
Seventeenth Dynasty XVII 1580–1549
New Kingdom
Eighteenth Dynasty XVIII 1549–1292
Nineteenth Dynasty XIX 1292–1189
Twentieth Dynasty XX 1189–1077
Third Intermediate
Twenty-first Dynasty XXI 1069–945
Twenty-second Dynasty XXII 945–720
Twenty-third Dynasty XXIII 837–728
Twenty-fourth Dynasty XXIV 732–720
Twenty-fifth Dynasty XXV 732–653
Late Period
Twenty-sixth Dynasty XXVI 672–525
Twenty-seventh Dynasty
(1st Persian Period)
XXVII 525–404
Twenty-eighth Dynasty XXVIII 404–398
Twenty-ninth Dynasty XXIX 398–380
Thirtieth Dynasty XXX 380–343
Thirty-first Dynasty
(2nd Persian Period)
XXXI 343–332
Ptolemaic (Hellenistic)
Argead Dynasty 332–305
Ptolemaic Kingdom 323–30
See also: List of Pharaohs by Period and Dynasty
Name of satrap
Reigning monarch
Pherendates II c.343–before 333 BC Artaxerxes III
Sabaces † 333 BC Darius III Killed in the battle of Issus
Mazaces c.333–332 BC Darius III
Fragments of Ctesias (Persica)
Diodorus Siculus (Bibliotheca historica)
Fragments of Manetho (Aegyptiaca)
Flavius Josephus (Antiquities of the Jews)
Twenty-seventh Dynasty of Egypt (525 BC−404 BC) — also known as the First Egyptian Satrapy.
Sassanid conquest of Egypt
^ O'Brien, Patrick Karl (2002). Atlas of World History. Oxford University Press. pp. 42–43. ISBN 9780195219210.
^ Philip's Atlas of World History. 1999.
^ Davidson, Peter (2018). Atlas of Empires: The World's Great Powers from Ancient Times to Today. i5 Publishing LLC. ISBN 9781620082881.
^ Barraclough, Geoffrey (1989). The Times Atlas of World History. Times Books. p. 79. ISBN 0723003041.
^ Artaxerxes III PersianEmpire.info History of the Persian Empire
^ Miller, James M. (1986). A History of Ancient Israel and Judah. John Haralson Hayes (photographer). Westminster John Knox Press. p. 465. ISBN 0-664-21262-X.
^ a b c d e Kovacs, Frank L. (2002). "Two Persian Pharaonic Portraits". Jahrbuch für Numismatik und Geldgeschichte. R. Pflaum. pp. 55–60.
^ "a Persian hero slaughtering an Egyptian pharaoh while leading four other Egyptian captives" Hartley, Charles W.; Yazicioğlu, G. Bike; Smith, Adam T. (2012). The Archaeology of Power and Politics in Eurasia: Regimes and Revolutions. Cambridge University Press. p. ix, photograph 4.6. ISBN 9781139789387.
^ "Victor, apparently wearing the tall Persian headdress rather than a crown, leads four bareheaded Egyptian captives by a rope tied to his belt. Victor spears a figure wearing Egyptian type crown." in Root, Margaret Cool (1979). The king and kingship in Achaemenid art: essays on the creation of an iconography of empire. Diffusion, E.J. Brill. p. 182. ISBN 9789004039025.
^ "Another seal, also from Egypt, shows a Persian king, his left hand grasping an Egyptian with an Egyptian hairdo (pschent), whom he thrusts through with his lance while holding four prisoners with a rope around their necks." Briant, Pierre (2002). From Cyrus to Alexander: A History of the Persian Empire. Eisenbrauns. p. 215. ISBN 9781575061207.
^ a b "Artaxerxes III Ochus ( 358 BC to 338 BC )". Retrieved March 2, 2008.
^ "Persian Period II". Archived from the original on February 17, 2008. Retrieved March 6, 2008.
^ CNG: CILICIA, Myriandros. Mazaios. Satrap of Cilicia, 361/0-334 BC. AR Obol (10mm, 0.64 g).
Bresciani, Edda (1998). "EGYPT i. Persians in Egypt in the Achaemenid period". Encyclopaedia Iranica, Vol VIII, Fasc. 3. pp. 247–249.
Colburn, Henry P. (2017). "KHARGA OASIS". Encyclopaedia Iranica.
Provinces of the Achaemenid Empire
(Behistun / Persepolis / Naqsh-e Rustam / Susa / Daiva inscriptions)
Amyrgoi
Arachosia
Bactria
Carmania
Caucasian Albania
Chorasmia
Colchis
Dahae
Drangiana
1st Egypt / 2nd Egypt
Eber-Nari (Levant)
Kush (Nubia)
Gandāra (Gandhara)
Gedrosia
Hyrcania
Hindush
Margiana
Lesser Media
Massagetae
Parthia
Hellespontine Phrygia
Greater Phrygia
Samaritan Province
Sattagydia
Skudra (Thrace)
Sogdia
Yehud
See also Tax Districts of the Achaemenid Empire (according to Herodotus)
Ancient Egypt topics
Glossary of artifacts
Architecture (Egyptian Revival architecture)
Cities (list)
Funerary practices
Great Royal Wives
Pharaohs (list)
Egyptologists
Retrieved from "https://en.wikipedia.org/w/index.php?title=Thirty-first_Dynasty_of_Egypt&oldid=906438875"
States and territories established in the 4th century BC
States and territories disestablished in the 4th century BC
Achaemenid satrapies
4th century BC in Egypt
340s BC
340s BC establishments
4th-century BC establishments in Egypt
4th-century BC disestablishments in Egypt


text:
Angie Mayhew 5 Facts About Peter Mayhew's Wife
May 3, 2019 by L.A Girl Leave a Comment
Angie Mayhew
Angie Mayhew is the longtime wife of British actor, Peter Mayhew –who gave life to Star Wars' beloved character, Chewbacca in the iconic movie series.
Angie and her husband were married for decades prior to his passing on April 30th. Peter was weeks shy from his 75th birthday when he died of a heart attack.
Mayhew went on to appear in "The Empire Strikes Back," "Return of the Jedi," "Revenge of the Sith," "The Force Awakens" and "The Star Wars Holiday Special." He was active on the "Star Wars" convention circuit and wrote two books, "Growing Up Giant" and "My Favorite Giant."
In addition to his acting, Angie's husband was well known due to his impressive height, Peter stood at 7'3″ at his tallest.
He is survived by wife, Angie and the couple's children. Find out more about the woman behind the actor in her top five facts below.
#1 She was his wife of 20-years
Angelique Mayhew, formerly known as Angelique Luker –became Peter Mayhew's wife in 1999. They remained together until his death.
#2 She is a Texas native
Angie Mayhew was born Mary Angelique Cigainero on October 24, 1953, in Texas. After their nuptials, the couple moved to Boyd, Texas –where Angie still lives.
#3 She was supportive of his career
Angie appeared on two documentaries; From The Beginning: The Inaugural Year of Hound, in 2011, and Standing in the Stars: The Peter Mayhew Story in 2016.
#4 She is a mom of three
Peter and Angie Mayhew welcomed three children together, daughters Katy, Sheryl and Kathleen.
#5 She and her husband run a foundation
The couple established the Peter Mayhew Foundation to provide funds for those in need, and suported the 501st Legion, Wounded Warriors, Make-a-Wish and other non-profits. Donations may be made to the Peter Mayhew Foundation.
Usman Hanif
Mr. Usman Hanif From his early beginnings in Pakistan to his college years in London and the many … Keep Reading...
Read More About: ENTERTAINMENT WAGS


The state of Louisiana has apparently reached a deal on the Cooperative Endeavor Agreement betwee Ochsner and University Health. This will put Ochsner in place to run the local safety net hospital and the LSU Med School in Shreveport.
We caught up with Matthew Block, the Governor's Executive Counsel to talk about this new deal.
KEEL News also caught up with State Senator Greg Tarver to get his opinion about this deal.
Once the agreement gets the ok by the LSU Board of Supervisors and the Joint Legislative Committee on the Budget it will be put into place. It's expected to begin October 1st.


text:
Premier League Tickets
La Liga Tickets
Bundesliga Tickets
Serie A Tickets
Champions League Tickets
Europa League Tickets
EXO Tickets
Westlife Tickets
The Chainsmokers Tickets
K-pop Festival Tickets
More Concert Tickets
More Artist Tickets
Theatre and Musicals »
Other Musicals Tickets
More Arts and Theatre Tickets
Search by city »
Overseas city
Ronald Cheng
Ronald Cheng Tickets
There are no scheduled events yet for Ronald Cheng
Watch the great Ronald Cheng– live in concert
One of the greatest entertainers to come from Hong Kong, Ronald Cheng is a Cantopop and Mandopop artist. He has been one of the biggest stars in the saturated 90s pop scene and is still an international sensation, touring in various countries such as the United States, Taiwan, China and many more. His voice is as amazing as it has ever been and his performances excite fans of all ages. Want to buy or sell your Ronald Cheng tickets? Head to StubHub and find many different artists where you'll be sure to find some amazing deals. Should you decide that you cannot use your tickets, simply sell them to another group of lucky fans, so that your money or tickets don't go to waste.
The best in movies and music
With a rich history in both music and film, Ronald Cheng has spent quite a long time both on the silver screen and in the recording studio. He had produced his first album in 1996 titled "In A Dilemma". His film career also took off one year later in "A Chinese Ghost Story: The Tsui Hark Animation". Despite being a best-selling artist in Hong Kong for many years, his first award didn't come until 2012 for his role in the comedy film "Vulgaria" at the Golden Horse Awards. His second acting award came in 2018 at the Film Awards of Hong Kong for his song in "Concerto of the Bully". Throughout his career, he has worked with and for other popular artists like Alan Tam, Richard Marx and Priscilla Chan. You can listen to all his greatest hits live when you order your Ronald Cheng tickets with StubHub and try your luck with getting the best seats available.
For a unique performance
Ronald Cheng has performed in various different venues throughout his career. Take your seat, relax, and prepare for a remarkable performance by Cheng and his band. The music will amaze you and if you've been a fan of his for many years, then you'll be reminded of this by his best hits, bringing you back many good memories. Take your family and enjoy a fun-filled night of music and entertainment. Stay up to date on Cheng's tour and be sure to buy your Ronald Cheng tickets with StubHub as soon as they become available. Cheng's fans from all over the country are looking to buy tickets too, so be sure to act fast!
CHAT Service: Mon-Fri 9:00-21:00
You are accessing StubHub Hong Kong
Buy tickets for Ronald Cheng at StubHub US
Change to StubHub US
Cambiar a StubHub Internacional Estados Unidos
Continue on StubHub Hong Kong
We use cookies to improve our web services. If you continue browsing, we consider that you agree to its use. Learn more about Cookie Policy here.


text:
Report: African migrants 'left to die' in Saudi Arabia's hellish Covid detention centres.
in Saudi
African migrants 'left to die' in Saudi Arabia's hellish Covid detention centres
A few months after Saudi Arabia pledged to investigate slave-like conditions inside detention centres for tens of thousands of Ethiopian migrants, a new report shows nothing has changed and this slave-like culture continues
Those migrants who found a way to speak to international media, told the Telegreaph that since news of their plight echoed around the world, they have been routinely beaten by prison guards who scoured frantically looking for smuggled phones. Reports indicate that the prisoners were stripped naked, searched and abused.
After a widespread international outcry, which included a vote of condemnation by the European Parliament, Saudi officials promised to investigate all the government centres.
However, in September migrants told The Telegraph they were being punished for trying to communicate with the outside world. Detainees said they had been handcuffed to each other at the ankles, stripped naked and kept without food or water for 24 hours as punishment.
"It is shocking to hear that up to 16,000 Ethiopian migrants might be languishing in detention in the Al Shumaisi facility. Human Rights Watch and the Telegraph documented horrific conditions in two other centres in Jazan Saudi Arabia where thousands more Ethiopian migrants may also reside," said Nadia Hardman, a researcher at the NGO Human Rights Watch.
"We repeat our call on Saudi Arabia to immediately release the most vulnerable and improve the miserable conditions for the thousands that remain."
Within the last few weeks, Saudi Arabia sent nearly 150 women and children back to Ethiopia. This was initially greeted as good news and a step in the right direction.
However, an Ethiopian document from last August that was leaked shows that the repatriation was part of an arrangement between Saudi and Ethiopian authorities, which disgustingly requires migrants to purchase their own one way-tickets home, using the Ethiopian Airline. something the vast majority of migrants can't do.
Tags: African migrantsCovid detention centresSAUDI ARABIA
Priti Patel comes under-fire for visiting Bahraini prison linked with abuse
Tweet about Sheikh Alodah and detainees in Saudi prisons
AOHR UK Calls for the Release of Ten Egyptian Citizens Illegally Held in Saudi Arabia


text:
Startups and Banks: It's Just Easier to Cooperate
Binna Kim
Our office recently caught up with something important that PayPal founder Max Levchin said, which was captured in the Spring issue of Strategy + Business.
Fintechs have what banks want: superior underwriting engines with models and access to troves of big data, modern and relevant front ends aligned to customer expectations and preferences, and software architecture that has been developed from the ground up based on modern technologies and principles.
This quote came in the context of an article that examines how established companies in many fields can join forces with upstart competitors to the mutual benefit of both the incumbent and the startup. But it speaks to the relationship between banks and startups directly.
The point that Levchin and the article's authors have captured is the simple reason why fintech startups have not and will not destroy traditional banking services: because they have no interest in doing so. A startup replacing a bank would be like a startup replacing the electric grid.
Instead, it's just easier to for new, innovative companies to cooperate with the established banks. These startups depend on the infrastructure of traditional banks and are perfectly happy to take a cut for bringing business into that ecosystem.
The takeaway here for communicators is that, in order to understand today's banking challenges full-circle, one must be familiar with the startup scene, particularly in New York, where much of the fintech innovation is occurring. Both culturally and operationally, the startup grind is much, much different from institutional banking, and when the two fields cooperate, telling a unified story is a balancing act that only the best communicators can pull off.


text:
Q: Jquery TypeError when replacing page content I'm trying to achieve the following:
A simple Java Spring application, after receiving a GET request, sends me an HTML page with a form. When the button is pressed in this form, there is a POST request with an XML content sent back to the Spring app, which, in turn, responds with an HTML page. I would like to be able to display this response as a proper page in a browser, including all the scripts being downloaded and fully functional.
The form HTML page:
<!DOCTYPE html>

    <meta charset="UTF-8" />
    <title>Request Report Form</title>

<form method="post" action="">

</form>

The $("html").html(data); part above is supposed to replace the current page's content with the content received from the server, as far as I understand. But the page is not being displayed. There is an error message in the browser's console: "TypeError: n.head is null", it seems to have to do with JQuery, see the image link.

My questions are, why does JQuery kicks in and what is it trying to do? And how do I fix this error?
I don't know much about frontend side of development, so please go easy on me ;-)
Edit
Just realised that my first question is moot, I am trying to display the response page using JQuery, so obviously, it kicks in at that point. But the call fails for some reason.
The content of the response from the server that I'd like to see rendered by the browser:
<!DOCTYPE html>

    <meta charset="UTF-8">
    <title>Progress Report</title>
    <link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.3.1/css/bootstrap.min.css" integrity="sha384-ggOyR0iXCbMQv3Xipma34MD+dH/1fQ784/j6cY/iJTQUOhcWr7x9JvoRxT2MZw1T" crossorigin="anonymous">

<body data-user="eyJjaGFydCI6eyJyZW5kZXJUbyI6IlByb2dyZXNzIiwidHlwZSI6ImNvbHVtbiJ9LCJzZXJpZXMiOlt7Im5hbWUiOiJQcm9ncmVzcyIsImRhdGEiOlsxLDEsMCwwLDAsMCwwLDAsMCwwXX1dLCJ0aXRsZSI6eyJ0ZXh0IjoiUHJvZ3Jlc3MifSwieEF4aXMiOlt7InR5cGUiOiJsaW5lYXIiLCJjYXRlZ29yaWVzIjpbIlJlZ2lzdGVyZWQ8YnI+KDQuNi4xMykiLCJTZXNzaW9uIDE8YnI+KDEyLjcuMTUpIiwiU2Vzc2lvbiAyIiwiU2Vzc2lvbiAzIiwiU2Vzc2lvbiA0IiwiU2Vzc2lvbiA1IiwiU2Vzc2lvbiA2IiwiU2Vzc2lvbiA3IiwiU2Vzc2lvbiA4IiwiRmluaXNoZWQiXX1dLCJ5QXhpcyI6W3sidGl0bGUiOnsidGV4dCI6IlNlc3Npb24gU3RhcnRlZCJ9LCJtaW4iOjB9XX0=">

A: Found an answer here: stackoverflow.com/a/11984907/3182810. Replacing
$("html").html(data);

in the form with
document.open();
document.write(data);
document.close();

does the trick.


The EMS High Precision, DLC tweezers feature tips covered in a pure diamond film grown directly on the exposed metallic substrate via an innovative plasma-assisted deposition technique. It is not an adhesive-bonded diamond powder. The coating is comprised of carbon clusters which develop a crystalline structure and properties similar to a natural diamond. This procedure leaves the coating hydrogen free. These tweezers perform well in demanding enviroments and working with hard samples or biological materials. Ideal for use in clean rooms. Tips stand up to repeated use. The body of the tweezer is non-magnetic, low carbon stainless steel.
Anti-Acid/Anti-Mag SS - tips: straight, sharp, fine, superior finish. OAL: 120mm, 4¾", Flat, sharp fine tips.
Anti-Acid/Anti-Mag SS - tips: flat, round, curved, superior finish. OAL: 120mm, 4¾", Curved.
Anti-Acid/Anti-Mag SS - tips: straight, extra fine, superior finish. OAL: 110mm, 4¼", Extra fine tips.
Anti-Acid/Anti-Mag SS - tips: straight, extra fine, very sharp, superior finish. OAL: 140mm, 5 1/2", Extra fine tip.
Anti-Acid/Anti-Mag SS - tips: straight, extra fine, very sharp, superior finish. OAL: 150mm, 6", Extra fine tip.


The Green Plate Special program incorporates the use of a logo that all restaurants in the city can use to highlight dishes that feature local ingredients. In order to use the logo and participate in the program, over 50% of a menu item's main ingredients must be locally sourced within 300 miles, and the description of the dish must tell people the source of the ingredients. Using this logo will encourage residents to buy local dishes and give recognition to restaurants that make the extra effort to get locally sourced goods.


text:
Q: Send Emails using Excel VBA from a table I have a list of emails that are in a table and I would like to send these people emails.
At the moment, my code only references one cell where I have stored multiple emails.
emailItem.To = Range("A2").Value
emailItem.CC = Range("B2").Value

How do I reference a table array so when I add or remove someone from the distribution list, it becomes 'dynamic'.
Here is what my table looks like:

Here is the code I'm working with:
Option Explicit

Sub Send_Email_With_Attachment()
    Dim emailApplication As Object
    Dim emailItem As Object

    Set emailApplication = CreateObject("Outlook.Application")
    Set emailItem = emailApplication.CreateItem(0)

    'Date Update in Subject Line

    Dim lastSunday As Date
    lastSunday = DateAdd("d", 1 - Weekday(Now), Now)

    'Now build the email.
    emailItem.To = Range("A2").Value
    emailItem.CC = Range("B2").Value

    emailItem.Subject = "Training Report  - " & Format(lastSunday, "dd-MM-yyyy")
    emailItem.Body = "Dear All" & vbCrLf & vbCrLf & "Please find attached the Weekly  Training report." & vbCrLf & vbCrLf & "Kind Regards,"

    ' Attach any file from computer

    'Send the email
    emailItem.Display
End Sub

A: Instead of
emailItem.To = Range("A2").Value
emailItem.CC = Range("B2").Value

use
Dim EmailTable As ListObject  ' define your email table in the sheet
Set EmailTable = ThisWorkbook.Worksheets("Sheet1").ListObjects("Email2")

emailItem.To = Join(Application.Transpose(EmailTable.ListColumns("To").DataBodyRange.Value2), ";")
emailItem.CC = Join(Application.Transpose(EmailTable.ListColumns("CC").DataBodyRange.Value2), ";")

Note that Email2 is the name of your table and Sheet1 needs to be the name of the worksheet. Transpose will make a one dimensional array out of the column that we can Join into a string seperated by ;

A: This is code I used to generate emails.
The code will only work if BOTH 'To & CC' are in the same Table.
The code will work only on the ACTIVE Sheet that you're in.
The code also references a PAST date and can be modified very easily. Change this part of the code: "("d", 1 - Weekday(Now), Now)" to suit your need.
Option Explicit

Sub Send_Email_With_Attachment()
    Dim OutApp As Object, OutMail As Object
    Dim emailTo As String, emailCC As String
    Dim lastSunday As Date
    Dim c As Range

    lastSunday = DateAdd("d", 1 - Weekday(Now), Now)

    emailTo = WorksheetFunction.TextJoin(";", True, ActiveSheet.Range("Email2[To]"))
    emailCC = WorksheetFunction.TextJoin(";", True, ActiveSheet.Range("Email2[CC]"))

    Set OutApp = CreateObject("Outlook.Application")
    Set OutMail = OutApp.CreateItem(0)
    With OutMail
        .To = emailTo
        .CC = emailCC
        .Subject = "Report  - " & Format(lastSunday, "dd-MM-yyyy")
        .Body = "Dear All" & vbCrLf & vbCrLf & _
        "Please find attached the Weekly report." & vbCrLf & vbCrLf & "Kind Regards,"
        '.Attachments.Add ""
        .Send
    End With
End Sub