共查询到20条相似文献,搜索用时 46 毫秒
1.
Yu-Chieh Wu 《Knowledge and Information Systems》2014,39(2):305-328
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. 相似文献
2.
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. 相似文献
3.
Carmen Chiri?? 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2012,16(6):979-987
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. 相似文献
4.
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. 相似文献
5.
The parallel complexity class $\textsf{NC}$ 1 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}$ 1 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}$ 1. We also consider polynomial-degree restrictions of $\textsf{SC}$ i , denoted $\textsf{sSC}$ i , and show that the Boolean class $\textsf{sSC}$ 1 is sandwiched between $\textsf{NC}$ 1 and $\textsf{L}$ , whereas $\textsf{sSC}$ 0 equals $\textsf{NC}$ 1. On the other hand, the arithmetic class $\textsf{\#sSC}$ 0 contains $\textsf{\#BWBP}$ and is contained in $\textsf{FL}$ , and $\textsf{\#sSC}$ 1 contains $\textsf{\#NC}$ 1 and is in $\textsf{SC}$ 2. We also investigate some closure properties of the newly defined arithmetic classes. 相似文献
6.
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. 相似文献
7.
Bernhard Beckermann Jorge Bustamante Reinaldo Martínez-Cruz José M. Quesada 《Calcolo》2014,51(2):319-328
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. 相似文献
8.
Jiří Močkoř 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2014,18(5):839-847
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. 相似文献
9.
S. S. Li P. Brucker C. T. Ng T. C. E. Cheng N. V. Shakhlevich J. J. Yuan 《Journal of Scheduling》2013,16(4):417-422
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}$ . 相似文献
10.
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. 相似文献
11.
Rodolphe Buda 《Computational Economics》2013,41(4):517-524
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. 相似文献
12.
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. 相似文献
13.
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. 相似文献
14.
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. 相似文献
15.
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. 相似文献
16.
Anke Schneider Klaus-Peter Kröhn Anne Püschel 《Computing and Visualization in Science》2012,15(4):163-168
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. 相似文献
17.
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. 相似文献
18.
Javad Mohammadpour Velni Mona Meisami-Azad Karolos M. Grigoriadis 《Structural and Multidisciplinary Optimization》2009,38(4):377-387
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. 相似文献
19.
Hifsi Altinok Rifat ?olak Yavuz Altin 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2012,16(6):1029-1034
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. 相似文献
20.
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). 相似文献