A fast quasi-Newton method for semi-supervised SVM

Due to its wide applicability, semi-supervised learning is an attractive method for using unlabeled data in classification. In this work, we present a semi-supervised support vector classifier that is designed using quasi-Newton method for nonsmooth convex functions. The proposed algorithm is suitable in dealing with very large number of examples and features. Numerical experiments on various benchmark datasets showed that the proposed algorithm is fast and gives improved generalization performance over the existing methods. Further, a non-linear semi-supervised SVM has been proposed based on a multiple label switching scheme. This non-linear semi-supervised SVM is found to converge faster and it is found to improve generalization performance on several benchmark datasets. (C) 2010 Elsevier Ltd. All rights reserved.

Global response sensitivity analysis of uncertain structures

The problem of characterizing global sensitivity indices of structural response when system uncertainties are represented using probabilistic and (or) non-probabilistic modeling frameworks (which include intervals, convex functions, and fuzzy variables) is considered. These indices are characterized in terms of distance measures between a fiducial model in which uncertainties in all the pertinent variables are taken into account and a family of hypothetical models in which uncertainty in one or more selected variables are suppressed. The distance measures considered include various probability distance measures (Hellinger,l(2), and the Kantorovich metrics, and the Kullback-Leibler divergence) and Hausdorff distance measure as applied to intervals and fuzzy variables. Illustrations include studies on an uncertainly parametered building frame carrying uncertain loads. (C) 2015 Elsevier Ltd. All rights reserved.

Efficient algorithms for learning kernels from multiple similarity matrices with general convex loss functions

In this paper we consider the problem of learning an n × n kernel matrix from m(1) similarity matrices under general convex loss. Past research have extensively studied the m = 1 case and have derived several algorithms which require sophisticated techniques like ACCP, SOCP, etc. The existing algorithms do not apply if one uses arbitrary losses and often can not handle m > 1 case. We present several provably convergent iterative algorithms, where each iteration requires either an SVM or a Multiple Kernel Learning (MKL) solver for m > 1 case. One of the major contributions of the paper is to extend the well knownMirror Descent(MD) framework to handle Cartesian product of psd matrices. This novel extension leads to an algorithm, called EMKL, which solves the problem in O(m2 log n 2) iterations; in each iteration one solves an MKL involving m kernels and m eigen-decomposition of n × n matrices. By suitably defining a restriction on the objective function, a faster version of EMKL is proposed, called REKL,which avoids the eigen-decomposition. An alternative to both EMKL and REKL is also suggested which requires only an SVMsolver. Experimental results on real world protein data set involving several similarity matrices illustrate the efficacy of the proposed algorithms.

On some results of A. E. Livingston and coefficient problems for concave univalent functions

We consider functions that map the open unit disc conformally onto the complement of a bounded convex set. We call these functions concave univalent functions. In 1994, Livingston presented a characterization for these functions. In this paper, we observe that there is a minor flaw with this characterization. We obtain certain sharp estimates and the exact set of variability involving Laurent and Taylor coefficients for concave functions. We also present the exact set of variability of the linear combination of certain successive Taylor coefficients of concave functions.

A Convex Optimization Framework for Almost Budget Balanced Allocation of a Divisible Good

We address the problem of allocating a single divisible good to a number of agents. The agents have concave valuation functions parameterized by a scalar type. The agents report only the type. The goal is to find allocatively efficient, strategy proof, nearly budget balanced mechanisms within the Groves class. Near budget balance is attained by returning as much of the received payments as rebates to agents. Two performance criteria are of interest: the maximum ratio of budget surplus to efficient surplus, and the expected budget surplus, within the class of linear rebate functions. The goal is to minimize them. Assuming that the valuation functions are known, we show that both problems reduce to convex optimization problems, where the convex constraint sets are characterized by a continuum of half-plane constraints parameterized by the vector of reported types. We then propose a randomized relaxation of these problems by sampling constraints. The relaxed problem is a linear programming problem (LP). We then identify the number of samples needed for ``near-feasibility'' of the relaxed constraint set. Under some conditions on the valuation function, we show that value of the approximate LP is close to the optimal value. Simulation results show significant improvements of our proposed method over the Vickrey-Clarke-Groves (VCG) mechanism without rebates. In the special case of indivisible goods, the mechanisms in this paper fall back to those proposed by Moulin, by Guo and Conitzer, and by Gujar and Narahari, without any need for randomization. Extension of the proposed mechanisms to situations when the valuation functions are not known to the central planner are also discussed. Note to Practitioners-Our results will be useful in all resource allocation problems that involve gathering of information privately held by strategic users, where the utilities are any concave function of the allocations, and where the resource planner is not interested in maximizing revenue, but in efficient sharing of the resource. Such situations arise quite often in fair sharing of internet resources, fair sharing of funds across departments within the same parent organization, auctioning of public goods, etc. We study methods to achieve near budget balance by first collecting payments according to the celebrated VCG mechanism, and then returning as much of the collected money as rebates. Our focus on linear rebate functions allows for easy implementation. The resulting convex optimization problem is solved via relaxation to a randomized linear programming problem, for which several efficient solvers exist. This relaxation is enabled by constraint sampling. Keeping practitioners in mind, we identify the number of samples that assures a desired level of ``near-feasibility'' with the desired confidence level. Our methodology will occasionally require subsidy from outside the system. We however demonstrate via simulation that, if the mechanism is repeated several times over independent instances, then past surplus can support the subsidy requirements. We also extend our results to situations where the strategic users' utility functions are not known to the allocating entity, a common situation in the context of internet users and other problems.

On concave univalent functions

We consider functions that map the open unit disc conformally onto the complement of an unbounded convex set with opening angle pa, a ? (1, 2], at infinity. In this paper, we show that every such function is close-to-convex of order (a - 1) and is included in the set of univalent functions of bounded boundary rotation. Many interesting consequences of this result are obtained. We also determine the extreme points of the set of concave functions with respect to the linear structure of the Hornich space.

Finite volume evolution Galerkin method for hyperbolic conservation laws with spatially varying flux functions

We present a generalization of the finite volume evolution Galerkin scheme [M. Lukacova-Medvid'ova,J. Saibertov'a, G. Warnecke, Finite volume evolution Galerkin methods for nonlinear hyperbolic systems, J. Comp. Phys. (2002) 183 533-562; M. Luacova-Medvid'ova, K.W. Morton, G. Warnecke, Finite volume evolution Galerkin (FVEG) methods for hyperbolic problems, SIAM J. Sci. Comput. (2004) 26 1-30] for hyperbolic systems with spatially varying flux functions. Our goal is to develop a genuinely multi-dimensional numerical scheme for wave propagation problems in a heterogeneous media. We illustrate our methodology for acoustic waves in a heterogeneous medium but the results can be generalized to more complex systems. The finite volume evolution Galerkin (FVEG) method is a predictor-corrector method combining the finite volume corrector step with the evolutionary predictor step. In order to evolve fluxes along the cell interfaces we use multi-dimensional approximate evolution operator. The latter is constructed using the theory of bicharacteristics under the assumption of spatially dependent wave speeds. To approximate heterogeneous medium a staggered grid approach is used. Several numerical experiments for wave propagation with continuous as well as discontinuous wave speeds confirm the robustness and reliability of the new FVEG scheme.

Dynamics of a dilute sheared inelastic fluid. I. Hydrodynamic modes and velocity correlation functions

The hydrodynamic modes and the velocity autocorrelation functions for a dilute sheared inelastic fluid are analyzed using an expansion in the parameter epsilon=(1-e)(1/2), where e is the coefficient of restitution. It is shown that the hydrodynamic modes for a sheared inelastic fluid are very different from those for an elastic fluid in the long-wave limit, since energy is not a conserved variable when the wavelength of perturbations is larger than the ``conduction length.'' In an inelastic fluid under shear, there are three coupled modes, the mass and the momenta in the plane of shear, which have a decay rate proportional to k(2/3) in the limit k -> 0, if the wave vector has a component along the flow direction. When the wave vector is aligned along the gradient-vorticity plane, we find that the scaling of the growth rate is similar to that for an elastic fluid. The Fourier transforms of the velocity autocorrelation functions are calculated for a steady shear flow correct to leading order in an expansion in epsilon. The time dependence of the autocorrelation function in the long-time limit is obtained by estimating the integral of the Fourier transform over wave number space. It is found that the autocorrelation functions for the velocity in the flow and gradient directions decay proportional to t(-5/2) in two dimensions and t(-15/4) in three dimensions. In the vorticity direction, the decay of the autocorrelation function is proportional to t(-3) in two dimensions and t(-7/2) in three dimensions.

Hybrid stiff-string-polynomial basis functions for vibration analysis of high speed rotating beams

A new finite element is developed for free vibration analysis of high speed rotating beams using basis functions which use a linear combination of the solution of the governing static differential equation of a stiff-string and a cubic polynomial. These new shape functions depend on rotation speed and element position along the beam and account for the centrifugal stiffening effect. The natural frequencies predicted by the proposed element are compared with an element with stiff-string, cubic polynomial and quintic polynomial shape functions. It is found that the new element exhibits superior convergence compared to the other basis functions.

Deep inelastic electroproduction structure functions for polarized and unpolarized proton targets

Following Ioffe's method of QCD sum rules the structure functions F2(x) for deep inelastic ep and en scattering are calculated. Valence u-quark and d-quark distributions are obtained in the range 0.1 less, approximate x <0.4 and compared with data. In the case of polarized targets the structure function g1(x) and the asymmetry Image Full-size image are calculated. The latter is in satisfactory agreement in sign and magnitude with experiments for x in the range 0.1< x < 0.4.

Do H-functions always increase during Violent Relaxation

Recent work on the violent relaxation of collisionless stellar systems has been based on the notion of a wide class of entropy functions. A theorem concerning entropy increase has been proved. We draw attention to some underlying assumptions that have been ignored in the applications of this theorem to stellar dynamical problems. Once these are taken into account, the use of this theorem is at best heuristic. We present a simple counter-example.

Testing threshold functions using implied minterm structure

A geometrical structure called the implied minterm structure (IMS) has been developed from the properties of minterms of a threshold function. The IMS is useful for the manual testing of linear separability of switching functions of up to six variables. This testing is done just by inspection of the plot of the function on the IMS.

Transmission loss analysis of rectangular expansion chamber with arbitrary location of inlet/outlet by means of Green's functions

Transmission loss of a rectangular expansion chamber, the inlet and outlet of which are situated at arbitrary locations of the chamber, i.e., the side wall or the face of the chamber, are analyzed here based on the Green's function of a rectangular cavity with homogeneous boundary conditions. The rectangular chamber Green's function is expressed in terms of a finite number of rigid rectangular cavity mode shapes. The inlet and outlet ports are modeled as uniform velocity pistons. If the size of the piston is small compared to wavelength, then the plane wave excitation is a valid assumption. The velocity potential inside the chamber is expressed by superimposing the velocity potentials of two different configurations. The first configuration is a piston source at the inlet port and a rigid termination at the outlet, and the second one is a piston at the outlet with a rigid termination at the inlet. Pressure inside the chamber is derived from velocity potentials using linear momentum equation. The average pressure acting on the pistons at the inlet and outlet locations is estimated by integrating the acoustic pressure over the piston area in the two constituent configurations. The transfer matrix is derived from the average pressure values and thence the transmission loss is calculated. The results are verified against those in the literature where use has been made of modal expansions and also numerical models (FEM fluid). The transfer matrix formulation for yielding wall rectangular chambers has been derived incorporating the structural–acoustic coupling. Parametric studies are conducted for different inlet and outlet configurations, and the various phenomena occurring in the TL curves that cannot be explained by the classical plane wave theory, are discussed.

Learning Optimal Discriminant Functions through a Cooperative Game of Automata

The problem of learning correct decision rules to minimize the probability of misclassification is a long-standing problem of supervised learning in pattern recognition. The problem of learning such optimal discriminant functions is considered for the class of problems where the statistical properties of the pattern classes are completely unknown. The problem is posed as a game with common payoff played by a team of mutually cooperating learning automata. This essentially results in a probabilistic search through the space of classifiers. The approach is inherently capable of learning discriminant functions that are nonlinear in their parameters also. A learning algorithm is presented for the team and convergence is established. It is proved that the team can obtain the optimal classifier to an arbitrary approximation. Simulation results with a few examples are presented where the team learns the optimal classifier.

Application of Haar functions for transmission line and transformer differential protection

The development of algorithms, based on Haar functions, for extracting the desired frequency components from transient power-system relaying signals is presented. The applications of these algorithms to impedance detection in transmission line protection and to harmonic restraint in transformer differential protection are discussed. For transmission line protection, three modes of application of the Haar algorithms are described: a full-cycle window algorithm, an approximate full-cycle window algorithm, and a half-cycle window algorithm. For power transformer differential protection, the combined second and fifth harmonic magnitude of the differential current is compared with that of fundamental to arrive at a trip decision. The proposed line protection algorithms are evaluated, under different fault conditions, using realistic relaying signals obtained from transient analysis conducted on a model 400 kV, 3-phase system. The transformer differential protection algorithms are also evaluated using a variety of simulated inrush and internal fault signals.