Exponentiated gradient algorithms for conditional random fields and max-margin Markov Networks

Log-linear and maximum-margin models are two commonly-used methods in supervised machine learning, and are frequently used in structured prediction problems. Efficient learning of parameters in these models is therefore an important problem, and becomes a key factor when learning from very large data sets. This paper describes exponentiated gradient (EG) algorithms for training such models, where EG updates are applied to the convex dual of either the log-linear or max-margin objective function; the dual in both the log-linear and max-margin cases corresponds to minimizing a convex function with simplex constraints. We study both batch and online variants of the algorithm, and provide rates of convergence for both cases. In the max-margin case, O(1/ε) EG updates are required to reach a given accuracy ε in the dual; in contrast, for log-linear models only O(log(1/ε)) updates are required. For both the max-margin and log-linear cases, our bounds suggest that the online EG algorithm requires a factor of n less computation to reach a desired accuracy than the batch EG algorithm, where n is the number of training examples. Our experiments confirm that the online algorithms are much faster than the batch algorithms in practice. We describe how the EG updates factor in a convenient way for structured prediction problems, allowing the algorithms to be efficiently applied to problems such as sequence learning or natural language parsing. We perform extensive evaluation of the algorithms, comparing them to L-BFGS and stochastic gradient descent for log-linear models, and to SVM-Struct for max-margin models. The algorithms are applied to a multi-class problem as well as to a more complex large-scale parsing task. In all these settings, the EG algorithms presented here outperform the other methods.

Parameterized Algorithms for MAX COLORABLE INDUCED SUBGRAPH Problem on Perfect Graphs

We address the parameterized complexity ofMaxColorable Induced Subgraph on perfect graphs. The problem asks for a maximum sized q-colorable induced subgraph of an input graph G. Yannakakis and Gavril IPL 1987] showed that this problem is NP-complete even on split graphs if q is part of input, but gave a n(O(q)) algorithm on chordal graphs. We first observe that the problem is W2]-hard parameterized by q, even on split graphs. However, when parameterized by l, the number of vertices in the solution, we give two fixed-parameter tractable algorithms. The first algorithm runs in time 5.44(l) (n+#alpha(G))(O(1)) where #alpha(G) is the number of maximal independent sets of the input graph. The second algorithm runs in time q(l+o()l())n(O(1))T(alpha) where T-alpha is the time required to find a maximum independent set in any induced subgraph of G. The first algorithm is efficient when the input graph contains only polynomially many maximal independent sets; for example split graphs and co-chordal graphs. The running time of the second algorithm is FPT in l alone (whenever T-alpha is a polynomial in n), since q <= l for all non-trivial situations. Finally, we show that (under standard complexitytheoretic assumptions) the problem does not admit a polynomial kernel on split and perfect graphs in the following sense: (a) On split graphs, we do not expect a polynomial kernel if q is a part of the input. (b) On perfect graphs, we do not expect a polynomial kernel even for fixed values of q >= 2.

On The Center Sets and Center Numbers of Some Graph Classes

For a set S of vertices and the vertex v in a connected graph G, max x2S d(x, v) is called the S-eccentricity of v in G. The set of vertices with minimum S-eccentricity is called the S-center of G. Any set A of vertices of G such that A is an S-center for some set S of vertices of G is called a center set. We identify the center sets of certain classes of graphs namely, Block graphs, Km,n, Kn −e, wheel graphs, odd cycles and symmetric even graphs and enumerate them for many of these graph classes. We also introduce the concept of center number which is defined as the number of distinct center sets of a graph and determine the center number of some graph classes

Authenticating the identity of computer users with typing biometrics and the fuzzy min-max neural network

In this paper, typing biometrics is applied as an additional security measure to the password-based or Personal Identification Number (PIN)-based systems to authenticate the identity of computer users. In particular, keystroke pressure and latency signals are analyzed using the Fuzzy Min-Max (FMM) neural network for authentication purposes. A special pressure-sensitive keyboard is designed to collect keystroke pressure signals, in addition to the latency signals, from computer users when they type their passwords. Based on the keystroke pressure and latency signals, the FMM network is employed to classify the computer users into two categories, i.e., genuine users or impostors. To assess the effectiveness of the proposed approach, two sets of experiments are conducted, and the results are compared with those from statistical methods and neural network models. The experimental outcomes positively demonstrate the potentials of using typing biometrics and the FMM network to provide an additional security layer for the current password-based or PIN-based methods in authenticating the identity of computer users.

Transfer learning using the online Fuzzy Min-Max neural network

In this paper, we present an empirical analysis on transfer learning using the Fuzzy Min–Max (FMM) neural network with an online learning strategy. Three transfer learning benchmark data sets, i.e., 20 Newsgroups, WiFi Time, and Botswana, are used for evaluation. In addition, the data samples are corrupted with white Gaussian noise up to 50 %, in order to assess the robustness of the online FMM network in handling noisy transfer learning tasks. The results are analyzed and compared with those from other methods. The outcomes indicate that the online FMM network is effective for undertaking transfer learning tasks in noisy environments.

An enhanced fuzzy min-max neural network for pattern classification

An enhanced fuzzy min-max (EFMM) network is proposed for pattern classification in this paper. The aim is to overcome a number of limitations of the original fuzzy min-max (FMM) network and improve its classification performance. The key contributions are three heuristic rules to enhance the learning algorithm of FMM. First, a new hyperbox expansion rule to eliminate the overlapping problem during the hyperbox expansion process is suggested. Second, the existing hyperbox overlap test rule is extended to discover other possible overlapping cases. Third, a new hyperbox contraction rule to resolve possible overlapping cases is provided. Efficacy of EFMM is evaluated using benchmark data sets and a real medical diagnosis task. The results are better than those from various FMM-based models, support vector machine-based, Bayesian-based, decision tree-based, fuzzy-based, and neural-based classifiers. The empirical findings show that the newly introduced rules are able to realize EFMM as a useful model for undertaking pattern classification problems.

A modified fuzzy min-max neural network for data clustering and its application to power quality monitoring

When no prior knowledge is available, clustering is a useful technique for categorizing data into meaningful groups or clusters. In this paper, a modified fuzzy min-max (MFMM) clustering neural network is proposed. Its efficacy for tackling power quality monitoring tasks is demonstrated. A literature review on various clustering techniques is first presented. To evaluate the proposed MFMM model, a performance comparison study using benchmark data sets pertaining to clustering problems is conducted. The results obtained are comparable with those reported in the literature. Then, a real-world case study on power quality monitoring tasks is performed. The results are compared with those from the fuzzy c-means and k-means clustering methods. The experimental outcome positively indicates the potential of MFMM in undertaking data clustering tasks and its applicability to the power systems domain.

Cervical soft tissue imaging using a mobile CBCT scanner with a flat panel detector in comparison with corresponding CT and MRI data sets

OBJECTIVE: The aim of this study was to evaluate soft tissue image quality of a mobile cone-beam computed tomography (CBCT) scanner with an integrated flat-panel detector. STUDY DESIGN: Eight fresh human cadavers were used in this study. For evaluation of soft tissue visualization, CBCT data sets and corresponding computed tomography (CT) and magnetic resonance imaging (MRI) data sets were acquired. Evaluation was performed with the help of 10 defined cervical anatomical structures. RESULTS: The statistical analysis of the scoring results of 3 examiners revealed the CBCT images to be of inferior quality regarding the visualization of most of the predefined structures. Visualization without a significant difference was found regarding the demarcation of the vertebral bodies and the pyramidal cartilages, the arteriosclerosis of the carotids (compared with CT), and the laryngeal skeleton (compared with MRI). Regarding arteriosclerosis of the carotids compared with MRI, CBCT proved to be superior. CONCLUSIONS: The integration of a flat-panel detector improves soft tissue visualization using a mobile CBCT scanner.

Fuzzy min-max neural networks for categorical data: application to missing data imputation

The fuzzy min–max neural network classifier is a supervised learning method. This classifier takes the hybrid neural networks and fuzzy systems approach. All input variables in the network are required to correspond to continuously valued variables, and this can be a significant constraint in many real-world situations where there are not only quantitative but also categorical data. The usual way of dealing with this type of variables is to replace the categorical by numerical values and treat them as if they were continuously valued. But this method, implicitly defines a possibly unsuitable metric for the categories. A number of different procedures have been proposed to tackle the problem. In this article, we present a new method. The procedure extends the fuzzy min–max neural network input to categorical variables by introducing new fuzzy sets, a new operation, and a new architecture. This provides for greater flexibility and wider application. The proposed method is then applied to missing data imputation in voting intention polls. The micro data—the set of the respondents’ individual answers to the questions—of this type of poll are especially suited for evaluating the method since they include a large number of numerical and categorical attributes.

Global compilation of benthic data sets I

Approaches to quantify the organic carbon accumulation on a global scale generally do not consider the small-scale variability of sedimentary and oceanographic boundary conditions along continental margins. In this study, we present a new approach to regionalize the total organic carbon (TOC) content in surface sediments (<5 cm sediment depth). It is based on a compilation of more than 5500 single measurements from various sources. Global TOC distribution was determined by the application of a combined qualitative and quantitative-geostatistical method. Overall, 33 benthic TOC-based provinces were defined and used to process the global distribution pattern of the TOC content in surface sediments in a 1°x1° grid resolution. Regional dependencies of data points within each single province are expressed by modeled semi-variograms. Measured and estimated TOC values show good correlation, emphasizing the reasonable applicability of the method. The accumulation of organic carbon in marine surface sediments is a key parameter in the control of mineralization processes and the material exchange between the sediment and the ocean water. Our approach will help to improve global budgets of nutrient and carbon cycles.

Data compilation on the biological response to ocean acidification: environmental and experimental context of data sets and related literature

The exponential growth of studies on the biological response to ocean acidification over the last few decades has generated a large amount of data. To facilitate data comparison, a data compilation hosted at the data publisher PANGAEA was initiated in 2008 and is updated on a regular basis (doi:10.1594/PANGAEA.149999). By January 2015, a total of 581 data sets (over 4 000 000 data points) from 539 papers had been archived. Here we present the developments of this data compilation five years since its first description by Nisumaa et al. (2010). Most of study sites from which data archived are still in the Northern Hemisphere and the number of archived data from studies from the Southern Hemisphere and polar oceans are still relatively low. Data from 60 studies that investigated the response of a mix of organisms or natural communities were all added after 2010, indicating a welcomed shift from the study of individual organisms to communities and ecosystems. The initial imbalance of considerably more data archived on calcification and primary production than on other processes has improved. There is also a clear tendency towards more data archived from multifactorial studies after 2010. For easier and more effective access to ocean acidification data, the ocean acidification community is strongly encouraged to contribute to the data archiving effort, and help develop standard vocabularies describing the variables and define best practices for archiving ocean acidification data.

Global data compilation of benthic data sets II

In this study we present a global distribution pattern and budget of the minimum flux of particulate organic carbon to the sea floor (J POC alpha). The estimations are based on regionally specific correlations between the diffusive oxygen flux across the sediment-water interface, the total organic carbon content in surface sediments, and the oxygen concentration in bottom waters. For this, we modified the principal equation of Cai and Reimers [1995] as a basic monod reaction rate, applied within 11 regions where in situ measurements of diffusive oxygen uptake exist. By application of the resulting transfer functions to other regions with similar sedimentary conditions and areal interpolation, we calculated a minimum global budget of particulate organic carbon that actually reaches the sea floor of ~0.5 GtC yr**-1 (>1000 m water depth (wd)), whereas approximately 0.002-0.12 GtC yr**-1 is buried in the sediments (0.01-0.4% of surface primary production). Despite the fact that our global budget is in good agreement with previous studies, we found conspicuous differences among the distribution patterns of primary production, calculations based on particle trap collections of the POC flux, and J POC alpha of this study. These deviations, especially located at the southeastern and southwestern Atlantic Ocean, the Greenland and Norwegian Sea and the entire equatorial Pacific Ocean, strongly indicate a considerable influence of lateral particle transport on the vertical link between surface waters and underlying sediments. This observation is supported by sediment trap data. Furthermore, local differences in the availability and quality of the organic matter as well as different transport mechanisms through the water column are discussed.

On the construction of new bent functions from the max-weight and min-weight functions of old bent functions

Given a bent function f (x) of n variables, its max-weight and min-weight functions are introduced as the Boolean functions f + (x) and f − (x) whose supports are the sets {a ∈ Fn2 | w( f ⊕la) = 2n−1+2 n 2 −1} and {a ∈ Fn2 | w( f ⊕la) = 2n−1−2 n 2 −1} respectively, where w( f ⊕ la) denotes the Hamming weight of the Boolean function f (x) ⊕ la(x) and la(x) is the linear function defined by a ∈ Fn2 . f + (x) and f − (x) are proved to be bent functions. Furthermore, combining the 4 minterms of 2 variables with the max-weight or min-weight functions of a 4-tuple ( f0(x), f1(x), f2(x), f3(x)) of bent functions of n variables such that f0(x) ⊕ f1(x) ⊕ f2(x) ⊕ f3(x) = 1, a bent function of n + 2 variables is obtained. A family of 4-tuples of bent functions satisfying the above condition is introduced, and finally, the number of bent functions we can construct using the method introduced in this paper are obtained. Also, our construction is compared with other constructions of bent functions.