text:
\section{Introduction}
Clustering is a core Machine Learning task and one of the most widely used types of algorithms in general.
$k$-means and Gaussian mixture models (GMMs) represent two of the most popular clustering algorithms \citep[see, e.g.,][]{Berkhin2006,McLachlanPeel2004}.
Both require ${\mathcal O}(NCD)$ numerical operations per iteration (see abstract for definitions of $N$, $C$, and $D$).
Active ongoing research provides ever improving bounds on convergence times in terms of iteration steps \citep{ArthurEtAl2009,MoitraValiant2010,XuEtAl2016}, and empirical results show very fast convergence in practice \citep{Duda2007}.
\paragraph{Related work and own contribution.}
Convergence times can be strongly improved by careful seeding, and seeding methods have recently been made very efficient \citep{BachemEtAl2016b}.
After seeding, the limiting factor for efficiency remains the complexity of one $k$-means or GMM iteration \citep[e.g.,][for a discussion]{BachemEtAl2016a}, which can be very relevant in practice \cite[e.g.,][]{RosenbaumWeiss2015}.
The reduction of complexity per iteration (e.g., of $k$-means) is therefore also the goal of other popular approaches.
The efficiency of distance computations can, e.g., be improved by exploiting the triangle inequality \citep{Elkan2003}, or random projections for independence of the dimensionality $D$ \citep{ChanLeung2017}.
And by following the idea of \citet{Moore1999} or coresets \citep{HarPeledMazumdat2004,FeldmanEtAl2011,LucicEtAl2017,BachemEtAl2017} the dependency on the number of data points $N$ can drastically be reduced.
In this work our focus is on reducing the linear dependency on the number of clusters~$C$.
There are two views which may highlight the importance of this dependency:
First, with very large numbers of data points $N$, a complexity reduction, e.g., from ${\mathcal O}(NCD)$ to ${\mathcal O}(NGD)$ with $G\ll C$ provides a very large reduction in terms of required computations.
Second, if coresets are used to reduce $N$, and triangle inequalities or random projections are used to reduce the dependence on $D$, then the dependence on $C$ remains the main bottleneck.

Our tool for complexity reduction is the application of truncated distributions to approximate exact posteriors.
Truncated approximations have been applied to a number of probabilistic data models, and most frequently to multiple-causes models for which the number of latent states increases
exponentially with the number of latents \citep{PuertasEtAl2010,DaiEtAl2013,HennigesEtAl2014,SheikhEtAl2014}.
Truncated approximations do not assume a-posteriori independence like factored variational approaches \citep{SaulEtAl1996,JordanEtAl1999}, they typically result in tight free energy bounds, and they are very efficient \citep{SheikhEtAl2014,SheikhLucke2016}.
For mixture models, truncated distributions represent a very natural choice.
If considering the posterior of a given data point (i.e., its cluster responsibilities), then typically only few clusters contribute significantly to the over-all posterior mass.
Truncated distributions approximate the full posteriors by maintaining just the $C'$ highest posterior values while setting all other values to zero (see \cref{FigVarGMM}, top).
\citet{DaiLucke2014} used truncated distributions to make position invariant mixture models for images more efficient,
\citet{ForsterLucke2017} applied truncated distributions to standard Poisson mixtures, and \citet{SheltonEtAl2017}, \citet{HughesSudderth2016}, and \citet{LuckeForster2017} used truncated posteriors for standard GMMs.
In all these applications, truncated distributions reduced the computational cost compared to exact EM.
None of these contributions aimed to show or have shown that one complete EM iteration for clustering can scale sublinearly with $C$.
While, e.g., \citet{HughesSudderth2016} and \citet{ForsterLucke2017} discuss the reduction of M-step complexity, and while $k$-means \citep[see][for its variational EM formulation]{LuckeForster2017} has an M-step complexity of ${\mathcal O}(ND)$, all these algorithms use a full variational E-step with $NC$ distance evaluations (${\mathcal O}(NCD)$ computations).
Other work with focus on $k$-means also aimed at reducing the dependency on $C$.
Often such work remains theoretical, including run-time analysis in terms of iterations \citep[see][for a discussion of the literature]{KanungoEtAl2002}, but also concrete suggestions for practically applicable versions of $k$-means have been made \citep[][and others]{Phillips2002,ShindlerEtAl2011,Curtin2017}.
\citet{ShindlerEtAl2011} focus on efficient memory usage. \citet{Phillips2002} shows a reduction to ${\mathcal O}(ND\gamma + C^2D + C \log(C))$ run-time complexity
per iteration but $\gamma$ is large (on the order of $C$) initially. \citet{Curtin2017} uses tree-based algorithms and novel pruning strategies to achieve a complexity (after initialization, per iteration, $D$ not considered) of ${\mathcal O}(N + C \log(C))$ under mild assumptions.

To the knowledge of the authors, neither \citet{Phillips2002,Curtin2017} nor any other contribution shows or has considered possible a complexity reduction in $C$ to a level similar to the one reported here.
More specifically, we are not aware of work that effectively improves a $k$-means or GMM objective while the complexity of one iteration does not depend on $C$.\vspace{-1mm}

\section{Truncated EM for GMMs}
Given a set of $N$ data points, $(\yVec^{(1)},\ldots,\yVec^{(N)})$, our goal is to find parameters $\Theta$ that maximize the data log-likelihood,
where $p(\yVec\,|\,\Theta)$ is given by a GMM with isotropic, equally weighted Gaussians:\vspace{0mm}
\begin{align}
&\textstyle {\mathcal L}(\Theta) = \sum_{n} \log\!\big( p(\yVec[(\inpn)]\,|\,\Theta) \big)\text{, where} \label{EqnLikelihood}\\
&\textstyle p(\yVec\,|\,\Theta) = \frac{1}{C} (2\pi\sigma^2)^{-\frac{D}{2}} \sum_{c} \exp\!\big(\!-\!\frac{1}{2\sigma^2}\|{}\yVec-\vec{\mu}_c\|{}^2\big).\label{EqnGMMIso}
\end{align}
The presumably most popular method to optimize a GMM
is EM, which consists for \cref{EqnGMMIso} of the updates:
\begin{align}
&\!\! \textstyle d_{c}^{(n)} = \|{}\yVec[(\inpn)]-\vec{\mu}_c\|,\,\, s_c^{(n)} = \frac{\exp\!\big(-\frac{1}{2}(d_{c}^{(n)} / \sigma)^2\big)} {\sum_{c'}\exp\!\big(-\frac{1}{2}(d_{c'}^{(n)} / \sigma)^2\big)}, \label[pluralequation]{EqnGMMEStep} \\
&\!\! \textstyle \vec{\mu}^{\mathrm{\,new}}_c \!\! = \! \frac{\sum_{n}\!s_c^{(n)}\yVec[(\inpn)]}{\sum_{n}s_c^{(n)}}\!,
\sigma_{\mathrm{new}}^2 \!\! = \! \frac{1}{DN}\!\sum\limits_{n,c}s_c^{(n)} \|\yVec[(\inpn)]-\vec{\mu}^{\mathrm{\,new}}_c\|^2\!.\!\!\!
\label[pluralequation]{EqnGMMMStep}
\end{align}
Standard EM for the model (\ref{EqnGMMIso}) iterates E-step (\ref{EqnGMMEStep}) and M-step (\ref{EqnGMMMStep}), and each iteration changes the parameters $\Theta=(\vec{\mu}_{1:C},\sigma^2)$ such that the likelihood is monotonously increased (until convergence to potentially local maxima).
We will refer to this algorithm as standard GMM.\vspace{-1mm}

In order to reduce the complexity of standard GMM, we here apply variational EM.
Instead of seeking to maximize the likelihood directly, the basic idea of variational EM is to maximize a lower-bound of the likelihood, the free energy.
The free energy depends on variational distributions which are chosen to (A)~approximate exact posterior distributions $p(c\,|\,\yVec,\Theta)$ as closely as possible, and to (B)~result in a less complex optimization objective.
For our purposes, we use variational distributions $q^{(n)}(c;{\mathcal K},\hat{\Theta})$ which depend
on two types of variational parameters, sets of states ${\mathcal K}=({\mathcal K}^{(1)},\ldots,{\mathcal K}^{(N)})$ and $\hat{\Theta}$:
\begin{align}
\!\!\!\! s_c^{(n)} \approx q^{(n)}(c;{\mathcal K},\hat{\Theta})
& = \frac{p(c,\yVec[(\inpn)]|\hat{\Theta})}{\!\!\!\!\sum\limits_{c'\in\KK^{(n)}}\!\!\!\!p(c',\yVec[(\inpn)]|\hat{\Theta})}\,\delta(c\in\KK^{(n)}),\!\!
\label{EqnQMain}
\end{align}
where $\delta(c\!\in\!\KK^{(n)})=1$ if $c\!\in\!\KK^{(n)}$ and zero otherwise.
The used variational distributions \cref{EqnQMain} are truncated posteriors, i.e., they are proportional to the exact posterior for all $c\in\KK^{(n)}$ while they are exactly zero for all other $c\notin \KK^{(n)}$.
\Cref{FigVarGMM} (top: $s_c^{(m)}$ and $q_c^{(m)}$) illustrates the approximation.
If we choose $\KK^{(n)}$ for the GMM to contain all $c$, i.e.\, $\KK^{(n)}=\{1,\ldots,C\}$, we recover standard GMM.
If we choose $\KK^{(n)}$ to contain just one single element, we can recover standard $k$-means \citep{LuckeForster2017}, without having to take the limit to zero variances $\sigma^2$.
Given the variational distributions \cref{EqnQMain}, the corresponding free energy is:
\begin{align}
{\mathcal F}({\mathcal K},\hat{\Theta},\Theta) \! \vcentcolon= &
    \sum\limits_{n} \! \Big( \!
      \sum_{c} q^{(n)}(c;{\mathcal K},\hat{\Theta})
       \log \!\big( p(c,\yVec[(\inpn)]\,|\,\Theta)\big) \!
      \Big) \nonumber \\
      & + \sum\limits_{n}H\big(q^{(n)}(c;{\mathcal K},\hat{\Theta})\big)\,,
\label{EqnFreeEnergy}
\end{align}
where $H(p(c))$ is the entropy of a distribution $p(c)$.
Maximization of the free energy \cref{EqnFreeEnergy} involves a three-stages optimization w.r.t.\ the parameters ${\mathcal K}$, $\hat{\Theta}$ and $\Theta$.
Because of the standard functional form of the free energy \cref{EqnFreeEnergy}, the update equations for $\Theta$ (the M-step) remain identical to \cref{EqnGMMMStep} but use the approximation \cref{EqnQMain} instead of the exact $s_c^{(n)}$ in \cref{EqnGMMEStep}.
The complexity of one M-step is given by the number of non-zero $s_c^{(n)}$ values and by $D$, i.e., for $|\KK^{(n)}|=C'$ one update of $\Theta$ has a complexity of ${\mathcal O}(NC'D)$.

For the variational E-step it was shown \citep[][]{Lucke2016} that it is sufficient to set $\hat{\Theta}=\Theta$ and to maximize a simplified expression of ${\mathcal F}({\mathcal K},\Theta,\Theta)=:{\mathcal F}({\mathcal K},\Theta)$:
\begin{equation}
{\mathcal K}^{\ast} = \myargmax{{\mathcal K}}{\big\{{\mathcal F}({\mathcal K},\Theta)\big\}}
\end{equation}
Here, we now replace the maximization of the free energy by an increase of the free energy (partial E-step).
For the GMM of \cref{EqnGMMIso} it can be shown
that an increase of ${\mathcal F}({\mathcal K},\Theta)$ has a direct geometrical interpretation (\cref{app:ProofProp1} provides the proof following \citet{LuckeForster2017} and \citet{Lucke2016}):\vspace{-2mm}

\paragraph{Proposition 1.}
If we replace for an arbitrary $n$ a cluster $c\in\KK^{(n)}$ by a cluster $\tilde{c}\not\in\KK^{(n)}$ such that \mbox{$\|\yVec[(\inpn)]-\vec{\mu}_{\tilde{c}}\|<\|\yVec[(\inpn)]-\vec{\mu}_{c}\|$}, then ${\mathcal F}({\mathcal K},\Theta)$ increases.

\begin{figure}[b!]
\centering
  \vspace{4pt}
	\resizebox{0.41\textwidth}{!}{
  		\input{./figs/FigVarGMMTrunc01.pdf_t}
	}

	\caption{
\textbf{Top:} Exact responsibilities $s_c^{(m)}$ and truncated responsibilities $q_c^{(m)}$ for a data point $\yVec^{(m)}$ with ${\mathcal K}^{(m)}$ containing the closest ${C'=3}$ clusters.
\textbf{Remainder:} Illustration of the search space $\GG^{(n)}$ to find clusters increasingly close to $\yVec[(\inpn)]$.
The search space consists of the clusters in $\KK^{(n)}$ and the nearest neighbors of these clusters ($\GG_{c}$ with $c\in\KK^{(n)}$).
For the illustration we used well separated clusters, $|\KK^{(n)}|=C'=3$ and $|\GG_{c}|=G=5$.
Cluster centers $\vec{\mu}_c$ were assumed here to already represent the clusters well.
See \cref{app:IllustrationOFAlgorithms} for more information and a complete illustration across iterations.}
  \label{FigVarGMM}
\end{figure}
\section{Efficient Partial EM}
Our algorithms iteratively increase the free energy using Prop.\,1 and M-step \cref{EqnGMMMStep} until convergence.
By relating partial EM to the geometric interpretation of cluster distances (Prop.\,1), our approach maintains the guarantee to monotonously increase the free energy whenever clusters are found that are closer to $\yVec[(\inpn)]$ than those previously considered.
Finding closer clusters can be realized much more efficiently than finding the closest clusters (which is of order ${\mathcal O}(NCD)$).
To reduce run-time complexity, our goal is to as efficiently as possible find clusters $c$ for each $\KK^{(n)}$ such that the free energy is increased as effectively as possible.
The free energy will always increase if we use Prop.\,1 to update $\KK^{(n)}$.
However, blindly (e.g. uniform randomly) searching for closer clusters can be expected to be very inefficient.
Instead, we here follow the strategy of defining a search space for each data point based on nearest cluster neighborhoods of each cluster in $\KK^{(n)}$.

Although more efficient in terms of computational complexity, partial E-steps require us to memorize the variational parameters $\KK^{(n)}$ across iterations.
With one set $\KK^{(n)}$ for each data point, we have with $|\KK^{(n)}|=C'$ an additional memory requirement of ${\mathcal O}(NC')$ for all our variational algorithms.

\begin{algorithm}[t]
init $\vec{\mu}_{1:C}$, $\sigma$ and $\KK^{(n)}$ for all $n$;\\[1mm]
\Repeat{$\vec{\mu}_{1:C}$ and $\sigma^2$ have converged\vspace{0.0mm}}
{
\For{$c=1:C$}{
  \For{$\tilde{c}=1:C$}{
    $d_{c\tilde{c}} = \|\vec{\mu}_{\tilde{c}}\,-\,\vec{\mu}_c\|$;
  }
  $\GG_{c}= \{\tilde{c}\,|\,d_{c\tilde{c}}$ is among the $G$ \linebreak
  \phantom{$\GG_{c}= \{\tilde{c}\,|$}smallest distances $d_{c:}\}$;
}
	\For{$n=1:N$}{
  $\GG^{(n)} =\bigcup_{c\in\KK^{(n)}}\GG_{c}$;\\[1mm]
  \For{$c\in\GG^{(n)}$}{
      $d^{(n)}_{c} = \|\yVec[(\inpn)]\,-\,\vec{\mu}_{c}\|$;
  }
  $\KK^{(n)} = \{c\,|\,d^{(n)}_{c}$ is among the $C'$ \linebreak
  \phantom{$\KK^{(n)}=\{c\,|$}smallest distances$\}$;

}
\For{$n=1:N$}{
  \For{$c\in\KK^{(n)}$}{
            $s_c^{(n)} = \frac{\exp\!\big(-\frac{1}{2}(d_{c}^{(n)} / \sigma)^2\big)}{\sum_{c'\in\KK^{(n)}}\exp\!\big(-\frac{1}{2}{(d_{c'}^{(n)} / \sigma)}^2\big)}$;
  }
}
  %
  %
update $\vec{\mu}_{1:C}$ and $\sigma^2$ using \cref{EqnGMMMStep} with \cref{EqnQMain};
}
\caption{GMM with partial truncated E-step and exhaustive cluster neighborhood evaluation.
\label{alg:var-GMM-X}}
\end{algorithm}

\subsection{Exhaustive Cluster Neighborhoods}
To illustrate our approach, first consider \cref{FigVarGMM}.
It visualizes a set $\KK^{(n)}$ and its distances to the data point $\yVec[(\inpn)]$ and its closest neighboring clusters.
We denote the set of clusters consisting of $c$ and its $G-1$ nearest neighboring clusters by $\GG_{c}$ and the union of sets $\GG_{c}$ belonging to clusters $c\in\KK^{(n)}$ as $\GG^{(n)}$.
To update $\KK^{(n)}$ such that it only includes clusters with equal or smaller distances to $\yVec[(\inpn)]$ as before, we now won't evaluate all data-to-cluster distances.
Instead, we only calculate the distances of $\yVec[(\inpn)]$ to the clusters in $\GG^{(n)}$ and choose the $C'$ closest clusters from these as new $\KK^{(n)}$.
Optimization of $\KK^{(n)}$ then involves at most \mbox{$C'G<C$} distance evaluations, and it can be considered much more likely than random search that clusters~$c$ which improve the free energy are found.
However, we require additional computations to determine the nearest neighbors for each cluster.
These computations are, however, independent of $N$.

\cref{alg:var-GMM-X} shows the complete algorithm, which consists of three blocks of computation: (1st block)~computation of cluster-to-cluster distances and definition of sets $\GG_{c}$; (2nd block)~computation of data-to-cluster distances and update of $\KK^{(n)}$; and (3rd block)~update of model parameters $\Theta$.
The complexities are given as follows:

The first block computes the nearest neighbor sets $\GG_{c}$ (where we do not exploit symmetry of $d_{c\tilde{c}}$ for simplicity).
The complexity of the required distance evaluations is ${\mathcal O}(C^2D)$.
The following problem of finding the $G$ smallest elements in an array of $C$ elements is an unordered partial sorting problem.
This is provably solvable with complexity ${\mathcal O}(C)$, e.g., by applying the median-of-medians algorithm \citep{BlumEtAl1973} or introselect \citep{Musser1997}.

The second block computes for each data point the distances to all clusters in $\GG^{(n)}$ consisting of all $G$ neighbors $\GG_{c}$ (including $c$) of all $C'$ clusters $c\in\KK^{(n)}$.
We thus have to compute ${\mathcal O}(C'G)$ distances for each $n$, which amounts to ${\mathcal O}(NC'GD)$.
If the clusters in $\KK^{(n)}$ are close together, they might share some nearest neighbors, which reduces the actual number of distance computations.
Also note that the ${\mathcal O}(C'G)$ can never exceed the total number of clusters $C$.
To update one set of $\KK^{(n)}$, we again have to solve an unordered partial sorting problem.
For a given $n$, we have $C'G$ distances, such that finding the $C'$ smallest elements is of complexity ${\mathcal O}(C'G)$, with ${\mathcal O}(NC'G)$ total evaluations.
Hence, the evaluations of distances $d_{c}^{(n)}$ dominate the second block, which has an overall complexity of~${\mathcal O}(NC'GD)$.

Finally, the third block computes the responsibilities $s_c^{(n)}$ and updates the model parameters $\vec{\mu}_{1:C}$ and $\sigma^2$.
Both have a complexity of ${\mathcal O}(NC'D)$.

The overall complexity of one EM iterations of \cref{alg:var-GMM-X} is consequently given by ${\mathcal O}(NC'GD+C^2D)$.
Storage of sets $\GG_{c}$ requires ${\mathcal O}(CG)$ additional memory, which results in a total of ${\mathcal O}(CD+NC'+CG)$ memory demand.
We provide an illustration of the algorithm in \cref{app:IllustrationOFAlgorithms} and a line-by-line complexity analysis in \cref{app:ComplexityAnalysis}.

\subsection{Estimated Cluster Neighborhoods}
For \cref{alg:var-GMM-X}, we introduced new sets ${\mathcal G}_c$ that require additional evaluations of cluster-to-cluster distances.
This can allow for a complexity reduction in the updates of our variational parameters $\KK^{(n)}$, but adds a computational cost of ${\mathcal O}(C^2D)$.
With \Cref{alg:var-GMM-S} we show a new way to further reduce this algorithmic complexity.

In \Cref{alg:var-GMM-S}, the data-to-cluster distance computations and updates of the sets $\KK^{(n)}$ remain exactly as in \cref{alg:var-GMM-X}.
However, to further improve efficiency, we now {\em estimate} the cluster-to-cluster distances $d_{c\tilde{c}}$ using the data-to-cluster distances $d_{c}^{(n)}$ which we anyway have to compute.
To do this, the ordering of the first and second blocks of \cref{alg:var-GMM-X} now changes -- \cref{alg:var-GMM-S} first computes the data-to-cluster distances $d_{c}^{(n)}$ before the sets $\GG_{c}$ are updated -- and we replace the exhaustive $\GG_{c}$ evaluation of \cref{alg:var-GMM-X} by estimated cluster neighborhoods.

To illustrate the estimation approach, first consider two non-overlapping clusters $c$ and $\tilde{c}$ with cluster centers $\vec{\mu}_c$ and $\vec{\mu}_{\tilde{c}}$ that already represent the two clusters well.
If we denote by ${\mathcal I}_c$ the set of all points $\yVec[(\inpn)]$ that have $c$ as closest cluster, ${{\mathcal I}_c=\{n\,|\,c=\myargmin{\tilde{c}=1:C}\,\|\yVec[(\inpn)]-\vec{\mu}_{\tilde{c}}\|\}}$\vspace{-4pt}, we may
estimate:
\begin{align}
d_{c\tilde{c}} \approx \frac{1}{|{\mathcal I}^*_c|} \!\!\! \sum_{\substack{n\in{\mathcal I}_c \\ \ \mathrm{if}\,\tilde{c}\in\GG^{(n)}}}\!\!\!\! \|\yVec[(\inpn)] - \vec{\mu}_{\tilde{c}}\| = \frac{1}{|{\mathcal I}^*_c|}\!\!\!\sum_{ \substack{n\in{\mathcal I}_c \\ \ \mathrm{if}\,\tilde{c}\in\GG^{(n)}}}\!\!\!\! d_{\ct}^{(n)}\,.
\label{EqnDCCEstimation}
\end{align}
If we sum over all $n\in{\mathcal I}_c$ (by ignoring the additional conditions for the sums and assuming ${\mathcal I}_c={\mathcal I}^*_c$ for now), then \Cref{EqnDCCEstimation} becomes exact for well separated clusters and close to optimal convergence points.
However, in general not all the $d_{\ct}^{(n)}$ that we require for \cref{EqnDCCEstimation} have been computed before.
We therefore introduce the condition $\tilde{c}\in\GG^{(n)}$, which ensures that only data points $n$ with known $d_{\ct}^{(n)}$ are summed over (see \cref{app:IllustrationOFAlgorithms} for an example).
$|{\mathcal I}^*_c|$ is then simply the number of summands.
For already well-learned $\KK^{(n)}$ and cluster centers $\vec{\mu}_c$, \cref{EqnDCCEstimation} estimates the $d_{c\tilde{c}}$ of close-by clusters well (and we are only interested in those close-by distances).
The summation in \cref{EqnDCCEstimation} for distances to far-away clusters may not contain any data points and are ignored in practice.
Away from convergence of $\Theta$ and $\KK^{(n)}$, the estimation of $d_{c\tilde{c}}$ may be very coarse, but because of Prop.\,1 the updates of $\KK^{(n)}$ still warrant a monotonous increase of the free energy.

Regarding the computational complexity of \cref{alg:var-GMM-S}, the first and last block are identical to the second and third block of \cref{alg:var-GMM-X}.
Thus, we now only have to evaluate the complexity of the new middle part for the $\GG_{c}$ estimation, replacing what was the first block of \cref{alg:var-GMM-X}.

This new middle part of \cref{alg:var-GMM-S} consists of two steps: definition of auxiliary sets ${\mathcal I}_c$ and subsequent estimation of cluster neighborhoods $\GG_{c}$.
The definition of all sets ${\mathcal I}_c$ here requires a complexity of ${\mathcal O}(NC'G)$.
In the next computational block, the sets ${\mathcal I}_c$ are used to estimate the distances $d_{c\tilde{c}}$ according to \cref{EqnDCCEstimation}.
There we loop over all clusters $c$ and $\tilde{c}$ and then over all $n\in{\mathcal I}_c$ to estimate the distances.
But there we only consider already computed $d_{\ct}^{(n)}$ (using the condition of Eq.\,\ref{EqnDCCEstimation}).
The loops over $c=1:C$ and $\tilde{c}=1:C$ of the third block may at first seem to suggest that their complexity depends on $C$.
We can however rewrite the loops to show that this is actually not the case.
If we formalize them as sums for computing functions $F^{(n)}_{c\tilde{c}}$, we obtain:
\vspace{-14pt}
\begin{align}
\sum_{c=1}^C\sum_{\tilde{c}=1}^C\!\sum_{n\in{\mathcal I}_c}\!\delta(\tilde{c}\in\GG^{(n)})\,F^{(n)}_{c\tilde{c}}  =  \sum_{c=1}^C\sum_{n\in{\mathcal I}_c}\!\!\!\!\sum_{\,\,\,\,\,\tilde{c}\in\GG^{(n)}}\!\!\!\!F^{(n)}_{c\tilde{c}},
\label{EqnLoops}
\end{align}

\vspace{-8pt}
where $\delta(\tilde{c}\in\GG^{(n)})$ is an indicator function representing the `if'-condition.
Further note that the sets ${\mathcal I}_c$ contain $(N/C)$ data points on average and that $\sum_{c=1}^C\sum_{n\in{\mathcal I}_c}$ by construction of ${\mathcal I}_c$ then goes over exactly $N$ values.
As a set $\GG^{(n)}$ contains at most $C'G$ elements, the total summation, i.e., the total cost of $d_{c\tilde{c}}$ estimations in \cref{alg:var-GMM-S}, has a complexity of ${\mathcal O}(NC'G)$.
For each $c$ our procedure estimates on average $(N/C)C'G$ distances $d_{c\tilde{c}}$.
For each $\GG_{c}$, finding the $G$ smallest elements (unordered partial sorting) then requires a computational cost of on average ${\mathcal O}((N/C)C'G)$, with a total cost for defining all sets $\GG_{c}$ of ${\mathcal O}(NC'G)$.
Storage of all $d_{c}^{(n)}$ distances within one iteration results (without additional measures) in an extra ${\mathcal O}(NC'G)$ memory demand.

Everything taken together, \cref{alg:var-GMM-S} has a run-time complexity of ${\mathcal O}(NC'GD)$ and a memory demand of ${\mathcal O}(CD+NC'G+CG)$ for the storage of all model parameters $\vec{\mu}_c$ and $\sigma$, variational parameters $\KK^{(n)}$ and nearest neighbors $\GG_{c}$, and computed distances $d_{c}^{(n)}$.
A line-by-line complexity analysis of a more detailed version of \cref{alg:var-GMM-S} can be found in \cref{app:ComplexityAnalysis}.

Considering \cref{alg:var-GMM-S}, e.g., the estimation of cluster-to-cluster distances may be deemed to cause problems.
For the sake of complexity reduction, we accepted very coarse estimates.
However, those estimates were far from random and can in principle and finally be good estimates for close-by clusters.
Because of the way we defined the $\KK^{(n)}$ updates in \cref{alg:var-GMM-S}, a data-driven and finally relatively precise cluster-to-cluster distance estimation is all we require.
The reason is that Prop.\,1 warrants that the $\KK^{(n)}$ updates will always monotonously increase the free energy, and the M-step with these updated $\KK^{(n)}$ will in turn
monotonously increase the objective.
Such a provably monotonous increase ensures that learning proceeds in the right direction, and we know that truncated free-energies can result in very tight lower likelihood bounds (see also \cref{app:DetailedResults}).
If \cref{alg:var-GMM-S} really does result in efficient optimization of the clustering objective, remains to be verified and investigated empirically in the next section.

\begin{algorithm}[t]
init $\vec{\mu}_{1:C}$ and $\sigma^2$, and init $\GG^{(n)}$ for all $n$;\\[1mm]
\Repeat{$\vec{\mu}_{1:C}$ and $\sigma^2$ have converged\vspace{0.5mm}}
{
\For{$n=1:N$}{
  $\GG^{(n)} =\bigcup_{c\in\KK^{(n)}}\GG_{c}$;\\[1mm]
  \For{$c\in\GG^{(n)}$}{
      $d^{(n)}_{c} = \|\yVec[(\inpn)]\,-\,\vec{\mu}_{c}\|$;
  }
  $\KK^{(n)} = \{c\,|\,d^{(n)}_{c}$ is among the \linebreak
  \phantom{$\KK^{(n)}=\{c\,|$}smallest distances$\}$;
}
\For{$n=1:N$}{
  $c_o^{(n)} = \myargmin{c\in\GG^{(n)}}\,\big\{d^{(n)}_{c}\big\}$;\\%\\[1mm]
  ${\mathcal I}_{c_o^{(n)}} = {\mathcal I}_{c_o^{(n)}} \cup \{n\}$;
}
\For{$c=1:C$}{
  \For{$\tilde{c}=1:C$}{
    \For{$n\in{\mathcal I}_c$}{
      \If{$\tilde{c}\in\GG^{(n)}$}{
        $d_{c\tilde{c}} =  d_{c\tilde{c}} + d^{(n)}_{\tilde{c}}$;
      }
    }
    $d_{c\tilde{c}} =  d_{c\tilde{c}} \,/\, |{\mathcal I}^*_c|$;
  }
  $d_{cc}=0;$\\
  $\GG_{c}= \{\tilde{c}\,|\,d_{c\tilde{c}}$ is among the $G$ \linebreak
  \phantom{$\GG_{c}= \{\tilde{c}\,|$}smallest distances $d_{c:}\}$;
}
\For{$n=1:N$}{
  \For{$c\in\KK^{(n)}$}{
    $s_c^{(n)} = \frac{\exp\!\big(-\frac{1}{2}(d_{c}^{(n)} / \sigma)^2\big)}{\sum_{c'\in\KK^{(n)}}\exp\!\big(-\frac{1}{2}{(d_{c'}^{(n)} / \sigma)}^2\big)}$;
  }
}
update $\vec{\mu}_{1:C}$ and $\sigma^2$ using \cref{EqnGMMMStep} with \cref{EqnQMain};
}
\caption{GMM with partial truncated E-step and estimated cluster neighborhood evaluation.\label{alg:var-GMM-S}}
\end{algorithm}

\section{Numerical Experiments}
Theoretical investigations of convergence are typically very intricate already for standard $k$-means \citep[e.g.,][]{HarPeledSadri2005} or standard GMMs \citep[e.g.,][]{XuEtAl2016}.
We therefore verify sufficiently efficient optimization of the clustering objectives numerically.

\Cref{alg:var-GMM-X,alg:var-GMM-S} both allow for different choices of $G$ and $C'$, which optimized on a variety of data sets would quickly result in a large combinatorics of different algorithms and data sets.
As our primary aim here is to show that a clustering which scales sublinearly with $C$ is possible, we focus on two algorithms: variational GMM and variational $k$-means (see below).
We use a BIRCH artificial data set with $5\times{}5$ clusters to show the viability of the exhaustive and estimated algorithms (\cref{alg:var-GMM-X,alg:var-GMM-S}) compared to their non-variational counterparts.
We then use the more efficient estimated algorithm (\cref{alg:var-GMM-S}) on artificial BIRCH data sets of up to $C=4096$ clusters to show that the gained computational benefits are not traded off by a higher number of necessary training iterations.
Further experiments on KDD2004 ($C=200$) and SONG ($C=2000$) demonstrate large-scale applicability of the algorithms to natural data.

\paragraph{Variational GMM.}
For simplicity we choose $C'=G$ such that we remain with one parameter $G$ that relates to cluster neighborhood relations.
The resulting algorithm is similar to EM for GMM but optimizes a variational free energy instead of the likelihood directly.
We therefore refer to \cref{alg:var-GMM-X} with $C'=G$ as variational-GMM-exhaustive (var-GMM-X), and to \cref{alg:var-GMM-S} with $C'=G$ as variational-GMM-estimated (var-GMM-S).

\paragraph{Variational $k$-means.}
It was recently shown \citep{LuckeForster2017} that $k$-means is equivalent to truncated variational EM with a full E-step if we choose $|\KK^{(n)}|=C'=1$.
If we maintain the choice of $C'=1$ but replace the full E-step by a partial E-step with $G < C$ following \cref{alg:var-GMM-X} or \cref{alg:var-GMM-S}, we obtain algorithms for which each iteration is more efficient in terms of required distance evaluations than $k$-means.
Following the naming above, \cref{alg:var-GMM-X} with $C'=1<G<C$ will be referred to as var-$k$-means-X, and \cref{alg:var-GMM-S} with $C'=1<G<C$ we will refer to as var-$k$-means-S.

\paragraph{Complexities.}
The complexities of the four algorithms above directly result from the complexity considerations of \cref{alg:var-GMM-X,alg:var-GMM-S}.
We here summarize the run-time and memory demand of the algorithms.
The main approximation parameter is $G$, while keeping in mind that for var-GMM $C'=G$ and for var-$k$-means $C'=1$.
By inserting into the previously derived complexity formulas for \cref{alg:var-GMM-X,alg:var-GMM-S}, we obtain \cref{tab:complexities}:

\begin{table}[h]
	\vspace{-5pt}
	\caption{Computational complexities, see also \cref{app:ComplexityAnalysis}}
	\vspace{-8pt}
  \input{figs/complexity.tex}
	\label{tab:complexities}
	\vspace{-10pt}
\end{table}

\paragraph{Data sets.}
We apply the var-GMM and var-$k$-means algorithms to three data sets:
(I)~A `BIRCH' data set \citep[based on][]{ZhangEtAl1997}, which is an artificial $D=2$-dimensional data set of $C$ isotropic Gaussians, arranged in equal distances on a $\sqrt{C}\times\sqrt{C}$ grid.
We investigate settings of $C=25$~to~$4096$ Gaussians with $\sigma^2 = 1$ in nearest neighbor distances of $4\sqrt{2}$ and $100$~samples per cluster, i.e., $N=$~\num{2500}~to~\num{409600} samples in total.
(II)~The KDD-Cup 2004 Protein Homology (KDD2004) data set, which was originally designed as a supervised classification set for the KDD competition 2004 but is also frequently used as a clustering benchmark.
It consists of $N=$~\num{145751} data points with $D=74$ numerical features each.
(III)~The Year Prediction Million Song Dataset (SONG) \citep{BertinMahieuxEtAl2011}, which contains $N=$~\num{515345} data points with $D=$~\num{90} audio features (timbre averages and covariances).
This represents the largest data set in our experiments.

\subsection{Empirical Results}
For \cref{alg:var-GMM-X,alg:var-GMM-S}, we monitor the standard quantization error during training: $\phi = \sum_n \min_{c\in C} \|\yVec[(\inpn)] - \vec{\mu}_{c}\|^2$.
On the BIRCH and KDD data sets we allow for a maximum of 200 and on SONG of 500~training iterations for all algorithms.
In all cases, we use \textsc{afk-mc$^2$} \citep{BachemEtAl2016b} for initialization of the means.

\paragraph{Validity.}

We first consider a small scale $5 \times 5$ BIRCH data set as described above to compare the partial variational algorithms with their respective non-variational counterparts.
Considering \cref{fig:BIRCH5x5}, we note that initially var-GMM and var-$k$-means require more EM iterations than standard GMM or $k$-means to obtain comparable quantization errors.
The primary reason for this is the random $\KK^{(n)}$ and $\GG^{(n)}$ initialization, which requires a couple of iterations until these reflect the true neighborhood of a data point.
The number of additional EM iterations is however relatively small, and only more significant for very low values of $G$ (small cluster neighborhoods).
Differences between exhaustive cluster neighborhoods (var-GMM-X and var-$k$-means-X) and estimated neighborhoods (var-GMM-S and var-$k$-means-S) are only observable for very low $G$, which verifies that the estimation of cluster-to-cluster distances does not negatively affect performance at least not above such very low values.
We will therefore from here on focus on the two most run-time efficient algorithms, var-GMM-S and var-$k$-means-S, which scale with ${\mathcal O}(NG^2D)$ and ${\mathcal O}(NGD)$, respectively.

\begin{figure}[htb]
  \begin{subfigure}[c]{0.23\textwidth}
    \begin{adjustbox}{trim=5pt 8pt 0pt 5pt}
      \input{./figs/BIRCH_GMM_exhaustive_QE-main.tex}
    \end{adjustbox}
	\end{subfigure}
	%
  \begin{subfigure}[c]{0.23\textwidth}
    \begin{adjustbox}{trim=3pt 24pt 0pt 5pt}
      \input{./figs/BIRCH_GMM_estimated_QE-main.tex}
    \end{adjustbox}
	\end{subfigure}\\
	%
  \begin{subfigure}[c]{0.23\textwidth}
    \begin{adjustbox}{trim=3pt 0pt 0pt 5pt}
      \hspace{-5pt}
      \input{./figs/BIRCH_k-means_exhaustive_QE-main.tex}
    \end{adjustbox}
	\end{subfigure}
	%
  \begin{subfigure}[c]{0.23\textwidth}
    \begin{adjustbox}{trim=3pt 0pt 0pt 5pt}
      \hspace{-5pt}
      \input{./figs/BIRCH_k-means_estimated_QE-main.tex}
    \end{adjustbox}
	\end{subfigure}
	%
\vspace{-8pt}\ \\
	%
  \caption{
Results of \cref{alg:var-GMM-X,alg:var-GMM-S} on the BIRCH~$5\times 5$ data set.
The mean quantization error (solid), shaded with its SEM, as well as the single run with lowest final quantization error (dotted) over 100~independent training runs is given.
Only in the extreme case of var-$k$-means-S with $C'=1$ and $G=2$ the distance estimation fails to recover viable results.}
  \label{fig:BIRCH5x5}
  \vspace{1pt}
\end{figure}

\paragraph{Neighborhood initialization and exploratory neighbors.}
For large scale data with many clusters in low-dimensional spaces, the random initialization of cluster neighborhoods can be arbitrarily bad and can take many iterations until better neighborhoods are found.
Performing M-steps during this initial period can have unwanted, destructive effects.
For large-scale experiments we therefore allow for a couple of initial E-steps (optimized on the training quantization error) to find better initial neighborhood relations $\KK^{(n)}$, $\GG_{c}$.
Furthermore, allowing for a single extra randomly picked exploratory cluster per data point within $\GG^{(n)}$ helps to overcome large gaps between areas of dense clusters.

\paragraph{Absolute vs. relative complexity.}
Per iteration, the var-$k$-means and var-GMM algorithms save a significant amount of required distance evaluations.
However, if this would result in an equally higher amount of required training iterations, the absolute gain of this relative reduction would vanish again.
Already in \cref{fig:BIRCH5x5} we saw that training times will not necessarily increase (equally) with $G < C$.
We now further investigate this behavior on larger data sets by using systematically increasing sizes of BIRCH.
As measure for training time we count the initial E-step iterations (see previous paragraph) and following EM iterations until the mean quantization error of var-$k$-means-S and var-GMM-S surpasses the mean converged quantization error of standard $k$-means.
For both algorithms, we use $G=2$ as well as $G=5$, and for each $G$ an additional randomly picked cluster in $\GG^{(n)}$ (as described before).
The compared means were taken over 5~independent training runs for each setting.
As seen in \cref{fig:BIRCH-Iterations-C}, the reduction of distance evaluations per iteration in the variational algorithms does here not result in an equally increasing number of necessary iterations with respect to $k$-means.
In most cases even less iterations were necessary than for $k$-means while the same quantization error was reached (all plots below the black dashed line).
Importantly, the number of iterations increases less than linearly with $C$ (which would in the log-log plot for small offsets result in linear graphs with slopes of $1$, parallel to the lines of the background shading).

\begin{figure}[tb]
  \begin{adjustbox}{trim=8pt 6pt 0pt 5pt}
    \input{figs/BIRCH-Iterations-C.tex}
  \end{adjustbox}
  \caption{Total number of iterations (for initialization and training) until the variational algorithms or surpass the converged quantization error of standard $k$-means on BIRCH data sets of different sizes, given by the number of clusters $C$.
  The number of iterations for $k$-means until convergence is given as dashed line.
  A slope of 1 is indicated by the background for reference.
  }
  \label{fig:BIRCH-Iterations-C}
  \vspace{2pt}
\end{figure}

In all here investigated cases, the quantization error of var-$k$-means-S and var-GMM-S improved on standard $k$-means.
Similar observations of better avoidance of local optima through truncated variational approaches were reported e.g.\ by \citet{ForsterLucke2017} for Poisson Mixtures and by \citet{LuckeForster2017} for GMMs (however on a much smaller scale).
The optimal degree of truncation is thereby primarily dependent on the geometric structure in the data.
However, using smaller than optimal neighborhoods can still lead to viable results with potentially huge computational savings for large scale data.

\paragraph{Performance on large scale and natural data.}
The BIRCH data set is well suited to controllably increase the number of clusters within the data without changing their overall geometric structure.
However, the low dimensionality, high regularity and good cluster separation within this data set does not necessarily reflect natural data very well.
Real world practical implications are therefore demonstrated on two additional, large scale, high-dimensional, natural data sets: KDD and SONG.
As for the BIRCH data sets we again also for SONG use initial E-steps and one single additional randomly selected cluster in $\GG^{(n)}$ (denoted by the `$+1$' for $G$), and we now report mean quantization errors over 5~independent runs.
\Cref{tab:speedup} shows the trade-off between computational gain and quantization error for these two natural as well as high scale BIRCH data sets.
Especially where the number of clusters is very large, var-$k$-means shows significant speedups of two to three orders of magnitude, reaching comparable quantization errors on the natural data sets and even improving on $k$-means on the BIRCH data sets.
On the other hand, var-GMM-S consistently improves on the $k$-means baseline for $G \geq 5$ on the natural data sets, and in all settings on BIRCH.
Furthermore, while results on KDD for the full GMM were still obtainable with high computational effort (see \cref{app:DetailedResults} for results), evaluation of GMMs on SONG was only possible due to the significant computational savings of the var-GMM-S algorithm of up to two orders of magnitude.

\begin{table}[bt]
  \caption{
Relative speedup in terms of saved distance evaluations per iteration  with respect to the respective non-variational variants and relative quantization error with respect to standard $k$-means for both algorithms (as evaluation with full GMMs was computationally not feasible for these large data sets).
For var-GMM-S both the theoretical minimal (first value) as well as the experimentally measured (second value) speedup is given, as in praxis overlaps of cluster neighborhoods $\GG_{c}$ can reduce the number of distance evaluations significantly.}
  \vspace{-7pt}
  \input{figs/speedup.tex}
  \label{tab:speedup}
\end{table}

\section{Discussion}
Using partial variational EM, we derived efficient clustering algorithms which require less than ${\mathcal O}(NCD)$ numerical operations per iteration.
Most notably, algorithm var-GMM-S reduces the number of required distance evaluations per iteration from ${\mathcal O}(NC)$ to ${\mathcal O}(NG^2)$ where $G$ is a small constant which relates to the cluster neighborhood relationship.
\Cref{fig:BIRCH-Iterations-C} shows that the clustering objective is effectively and efficiently increased within the same number of iterations as $k$-means even if $G$ is kept at a constant value while $C$ is increased.
The strong reduction of complexity per iteration with a sublinear scaling of required iterations with $C$ (e.g.\,\cref{fig:BIRCH-Iterations-C}) is evidence for clustering being scalable sublinearly with $C$.
For real data with many clusters, the complexity reduction amounted to a reduction of distance evaluations by two to almost three orders of magnitude (\cref{tab:speedup}) compared to $k$-means, while comparable (or better) clustering results were obtained.
And distance evaluations dominate the computational demand (see \cref{app:ComplexityAnalysis}).
But in what sense can clustering feature such a sublinear scaling? In one sense, all clustering algorithms scale
with $C$ as implicitly we demand $N>C$, and only a value of $N$ several times larger than $C$ is sensible \citep[but see][]{KlamiJitta2016}.
A sublinear dependency on $C$ may also be perceived as counter-intuitive because we want to update each of the $C$ clusters in one iteration.
Sublinear scaling with $C$, therefore, has to be interpreted as a sublinear scaling with $NC$. In this case, our reduction to ${\mathcal O}(NG^2)$ (or ${\mathcal O}(NG)$)
distance evaluations per iteration still provides sufficient information (in the form of non-zero $s_c^{(n)}$) to update all clusters because $NG$ or $NG^2$ is greater than $C$ (typically several times).
The sublinearity suggested by our empirical results also relies on specific properties of the data, especially certain neighborhood relationships among clusters.
Data sets and initial conditions {\em can} be constructed that will result in a poor performance.
These situations can typically be obtained using well separated areas with many close-by clusters, and by deliberately not assigning any cluster center to one area.
With careful seeding (we used \citet{BachemEtAl2016b}) and for typical data sets, such situations are unlikely, however. In practice, seeding (which may
itself depend on $C$ but not necessarily on $NC$, \citet{BachemEtAl2016b}) also limits the number of EM iterations required for convergence although it remains very difficult
to obtain theoretical results for convergence times.
Finally, our results clearly show that memory requirement does linearly scale with $C$ (but not with $NC$), and increases for algorithms with decreasing run-time complexity (Tab.\,1).
For memory reduction and more generally, combinations with coresets may represent promising future research. Coresets are complementary as they focus on the dependence on $N$, and as
their weighted likelihood \citep[compare, e.g.,][]{LucicEtAl2017} can be treated by our approach very similarly to (\ref{EqnLikelihood}). Coresets are also available for general GMMs, and such generalizations
likewise represents future research in the context of this work.

To summarize, we can (under the conditions discussed above) state that our empirical results suggest that a run-time scaling of clustering sublinear with its clusters is possible.
In combination with recent advances in complementary lines of research, especially seeding \citep{BachemEtAl2016b}, efficient distance evaluations \citep{Elkan2003}, or coresets \citep{HarPeledMazumdat2004,FeldmanEtAl2011,BachemEtAl2017}, the significance of such a scaling being in principle and in practice possible may be very substantial.

\subsubsection*{Acknowledgments}
We acknowledge funding by DFG grants \mbox{LU 1196/5-1} (DF) and \mbox{EXC 1077/1} (JL), and thank Florian Hirschberger for very helpful feedback.

{
\renewcommand\baselinestretch{0.98}
\small
\bibliographystyle{abbrvnat}

redpajama_set_name: RedPajamaArXiv


text:
Former Lawman Sent To Prison For Intoxicated Manslaughter
aijohn784, ThinkStock
EL PASO, Texas (AP) — An ex-sheriff's deputy in West Texas must serve 17 years in prison for a 2012 drunken driving wreck that killed a man who was changing a flat tire.
Raymundo Carranza was sentenced Tuesday in El Paso. The 49-year-old Carranza on Monday was convicted of intoxicated manslaughter.
Carranza, who was a 17-year veteran of the El Paso County Sheriff's Office, was off-duty when his pickup truck struck 26-year-old Richard Lopez. The victim died at the scene.
Records show that Carranza, three hours after the crash, still had a blood alcohol level exceeding the legal limit for driving.
He resigned as a deputy shortly after the accident.
Filed Under: drunken driving, El Paso, texas

redpajama_set_name: RedPajamaCommonCrawl


text:
Tag: gbc
Gaming History #1: Did Nintendo made the only handheld?
Alright, this article is a part of the GB(C) month. In this very first article of "Gaming History", I'll take a look at the history of a game, company, console or a series. I can also take a look at certain events or beta's. Anyways, for the theme of this month, I thought it would be interesting to look at the competition of the Gameboy and Gameboy Color and why Nintendo ultimately won the battle for handhelds. I tried have the most correct information as I could, but if I do made a mistake, feel free to tell me in the comments. Anyways, let's dive right into the competition of the gameboy and gameboy color. I'm quite excited to talk about this myself.
Let's be clear for a moment. When I talk about handhelds in this article, most of the time I mean gaming handhelds. PDA's and such, I take out of the picture for this article. Anyways, the first handhelds we see in the second generation. While some sources told me that the Game & Watch was first, I didn't believe it.
I looked further until I found the first handheld ever made. Mattel was a few years before Nintendo. The Game & Watch was released in 1980, while Mattel released their handhelds in 1976. The first handheld I found was Mattel Auto Race.
But why did the Game & Watch win over Mattel? The Game & Watch had something that I don't see at the early Mattel handhelds. All the graphics of the G&W are pre-printed on the screen. This makes the device, according to me, last longer. Not only that, it was cheaper to produce, so it was a cheaper product… I think you can easily fill in the rest.
While it's quite possible to talk hours upon hours about the history of handhelds, for sake of having a bite-sized article, let's talk about a competitor that were also on the market when the Gameboy or Gameboy Color was.
this handheld was released in the same year that the gameboy was released. The year was 1989. Now, why did this handheld failed against the Gameboy? According to me, it's the design. Just look at the device. It doesn't look like it would be great to play on. The placement of the speaker is the issue.
According to some research, the gameboy won from the Lynx because of the price and battery life. Who knew that a green-ish and black display would do wonders like that?
Tetris?
When Tetris was developed, Russia was still known as Soviet Russia. So, the original creator of the puzzle game needed to give the intellectual rights to Mother Russia. A few companies fought over the rights. Nintendo was one. Temco as well. Both released a version on the NES. Because Temco couldn't release it officially, they released it on a black reproduction cartridge.
How does that relate to history of the gameboy? Believe it or not, this game outsold Pokémon. It's the most sold game on the system. It sold around 40 million units. It was even a launch title.
The documentaries I watched about the gameboy actually told a lot about this. If you want to know more about the history of Tetris, I highly recommend reading up on it.
I know that this article is extremely short. But since this is an experiment I want to know if you guys like these sort of articles. If that's the case, I might write more articles like this.
I hope you enjoyed reading a little bit about the history of the gameboy. I enjoyed writing it for you guys. Take care, have a nice holiday period and until the next article!
Posted on December 28, 2014 December 28, 2014 by NekoJonezPosted in Gaming HistoryTagged 001, and, arpegi, buttonsmashers, game, gameboy, GB, gbc, Handhelds, history, information, Jonez, jonez001, jonezjea, month, more, neko, NekoJonez, Nintendo, Of, other, Tetris, The, there, watch, where. Leave a comment
First Impression: Tarzan (GBC) ~ Hide and SEEK.
IGN entry
So, one day on a garage sale, I saw this game. Since one of the very first games I ever played was Tarzan on the PC, I had to have this. I enjoyed this game quite a lot. And now, after all those years, I still have the same cartridge and the instruction booklet. I'm quite happy that I still have it since I have fond memories of it. Now, I have never finished this game since I couldn't get passed the tiger battle as a kid. That's why I'm writing a first impression. Anyways, enough stalling, let's dive right into this game and let's take a look at it. As usual, feel free to leave a comment on the game and or the content of this article.
Collect-a-banana gameplay.
The story in this game is amazing. They made it work on the Gameboy Color! They follow the movie quite perfect. The levels and stages are designed around some amazing scenes of the movie. As a kid, I watched that movie a lot.
While the characters don't have a lot of development in the game, I still enjoyed this story quite a lot. I'm so glad that they know what the gameboy color was capable of doing.
The game is surprisingly longer then you would think. This game consists out of 23 stages. Which is quite long for a movie game. It's actually quite good too. This game is a platformer, but not in your traditional sense. You need to collect a certain amount of banana's before you can advance to the next stage. The amount of banana's you need to collect are shown when you start the level.
You don't always play as Tarzan, there are levels as Tuck… but…
The bad things.
… There is barely any variation between the characters. They all play the same. Apart from Tuck's hitbox being slightly bigger then Tarzan's.
While the controls are really solid, the jump animation is a bit broken. Sometimes the jumps, well, don't work. You can't grab a ledge you see clearly in front of you or you clip right through the edge.
I don't know it was my copy or not, but the sound was messed up. The music had like a missing line of melody. The noise it added was rather annoying.
A disappointment was that you couldn't multiplayer the hide and seek mode. You had to pass your gameboy to your friend after you had hidden one of the characters. That was a major let down for me. Thankfully, this allowed me to play this game with my sister. Since we only had one copy of the game back then.
Another annoyance is that the checkpoints aren't clearly indicated. Suddenly, you get shown that you reached a checkpoint, but it looked like a usual ledge or platform to me at first. Also, if i remember correctly, once taken is always taken.
Oh, don't get me started on the password system. It's quite creative by using symbols but why do they have a password system in place for this game? There were games like the Legend of Zelda who showed that they can make a saving system work on the Gameboy color!
Is it bad?
So, I have talked about most of the things this game does wrong. But it isn't that bad. Thankfully, this game has some other good things. The animation blew my mind, and it still does today. What Disney displays here, is just amazing. The game feels tense and nice.
Looking at it now, you could argue that this game has the problem of design over gameplay. I mentioned earlier that some jumps didn't work correctly. I think the culprit is that the animation is too good.
The difficulty curve is just perfect. While some parts might be a bit unforgiving, I don't think that is such a bad thing. Do you seriously expect games from that age to be forgiving.
Visually, this game is nice to look at. The game is sometimes a maze… Oh, yeah, I forgot to mention that a map would be nice. But at the other hand, I understand why there isn't a map. Since you play inside the jungle, which is unmapped terrain in the first place. Also, Tarzan doesn't know the whole jungle like the back of his hand.
Another thing I forgot to mention is how you go to the next level. As soon as you got all the required banana's you don't go to the next level automatically, you have to find your partner. He is hidden in sometimes a hard to reach area. This tests your knowledge of the level and you have to use all your skills.
What I don't understand, and I can't test it since I don't have one, is that this game supports the Gameboy Printer. Yes, you can make images and print them. This is wasted potential in my eyes.
Before I wrap up this article, I think I should talk a bit more about the controls. Since there isn't any tutorial, I liked it that you can find out what each button does on your own. But, as soon as you play, you will understand that this isn't the best choice. You'll have to play that in order to understand it. Otherwise I ruined each surprise.
Anyways, let's wrap up this first impression here. I almost wanted to start the conclusion as I was writing a review. But I haven't beaten this game, so I can't write a review. Anyways, I think this game deserves a play. It isn't perfect, but it's good. It isn't polished, but it's fun.
Thanks for reading and I hope you enjoyed this article. I wish you happy holidays and I look forward to seeing you guys soon. Since the Gameboy and Gameboy Color month will still go in January. I had a way more busy time then I expected, so I couldn't write enough articles as I wanted for this theme. That's why I decided that. But anyways~ Take care!
Posted on December 24, 2014 December 24, 2014 by NekoJonezPosted in First ImpressionTagged and, arpegi, bad, banana, best, buttonsmashers, color, disney, ever, first, game, gameboy, GB, gbc, good, hide, his, impression, in, information, is, it, Jonez, jonez001, jonezjea, made, more, neko, NekoJonez, Nintendo, one, opinion, or, own, review, rocks, seek, sucks, Tarzan, that, two, year. Leave a comment
Gamer's Diary #5: One time special!
Since I want to do something special this month, I decided to get my old series "game diary" back for one time. To avoid that only there are only reviews and first impressions from a given console or handheld. Anyways, enough introduction and reason why I bring the series back for this one time. In this article you will find a story where 20 game titles are hidden. Do you know enough games to find them all? If there are more then ten, feel free to tell me. The solution is underneath the story. To avoid spoiling yourself, I made the text white. This way you have to scroll over it to reveal it. Anyways, I hope you enjoy this one. Good luck and have fun! To avoid confusion, I used the Wikipedia lists of all titles on the gameboy and gameboy color. I also hid 10 titles of each handheld. Oh, and before I forget, let me know in the comments how many you got and or some feedback on this article.
Gameboy part
Hello there, I was just trying to find some worms in my backyard for a biology project. It's kinda gross, I know. But we are going to study how fish react to them. I'm quite disappointed that I had to cancel my tennis training. Otherwise I wouldn't had enough time.
I could be lazy and go to the animal breeder in the alleyway, but what's the fun of that? I like to find other insects like centipedes to scare the living hell out of my sister.
Before I forget, the guy who owns the animal shop has like a monopoly on animals in my town. I thought Chinese people only played Mahjong. Stereotypical, I know. I prefer card games more myself honestly. My dad, who is a fire fighter, is more of a chessmaster. But he is on in a meeting now in Shangai.
Gameboy Color part
Hello there, my name is Laura. I might not be able to make a 720* on my skateboard, but I do some basic tricks. I don't like to go to VIP parties since, I'm never invited. They think I'm a nerd because I like to play backgammon with my family.
Oh well, that's their problem. They are like running animals, not a chicken run … but more running ants. Annoying but useful sometimes.
Look who we have there, my dad is home from his job as a deer hunter. He has a big gift for mom. I have a déjà vu. Didn't he do the same thing last week? I shouldn't care too much about that, otherwise bad thoughts will spawn in my head.
Animal Breeder
First of all, this should be released last weekend, but I was busy and such. Sorry for the delay. I know it's shorter then the other entries but I'm so busy but I wanted to make sure that it got released.
It's a difficult game, isn't it? I wouldn't be surprised if you barely found any title in the story. That's because you shouldn't pick generic titles. Then you don't stand out, then you blend in a story so nicely.
Anyways, thanks for reading and hopefully you enjoyed reading it. I also hope to see you another time here on my blog. (Also, this was an exclusive article on my blog, not reblogged on other partner sites)
Posted on December 17, 2014 December 17, 2014 by NekoJonezPosted in Game DiaryTagged arpegi, blog, buttonsmashers, color, dairy, diary, find, game, gameboy, games, GB, gbc, hidden, jea, Jonez, jonez001, jonezjea, neko, NekoJonez, Nintendo, post, puzzle, ten, The. 2 Comments
Gamer's Thoughts: 10 facts about the gameboy and gameboy color
Let's do something different, not a review or a first impression. Let's not talk about the game music or something along those lines. In this article I want to talk about the history of the gameboy and gameboy color and maybe some facts you didn't know about yet. So, this is an experimental article. It would help me if you guys left a comment about the content and subject of this article. Let's begin.
1) Kirby's color is white?
Did you know, that Kirby's first appearance in the west was actually white? The reason for that is when Nintendo USA got the code for the game in order to translate, they didn't mention that Kirby was pink. Because his first installment was on the gameboy, it was unclear which color he had. That's why Nintendo decided to give him a white color.
Also, there are some rumors of Kirby's name. It might have to do with a story of a lawyer that defended Nintendo when Universal Studio's sued Nintendo for copyright infringement on their Donkey Kong license. But that's only a rumor… right?
2) A calculator as inspiration.
Gunpei Yokoi was sitting on the train when he saw a business man playing around on his calculator. You know that stuff you did back in class? Turning the numbers upside down to try and spell out words? It didn't take long before your dirty mind took over and you turned the number "80085" upside down.
So, that's what gave Gunpei the inspiration to make the gameboy with the RD&1 of Nintendo. Sadly enough, the creator of the gameboy has passed away in a car accident a few years ago.
He got a few awards under his belt, but to me he will always be remember as the creator of the gameboy :)!
3) The Gameboy Advance SP wasn't the first back-lit gameboy.
Remember those painful days when you had to have a lamp on to play the gameboy? When you couldn't play it under your sheets easily because the gameboy didn't had a light-up screen?
Well, the successor, the gameboy pocket got a second release in Japan. The gameboy light was actually the solution to the issue. Strangely enough, the device only stayed in Japan. In the USA and Europe we got all sorts of crazy attachments that barely worked.
What's an every bigger mystery is why they didn't include this feature in the gameboy color. Yes, we had to wait until the gameboy advance SP until we had backlit gameboy screens. What a shame actually. But hey, it was fun trying to hide the gameboy and put out the lights at night to avoid your parents busting in…. Just don't forget you lower your volume.
4) The gameboy wasn't the first Nintendo handheld
So, this relates to my 2nd point about the calculator. When Gunpei started to design the first handheld game for Nintendo, he developed the Game & Watch series.
The Game & Watch series are now a big collector item. It's even believed that some Game & Watch systems gave the inspiration to the Nintendo DS's design.
Well, more on Game & Watch devices later.
5) Samsung sold it!
Around the time the WO II ended, Korea actually banned products made in Japan. Which meant that the Gameboy was banned. But that didn't stop from being sold in Korea.
Samsung Korea actually sold the gameboy under another name, called the "Comboy". It's not the only system that Samsung sold. I know that they sell a version of the DS as well, so I wouldn't be surprised that they helped to sell the whole gameboy line in Korea. But notice that's I'm doubting since I don't know for certain.
1) The SNES gameboy "port"
Back in the day, you could play Gameboy games on your TV using the Super Gameboy. You can even play with the color.
But strangely enough, the Super Gameboy couldn't run Gameboy Color games. The SNES would be strong enough to run those games and it has color for sure.
We had to wait until the GameCube before we would be able to play these games legally on a big screen.
2) Trivia
The Gameboy color is the only system in the Gameboy series that has clear cartrigdes.
The colors in the name of the Gameboy color stand for each different color the gameboy color was originally released in.
And final part of trivia, all black gameboy cartridges are enhanced to be in color on the gameboy color!
3) Pokemon Crystal, two versions?
The most popular game on the Gameboy Color was Pokémon Gold & Silver. But strangly enough, Pokémon Crystal got two releases. I discovered this when I found out that I had two Pokémon Crystal cartridges.
When I saw the area code, somehow a "-1″ was printed on it. After I researched it, it turns out that there was a v1.1 released. There is barely anything known what is patched. But hey, time to hunt a copy down for your collection!
4) Wireless.
If you thought that you needed to use cables when it came to connecting two gameboy colors, think again. Some games actually used the infrared port on top of the gameboy.
I never used it as a kid, but it's interesting to learn more about. Since according to my research, it was the first handheld that had wireless communication.
5) Motion Control before it was cool.
Oh, and it wasn't the only first. Kirby Tilt 'n' Tumble was the first motion controlled game. It's a sort of maze / Super Monkey Ball-ish game.
It actually worked with tilting the gameboy around. I haven't played it, but I have seen video's about it. It made me want to grab a copy of it. Since you can't have the same experience with these kind of games on an emulator.
So, that was the article I wanted to release last week. But, I was busy and tired, so I moved it to this week. I hope you enjoyed reading about the gameboy and gameboy color. If you knew all these ten facts, I hope it was a nice refresher.
I enjoyed writing this, did you enjoy reading it? Anyways, I hope to see you another time. Thanks for reading.
Posted on December 10, 2014 March 29, 2015 by NekoJonezPosted in ButtonSmashersTagged 001, about, buttonsmashers, color, crystal, did, DIY, facts, gameboy, GB, gbc, jea, Jonez, jonez001, jonezjea, kirby, know, land, mario, neko, NekoJonez, not, only, Pokémon, port, SNES, super, Tetris, The, tilt'n'tumblr, trivia, tumble, v1.1, you. Leave a comment
Review #037: The Legend Of Zelda – Links Awakening (DX) (GB/C) ~ Where is the color?!
One of my first Zelda games was the Oracle Of Ages game. When I finished the game and saw that the game was going to be continued in Oracle of Seasons, I hunted for a copy on garage sales like a mad-man. One time, I found this game instead of Oracle of Seasons. I started to play it and I wasn't disappointed. I don't own the remake in cartridge form, since I have it on my 3DS as an eShop title. Anyways, let's keep this introduction short, I want to review this game. As always, feel free to leave a comment with your opinion on the game and or my article.
Where is the color?!
I found this image on it's WikiPedia page. When the game first released, it was in typical gray-white gameboy graphics. Honestly, I didn't care. But since there was a fan outrage, Nintendo remade this game with color and an extra dungeon. Apart from that, it's as good as the same game. So, that's why I combined both games into one review.
Let's first talk about the story. Since this game doesn't take place in Hyrule. You are Link, traveling home from a long day at work…? If I tell why, I spoil parts of another game, so yeah. Joking aside, Link is caught in a storm and is shipwrecked on an island.
This story doesn't really feel like a Zelda story. The final parts of the game doesn't help either. This game has a very lighthearted story that doesn't take itself seriously. And you know what, it's a nice break from always saving the world and killing Ganon.
Yet, in terms of writing, I have one complaint. The text when you find the compass in a dungeon gets annoying quickly. It talks about the new feature it has. That you hear a sound when a key is hidden in that room. Sweet update, but why do you need to see that each and every dungeon?
You might already know that there are various Mario references in this game. I'm honestly on the fence about it. While I feel that adds to the personality of this game, on the other hand, I feel like it makes the game look unoriginal and at those places and part recycled.
DX TIME
The gameplay of this game was groundbreaking for the series. For the first time ever in a Zelda game, you could have two different items on the A and B button. This made for some interesting puzzles. So you would think, actually almost all those puzzles are solved with the Pegasus Boots and another item. But hey, it was their first attempt, so it's a nitpick.
Before I forget to mention it, there is something that feels extremely out of place in a Zelda game, and that are power-ups. Yes, you read it right. There are power-ups in this game. Sometimes an enemy drops a power up that gives you a temp attack or defense boost. This is extremely out of place for a Zelda game in my opinion.
Apart from that, I have no big complaints in terms of the gameplay. It's your typical Zelda fare. Go from dungeon to dungeon, while defeating the boss. In the DX version, there is an additional color dungeon. The puzzle to get to it is quite nice. But the dungeon in itself is quite short and I beat it on my first try.
The difficulty of this game is not so well done. While some bosses can be annoyingly difficult, some bosses are really easy. Also, the reward in the color dungeon is just overpowered. I won't spoil it, but my advice is that you beat it near the end of the game.
This game also has a side quest. Since it's the first time you had side quests in the Zelda series, you need to do a part in order to advance.
Earlier, I already talked about some parts of this game's design. Some enemies are recycled from other series. But overall, the design and animation of this game is really well done. They made a portable Zelda game have the Zelda vibe the console games have.
Both the black and white and the color version both have their charms, so DX isn't the better looking game because it has color. Honestly, if you dive deeper into the story then what's just presented on screen, the black and white theme is actually more fitting.
The music for this game is just 8bit-gameboy-chiptune glory. Sometimes I can't get a tune from this game out of my head. It's that good in my opinion.
Oh, before I forget, you can also be a thief in this game. But if you steal from the village's shop… Never go back in or your name will be permanently changed to thief.
Lengthwise, this game is actually quite long for a gameboy game. It has 8 dungeons before the final boss. The whole world is quite big and it's worth exploring. Since the controls are just perfect for the gameboy.
One thing that annoyed me too is that there isn't a way to gain more then 1 ruppee at a time. Apart from treasure chests, the enemies only drop one ruppee. Which I can understand because you don't have color, but couldn't they do anything with the size of the sprite…?
Anyways, I think it's time to go to the conclusion of this review. I think I said everything I wanted to say about this game. Let's just warp this one up!
– The text for the compass.
– Recycled enemies.
– No more then one ruppee.
– The colorless version is a let-down for some people.
+ The game looks good.
+ Great soundtrack.
+ Silly, yet entertaining story.
+ Great controls.
+ Nice gameplay.
This might be my least favorite portable Zelda game, but it's not a bad game. Not at all. I agree that this game has some flaws, like the recycled enemies, but it doesn't ruin the game. Also, this game did some things that are now a staple in the Zelda series!
So, that were my thoughts on this game. I hope you enjoyed reading them. I also hope to see you at another article on my blog.~ Until then guys!
Score: 80/100.
Posted on November 30, 2014 November 30, 2014 by NekoJonezPosted in ReviewsTagged 001, a, arpegi, awakening, buttonsmashers, color, DX, first, game, gameboy, GB, gbc, impression, in, jea, Jonez, jonez001, jonezjea, Legend, link, link's, mario, neko, NekoJonez, Nintendo, Of, Preview, RD-1, review, The, Zelda. 1 Comment
Game Music: My Favorites – Numbero 11: GB(C) month special.
Let's start off with an article that last month's theme lacked. An article about video game music. In this series, I take a look at my favorite game tracks. I can't pick one track as my favorite and since I want to talk about so many tracks, I started this series. This time I want to talk about my favorite tracks of some gameboy (color) games. Keep in mind that these are my favorite tracks and they might differ from yours. Also, this isn't a top 10 or anything like that. So, don't be mad if your favorite track isn't in this article. Man, I'm sounding now like I'm introducing the wrong type of article and trying to make the introduction longer. I'm totally not doing that, believe me. Okay? Anyways, the rules are simple. Only one track of a game per article. Oh, and feel free to leave a comment on the tracks, content of this article and or your opinion of the soundtracks of the GB(C) games.
#1: Pokémon Blue & Red (GB) ~ Battle Theme
Link to my review – Link to the music
Who doesn't remember the good old gym leader theme of Pokémon Red & Blue? As a kid I was always pumped whenever I heard this melody pop-up. I wanted to defeat that gym leader.
Whenever I hear this melody, I get hyped. I know that something big is coming that has to do with Pokémon.
I even remember that I sometimes let my gameboy play just hear this song. Since it's the only way I can hear it "clean". What I mean by that is that near the end of almost every version of YouTube, Pokémon battle sounds start playing.
But hey, it's still a memorable and nice track to listen too!
#2: The Legend Of Zelda – Oracle Of Ages (GBC) ~ Nayru's Song
Review – Link to the music (extended)
There are two songs that makes me sometimes tear up of nostalgia in the Zelda series. One of these songs is Nayru's song. The reason why is because it's the first puzzle I solved in my favorite Zelda game. It was the start of a thrilling adventure I never forgot.
As a kid I didn't have a console or a good PC. So, I played a lot on my gameboy. So, that's why my love for the gameboy games is so big. While I don't remember if this was my first Zelda game or the NES remake on the GBA, but it was one of the first.
It was also a different game then I used to play. Different from the pure puzzle games and platformer games. Yeah, the memories.
#3: Super Mario Land (GB) ~ Overworld
The hate this game gets is just… Well, it's mixed for me. At one side, I understand how this game is a mediocre Mario game compared to the other Mario games. It isn't in color, it's outside the Mushroom Kingdom, the story is about another princess, the fireballs bounce, you can't save…
At the other hand, it's the Mario game I grew up with. It's the first Mario game I ever played. Even when I played the NES game at my cousin's house, I found that the NES game wasn't as much fun as Super Mario Land. Something didn't click with me.
Wow, I got sidetracked extremely fast. But the memories behind this game are just too big. Maybe I should write an article about it…?
#4: Tetris DX (GB/C) ~ Type A
Link to the music
So, I got a gameboy color… And what's the first game I get myself? That's right! Tetris DX! Why? Because my grandmom got a Gameboy color herself.
In this gaming nostalgia article, I talked about how my aunt's brick, I mean oldschool gameboy died. The only two games I could play on there were Pac-Man and Tetris. So, when I saw this, I wanted to play Tetris again.
I have multiple stories about this game, but this game is the sole reason why the Tetris theme is so memorable to me. It's one of the biggest tunes in gaming is it not?
#5: Harry Potter and the Chamber Of Secrets (GBC) ~ Main Theme
I was a kid right when the Harry Potter craze was in full swing. Besides Pokémon and Yu-Gi-Ho, Harry Potter was extremely popular with the kids.
While this game was also made on the PC and several other consoles, I played the Gameboy Color version. I didn't have any fancy consoles or the game on PC.
But I enjoyed myself. I had both games, from the first movie and the second movie. The reason why I picked this track is because I had a hard time finding the music of the first game of the gameboy version. And this popped right up in my search results.
As I feared, this article turned into a sort of gaming nostalgia article. When it comes to gameboy and gameboy color games I always want to talk about more then just the music. I hope you can forgive me for that.
So, till Christmas, I will write a few articles of gameboy and gameboy color games. I'm going to try to do my best to not be overly nostalgic like in this article. It's for that reason why I kept this article shorter then my usual articles.
I hope you enjoyed reading it! Hopefully I can see you another time here on my blog for a new article. Take care guys~
Posted on November 29, 2014 November 29, 2014 by NekoJonezPosted in Gaming MusicTagged 001, and, arpegi, blue, buttonsmashers, chamber, color, colour, crystal, extended, game, gameboy, gaming, GB, gbc, gold, harry, jea, Jonez, jonez001, jonezjea, more, music, neko, NekoJonez, nostalgia, Of, OST, Pokémon, potter, red, secrets, silver, soundtrack, special, such, The, version, yellow. Leave a comment
Game Nostalgia #5: My Gameboy Retrospective
S o, in the last article of this series, I talked about my history with the DS and 3DS. So, I think that it's now time to talk about my memories with the gameboy series. While I'm supposed to talk only about the Gameboy Advance, since it's this month's theme, the article wouldn't be as long as it should be. That's why I decided to write a whole article about my memories of all the Gameboy's I got. That way you have an idea of my journey through the world of gaming, since I mostly only played on the gameboy. That and my hobby of writing was my childhood. So, prepare yourself for a personal story. Feel free to leave yours in the comments or your opinions on my story.
Exploding start
The first gameboy I played on wasn't actually mine. It was my aunt's. She only had Pac-Man and Tetris. Somehow my young mind didn't need anything more. It were my first real encounters with gaming, but I was hooked. I used to play games like DuckHunt or Mario Bros. at my nephew's place, but those moments were then far and few between.
One day, I was at my aunt's place and I stopped playing since the back of the gameboy started to feel hot. A few moments after I put it down, the batteries actually exploded, damaging the gameboy heavily. That was a big shocker. I didn't know what to do. My aunt wasn't even mad, since it wasn't my fault. It turned out that there was a flaw with the batteries we used, and it leaked battery acid into the system. Yeah.
That story was my earliest memory with a gameboy. A bit later, my aunt started to take me to her babysitting job. At that place, they also had a gameboy and more then one game. I remember it well, it were two girls, two sisters. While they were doing their girl things, I was allowed to play on the gameboy. My love grew and grew even stronger.
I already talked about how awesome my family is. When they saw that I was so much in love with the Gameboy, they actually got me a gameboy. Not only was it the latest model, they got it in my favorite color! To this day, I still own that very silver gameboy pocket. I was so happy, I had my own gameboy. I did jobs around the house to be able to buy new batteries for the gameboy. Then they got me rechargeable batteries, and my life was complete.
I never showed my latest garage sale loot here on my blog. Whoops.
In my childhood, we had this tradition to go to the sea on holiday. Man, always to the same house. I used to look forward to it every single year. Sadly enough, the owners of the house sold it, and the tradition is over now.
But back then, they used to take me to garage sales. So, as a young kid, they asked me to wake up early in the morning in the summer holidays. I honestly didn't care one bit. Since I was allowed to buy games.
My family didn't want that I bought a lot of games, now-a-days that's a very different story, since they were so expensive. A garage sale was such an easy solution. The best thing they did was that they let me roam the garage sales on my own with a notebook and a pen. They said that I could write down the games I wanted and then I had the difficult job to decide which one I wanted.
To this very day, I love to wake up early and go to a garage sale. Every year, I go to around 10 garage sales, if not more. I never go alone, since that would ruin part of the fun for me. The nostalgia of hunting down games, which were pretty rare on the garage sales I went too, is just amazing. The moment a family member bumped me in the arm and pointed to a game, I think they loved to see that sparkle in my eyes of happiness.
Typical me is typical
Garage sales memories are for another article. I was extremely attached to my games. I was always hard to pick games I had to sell. I had to sell a few games before I was allowed to buy new games. Now-a-days, I don't have that restriction anymore.
One time I forgot my gameboy at a restaurant and I begged my mother to turn back and get it. I even begged that they called the restaurant so that nobody could pick up my gameboy and claim it.
Later, my gameboy pocket became my sister's gameboy and I got a gameboy color. Then my sister got a purple gameboy advance and I got a silver gameboy advance SP, the one with the tattoo design on it.
To this very day, I still own most of the games I had back then. Of course, my library of games has grown quite a lot. If only I had the library I had back then, the nights I kept playing on my gameboy would be so much more fun. I remember that I had a lamp you needed to hit a button at the top in order to the lights go out. Since my room was at the end of a hallway, I could hear my parents and a simple slap on the lamp and putting the gameboy screen down, gave the illusion of my sleeping.
My parents knew that I was playing the gameboy under my sheets, but they were never able to catch my red handed. Okay, honestly, they were able a few times but usually, I was always able to dodge the bullet.
I could talk hours about my memories of the gameboy days, but I think I will end my article here. Since I have reached my usual length. I hope you enjoyed reading another special entry in the gameboy advance month. While it isn't fully about the GBA, I hope you don't mind that much.
Thanks again for reading and until another article. Also, don't shit your pants but it's Halloween.
Posted on October 31, 2014 October 31, 2014 by NekoJonezPosted in Gaming NostalgiaTagged 001, advance, arpegi, buttonsmashers, color, colour, easter, egg, gameboy, garage, GB, GBA, gbc, information, jea, jealous, Jonez, jonez001, jonezjea, month, more, neko, NekoJonez, nostalgia, Of, past, retrospective, sales, Stories, The, young. 1 Comment
My gamer style ~ What's your style?
So, this article is going to be something really different. I'm going to talk about how I game, how I select my games to review and play. Also, I'll be talking about how important gaming is and was till this point of time. I might write several articles about this subject but that depends if I'm not lazy. This blog was started with these sort of articles in the back of my mind. I wanted to write more then just reviews. I wanted to share my adventures in the wonderful land of gaming with you. So, to explain this differently, I'll be looking at how I roam the land of gaming. Feel free to share your gamer experiences here. I love to read them, so drop a comment. But without further ado, let's dive into my gamers life.
Brief history.
Sometimes I think I was born with a Nintendo Gameboy. As soon as Pokémon came out, I got the blue version of the game and I couldn't stop playing. But that wasn't my very first game.
Before that, I played Pac-Man on my gameboy. That's the very first game I remember owning. I also had games like Alleyway for my gameboy.
My gameboy & I couldn't be separated. Man, I took that thing everywhere. On the bus, at school, on the toilet. I even remember playing at the egde of my bathtub. Okay, I might have not taken it with me in the shower and believe me, I'll never try.
Although I have 3 consoles in my collection, my passion is still with handheld gaming. That's because of how I grew up. My parents didn't want a NES or SNES hooked up to their TV. They wanted to see their shows, you know. Parents are often that way. Well, expect modern parents then. Games like WarioWorld, Super Mario World 2, The Legend Of Zelda… kept me coming back over and over again.
I was always so jealous when I went over to my cousin's place. He had a NES and DuckHunt. I remember on a birthday party that I played it nearly non-stop. I enjoyed the game so much I couldn't put it down. And in addition to that, my love for Nintendo was already extremely big, so why continue?
Fast forward to June 2013, a year that flew by. I have a rather nice collection in my opinion. More then just Nintendo. And now I play games on many devices. I often start my gaming sessions by playing a bit on my laptop, then moving on to my consoles and then finishing with my handhelds.
My favorite style of games
Readers of my blog and people who know me in my real life will know that I play a big variety of games.
My most loved genres are visual novel, adventure, action, role-play, point & click, puzzle and RPG. The genres you see me play very often are shooters. Games I'll never play are games like Fighting or Racing games.
I have nothing against the genres but I just don't like them. In fighting games I don't like the fact that you have to defeat one opponent and that's all that there is to the game. It doesn't do enough to keep me coming back. And racing games, I have a great friend who actually is way better then me. Plus, they require you to know a bit about cars, which I don't know a thing about.
Games with a big open-world, a memorable adventure and great gameplay is the recipe for a game that I'll rate extremely high. Perfect examples are Okami, Zelda and Tomb Raider.
But there are games with a deep story that I enjoy too. Examples of that are Ace Attorney and Corpse Party.
I admit that I developed a love for games that much that some manage to emotionally influence me. Those series can't do anything wrong in my eyes and I sometimes forgive major gameplay flaws in game.
But how exactly do I play games? Well, I mostly lay on the sofa or sit on my bed. I find that rather comfy. On my nightstand I have my bottle of water or soda and some snacks. My tablet is also there. In case I need a walkthrough or when I want to post on my forum.
About walkthroughs, I prefer not reading them or looking them up. I can be rather stubborn and try over and over again until I got it. I might have rage-quit multiple games because of that, but which gamer doesn't do that from time to time. But when I'm really stuck, I just look at a walkthrough and try to get a hint so I can continue.
All bottles of the nope!
There are things in games that actually can turn me away from a game. Broken menu's I can forgive but when a game has a tutorial that is basically holding your hand, well I might put the game down faster.
Games that don't have a story, I also won't play often. Admitted, almost every game has a story but I don't like them that much. Unless they are puzzle games like Magic Inlay that really got my attention.
I actually don't like multiplayer. Yes, I'm a big loner in games. Unless you count playing survival in Minecraft with my friends. But the reason I don't like multiplayer that much is because of games aren't really meant for multiplayer.
The Call Of Duty series is a big wrongdo-er in the main reason I don't like multiplayer. It makes the single player get weaker and weaker. And this disappoints me. Plus, you got the option to share and brag to your friends that "you are better then them". Let the bullying commence. I like to stay away from multiplayer since I prefer to experience the game on my own and when I'm done with the game, I might test the multiplayer. But expect Halo for sometime, there isn't really a multiplayer that made me come back.
Actually, this is going on for quite a while. I think I will abruptly end this article here. Thanks for reading and stay tuned for more gaming memories, personal opinions, reviews and first impressions. Keep it here.
NekoJonez signing out.
Posted on June 5, 2013 June 5, 2013 by NekoJonezPosted in ArticlesTagged 001, do, ds, gamer, games, gaming, GBA, gbc, how, i, Jonez, jonez001, my, neko, NekoJonez, Nintendo, pc, psp, review, sony, style. Leave a comment
Review #004: The Legend Of Zelda – Oracle Of Seasons ~ Which weather do we take today?
Link to the page in the Zelda wiki about this game.
So last review we went over the sister game of this game. Or brother game, whatever you prefer. I gave the Oracle Of Ages game a very high score. But is this game worthy of the same praise? It was released on the same day but that could make it flawed and feel very rushed. Well, for that you will need to stick around at the end of the review to get your answer. One thing I already can tell you, the game is pretty neat. But now I will dive into this game. The game that you need to play after Oracle of Ages, or before. It's not that I'm trying to write this intro as long as the image for making it visually more interesting to read. Okay, I might be just doing that. So, enough rambling about the intro here and let's dive into this game and check if it's actually good or not. Maybe I lied earlier in the introduction, who knows?
Dancing on a tree stump
In this game's story you aren't left alone. The introduction of the game is the same as the Oracle Of Ages game, you start by riding you trusty horse Epona. (Dirty minds aren't my problem.) So, now the first people you meet actually claim that Din saved you. Which is strange, since they let you rot two screen away in the bushes.
In the other game you talk to animals which doesn't get explained, but who cares, it's an adventure game. In this game, the problems pop up way sooner as Din is kidnapped. To be fair, this game has a great story. It might be your standard "rescue the kidnapped damsel in distress" but it has a twist in this game.
What's pretty neat in this game is that you can change the seasons once you have the season staff. A concept I liked over the Ages game.
The story is now about a sleepy tree that aids you on your quest. Lucky for us, the tree doesn't want to marry us. As you don't receive the blade right away, it's obvious that this game has less puzzles and more action. Yes, the Oracle games have split the Zelda formula in half. This is the more action game. As the other Oracle game, this game has also a 2nd dimension. It's smaller, but it does the trick. I even dare to say that this game's world is bigger then the ages game.
Overdoing Link's clothing
In the other dimension, the characters look like they are fans of Link. They all wear a green tunic, but in overdrive.
And this brings us to a disappoint point of the game, the bosses and some characters are and feel borrowed from previous games. As it's an awesome nod to the older games, it makes the game feel a tad bit creative. There is certainly missed potential with remaking the bosses of the older games.
Yet, to be fair, the animation is great in this game. I really enjoyed the animation in this game and it really pulled me in this game. Also the graphics are extremely well done. How fast you can move through the seasons is better compared against the longer time travel animation of the Ages game.
The worlds look colorful, and white in the winter, and lively. The game has multiple chase quests that can get frustrating because of the limitations of the gameboy.
It still is impressive how the code linking works. If you named the child in the Ages game, the child will be here in the Seasons game. Like in the Ages game, there is also a trade quest, with the same pay-off. Play it to check it out.
Hairpulling
The game is difficult. No doubt about that. You won't go through this game in one sitting. The controls are pretty tight and if you die, it's your fault. Even the jumping is less annoying the in the Ages game.
The items are actually creative. It still has the same gameplay as all the other Zelda portable games but like I said in my previous reviews, it's extremely well implemented. But back on the subject of the items. You have great items, some of the Ages game, that you get to aid you in your quest. This game might be more difficult then Ages in terms of action but the puzzles in this game can be pretty hairpulling sometimes.
The biggest hair pulling moment is where you need to fight Onox. The final boss is extremely difficult because you need to use your spin attack, which is difficult to pull of since he uses Din as a shield. With Veran in Ages I had less trouble. The challenge is still pretty fair and after some practice you get the pattern down and you'll be able to defeat him.
The last thing but not least, are the music and the sound effects. Like in Oracle of Ages, the sound effects are pretty standard. But the music is still pretty amazing. I extremely enjoy the music and really sets the mood. It's really upbeat and the melodies sometimes kept stuck in my head for days on end.
Oh, before I forgot. In the Ages game you were able to select the track you wanted easily. Not here, if you want the right season, it's using the staff on a tree stump and hoping it goes to the right season. Little bit annoying though.
+ Challenges everywhere.
+ Nice animation.
+ Extremely well done music.
+ Great story.
+ Unique items.
– Soundeffects are pretty mediocre.
– The seasons should be better selectable.
– The chase missions.
– Missed opportunity with the final bosses.
Do I truly need to repeat myself? This game is extremely well done but is a bit weaker then the Ages game. The game world is pretty big so this game will least you quite a while. I seriously enjoyed this game and I replay it often. I missed the moments where I was able to explore the game for the very first time since then the game is the most fun.
Posted on May 24, 2013 May 24, 2013 by NekoJonezPosted in ReviewsTagged action, adventure, Ages, capcom, color, game, gameboy, gbc, Jonez, jonez001, Legend, neko, NekoJonez, Nintendo, Of, Oracle, review, seasons, The, Zelda. 6 Comments
Review #003: The Legend Of Zelda: Oracle Of Ages (GBC) ~ No need for a car.
Zelda Wiki link for more information.
This game is the game that got me into the Legend Of Zelda series. But it's not the first Zelda game I played, that was the GBA classic release of the original NES game. When I saw this game collecting dust on a stall at the flea market at my beach holiday, I decided to buy it. And man, did I have fun with this game. I got so frustrated with the "To be continued" screen. Since I needed to buy the 2nd Oracle game, Oracle of Seasons, which I'll review a later day. Maybe my next review. But this game is great, so I really needed to pay attention that my fanboy-ish love for this game didn't influence this review. I tried to be as fair and square for each game as I can. So, let's dive into this game and tell you what is good and what is bad so you might consider buying the limited re-release on the 3DS e-shop when it comes out.
Accept your quest.
The game starts off with Link riding Epona, checking on the Triforce. Once arrived, the Triforce teleports him to the lands of Labrynna. There you meet Impa, well the more gray version of Impa. And then after some other events, all hell breaks lose. The flow of time gets then disrupted and it's up to you to fix what Veran destroyed.
In short, the story was good for a handheld game. It will end up like your typical rescue story but there isn't anything wrong with that. As long as it's interestingly executed. Yet, I like the story of this game over the Oracle Of Seasons one. Yet, it uses elements that were used in a SNES game before. Time travel.
As the name would suggest, insert here a "You don't say".jpg, the game revolves around time travel. A lot of puzzles in this game require you to go back and forth from the past to the present. This actually doubles the world map of the already big game area.
What I like so much about the story of this game is that it's so simple, you don't even notice it's there to begin with. The Zelda games are and have been adventure games to the core, and those have always epic tales of hero's who fight evil. This one is about a tree that wants to marry you.
There is only one minor issue with the start. I got stuck in the first few screens of the game. Since you need to talk all the animals and then again to the bear. Yeah, not that easy. And yes, it's a sign for what to come. Don't take this game too lightly. This game is actually a great challenge for each generation. The bosses in the dungeon are creative and require you to think up unique ways to use the newly acquired item in the dungeon.
This game is filled with puzzles. Puzzles where you need to move blocks, where you need to get a floor all colored and where you need to solve puzzles. Okay, scrap that last one. But it keeps the game pretty varied. Sometimes you need to fight the monsters in a certain time limit and other times you need to sneak into the castle. There is one puzzle I liked so much I tried to program my own version of it. I succeeded but the project died.
The big trading
There is a lovely side quest to the whole game with a reward. That reward really pays off the effort you need to do for it. This side quest is actually sort of a standard in the portable games of The Legend Of Zelda, because as far as I know, it nearly appeared in each portable TLOZ game.
There is a trade quest where you need to trade items with other characters. What the reward is, well I'll leave that up to you guys to explore.
The gameplay is your standard Zelda gameplay. You get an item, you go to dungeon, get new item, defeat boss, get a heart container, puzzle to open next dungeon and repeat. Yup, nothing new there. And it still holds up till today. The game is still extremely fun and pulls you in. Pay attention when you play this game, the hours will fly by. And the game is quite lengthy too, so you won't finish this game in one sitting.
Once you finished the game, you can link up the sister game Oracle of Seasons with a password. This way you pass over the names you gave to characters and you can see the true ending. This game will tease you with a "To Be Continued" screen at the end of the game.
The animation in this game is basic but it works. Actually, I take that back. The animation is pretty neat but not really for the impatient type of people. Burning a bush can take a while. And you aren't able to skip certain animations like time travel. Time travel can be annoying when you go to close to a portal and you go in it by accident.
The music is, as it always in a Zelda game, short of amazing. It was blasting through my speakers the entire time I was writing this review. I even have the music on my harddrive and I listen to it here and there.
The game looks extremely well. The world looks colorful and the past looks aged. I really enjoy both world and the colors given to it. The level desgin is nicely implemented.
But is this game perfect?
As a big Zelda fan, which I am, I would tell you: yes it is. But that wouldn't make for a fair review, wouldn't it? So, let's rip this game a new— oh, nope, let's not finish that sentence.
What I didn't like about this game is how basic the sound effects sound to me. The sound effects are most likely all pulled from a library of other gameboy games and fail to impress me. I even have trouble with placing some of the sound effects in this game. (Yeah, I can be into Zelda too much)
Also the GBA shop is in my opinion a cool addition but truth to be told, it's a cheap marketing trick to get people to buy a GBA. Well played Nintendo, well played.
Also, I wished that Maple appeared a bit more. She nearly never appears and I often sometimes just pass by the screen and miss her. It's even more annoying when you miss her and you needed her for your trade quest.
To finish up this review, I'm going to mention something positive. The controls are extremely well done in this game. Apart from the jumping that can be a bit annoying…
+ Great music.
+ Decent story.
+ Great, long adventure.
+ Lovely puzzles.
+ Nice graphics.
– Cheaty Maple.
– The cheap "buy GBA" promotion.
– Weaker sound effects.
I had an hard time finding bad elements in this game. I went searching around what other reviewers had to say and they gave it all nearly a perfect score. This game is one of the best gameboy color games period. It's even one of my favorite Zelda games. Actually the Oracle games are my favorite in the series.
As a Zelda fan, you really owe yourself to play this game. And if you love adventure games, you need to play this game. Don't wait, play it. But first let me know in the comments what you think of this game.
Posted on May 23, 2013 May 23, 2013 by NekoJonezPosted in ReviewsTagged 3DS, adventure, Ages, back, best, capcom, color, colour, download, e-shop, for, game, gameboy, gbc, is, Jonez, jonezjea, Legend, neko, NekoJonez, new, Nintendo, Of, on, Oracle, release, review, score, shop, The, Zelda. 9 Comments


The lounge chair was designed by Verner Panton in the 1970s. This model was manufactured by Fritz Hansen in Denmark. The chair features a steel frame and new black Kvadrat upholstery. It is in a very good vintage condition.