Optimized Parameter Search for Large Datasets of the Regularization Parameter and Feature Selection for Ridge Regression

In this paper we propose mathematical optimizations to select the optimal regularization parameter for ridge regression using cross-validation. The resulting algorithm is suited for large datasets and the computational cost does not depend on the size of the training set. We extend this algorithm to forward or backward feature selection in which the optimal regularization parameter is selected for each possible feature set. These feature selection algorithms yield solutions with a sparse weight matrix using a quadratic cost on the norm of the weights. A naive approach to optimizing the ridge regression parameter has a computational complexity of the order $O(R K N^{2} M)$ with $R$ the number of applied regularization parameters, $K$ the number of folds in the validation set, $N$ the number of input features and $M$ the number of data samples in the training set. Our implementation has a computational complexity of the order $O(KN^3)$ . This computational cost is smaller than that of regression without regularization $O(N^2M)$ for large datasets and is independent of the number of applied regularization parameters and the size of the training set. Combined with a feature selection algorithm the algorithm is of complexity $O(RKNN_s^3)$ and $O(RKN^3N_r)$ for forward and backward feature selection respectively, with $N_s$ the number of selected features and $N_r$ the number of removed features. This is an order $M$ faster than $O(RKNN_s^3M)$ and $O(RKN^3N_rM)$ for the naive implementation, with $N \ll M$ for large datasets. To show the performance and reduction in computational cost, we apply this technique to train recurrent neural networks using the reservoir computing approach, windowed ridge regression, least-squares support vector machines (LS-SVMs) in primal space using the fixed-size LS-SVM approximation and extreme learning machines.     

An improved FPTAS for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem

Recently, Shabtay and Bensoussan (2012) developed an original exact pseudo-polynomial algorithm and an efficient $\upvarepsilon $ -approximation algorithm (FPTAS) for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem. The complexity of the FPTAS is $O$ (( $n^{4}/\upvarepsilon $ )log( $n$ / $\upvarepsilon $ )), where $n$ is the number of jobs. In this note we suggest another pseudo-polynomial algorithm that can be converted to a new FPTAS which improves Shabtay–Bensoussan’s complexity result and runs in $O(n^{3}/\upvarepsilon )$ time.     

A sparse {\varvec{L}}_{2}-regularized support vector machines for efficient natural language learning

Linear kernel support vector machines (SVMs) using either $L_{1}$ -norm or $L_{2}$ -norm have emerged as an important and wildly used classification algorithm for many applications such as text chunking, part-of-speech tagging, information retrieval, and dependency parsing. $L_{2}$ -norm SVMs usually provide slightly better accuracy than $L_{1}$ -SVMs in most tasks. However, $L_{2}$ -norm SVMs produce too many near-but-nonzero feature weights that are highly time-consuming when computing nonsignificant weights. In this paper, we present a cutting-weight algorithm to guide the optimization process of the $L_{2}$ -SVMs toward a sparse solution. Before checking the optimality, our method automatically discards a set of near-but-nonzero feature weight. The final objects can then be achieved when the objective function is met by the remaining features and hypothesis. One characteristic of our cutting-weight algorithm is that it requires no changes in the original learning objects. To verify this concept, we conduct the experiments using three well-known benchmarks, i.e., CoNLL-2000 text chunking, SIGHAN-3 Chinese word segmentation, and Chinese word dependency parsing. Our method achieves 1–10 times feature parameter reduction rates in comparison with the original $L_{2}$ -SVMs, slightly better accuracy with a lower training time cost. In terms of run-time efficiency, our method is reasonably faster than the original $L_{2}$ -regularized SVMs. For example, our sparse $L_{2}$ -SVMs is 2.55 times faster than the original $L_{2}$ -SVMs with the same accuracy.     

The bideterminants of matrices over semirings

This paper deals with the relationships between the concepts of linear dependence and independence of vectors, and the bideterminant of a matrix including the links between the bideterminant and rank of a square matrix in semilinear spaces of $n$ -dimensional vectors over commutative zerosumfree semirings. First, it discusses some properties of bideterminant of a matrix, then introduces the concepts of semi-linear dependence and strong linear independence of a set of vectors, respectively, and gives a necessary and sufficient condition that the bideterminant of a matrix is equal to $0$ . In the end, it shows a necessary and sufficient condition that the rank of an $n$ -square matrix is equal to $n$ .     

Robust sparsity-preserved learning with application to image visualization

Linear subspace learning is of great importance for the purpose of visualization of high-dimensional observations. Sparsity-preserved learning (SPL) is a recently developed technique for linear subspace learning. Its objective function is formulated by using the $\ell _2$ -norm, which implies that the obtained projection vectors are likely to be distorted by outliers. In this paper, we develop a new SPL algorithm called SPL-L1 based on the $\ell _1$ -norm instead of the $\ell _2$ -norm. The proposed approach seeks projection vectors by minimizing a reconstruction error subject to a constraint of samples dispersion, both of which are defined using the $\ell _1$ -norm. As a robust alternative, SPL-L1 works well in the presence of atypical samples. We design an iterative algorithm under the framework of bound optimization to solve the projection vectors of SPL-L1. The experiments on image visualization demonstrate the superiority of the proposed method.     

The Parameterized Complexity of Unique Coverage and Its Variants

In this paper we study the parameterized complexity of the Unique Coverage problem, a variant of the classic Set Cover problem. This problem admits several parameterizations and we show that all, except the standard parameterization and a generalization of it, are unlikely to be fixed-parameter tractable. We use results from extremal combinatorics to obtain the best-known kernel for Unique Coverage and the well-known color-coding technique of Alon et al. (J. ACM 42(4), 844–856, 1995) to show that a weighted version of this problem is fixed-parameter tractable. Our application of color-coding uses an interesting variation of s-perfect hash families called (k,s)-hash families which were studied by Alon et al. (J. Comb. Theory Ser. A 104(1), 207–215, 2003) in the context of a class of codes called parent identifying codes (Barg et al. in SIAM J. Discrete Math. 14(3), 423–431, 2001). To the best of our knowledge, this is the first application of (k,s)-hash families outside the domain of coding theory. We prove the existence of such families of size smaller than the best-known s-perfect hash families using the probabilistic method (Alon and Spencer in The Probabilistic Method, Wiley, New York, 2000). Explicit constructions of such families of size promised by the probabilistic method is open.     

On weighted first-order logics with discounting

We introduce a linear temporal logic and a first-order logic in the weighted setup of the max-plus semiring with discounting parameters in $[0,1)$ . Furthermore, we define $\omega \hbox {-}d$ -star-free series and counter-free weighted Büchi automata. We show that the classes of series definable in fragments of the weighted linear temporal logic and first-order logic, the class of $\omega \hbox {-}d$ -star-free series, and a subclass of $\omega \hbox {-}d$ -counter-free series coincide. This extends a fundamental result, for first-order logic theory, to series over the max-plus semiring with discounting.     

Maximizing the weighted number of just-in-time jobs on a single machine with position-dependent processing times

We study the problem of maximizing the weighted number of just-in-time jobs on a single machine with position-dependent processing times. Unlike the vast majority of the literature, we do not restrict ourselves to a specific model of processing time function. Rather, we assume that the processing time function can be of any functional structure that is according to one of the following two cases. The first is the case where the job processing times are under a learning effect, i.e., each job processing time is a non-increasing function of its position in the sequence. In the second case, an aging effect is assumed, i.e., each job processing time is a non-decreasing function of its position in the sequence. We prove that the problem is strongly $\mathcal{N }\mathcal{P }$ N P -hard under a learning effect, even if all the weights are identical. When there is an aging effect, we introduce a dynamic programming (DP) procedure that solves the problem with arbitrary weights in $O(n^{3})$ O ( n 3 ) time (where $n$ n is the number of jobs). For identical weights, a faster optimization algorithm that runs in $O(n\log n)$ O ( n log n ) time is presented. We also extend the analysis to the case of scheduling on a set of $m$ m parallel unrelated machines and provide a DP procedure that solves the problem in polynomial time, given that $m$ m is fixed and that the jobs are under an aging effect.     

An approach to the DIN Kernel Lisp definition

A DIN Kernel LISP Draft (DKLisp) has been developed by DIN as Reaction to Action D1 (N79), short term goal, of ISO WG16. It defines a subset language, as compatible as possible with the ANSICommon-Lisp draft, but also with theEuLisp draft. It combines the most important LISP main stream features in a single, compact, but nevertheless complete language definition, which thereby could be well suited as basis for a short term InternationalLisp Standard. Besides the functional and knowledge processing features, the expressive power of the language is well comparable with contemporary procedural languages, as e.g. C++ (of course without libraries). Important features ofDKLisp are:

to be a “Lisp-1,” but allowing an easy “Lisp-2” transformation;

to be a simple, powerful and standardized educationalLisp;

to omit all features, which are unclean or in heavy discussion;

DKLisp programs run nearly unchanged inCommon-Lisp;

DKLisp contains a simple object and package system;

DKLisp contains those data classes and control structures also common to most modernLisp and non-Lisp languages;

DKLisp offers a simple stream I/O;

DKLisp contains a clean unified hierarchical class/type system;

DKLisp contains the typical “Lisp-features” in an orthogonal way;

DKLisp allows and encourages really small but powerful implementations;

DKLisp comes in levels, so allowing ANSICommon-Lisp to be an extension ofDKLisp level-1.

The present is the second version of the proposal, namely version 1.2, with slight differences with respect to the one sent to ISO. Sources of such changes were the remarks generously sent by many readers of the previous attempt.     

Privacy-preserving similarity evaluation and application to remote biometrics authentication

In this paper, a new method for secure remote biometric authentication preventing the vulnerability of compromised biometrics is presented. The idea is based on a public-key cryptographical protocol, referred as zero-knowledge proof, which allows a user to prove that she has surely a valid biometric data without revealing the data. Hence, the scheme is free from the risk of disclosure of biometric data. Even if a malicious administrator has a privilege access to the private database, it is infeasible for him to learn the private template. This paper studies two well-known definitions, the cosine correlation and the Euclidean distance as similarities of given two feature vectors. Both similarities are defined with some multiplications and additions, which can be performed in privacy-preserving way because of the useful property of public-key commitment scheme, additive homomorphism. The estimation based on the experimental implementation shows that the private Euclidean distance scheme archives better accuracy in terms of false acceptance and rejection than the private cosine coloration scheme, but it requires about $5/2 n \ell$ overhead to evaluate $n$ -dimension feature vectors consisting of $\ell$ -bit integers.     

Characterization of extended filters in residuated lattices

We give a characterization theorem of extended filters on residuated lattices, from which many results are immediately obtained. We show that, for a bounded integral commutative residuated lattice X, (1) an extended filter $E_F (B)$ associated with $B$ is characterized by $E_F (B) = [B) \rightarrow F$ , where $B\subseteq X$ and $F$ is a filter of $X$ ; (2) the class $E(B)$ of all extended filters associated with $B$ is a complete Heyting algebra. (3) the class $S(B)$ of all stable filters relative to $B\subseteq X$ is also a complete Heyting algebra.     

Nonlinear features of heart rate variability in paranoid schizophrenic

Cardiovascular mortality is significantly increased in patients suffering from schizophrenia. However, psychotic symptoms are quantified by means of the scale for the assessment of positive and negative symptoms, but many investigations try to introduce new etiology for psychiatric disorders based on combination of biological, psychological and social causes. Classification between healthy and paranoid cases has been achieved by time, frequency, Hilbert–Huang (HH) and a combination between those features as a hybrid features. Those features extracted from the Hilbert–Huang transform for each intrinsic mode function (IMF) of the detrended time series for each healthy case and paranoid case. Short-term ECG recordings of 20 unmedicated patients suffering from acute paranoid schizophrenia and those obtained from healthy matched peers have been utilized in this investigation. Frequency features: very low frequency (VLF), low frequency (LF), high frequency (HF) and HF/LF (ratio) produced promising success rate equal to 97.82 % in training and 97.77 % success rate in validation by means of IMF1 and ninefolds. Time–frequency features [LF, HF and ratio, mean, maximum (max), minimum (min) and standard deviation (SD)] provided 100 % success in both training and validation trials by means of ninefolds for IMF1 and IMF2. By utilizing IMF1 and ninefolds, frequency and Hilbert–Hang features [LF, HF, ratio, mean value of envelope ( \(\bar{a}\) )] produced 96.87 and 95.5 % for training and validation, respectively. By analyzing the first IMF and using ninefolds, time and Hilbert–Hang features [mean, max, min, SD, median, first quartile (Q1), third quartile (Q3), kurtosis, skewness, Shannon entropy, approximate entropy and energy, ( \(\bar{a}\) ), level of envelope variation ([ \(\dot{a}\) (t)]^2), central frequency \((\bar{W})\) and number of zero signal crossing \((\left| {\bar{W}} \right|)\) ] produced a 100 % success rate in training and 90 % success rate in validation. Time, frequency and HH features [energy, VLF, LF, HF, ratio and ( \(\bar{a}\) )] provided 97.5 % success rate in training and 95.24 % success rate in validation using IMF1 and sixfolds. However, frequency features have produced promising classification success rate, but hybrid features emerged the highest classification success rate than using features in each domain separately.     

CO 2 and cost optimization of reinforced concrete footings using a hybrid big bang-big crunch algorithm

A procedure is developed for the design of reinforced concrete footings subjected to vertical, concentric column loads that satisfies both structural requirements and geotechnical limit states using a hybrid Big Bang-Big Crunch (BB-BC) algorithm. The objectives of the optimization are to minimize cost, CO $_{2}$ emissions, and the weighted aggregate of cost and CO $_{2}$ . Cost is based on the materials and labor required for the construction of reinforced concrete footings and CO $_{2}$ emissions are associated with the extraction and transportation of raw materials; processing, manufacturing, and fabrication of products; and the emissions of equipment involved in the construction process. The cost and CO $_{2}$ objective functions are based on weighted values and are subjected to bending moment, shear force, and reinforcing details specified by the American Concrete Institute (ACI 318-11), as well as soil bearing and displacement limits. Two sets of design examples are presented: low-cost and low-CO $_{2}$ emission designs based solely on geotechnical considerations; and designs that also satisfy the ACI 318-11 code for structural concrete. A multi-objective optimization is applied to cost and CO $_{2}$ emissions. Results are presented that demonstrate the effects of applied load, soil properties, allowable settlement, and concrete strength on designs.     

A new method for solving an arbitrary fully fuzzy linear system

In this paper, We propose a simple and practical method (that works only for triangular fuzzy numbers) to solve an arbitrary fully fuzzy linear system (FFLS) in the form $\widetilde{A}\otimes \widetilde{x}=\widetilde{b},$ where $\widetilde{A}_{n \times n}$ is a fuzzy matrix, $\widetilde{x}$ and $\widetilde{b}$ are n × 1 fuzzy vectors. The idea of the presented method is constructed based on the extending 0-cut and 1-cut solution of original fully fuzzy linear systems (FFLS). We also define a fuzzy solution of FFLS and establish the necessary and sufficient conditions for the uniqueness of a fuzzy solution.     

Zone analysis: a visualization framework for classification problems

There have been large attempts to adopt the bias-variance framework from the regression problems to the classification problems. However, recently, it has been shown that only non-straightforward extensions exist for classification problems. In this paper, we present an alternative visualization framework for classification problems called zone analysis. Our zone analysis framework partly extends the bias-variance idea; instead of decomposing an error into two parts, i.e. the biased and unbiased components, our framework decomposes the error into K components. While bias-variance information is still contained in our framework, our framework provides interesting observations which are not obviously seen in the previous bias-variance framework, e.g. a prejudice behavior of the bagging algorithm to various unbiased instances. Our framework is suitable for visualizing an effect of context changes on learning performance. The type of context changes which we primarily investigate in the paper is “a change from a base learner to an ensemble learner such as bagging, adaboost, arc-x4 and multi-boosting”.     

Error estimation in a balanced norm for a convection-diffusion problem with two different boundary layers

The \(\varepsilon \) -weighted energy norm is the natural norm for singularly perturbed convection-diffusion problems with exponential layers. But, this norm is too weak to recognise features of characteristic layers. We present an error analysis in a differently weighted energy norm—a balanced norm—that overcomes this drawback.     

Reduced ordered binary decision diagram with implied literals: a new knowledge compilation approach

Reduced ordered binary decision diagram (ROBDD) is one of the most influential knowledge compilation languages. We generalize it by associating some implied literals with each node to propose a new language called ROBDD with implied literals (ROBDD- $L$ ) and show that ROBDD- $L$ can meet most of the querying requirements involved in the knowledge compilation map. Then, we discuss a kind of subsets of ROBDD- $L$ called ROBDD- $L_i$ with precisely $i$ implied literals $(0\le i\le \infty )$ , where ROBDD- $L_0$ is isomorphic to ROBDD. ROBDD- $L_i$ has uniqueness over any given linear order of variables. We mainly focus on ROBDD- $L_\infty $ and demonstrate that: (a) it is a canonical representation on any given variable order; (b) it is the most succinct subset in ROBDD- $L$ and thus also meets most of the querying requirements; (c) given any logical operation ROBDD supports in polytime, ROBDD- $L_\infty $ can also support it in time polynomial in the sizes of the equivalent ROBDDs. Moreover, we propose an ROBDD- $L_i$ compilation algorithm for any $i$ and an ROBDD- $L_\infty $ compilation algorithm, and then we implement an ROBDD- $L$ package called BDDjLu. Our preliminary experimental results indicate that: (a) the compilation results of ROBDD- $L_\infty $ are significantly smaller than those of ROBDD; (b) the standard d-DNNF compiler c2d and our ROBDD- $L_\infty $ compiler do not dominate the other, yet ROBDD- $L_\infty $ has canonicity and supports more querying requirements and relatively efficient logical operations; and (c) the method that first compiles knowledge base into ROBDD- $L_\infty $ and then converts ROBDD- $L_\infty $ into ROBDD provides an efficient ROBDD compiler.     

Completions of cut systems in Q-sets

Let $ Q$ be a complete residuated lattice. Let $\text {SetR}(Q)$ be the category of sets with similarity relations with values in $ Q$ (called $ Q$ -sets), which is an analogy of the category of classical sets with relations as morphisms. A cut in an $ Q$ -set $(A,\delta )$ is a system $(C_{\alpha })_{\alpha \in Q}$ , where $C_{\alpha }$ are subsets of $A\times Q$ . It is well known that in the category $\text {SetR}(Q)$ , there is a close relation between special cuts (called f-cuts) in an $ Q$ -set on one hand and fuzzy sets in the same $ Q$ -set, on the other hand. Moreover, there exists a completion procedure according to which any cut $(C_{\alpha })_{\alpha }$ can be extended onto an f-cut $(\overline{C_{\alpha }})_{\alpha }$ . In the paper, we prove that the completion procedure is, in some sense, the best possible. This will be expressed by the theorem which states that the category of f-cuts is a full reflective subcategory in the category of cuts.     

Geometric discord and measurement-induced nonlocality for well known bound entangled states

We employ geometric discord and measurement induced nonlocality to quantify quantumness of some well-known bipartite bound entangled states, namely the two families of Horodecki’s ( $2\otimes 4, 3\otimes 3$ and $4\otimes 4$ dimensional) bound entangled states and that of Bennett et al.’s in $3\otimes 3$ dimension. In most of the cases our results are analytic and both the measures attain relatively small value. The amount of quantumness in the $4\otimes 4$ bound entangled state of Benatti et al. and the $2\otimes 8$ state having the same matrix representation (in computational basis) is same. Coincidently, the $2m\otimes 2m$ Werner and isotropic states also exhibit the same property, when seen as $2\otimes 2m^2$ dimensional states.     

Enhancing web browser security against malware extensions

In this paper we examine security issues of functionality extension mechanisms supported by web browsers. Extensions (or “plug-ins”) in modern web browsers enjoy unrestrained access at all times and thus are attractive vectors for malware. To solidify the claim, we take on the role of malware writers looking to assume control of a user’s browser space. We have taken advantage of the lack of security mechanisms for browser extensions and implemented a malware application for the popular Firefox web browser, which we call browserSpy, that requires no special privileges to be installed. browserSpy takes complete control of the user’s browser space, can observe all activity performed through the browser and is undetectable. We then adopt the role of defenders to discuss defense strategies against such malware. Our primary contribution is a mechanism that uses code integrity checking techniques to control the extension installation and loading process. We describe two implementations of this mechanism: a drop-in solution that employs JavaScript and a faster, in-browser solution that makes uses of the browser’s native cryptography implementation. We also discuss techniques for runtime monitoring of extension behavior to provide a foundation for defending threats posed by installed extensions.