Efficient search for statistically significant dependency rules in binary data

Analyzing statistical dependencies is a fundamental problem in all empirical science. Dependencies help us understand causes and effects, create new scientific theories, and invent cures to problems. Nowadays, large amounts of data is available, but efficient computational tools for analyzing the data are missing. In this research, we develop efficient algorithms for a commonly occurring search problem - searching for the statistically most significant dependency rules in binary data. We consider dependency rules of the form X->A or X->not A, where X is a set of positive-valued attributes and A is a single attribute. Such rules describe which factors either increase or decrease the probability of the consequent A. A classical example are genetic and environmental factors, which can either cause or prevent a disease. The emphasis in this research is that the discovered dependencies should be genuine - i.e. they should also hold in future data. This is an important distinction from the traditional association rules, which - in spite of their name and a similar appearance to dependency rules - do not necessarily represent statistical dependencies at all or represent only spurious connections, which occur by chance. Therefore, the principal objective is to search for the rules with statistical significance measures. Another important objective is to search for only non-redundant rules, which express the real causes of dependence, without any occasional extra factors. The extra factors do not add any new information on the dependence, but can only blur it and make it less accurate in future data. The problem is computationally very demanding, because the number of all possible rules increases exponentially with the number of attributes. In addition, neither the statistical dependency nor the statistical significance are monotonic properties, which means that the traditional pruning techniques do not work. As a solution, we first derive the mathematical basis for pruning the search space with any well-behaving statistical significance measures. The mathematical theory is complemented by a new algorithmic invention, which enables an efficient search without any heuristic restrictions. The resulting algorithm can be used to search for both positive and negative dependencies with any commonly used statistical measures, like Fisher's exact test, the chi-squared measure, mutual information, and z scores. According to our experiments, the algorithm is well-scalable, especially with Fisher's exact test. It can easily handle even the densest data sets with 10000-20000 attributes. Still, the results are globally optimal, which is a remarkable improvement over the existing solutions. In practice, this means that the user does not have to worry whether the dependencies hold in future data or if the data still contains better, but undiscovered dependencies.

On the determination of energy eigenvalues and coupling strengths using duality

The Shifman-Vainshtein-Zakharov method of determining the eigenvalues and coupling strengths, from the operator product expansion, for the current correlation functions is studied in the nonrelativistic context, using the semiclassical expansion. The relationship between the low-lying eigenvalues, and the leading corrections to the imaginary-time Green function is elucidated by comparing systems which have almost identical spectra. In the case of an anharmonic oscillator it is found that with the procedure stated in the paper, that inclusion of more terms to the asymptotic expansion does not show any simple trend towards convergence to the exact values. Generalization to higher partial waves is given. In particular for the P-level of the oscillator, the procedure gives poorer results than for the S-level, although the ratio of the two comes out much better.

Finite element analysis of laminated anisotropic beams of bimodulus materials

This paper presents finite element analysis of laminated anisotropic beams of bimodulus materials. The finite element has 16 d.o.f. and uses the displacement field in terms of first order Hermite interpolation polynomials. As the neutral axis position may change from point to point along the length of the beam, an iterative procedure is employed to determine the location of zero strain points along the length. Using this element some problems of laminated beams of bimodulus materials are solved for concentrated loads/moments perpendicular and parallel to the layering planes as well as combined loads.

Systematic search for optical Barker codes with minimum length

A method that yields optical Barker codes of smallest known lengths for given discrimination is described.

Location of concentrators in a computer communication network: a stochastic automation search method

The following problem is considered. Given the locations of the Central Processing Unit (ar;the terminals which have to communicate with it, to determine the number and locations of the concentrators and to assign the terminals to the concentrators in such a way that the total cost is minimized. There is alao a fixed cost associated with each concentrator. There is ail upper limit to the number of terminals which can be connected to a concentrator. The terminals can be connected directly to the CPU also In this paper it is assumed that the concentrators can bo located anywhere in the area A containing the CPU and the terminals. Then this becomes a multimodal optimization problem. In the proposed algorithm a stochastic automaton is used as a search device to locate the minimum of the multimodal cost function . The proposed algorithm involves the following. The area A containing the CPU and the terminals is divided into an arbitrary number of regions (say K). An approximate value for the number of concentrators is assumed (say m). The optimum number is determined by iteration later The m concentrators can be assigned to the K regions in (mk) ways (m > K) or (km) ways (K>m).(All possible assignments are feasible, i.e. a region can contain 0,1,…, to concentrators). Each possible assignment is assumed to represent a state of the stochastic variable structure automaton. To start with, all the states are assigned equal probabilities. At each stage of the search the automaton visits a state according to the current probability distribution. At each visit the automaton selects a 'point' inside that state with uniform probability. The cost associated with that point is calculated and the average cost of that state is updated. Then the probabilities of all the states are updated. The probabilities are taken to bo inversely proportional to the average cost of the states After a certain number of searches the search probabilities become stationary and the automaton visits a particular state again and again. Then the automaton is said to have converged to that state Then by conducting a local gradient search within that state the exact locations of the concentrators are determined This algorithm was applied to a set of test problems and the results were compared with those given by Cooper's (1964, 1967) EAC algorithm and on the average it was found that the proposed algorithm performs better.

Nonlinear mode coupling of surface acoustic waves on an isotropic solid

The nonlinear mode coupling between two co-directional quasi-harmonic Rayleigh surface waves on an isotropic solid is analysed using the method of multiple scales. This procedure yields a system of six semi-linear hyperbolic partial differential equations with the same principal part governing the slow variations in the (complex) amplitudes of the two fundamental, the two second harmonic and the two combination frequency waves at the second stage of the perturbation expansion. A numerical solution of these equations for excitation by monochromatic signals at two arbitrary frequencies, indicates that there is a continuous transfer of energy back and forth among the fundamental, second harmonic and combination frequency waves due to mode coupling. The mode coupling tends to be more pronounced as the frequencies of the interacting waves approach each other.

Dessy : desktop search and synchronization

Current smartphones have a storage capacity of several gigabytes. More and more information is stored on mobile devices. To meet the challenge of information organization, we turn to desktop search. Users often possess multiple devices, and synchronize (subsets of) information between them. This makes file synchronization more important. This thesis presents Dessy, a desktop search and synchronization framework for mobile devices. Dessy uses desktop search techniques, such as indexing, query and index term stemming, and search relevance ranking. Dessy finds files by their content, metadata, and context information. For example, PDF files may be found by their author, subject, title, or text. EXIF data of JPEG files may be used in finding them. User–defined tags can be added to files to organize and retrieve them later. Retrieved files are ranked according to their relevance to the search query. The Dessy prototype uses the BM25 ranking function, used widely in information retrieval. Dessy provides an interface for locating files for both users and applications. Dessy is closely integrated with the Syxaw file synchronizer, which provides efficient file and metadata synchronization, optimizing network usage. Dessy supports synchronization of search results, individual files, and directory trees. It allows finding and synchronizing files that reside on remote computers, or the Internet. Dessy is designed to solve the problem of efficient mobile desktop search and synchronization, also supporting remote and Internet search. Remote searches may be carried out offline using a downloaded index, or while connected to the remote machine on a weak network. To secure user data, transmissions between the Dessy client and server are encrypted using symmetric encryption. Symmetric encryption keys are exchanged with RSA key exchange. Dessy emphasizes extensibility. Also the cryptography can be extended. Users may tag their files with context tags and control custom file metadata. Adding new indexed file types, metadata fields, ranking methods, and index types is easy. Finding files is done with virtual directories, which are views into the user’s files, browseable by regular file managers. On mobile devices, the Dessy GUI provides easy access to the search and synchronization system. This thesis includes results of Dessy synchronization and search experiments, including power usage measurements. Finally, Dessy has been designed with mobility and device constraints in mind. It requires only MIDP 2.0 Mobile Java with FileConnection support, and Java 1.5 on desktop machines.

Approximate solution for the redistribution of impurities during second oxidation

The impurity profile for the second oxidation, used in MOST fabrication, has been obtained by Margalit et al. [1]. The disadvantage of this technique is that the accuracy of their solution is directly dependent on the computer time. In this article, an analytical solution is presented using the approximation of linearizing the second oxidation procedure.

Mammalian brain plasma membranes: Isolation, enzymatic, and chemical characterization

Two variants of a simplified procedure for the isolation of plasma membrane fractions from monkey and rat brains, are described. The preparations show marked enrichments in the marker enzymes, (Na+-K+) adenosine triphosphatase, acetylcholinesterase, 5′-nucleotidase and adenylate cyclase. Lipid analysis and a protein electrophoretic pattern are presented. An enzymatic check has been made to assess for contamination by other cellular organelles. The amino acid composition of brain membrane proteins show a resemblance to the reported composition of erythrocyte ghost proteins but differ from myelin proteins.

Optimal adaptive sequential spatial sampling of soil using pair-copulas

A spatial sampling design that uses pair-copulas is presented that aims to reduce prediction uncertainty by selecting additional sampling locations based on both the spatial configuration of existing locations and the values of the observations at those locations. The novelty of the approach arises in the use of pair-copulas to estimate uncertainty at unsampled locations. Spatial pair-copulas are able to more accurately capture spatial dependence compared to other types of spatial copula models. Additionally, unlike traditional kriging variance, uncertainty estimates from the pair-copula account for influence from measurement values and not just the configuration of observations. This feature is beneficial, for example, for more accurate identification of soil contamination zones where high contamination measurements are located near measurements of varying contamination. The proposed design methodology is applied to a soil contamination example from the Swiss Jura region. A partial redesign of the original sampling configuration demonstrates the potential of the proposed methodology.

Standardization efforts: The relationship between knowledge dimensions, search processes and innovation outcomes

We explore how a standardization effort (i.e., when a firm pursues standards to further innovation) involves different search processes for knowledge and innovation outcomes. Using an inductive case study of Vanke, a leading Chinese property developer, we show how varying degrees of knowledge complexity and codification combine to produce a typology of four types of search process: active, integrative, decentralized and passive, resulting in four types of innovation outcome: modular, radical, incremental and architectural. We argue that when the standardization effort in a firm involves highly codified knowledge, incremental and architectural innovation outcomes are fostered, while modular and radical innovations are hindered. We discuss how standardization efforts can result in a second-order innovation capability, and conclude by calling for comparative research in other settings to understand how standardization efforts can be suited to different types of search process in different industry contexts.

An Optimal Mechanism for Sponsored Search Auctions on the Web and Comparison With Other Mechanisms

In this paper, we first describe a framework to model the sponsored search auction on the web as a mechanism design problem. Using this framework, we describe two well-known mechanisms for sponsored search auction-Generalized Second Price (GSP) and Vickrey-Clarke-Groves (VCG). We then derive a new mechanism for sponsored search auction which we call optimal (OPT) mechanism. The OPT mechanism maximizes the search engine's expected revenue, while achieving Bayesian incentive compatibility and individual rationality of the advertisers. We then undertake a detailed comparative study of the mechanisms GSP, VCG, and OPT. We compute and compare the expected revenue earned by the search engine under the three mechanisms when the advertisers are symmetric and some special conditions are satisfied. We also compare the three mechanisms in terms of incentive compatibility, individual rationality, and computational complexity. Note to Practitioners-The advertiser-supported web site is one of the successful business models in the emerging web landscape. When an Internet user enters a keyword (i.e., a search phrase) into a search engine, the user gets back a page with results, containing the links most relevant to the query and also sponsored links, (also called paid advertisement links). When a sponsored link is clicked, the user is directed to the corresponding advertiser's web page. The advertiser pays the search engine in some appropriate manner for sending the user to its web page. Against every search performed by any user on any keyword, the search engine faces the problem of matching a set of advertisers to the sponsored slots. In addition, the search engine also needs to decide on a price to be charged to each advertiser. Due to increasing demands for Internet advertising space, most search engines currently use auction mechanisms for this purpose. These are called sponsored search auctions. A significant percentage of the revenue of Internet giants such as Google, Yahoo!, MSN, etc., comes from sponsored search auctions. In this paper, we study two auction mechanisms, GSP and VCG, which are quite popular in the sponsored auction context, and pursue the objective of designing a mechanism that is superior to these two mechanisms. In particular, we propose a new mechanism which we call the OPT mechanism. This mechanism maximizes the search engine's expected revenue subject to achieving Bayesian incentive compatibility and individual rationality. Bayesian incentive compatibility guarantees that it is optimal for each advertiser to bid his/her true value provided that all other agents also bid their respective true values. Individual rationality ensures that the agents participate voluntarily in the auction since they are assured of gaining a non-negative payoff by doing so.

Star Camera Calibration Combined with Independent Spacecraft Attitude Determination

A methodology for determining spacecraft attitude and autonomously calibrating star camera, both independent of each other, is presented in this paper. Unlike most of the attitude determination algorithms where attitude of the satellite depend on the camera calibrating parameters (like principal point offset, focal length etc.), the proposed method has the advantage of computing spacecraft attitude independently of camera calibrating parameters except lens distortion. In the proposed method both attitude estimation and star camera calibration is done together independent of each other by directly utilizing the star coordinate in image plane and corresponding star vector in inertial coordinate frame. Satellite attitude, camera principal point offset, focal length (in pixel), lens distortion coefficient are found by a simple two step method. In the first step, all parameters (except lens distortion) are estimated using a closed-form solution based on a distortion free camera model. In the second step lens distortion coefficient is estimated by linear least squares method using the solution of the first step to be used in the camera model that incorporates distortion. These steps are applied in an iterative manner to refine the estimated parameters. The whole procedure is faster enough for onboard implementation.

Scaling for binary liquid systems and ferromagnets under pressure

Scaling relations between the critical indices are derived for two similar systems exhibiting λ lines: binary liquid systems and ferromagnets under pressure. In addition to the usual scaling relations, this procedure gives information about other weakly divergent quantities like isothermal compressibility and thermal expansion. Suggestions for more detailed investigations are made.