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.     

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.     

Polyadic tense \theta-valued \Lukasiewicz–Moisil algebras

In this paper we introduce the polyadic tense $\theta$ -valued $\L$ ukasiewicz–Moisil algebras (=polyadic tense $\hbox{LM}_{\theta}$ -algebras), as a common generalization of polyadic tense Boolean algebras and polyadic $\hbox{LM}_{\theta}$ -algebras. Our main result is a representation theorem for polyadic tense $\hbox{LM}_{\theta}$ -algebras.     

Optimal quadrature formulas in the sense of Sard in W_2^{(m,m-1)} space

This paper studies the problem of construction of optimal quadrature formulas in the sense of Sard in the $W_2^{(m,m-1)}(0,1)$ space. Using the Sobolev’s method we obtain new optimal quadrature formulas of such type for $N+1\ge m$ , where $N+1$ is the number of the nodes. Moreover, explicit formulas of the optimal coefficients are obtained. We investigate the order of convergence of the optimal formula for $m=1$ and prove an asymptotic optimality of such a formula in the Sobolev space $L_2^{(1)}(0,1)$ . It turns out that the error of the optimal quadrature formula in $W_2^{(1,0)}(0,1)$ is less than the error of the optimal quadrature formula given in the $L_2^{(1)}(0,1)$ space. The obtained optimal quadrature formula in the $W_2^{(m,m-1)}(0,1)$ space is exact for $\exp (-x)$ and $P_{m-2}(x)$ , where $P_{m-2}(x)$ is a polynomial of degree $m-2$ . Furthermore, some numerical results, which confirm the obtained theoretical results of this work, are given.     

Arithmetizing Classes Around \textsf{NC} 1 and \textsf{L}

The parallel complexity class $\textsf{NC}$ ¹ has many equivalent models such as polynomial size formulae and bounded width branching programs. Caussinus et al. (J. Comput. Syst. Sci. 57:200–212, 1992) considered arithmetizations of two of these classes, $\textsf{\#NC}$ ¹ and $\textsf{\#BWBP}$ . We further this study to include arithmetization of other classes. In particular, we show that counting paths in branching programs over visibly pushdown automata is in $\textsf{FLogDCFL}$ , while counting proof-trees in logarithmic width formulae has the same power as $\textsf{\#NC}$ ¹. We also consider polynomial-degree restrictions of $\textsf{SC}$ ⁱ , denoted $\textsf{sSC}$ ⁱ , and show that the Boolean class $\textsf{sSC}$ ¹ is sandwiched between $\textsf{NC}$ ¹ and $\textsf{L}$ , whereas $\textsf{sSC}$ ⁰ equals $\textsf{NC}$ ¹. On the other hand, the arithmetic class $\textsf{\#sSC}$ ⁰ contains $\textsf{\#BWBP}$ and is contained in $\textsf{FL}$ , and $\textsf{\#sSC}$ ¹ contains $\textsf{\#NC}$ ¹ and is in $\textsf{SC}$ ². We also investigate some closure properties of the newly defined arithmetic classes.     

Quantum discord in spin systems with dipole–dipole interaction

The behavior of total quantum correlations (discord) in dimers consisting of dipolar-coupled spins 1/2 are studied. We found that the discord $Q=0$ at absolute zero temperature. As the temperature $T$ increases, the quantum correlations in the system increase at first from zero to its maximum and then decrease to zero according to the asymptotic law $T^{-2}$ . It is also shown that in absence of external magnetic field $B$ , the classical correlations $C$ at $T\rightarrow 0$ are, vice versa, maximal. Our calculations predict that in crystalline gypsum $\hbox {CaSO}_{4}\cdot \hbox {2H}_{2}{\hbox {O}}$ the value of natural $(B=0)$ quantum discord between nuclear spins of hydrogen atoms is maximal at the temperature of 0.644  $\upmu $ K, and for 1,2-dichloroethane $\hbox {H}_{2}$ ClC– $\hbox {CH}_{2}{\hbox {Cl}}$ the discord achieves the largest value at $T=0.517~\upmu $ K. In both cases, the discord equals $Q\approx 0.083$  bit/dimer what is $8.3\,\%$ of its upper limit in two-qubit systems. We estimate also that for gypsum at room temperature $Q\sim 10^{-18}$  bit/dimer, and for 1,2-dichloroethane at $T=90$  K the discord is $Q\sim 10^{-17}$  bit per a dimer.     

Gaussian,Lobatto and Radau positive quadrature rules with a prescribed abscissa

For a given $\theta \in (a,b)$ , we investigate the question whether there exists a positive quadrature formula with maximal degree of precision which has the prescribed abscissa $\theta $ plus possibly $a$ and/or $b$ , the endpoints of the interval of integration. This study relies on recent results on the location of roots of quasi-orthogonal polynomials. The above positive quadrature formulae are useful in studying problems in one-sided polynomial $L_1$ approximation.     

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.     

A note on reverse scheduling with maximum lateness objective

The inverse and reverse counterparts of the single-machine scheduling problem $1||L_{\max }$ are studied in [2], in which the complexity classification is provided for various combinations of adjustable parameters (due dates and processing times) and for five different types of norm: $\ell _{1},\ell _{2},\ell _{\infty },\ell _{H}^{\Sigma } $ , and $\ell _{H}^{\max }$ . It appears that the $O(n^{2})$ -time algorithm for the reverse problem with adjustable due dates contains a flaw. In this note, we present the structural properties of the reverse model, establishing a link with the forward scheduling problem with due dates and deadlines. For the four norms $\ell _{1},\ell _{\infty },\ell _{H}^{\Sigma }$ , and $ \ell _{H}^{\max }$ , the complexity results are derived based on the properties of the corresponding forward problems, while the case of the norm $\ell _{2}$ is treated separately. As a by-product, we resolve an open question on the complexity of problem $1||\sum \alpha _{j}T_{j}^{2}$ .     

Interpolation splines minimizing a semi-norm

Using S.L. Sobolev’s method, we construct the interpolation splines minimizing the semi-norm in $K_2(P_2)$ , where $K_2(P_2)$ is the space of functions $\phi $ such that $\phi ^{\prime } $ is absolutely continuous, $\phi ^{\prime \prime } $ belongs to $L_2(0,1)$ and $\int _0^1(\varphi ^{\prime \prime }(x)+\varphi (x))^2dx<\infty $ . Explicit formulas for coefficients of the interpolation splines are obtained. The resulting interpolation spline is exact for the trigonometric functions $\sin x$ and $\cos x$ . Finally, in a few numerical examples the qualities of the defined splines and $D^2$ -splines are compared. Furthermore, the relationship of the defined splines with an optimal quadrature formula is shown.     

SIMUL 3.2: An Econometric Tool for Multidimensional Modelling

Initially developed in the context of ${\tt REGILINK}$ project, ${\tt SIMUL 3.2}$ econometric software is able to estimate and to run large-scale dynamic multi-regional, multi-sectoral models. The package includes a data bank management module, ${\tt GEBANK}$ which performs the usual data import/export functions, and transformations (especially the RAS and the aggregation one), a graphic module, ${\tt GRAPHE}$ , a cartographic module, ${\tt GEOGRA}$ for a “typical use”. For an “atypical use” the package includes ${\tt CHRONO}$ to help for the WDC (Working Days Correction) estimation and ${\tt GNOMBR}$ to replace the floating point arithmetic by a multi-precision one in a program. Although the current package includes a basic estimation’s (OLS) and solving’s (Gauss–Seidel) algorithms, it allows user to implement the equations in their reduced form ${Y_{r,b}=X_{r,b} + \varepsilon}$ and to use alternative econometric equations. ${\tt SIMUL}$ provides results and reports documentation in ASCII and ${\hbox{\LaTeX}}$ formats. The next releases of ${\tt SIMUL}$ should improve the OLS procedure according to the Wilkinson’s criteria, include Hildreth–Lu’s algorithm and comparative statics option. Later, the package should allow other models implementations (Input–Output, VAR etc.). Even if it’s probably outclassed by the major softwares in terms of design and statistic tests sets, ${\tt SIMUL}$ provides freely basic evolutive tools to estimate and run easily and safety some large scale multi-sectoral, multi-regional, econometric models.     

Hyper-Hamiltonian laceability of balanced hypercubes

The balanced hypercube, proposed by Wu and Huang, is a new variation of hypercube. The particular property of the balanced hypercube is that each processor has a backup processor that shares the same neighborhood. A Hamiltonian bipartite graph with bipartition $V_{0}\cup V_{1}$ is said to be Hamiltonian laceable if there is a Hamiltonian path between any two vertices $x\in V_{0}$ and $y\in V_{1}$ . A graph $G$ is hyper-Hamiltonian laceable if it is Hamiltonian laceable and, for any vertex $v\in V_{i}$ , $i\in \{0,1\}$ , there is a Hamiltonian path in G–v between any pair of vertices in $V_{1-i}$ . In this paper, we mainly prove that the balanced hypercube is hyper-Hamiltonian laceable.     

On reducing factorization to the discrete logarithm problem modulo a composite

The discrete logarithm problem modulo a composite??abbreviate it as DLPC??is the following: given a (possibly) composite integer n??? 1 and elements ${a, b \in \mathbb{Z}_n^*}$ , determine an ${x \in \mathbb{N}}$ satisfying a ^x ?=?b if one exists. The question whether integer factoring can be reduced in deterministic polynomial time to the DLPC remains open. In this paper we consider the problem ${{\rm DLPC}_\varepsilon}$ obtained by adding in the DLPC the constraint ${x\le (1-\varepsilon)n}$ , where ${\varepsilon}$ is an arbitrary fixed number, ${0 < \varepsilon\le\frac{1}{2}}$ . We prove that factoring n reduces in deterministic subexponential time to the ${{\rm DLPC}_\varepsilon}$ with ${O_\varepsilon((\ln n)^2)}$ queries for moduli less or equal to n.     

Local Discontinuous Galerkin Methods for One-Dimensional Second Order Fully Nonlinear Elliptic and Parabolic Equations

This paper is concerned with developing accurate and efficient nonstandard discontinuous Galerkin methods for fully nonlinear second order elliptic and parabolic partial differential equations (PDEs) in the case of one spatial dimension. The primary goal of the paper to develop a general framework for constructing high order local discontinuous Galerkin (LDG) methods for approximating viscosity solutions of these fully nonlinear PDEs which are merely continuous functions by definition. In order to capture discontinuities of the first order derivative $u_x$ of the solution $u$ , two independent functions $q^-$ and $q^+$ are introduced to approximate one-sided derivatives of $u$ . Similarly, to capture the discontinuities of the second order derivative $u_{xx}$ , four independent functions $p^{- -}, p^{- +}, p^{+ -}$ , and $p^{+ +}$ are used to approximate one-sided derivatives of $q^-$ and $q^+$ . The proposed LDG framework, which is based on a nonstandard mixed formulation of the underlying PDE, embeds a given fully nonlinear problem into a mostly linear system of equations where the given nonlinear differential operator must be replaced by a numerical operator which allows multiple value inputs of the first and second order derivatives $u_x$ and $u_{xx}$ . An easy to verify set of criteria for constructing “good” numerical operators is also proposed. It consists of consistency and generalized monotonicity. To ensure such a generalized monotonicity property, the crux of the construction is to introduce the numerical moment in the numerical operator, which plays a critical role in the proposed LDG framework. The generalized monotonicity gives the LDG methods the ability to select the viscosity solution among all possible solutions. The proposed framework extends a companion finite difference framework developed by Feng and Lewis (J Comp Appl Math 254:81–98, 2013) and allows for the approximation of fully nonlinear PDEs using high order polynomials and non-uniform meshes. Numerical experiments are also presented to demonstrate the accuracy, efficiency and utility of the proposed LDG methods.     

On the Exact Complexity of Evaluating Quantified k -CNF

We relate the exponential complexities 2 ^s(k)n of $\textsc {$k$-sat}$ and the exponential complexity $2^{s(\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf}))n}$ of $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ (the problem of evaluating quantified formulas of the form $\forall\vec{x} \exists\vec{y} \textsc {F}(\vec {x},\vec{y})$ where F is a 3-cnf in $\vec{x}$ variables and $\vec{y}$ variables) and show that s(∞) (the limit of s(k) as k→∞) is at most $s(\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf}))$ . Therefore, if we assume the Strong Exponential-Time Hypothesis, then there is no algorithm for $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ running in time 2 ^cn with c<1. On the other hand, a nontrivial exponential-time algorithm for $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ would provide a $\textsc {$k$-sat}$ solver with better exponent than all current algorithms for sufficiently large k. We also show several syntactic restrictions of the evaluation problem $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ have nontrivial algorithms, and provide strong evidence that the hardest cases of $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ must have a mixture of clauses of two types: one universally quantified literal and two existentially quantified literals, or only existentially quantified literals. Moreover, the hardest cases must have at least n?o(n) universally quantified variables, and hence only o(n) existentially quantified variables. Our proofs involve the construction of efficient minimally unsatisfiable $\textsc {$k$-cnf}$ s and the application of the Sparsification lemma.     

Developing a modelling tool for density-driven flow in complex hydrogeological structures

Beginning in 1995, the codes $\hbox {d}^{3}\hbox {f}$ (distributed density driven flow) and $\hbox {r}^{3}\hbox {t}$ (radionuclides, reaction, retardation, and transport) for modeling density-driven groundwater flow and nuclide transport using UG toolbox are developed in the framework of several joint projects. During this time, the codes were substantially extended as well as numerically improved, and the development is still ongoing. Now, $\hbox {d}^{3}\hbox {f}$ and $\hbox {r}^{3}\hbox {t}$ are no longer restricted to modeling of porous media, they also may be used for fractured rock. These are powerful tools that are able to handle salt and heat transport, salt concentrations up to saturation and complex hydrogeological structures with high permeability contrasts.     

A new set of generators and a physical interpretation for the SU (3) finite subgroup D(9,1,1;2,1,1)

After 100 years of effort, the classification of all the finite subgroups of $SU(3)$ is yet incomplete. The most recently updated list can be found in Ludl (J Phys A Math Theory 44:255204, 2011), where the structure of the series $(C)$ and $(D)$ of $SU(3)$ -subgroups is studied. We provide a minimal set of generators for one of these groups which has order $162$ . These generators appear up to phase as the image of an irreducible unitary braid group representation issued from the Jones–Kauffman version of $SU(2)$ Chern–Simons theory at level $4$ . In light of these new generators, we study the structure of the group in detail and recover the fact that it is isomorphic to the semidirect product $\mathbb Z _9\times \mathbb Z _3\rtimes S_3$ with respect to conjugation.     

Integrated damping parameter and control design in structural systems for \bf{\mathcal{H}^2} and {\mathcal{H}^{\infty}} specifications

The paper presents a linear matrix inequality (LMI)-based approach for the simultaneous optimal design of output feedback control gains and damping parameters in structural systems with collocated actuators and sensors. The proposed integrated design is based on simplified $\mathcal{H}^2$ and $\mathcal{H}^{\infty}$ norm upper bound calculations for collocated structural systems. Using these upper bound results, the combined design of the damping parameters of the structural system and the output feedback controller to satisfy closed-loop $\mathcal{H}^2$ or $\mathcal{H}^{\infty}$ performance specifications is formulated as an LMI optimization problem with respect to the unknown damping coefficients and feedback gains. Numerical examples motivated from structural and aerospace engineering applications demonstrate the advantages and computational efficiency of the proposed technique for integrated structural and control design. The effectiveness of the proposed integrated design becomes apparent, especially in very large scale structural systems where the use of classical methods for solving Lyapunov and Riccati equations associated with $\mathcal{H}^2$ and $\mathcal{H}^{\infty}$ designs are time-consuming or intractable.     

On the class of λ-statistically convergent difference sequences of fuzzy numbers

In this study, we introduce the sets $\left[ V,\lambda ,p\right] _{\Updelta }^{{\mathcal{F}}},\left[ C,1,p\right] _{\Updelta }^{{\mathcal{F}}}$ and examine their relations with the classes of $ S_{\lambda }\left( \Updelta ,{\mathcal{F}}\right)$ and $ S_{\mu }\left( \Updelta ,{\mathcal{F}}\right)$ of sequences for the sequences $\left( \lambda _{n}\right)$ and $\left( \mu _{n}\right) , 0<p<\infty $ and difference sequences of fuzzy numbers.     

Simple characterization of strict residuated lattices with an involutive negation

We consider property of strict residuated lattices (SRL-algebras) with a new involutive negation $\lnot, $ called here by SRL $_{\lnot }$ -algebras, and give a simple characterization of SRL $_{\lnot }$ -algebras. We also prove a prime filter theorem of SRL $_{\lnot }$ -algebras, from which we conclude that every linearly ordered SRL $_{\lnot }$ -algebra is simple. As a corollary to this fact, we have a well-known result that every SML $_{\lnot }$ -algebra (SBL $_{\lnot }$ -algebra) is a subdirect product of linearly ordered SML $_{\lnot }$ -algebras (SBL $_{\lnot }$ -algebras).