Minyoung Chung, Jusang Lee, Sanguk Park, Minkyung Lee, Chae Eun Lee, Jeongjin Lee, Yeong-Gil Shin
Dental panoramic X-ray imaging is a popular diagnostic method owing to its
very small dose of radiation. For an automated computer-aided diagnosis system
in dental clinics, automatic detection and identification of individual teeth
from panoramic X-ray images are critical prerequisites. In this study, we
propose a point-wise tooth localization neural network by introducing a spatial
distance regularization loss. The proposed network initially performs center
point regression for all the anatomical teeth (i.e., 32 points), which
automatically identifies each tooth. A novel distance regularization penalty is
employed on the 32 points by considering $L_2$ regularization loss of Laplacian
on spatial distances. Subsequently, teeth boxes are individually localized
using a cascaded neural network on a patch basis. A multitask offset training
is employed on the final output to improve the localization accuracy. Our
method successfully localizes not only the existing teeth but also missing
teeth; consequently, highly accurate detection and identification are achieved.
The experimental results demonstrate that the proposed algorithm outperforms
state-of-the-art approaches by increasing the average precision of teeth
detection by 15.71% compared to the best performing method. The accuracy of
identification achieved a precision of 0.997 and recall value of 0.972.
Moreover, the proposed network does not require any additional identification
algorithm owing to the preceding regression of the fixed 32 points regardless
of the existence of the teeth.
Authors' comments: 10 pages, 7 figures
R. Chhetri, A. Kimball, R. D. Ekers, E. K. Mahony, E. M. Sadler, T. Jarrett
Past studies of compact active galactic nuclei (AGNs), the dominant
population at high radio frequencies, selected them using flat spectral index
criteria. This biases the sample due to the steepening of AGN spectra at high
radio frequencies. We improve upon this by selecting 3610 compact AGNs using
their angular size information ($\sim$0.15 arcsec scale) from the Australia
Telescope 20 GHz (AT20G) high-angular-resolution catalogue. We cross-match
these against the Wide-field Infrared Survey Explorer All-WISE catalogue and
present a catalogue with 3300 (91%) matches, 91 (3%) rejects and 219 (6%)
nondetections that are excellent high redshift candidates. Of the matched
compact AGNs, 92% exhibit QSO mid-infrared colours (W1-W2>0.5). Therefore, our
sample of high frequency compact sources has a very high rate of identification
with mid-infrared QSOs. We find counterparts for 88% of 387 compact
steep-spectrum (CSS) sources in the AT20G survey, 82%$\pm$5% of which exhibit
QSO mid-infrared colours and have moderate redshifts (median redshift = 0.82),
while those dominated by host galaxy colours in mid-infrared have lower
redshifts (median redshift = 0.13). The latter classified into late- and
early-type galaxies using their mid-infrared colours shows a majority
(68%$\pm$4%) have colours characteristic of late-type galaxies. Thus, we find
that a larger fraction of these CSS sources are embedded in hosts with higher
gas densities than average early-type galaxies. We compare mid-infrared colours
of our AGNs against those reported for AGNs primarily selected using non-radio
techniques. This shows that mid-infrared SED of high frequency selected compact
radio AGN is comparatively less red, possibly due to contributions from their
hosts.
Authors' comments: Accepted for publication in MNRAS. 21 pages, 18 figures
Kristina Naskovska, André L. F. de Almeida, Martin Haardt
The slice-wise multiplication of two tensors is required in a variety of tensor decompositions (including PARAFAC2 and PARATUCK2) and is encountered in many applications, including the analysis of multidimensional biomedical data (EEG, MEG, etc.) or multi-carrier MIMO systems. In this paper, we propose a new tensor representation that is not based on a slice-wise (matrix) description, but can be represented by a double contraction of two tensors. Such a double contraction of two tensors can be efficiently calculated via generalized unfoldings. It leads to new tensor models of the investigated system that do not depend on the chosen unfolding and reveal the tensor structure of the data model (such that all possible unfoldings can be seen at the same time). As an example, we apply this new concept to the design of new receivers for multi-carrier MIMO systems in wireless communications. In particular, we consider MIMO OFDM systems with and without Khatri-Rao coding. The proposed receivers exploit the channel correlation between adjacent subcarriers, require the same amount of training symbols as traditional OFDM techniques, but have an improved performance in terms of the symbol error rate. Furthermore, we show that the spectral efficiency of the Khatri-Rao coded MIMO-OFDM can be increased by introducing "random coding" such that the "coding matrix" also contains useful information symbols. Considering this transmission technique, we derive a tensor model and two types of receivers for randomly coded MIMO-OFDM systems using the double contraction of two tensors.
Yeonjong Shin
Deep neural networks have been used in various machine learning applications and achieved tremendous empirical successes. However, training deep neural networks is a challenging task. Many alternatives have been proposed in place of end-to-end back-propagation. Layer-wise training is one of them, which trains a single layer at a time, rather than trains the whole layers simultaneously. In this paper, we study a layer-wise training using a block coordinate gradient descent (BCGD) for deep linear networks. We establish a general convergence analysis of BCGD and found the optimal learning rate, which results in the fastest decrease in the loss. More importantly, the optimal learning rate can directly be applied in practice, as it does not require any prior knowledge. Thus, tuning the learning rate is not needed at all. Also, we identify the effects of depth, width, and initialization in the training process. We show that when the orthogonal-like initialization is employed, the width of intermediate layers plays no role in gradient-based training, as long as the width is greater than or equal to both the input and output dimensions. We show that under some conditions, the deeper the network is, the faster the convergence is guaranteed. This implies that in an extreme case, the global optimum is achieved after updating each weight matrix only once. Besides, we found that the use of deep networks could drastically accelerate convergence when it is compared to those of a depth 1 network, even when the computational cost is considered. Numerical examples are provided to justify our theoretical findings and demonstrate the performance of layer-wise training by BCGD.
Michal Kozák, Eamonn A Gaffney, Václav Klika
The study of pattern emergence together with exploration of the exemplar
Turing model is enjoying a renaissance both from theoretical and experimental
perspective. Here, we implement a stability analysis of spatially dependent
reaction kinetics by exploring the effect of a jump discontinuity within
piece-wise constant kinetic parameters, using various methods to identify and
confirm the diffusion-driven instability conditions. Essentially, the presence
of stability or instability in Turing models is a local property for piece-wise
constant kinetic parameters and, as such, may be analysed locally. In
particular, a local assessment of whether parameters are within the Turing
space provides a strong indication that for a large enough region with these
parameters, an instability can be excited.
Authors' comments: 26 pages, 4 figures
Sean E. Lake, Edward L. Wright, Roberto J. Assef, Thomas H. Jarrett, Sara Petty, Spencer A. Stanford, Chao-Wei Tsai
The study of the extragalactic background light (EBL) in the optical and near
infrared has received a lot of attention in the last decade, especially near a
wavelength of $\lambda\approx 3.4\operatorname{\mu m}$, with remaining tension
among different techniques for estimating the background. In this paper we
present a measurement of the contribution of galaxies to the EBL at
$3.4\operatorname{\mu m}$ that is based on the measurement of the luminosity
function (LF) in Lake et al. (2018) and the mean spectral energy distribution
of galaxies in Lake & Wright (2016). The mean and standard deviation of our
most reliable Bayesian posterior chain gives a $3.4\operatorname{\mu m}$
background of $I_\nu = 9.0\pm0.5 \operatorname{kJy} \operatorname{sr}^{-1}$
($\nu I_\nu = 8.0\pm0.4 \operatorname{nW} \operatorname{m}^{-2}
\operatorname{sr}^{-1} e\operatorname{-fold}^{-1}$), with systematic
uncertainties unlikely to be greater than $2\operatorname{kJy}
\operatorname{sr}^{-1}$. This result is higher than most previous efforts to
measure the contribution of galaxies to the $3.4\operatorname{\mu m}$ EBL, but
is consistent with the upper limits placed by blazars and the most recent
direct measurements of the total $3.4\operatorname{\mu m}$ EBL.
Authors' comments: 14 pages, 8 figures, 2 tables, submitted to ApJ. Table 1 data to be
available from figshare under DOI 10.6084/m9.figshare.4245443, Table 2 under
DOI 10.6084/m9.figshare.8142284, and the data behind Figure 5 under
10.6084/m9.figshare.4757131
Kai Qiao, Chi Zhang, Jian Chen, Linyuan Wang, Li Tong, Bin Yan
Recently, visual encoding based on functional magnetic resonance imaging
(fMRI) have realized many achievements with the rapid development of deep
network computation. Visual encoding model is aimed at predicting brain
activity in response to presented image stimuli. Currently, visual encoding is
accomplished mainly by firstly extracting image features through convolutional
neural network (CNN) model pre-trained on computer vision task, and secondly
training a linear regression model to map specific layer of CNN features to
each voxel, namely voxel-wise encoding. However, the two-step manner model,
essentially, is hard to determine which kind of well features are well linearly
matched for beforehand unknown fMRI data with little understanding of human
visual representation. Analogizing computer vision mostly related human vision,
we proposed the end-to-end convolution regression model (ETECRM) in the region
of interest (ROI)-wise manner to accomplish effective and efficient visual
encoding. The end-to-end manner was introduced to make the model automatically
learn better matching features to improve encoding performance. The ROI-wise
manner was used to improve the encoding efficiency for many voxels. In
addition, we designed the selective optimization including self-adapting weight
learning and weighted correlation loss, noise regularization to avoid
interfering of ineffective voxels in ROI-wise encoding. Experiment demonstrated
that the proposed model obtained better predicting accuracy than the two-step
manner of encoding models. Comparative analysis implied that end-to-end manner
and large volume of fMRI data may drive the future development of visual
encoding.
Authors' comments: under review in Computational Intelligence and Neuroscience
Fabian Eitel, Emily Soehler, Judith Bellmann-Strobl, Alexander U. Brandt, Klemens Ruprecht, René M. Giess, Joseph Kuchling, Susanna Asseyer et al.
Machine learning-based imaging diagnostics has recently reached or even superseded the level of clinical experts in several clinical domains. However, classification decisions of a trained machine learning system are typically non-transparent, a major hindrance for clinical integration, error tracking or knowledge discovery. In this study, we present a transparent deep learning framework relying on convolutional neural networks (CNNs) and layer-wise relevance propagation (LRP) for diagnosing multiple sclerosis (MS). MS is commonly diagnosed utilizing a combination of clinical presentation and conventional magnetic resonance imaging (MRI), specifically the occurrence and presentation of white matter lesions in T2-weighted images. We hypothesized that using LRP in a naive predictive model would enable us to uncover relevant image features that a trained CNN uses for decision-making. Since imaging markers in MS are well-established this would enable us to validate the respective CNN model. First, we pre-trained a CNN on MRI data from the Alzheimer's Disease Neuroimaging Initiative (n = 921), afterwards specializing the CNN to discriminate between MS patients and healthy controls (n = 147). Using LRP, we then produced a heatmap for each subject in the holdout set depicting the voxel-wise relevance for a particular classification decision. The resulting CNN model resulted in a balanced accuracy of 87.04% and an area under the curve of 96.08% in a receiver operating characteristic curve. The subsequent LRP visualization revealed that the CNN model focuses indeed on individual lesions, but also incorporates additional information such as lesion location, non-lesional white matter or gray matter areas such as the thalamus, which are established conventional and advanced MRI markers in MS. We conclude that LRP and the proposed framework have the capability to make diagnostic decisions of...
Yona Falinie A. Gaus, Neelanjan Bhowmik, Samet Akçay, Paolo M. Guillen-Garcia, Jack W. Barker, Toby P. Breckon
X-ray baggage security screening is widely used to maintain aviation and
transport security. Of particular interest is the focus on automated security
X-ray analysis for particular classes of object such as electronics, electrical
items, and liquids. However, manual inspection of such items is challenging
when dealing with potentially anomalous items. Here we present a dual
convolutional neural network (CNN) architecture for automatic anomaly detection
within complex security X-ray imagery. We leverage recent advances in
region-based (R-CNN), mask-based CNN (Mask R-CNN) and detection architectures
such as RetinaNet to provide object localisation variants for specific object
classes of interest. Subsequently, leveraging a range of established CNN object
and fine-grained category classification approaches we formulate within object
anomaly detection as a two-class problem (anomalous or benign). While the best
performing object localisation method is able to perform with 97.9% mean
average precision (mAP) over a six-class X-ray object detection problem,
subsequent two-class anomaly/benign classification is able to achieve 66%
performance for within object anomaly detection. Overall, this performance
illustrates both the challenge and promise of object-wise anomaly detection
within the context of cluttered X-ray security imagery.
Authors' comments: IJCNN 2019
Qin Li, Dong Sun
Cases have shown that WENO schemes usually behave robustly on problems containing shocks with high pressure ratios when uniformed or smooth grids are present, while nonlinear schemes based on WENO interpolations might relatively be liable to numerical instability. In the meanwhile, the latter have manifested their advantages in computations on grids of bad quality, because the free-stream preservation is easily realized there, and what is more flux-splitting schemes with low dissipations can be engaged inherently as well. Targeting at above dissatisfactions, a method by hybridizing WENO implementations of interpolation and reconstruction-wise operation for upwind-biased schemes with flux splitting employed is proposed and corresponding third-, fifth- and seventh-order upwind-biased schemes are proposed. Based on the understandings of [Q. Li, et al. Commun. Comput. Phys. 22 (2017) 64-94], the free-stream preservation of proposed schemes is achieved with incorporation of frozen grid metrics in WENO reconstructions-wise operations on split fluxes. In proposed schemes, flux-splitting schemes with low dissipation can also be applied for the flux on a cell edge. As a byproduct, an implementation of WENO scheme with free-stream preservation is obtained. Numerical examples are provided as following with the third- and fifth-order schemes being tested. In tests of free-stream preservation, the property is achieved as expected (including two implementations of WENO). The computation of 1-D Sod problem shows the capability of proposed schemes on solving ordinary shock discontinuity. 2-D vortex preservation and double Mach reflection are tested on uniformed and randomized grids. The accomplishment by proposed schemes manifests their capability and robustness on solving problems under rigorous circumstances.
Emily Moravec, Anthony H. Gonzalez, Daniel Stern, Mark Brodwin, Tracy Clarke, Bandon Decker, Peter R. M. Eisenhardt, Wenli Mo et al.
We present the results from a pilot study with the Karl G. Jansky Very Large
Array (JVLA) to determine the radio morphologies of extended radio sources and
the properties of their host-galaxies in 10 massive galaxy clusters at z~1, an
epoch in which clusters are assembling rapidly. These clusters are drawn from a
parent sample of WISE-selected galaxy clusters that were cross-correlated with
the VLA Faint Images of the Radio Sky at Twenty-Centimeters survey (FIRST) to
identify extended radio sources within 1$^{\prime}$ of the cluster centers. Out
of the ten targeted sources, six are FR II sources, one is an FR I source, and
three sources have undetermined morphologies. Eight radio sources have
associated Spitzer data, 75% presenting infrared counterparts. A majority of
these counterparts are consistent with being massive galaxies. The angular
extent of the FR sources exhibits a strong correlation with the cluster-centric
radius, which warrants further investigation with a larger sample.
Authors' comments: accepted to ApJ
Linda C. P. Croton, Gary Ruben, Kaye S. Morgan, David M. Paganin, Marcus J. Kitchen
We present a pixel-specific, measurement-driven correction that effectively
minimizes errors in detector response that give rise to the ring artifacts
commonly seen in X-ray computed tomography (CT) scans. This correction is easy
to implement, suppresses CT artifacts significantly, and is effective enough
for use with both absorption and phase contrast imaging. It can be used as a
standalone correction or in conjunction with existing ring artifact removal
algorithms to further improve image quality. We validate this method using two
X-ray CT data sets, showing post-correction signal-to-noise increases of up to
55%, and we define an image quality metric to use specifically for the
assessment of ring artifact suppression.
Authors' comments: 11 pages, 7 figures, and 1 ancillary file; questions and comments are
welcome
Alper Hayreter, German Valencia
We present one loop results for the amplitudes giving rise to couplings
between a color octet scalar, a gluon, and an electroweak gauge boson. These
amplitudes could signal new physics in $\gamma$ jet, $Z$ jet and $W$ jet
production at the LHC. We compute the relevant branching ratios and identify
regions of parameter space where these decay modes become important. This can
happen for scalar masses below the threshold for decay into heavy quark pairs
($t\bar t$ and $t\bar b$); or for small Yukawa couplings in which case the
colored scalars are fermiophobic. In the case of light scalars, ${\cal B}(S\to
\gamma g)$ can reach up to 10\% whereas ${\cal B}(S\to Z g)$ can reach a few
percent. In the fermiophobic region of parameter space, ${\cal B}(S\to \gamma
g)$ and ${\cal B}(S\to Z g)$ can reach up to 72\% and 28\% respectively,
whereas ${\cal B}(S\to g g)$ can be 100\%. For the charged scalar, the decay
mode ${\cal B}(S^\pm \to W^\pm g)$ can become dominant in both scenarios.
Authors' comments: 17 pages, 7 Figures
Yuansheng Hua, Lichao Mou, Xiao Xiang Zhu
Aerial image classification is of great significance in remote sensing community, and many researches have been conducted over the past few years. Among these studies, most of them focus on categorizing an image into one semantic label, while in the real world, an aerial image is often associated with multiple labels, e.g., multiple object-level labels in our case. Besides, a comprehensive picture of present objects in a given high resolution aerial image can provide more in-depth understanding of the studied region. For these reasons, aerial image multi-label classification has been attracting increasing attention. However, one common limitation shared by existing methods in the community is that the co-occurrence relationship of various classes, so called class dependency, is underexplored and leads to an inconsiderate decision. In this paper, we propose a novel end-to-end network, namely class-wise attention-based convolutional and bidirectional LSTM network (CA-Conv-BiLSTM), for this task. The proposed network consists of three indispensable components: 1) a feature extraction module, 2) a class attention learning layer, and 3) a bidirectional LSTM-based sub-network. Particularly, the feature extraction module is designed for extracting fine-grained semantic feature maps, while the class attention learning layer aims at capturing discriminative class-specific features. As the most important part, the bidirectional LSTM-based sub-network models the underlying class dependency in both directions and produce structured multiple object labels. Experimental results on UCM multi-label dataset and DFC15 multi-label dataset validate the effectiveness of our model quantitatively and qualitatively.
Anson Lam, Matthew A. Malkan, Edward L. Wright
The combination of the AKARI and WISE infrared all-sky surveys provides an
unique opportunity to identify and characterize the most highly dust obscured
AGNs in the universe. Dust-obscured AGNs are not easily detectable and
potentially underrepresented in extragalactic surveys due to their high optical
extinction, but are readily found in the WISE catalog due to their extremely
red mid-IR colors. Combining these surveys with photometry from Pan-STARRS and
Herschel, we use SED modeling to characterize the extinction and dust
properties of these AGNs. From mid-IR WISE colors, we are able to compute
bolometric corrections to AGN luminosities. Using AKARI's far-IR wavelength
photometry and broadband AGN/galaxy spectral templates, we estimate AGN dust
mass and temperature using simple analytic models with 3-4 parameters. Even
without spectroscopic data, we can determine a number of AGN dust properties
only using SED analysis. These methods, combined with the abundance of archival
photometric data publically available, will be valuable for large-scale studies
of dusty, IR-luminous AGNs.
Authors' comments: 15 pages, 23 figures, accepted for publication by PASJ
Benedikt Bollig, Marie Fortin, Paul Gastin
Message sequence charts (MSCs) naturally arise as executions of communicating
finite-state machines (CFMs), in which finite-state processes exchange messages
through unbounded FIFO channels. We study the first-order logic of MSCs,
featuring Lamport's happened-before relation. We introduce a star-free version
of propositional dynamic logic (PDL) with loop and converse. Our main results
state that (i) every first-order sentence can be transformed into an equivalent
star-free PDL sentence (and conversely), and (ii) every star-free PDL sentence
can be translated into an equivalent CFM. This answers an open question and
settles the exact relation between CFMs and fragments of monadic second-order
logic. As a byproduct, we show that first-order logic over MSCs has the
three-variable property.
Authors' comments: Full version of CONCUR'18 paper:
http://dx.doi.org/10.4230/LIPIcs.CONCUR.2018.7
Adam C. Schneider, Kevin K. Hardegree-Ullman, Michael C. Cushing, J. Davy Kirkpatrick, Evgenya L. Shkolnik
We present Spitzer Space Telescope time-series photometry at 3.6 and 4.5
$\mu$m of 2MASS J11193254$-$1137466AB and WISEA J114724.10$-$204021.3, two
planetary-mass, late-type ($\sim$L7) brown dwarf members of the $\sim$10 Myr
old TW Hya Association. These observations were taken in order to investigate
whether or not a tentative trend of increasing variability amplitude with
decreasing surface gravity seen for L3-L5.5 dwarfs extends to later-L spectral
types and to explore the angular momentum evolution of low-mass objects. We
examine each light curve for variability and find a rotation period of
19.39$^{+0.33}_{-0.28}$ hours and semi-amplitudes of 0.798$^{+0.081}_{-0.083}$%
at 3.6 $\mu$m and 1.108$^{+0.093}_{-0.094}$% at 4.5 $\mu$m for WISEA
J114724.10$-$204021.3. For 2MASS J11193254$-$1137466AB, we find a single period
of 3.02$^{+0.04}_{-0.03}$ hours with semi-amplitudes of
0.230$^{+0.036}_{-0.035}$% at 3.6 $\mu$m and 0.453 $\pm$ 0.037% at 4.5 $\mu$m,
which we find is possibly due to the rotation of one component of the binary.
Combining our results with 12 other late-type L dwarfs observed with Spitzer
from the literature, we find no significant differences between the 3.6 $\mu$m
amplitudes of low surface gravity and field gravity late-type L brown dwarfs at
Spitzer wavelengths, and find tentative evidence (75% confidence) of higher
amplitude variability at 4.5 $\mu$m for young, late-type Ls. We also find a
median rotation period of young brown dwarfs (10-300 Myr) of $\sim$10 hr, more
than twice the value of the median rotation period of field age brown dwarfs
($\sim$4 hr), a clear signature of brown dwarf rotational evolution.
Authors' comments: Accepted for publication in the Astronomical Journal
Ralf-Dieter Scholz, Cameron P. M. Bell
We present three new nearby L dwarf candidates, found in a continued combined
color/proper motion search using WISE, 2MASS, and other survey data, where we
included extended WISE sources and looked closer to the Galactic plane region.
Their spectral types and distances were estimated from photometric comparisons
to well-known L dwarfs with trigonometric parallaxes. The first object, 2MASS
J07555430-3259589, is an extremely red L7.5p dwarf candidate at a photometric
distance of about 16 pc. Its position, proper motion and distance are
consistent with membership in the Carina-Near young moving group. The second
one, 2MASS J07414279-0506464, is resolved in Gaia DR1 as a close binary
(separation 0.3 arcsec), and we classify it as a equal-mass binary candidate
consisting of two L5 dwarfs at 19 pc. Our nearest new neighbor, 2MASS
J19251275+0700362, is an L7 dwarf candidate at 10 pc.
Authors' comments: 2 pages, 1 table, accepted by RNAAS (abstract not included in
original paper)
Yingjie Li, Fa-Cheng Li, Ye Xu, Chen Wang, Xin-Yu Du, Wenjin Yang, Ji Yang
We present a large scale survey of CO outflows in the Gem OB1 molecular cloud
complex and its surroundings using the Purple Mountain Observatory Delingha
13.7 m telescope. A total of 198 outflow candidates were identified over a
large area ($\sim$ 58.5 square degrees), of which 193 are newly detected.
Approximately 68% (134/198) are associated with the Gem OB1 molecular cloud
complex, including clouds GGMC 1, GGMC 2, BFS 52, GGMC 3 and GGMC 4. Other
regions studied are: Local Arm (Local Lynds, West Front), Swallow, Horn, and
Remote cloud. Outflow candidates in GGMC 1, BFS 52, and Swallow are mainly
located at ring-like or filamentary structures. To avoid excessive uncertainty
in distant regions ($\gtrsim$ 3.8 kpc), we only estimated the physical
parameters for clouds in the Gem OB1 molecular cloud complex and in the Local
arm. In those clouds, the total kinetic energy and the energy injection rate of
the identified outflow candidates are $\lesssim$ 1% and $\lesssim$ 3% of the
turbulent energy and the turbulent dissipation rate of each cloud, indicating
that the identified outflow candidates cannot provide enough energy to balance
turbulence of their host cloud at the scale of the entire cloud (several pc to
dozens of pc). The gravitational binding energy of each cloud is $\gtrsim$ 135
times the total kinetic energy of the identified outflow candidates within the
corresponding cloud, indicating that the identified outflow candidates cannot
cause major disruptions to the integrity of their host cloud at the scale of
the entire cloud.
Authors' comments: 53 pages, accepted for publication in ApJS
Jianbo Ye
This short article presents a new implementation for decision trees. By
introducing pre-sorted deques, the leaf-wise greedy tree growing strategy no
longer needs to re-sort data at each node, and takes O(kn) time and O(1) extra
memory locating the best split and branching. The consistent, superior
performance - plus its simplicity and guarantee in producing the same
classification results as the standard decision trees - makes the new
implementation a drop-in replacement for depth-wise tree induction with strong
performance.
Authors' comments: 4 pages, updated with new statistics and fix typos