OpenRaiser/Intern-Atlas huggingface dataset:
Automated Defect Localization via Low Rank Plus Outlier Modeling of Propagating Wavefield Data
Venue: arXiv cs.CV 2013
Year: 2013

This work proposes an agnostic inference strategy for material diagnostics, conceived within the context of laser-based non-destructive evaluation methods, which extract information about structural anomalies from the analysis of acoustic wavefields measured on the structure's surface by means of a scanning laser interferometer. The proposed approach couples spatiotemporal windowing with low rank plus outlier modeling, to identify a priori unknown deviations in the propagating wavefields caused by material inhomogeneities or defects, using virtually no knowledge of the structural and material properties of the medium. This characteristic makes the approach particularly suitable for diagnostics scenarios where the mechanical and material models are complex, unknown, or unreliable. We demonstrate our approach in a simulated environment using benchmark point and line defect localization problems based on propagating flexural waves in a thin plate.
Good Debt or Bad Debt: Detecting Semantic Orientations in Economic Texts
Venue: arXiv cs.CL 2013
Year: 2013

The use of robo-readers to analyze news texts is an emerging technology trend in computational finance. In recent research, a substantial effort has been invested to develop sophisticated financial polarity-lexicons that can be used to investigate how financial sentiments relate to future company performance. However, based on experience from other fields, where sentiment analysis is commonly applied, it is well-known that the overall semantic orientation of a sentence may differ from the prior polarity of individual words. The objective of this article is to investigate how semantic orientations can be better detected in financial and economic news by accommodating the overall phrase-structure information and domain-specific use of language. Our three main contributions are: (1) establishment of a human-annotated finance phrase-bank, which can be used as benchmark for training and evaluating alternative models; (2) presentation of a technique to enhance financial lexicons with attributes that help to identify expected direction of events that affect overall sentiment; (3) development of a linearized phrase-structure model for detecting contextual semantic orientations in financial and economic news texts. The relevance of the newly added lexicon features and the benefit of using the proposed learning-algorithm are demonstrated in a comparative study against previously used general sentiment models as well as the popular word frequency models used in recent financial studies. The proposed framework is parsimonious and avoids the explosion in feature-space caused by the use of conventional n-gram features.
Approaching Gaussian Relay Network Capacity in the High SNR Regime: End-to-End Lattice Codes
Venue: arXiv cs.IT 2013
Year: 2013

We present a natural and low-complexity technique for achieving the capacity of the Gaussian relay network in the high SNR regime. Specifically, we propose the use of end-to-end structured lattice codes with the amplify-and-forward strategy, where the source uses a nested lattice code to encode the messages and the destination decodes the messages by lattice decoding. All intermediate relays simply amplify and forward the received signals over the network to the destination. We show that the end-to-end lattice-coded amplify-and-forward scheme approaches the capacity of the layered Gaussian relay network in the high SNR regime. Next, we extend our scheme to non-layered Gaussian relay networks under the amplify-and-forward scheme, which can be viewed as a Gaussian intersymbol interference (ISI) channel. Compared with other schemes, our approach is significantly simpler and requires only the end-to-end design of the lattice precoding and decoding. It does not require any knowledge of the network topology or the individual channel gains.
Optimal Recombination in Genetic Algorithms
Venue: arXiv cs.NE 2013
Year: 2013

This paper surveys results on complexity of the optimal recombination problem (ORP), which consists in finding the best possible offspring as a result of a recombination operator in a genetic algorithm, given two parent solutions. We consider efficient reductions of the ORPs, allowing to establish polynomial solvability or NP-hardness of the ORPs, as well as direct proofs of hardness results.
The Random Coding Bound Is Tight for the Average Linear Code or Lattice
Venue: arXiv cs.IT 2013
Year: 2013

In 1973, Gallager proved that the random-coding bound is exponentially tight for the random code ensemble at all rates, even below expurgation. This result explained that the random-coding exponent does not achieve the expurgation exponent due to the properties of the random ensemble, irrespective of the utilized bounding technique. It has been conjectured that this same behavior holds true for a random ensemble of linear codes. This conjecture is proved in this paper. Additionally, it is shown that this property extends to Poltyrev's random-coding exponent for a random ensemble of lattices.
Efficient Range Reporting of Convex Hull
Venue: arXiv cs.CG 2013
Year: 2013

We consider the problem of reporting convex hull points in an orthogonal range query in two dimensions. Formally, let $P$ be a set of $n$ points in $\mathbb{R}^{2}$. A point lies on the convex hull of a point set $S$ if it lies on the boundary of the minimum convex polygon formed by $S$. In this paper, we are interested in finding the points that lie on the boundary of the convex hull of the points in $P$ that also fall with in an orthogonal range$[x_{lt},x_{rt}]\times{}[y_b, y_t]$. We propose a $O(n \log^{2} n) $ space data structure that can support reporting points on a convex hull inside an orthogonal range query, in time $O(\log^{3} n + h)$. Here $h$ is the size of the output. This work improves the result of (Brass et al. 2013) \cite{brass} that builds a data structure that uses $O(n \log^{2} n)$ space and has a $O(\log^{5} n + h)$ query time. Additionally, we show that our data structure can be modified slightly to solve other related problems. For instance, for counting the number of points on the convex hull in an orthogonal query rectangle, we propose an $O(n \log^{2}n)$ space data structure that can be queried upon in $O(\log^{3} n)$ time. We also propose a $O(n \log^{2} n) $ space data structure that can compute the $area$ and $perimeter$ of the convex hull inside an orthogonal range query in $O(\log^{3} n$) time.
On the Mailbox Problem
Venue: arXiv cs.DC 2013
Year: 2013

The Mailbox Problem was described and solved by Aguilera, Gafni, and Lamport in their 2010 DC paper with an algorithm that uses two flag registers that carry 14 values each. An interesting problem that they ask is whether there is a mailbox algorithm with smaller flag values. We give a positive answer by describing a mailbox algorithm with 6 and 4 values in the two flag registers.
Understanding Humans' Strategies in Maze Solving
Venue: arXiv cs.CV 2013
Year: 2013

Navigating through a visual maze relies on the strategic use of eye movements to select and identify the route. When navigating the maze, there are trade-offs between exploring to the environment and relying on memory. This study examined strategies used to navigating through novel and familiar mazes that were viewed from above and traversed by a mouse cursor. Eye and mouse movements revealed two modes that almost never occurred concurrently: exploration and guidance. Analyses showed that people learned mazes and were able to devise and carry out complex, multi-faceted strategies that traded-off visual exploration against active motor performance. These strategies took into account available visual information, memory, confidence, the estimated cost in time for exploration, and idiosyncratic tolerance for error. Understanding the strategies humans used for maze solving is valuable for applications in cognitive neuroscience as well as in AI, robotics and human-robot interactions.
An Information Theoretic Measure of Judea Pearl's Identifiability and Causal Influence
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we define a new information theoretic measure that we call the "uprooted information". We show that a necessary and sufficient condition for a probability $P(s|do(t))$ to be "identifiable" (in the sense of Pearl) in a graph $G$ is that its uprooted information be non-negative for all models of the graph $G$. In this paper, we also give a new algorithm for deciding, for a Bayesian net that is semi-Markovian, whether a probability $P(s|do(t))$ is identifiable, and, if it is identifiable, for expressing it without allusions to confounding variables. Our algorithm is closely based on a previous algorithm by Tian and Pearl, but seems to correct a small flaw in theirs. In this paper, we also find a {\it necessary and sufficient graphical condition} for a probability $P(s|do(t))$ to be identifiable when $t$ is a singleton set. So far, in the prior literature, it appears that only a {\it sufficient graphical condition} has been given for this. By "graphical" we mean that it is directly based on Judea Pearl's 3 rules of do-calculus.
Is there currently a scientific revolution in scientometrics?
Venue: arXiv cs.DL 2013
Year: 2013

The author of this letter to the editor would like to set forth the argument that scientometrics is currently in a phase in which a taxonomic change, and hence a revolution, is taking place. One of the key terms in scientometrics is scientific impact which nowadays is understood to mean not only the impact on science but the impact on every area of society.
Digital Watermarking for Image AuthenticationBased on Combined DCT, DWT and SVD Transformation
Venue: arXiv cs.MM 2013
Year: 2013

This paper presents a hybrid digital image watermarking based on Discrete Wavelet Transform (DWT), Discrete Cosine Transform (DCT) and Singular Value Decomposition (SVD) in a zigzag order. From DWT we choose the high band to embed the watermark that facilities to add more information, gives more invisibility and robustness against some attacks. Such as geometric attack. Zigzag method is applied to map DCT coefficients into four quadrants that represent low, mid and high bands. Finally, SVD is applied to each quadrant.
Computability of Probability Distributions and Characteristic Functions
Venue: arXiv cs.CC 2013
Year: 2013

As a part of our works on effective properties of probability distributions, we deal with the corresponding characteristic functions. A sequence of probability distributions is computable if and only if the corresponding sequence of characteristic functions is computable. As for the onvergence problem, the effectivized Glivenko's theorem holds. Effectivizations of Bochner's theorem and de Moivre-Laplace central limit theorem are also proved.
Relative Performance of a Multi-level Cache with Last-Level Cache Replacement: An Analytic Review
Venue: arXiv cs.AR 2013
Year: 2013

Current day processors employ multi-level cache hierarchy with one or two levels of private caches and a shared last-level cache (LLC). An efficient cache replacement policy at LLC is essential for reducing the off-chip memory transfer as well as conflict for memory bandwidth. Cache replacement techniques for inclusive LLCs may not be efficient for multilevel cache as it can be shared by enormous applications with varying access behavior, running simultaneously. One application may dominate another by flooding of cache requests and evicting the useful data of the other application. From the performance point of view, an exclusive LLC make the replacement policies more demanding, as compared to an inclusive LLC. This paper analyzes some of the existing replacement techniques on the LLC with their performance assessment.
On the $k$-error linear complexity of binary sequences derived from polynomial quotients
Venue: arXiv cs.CR 2013
Year: 2013

We investigate the $k$-error linear complexity of $p^2$-periodic binary sequences defined from the polynomial quotients (including the well-studied Fermat quotients), which is defined by $$ q_{p,w}(u)\equiv \frac{u^w-u^{wp}}{p} \bmod p ~ \mathrm{with} 0 \le q_{p,w}(u) \le p-1, ~u\ge 0, $$ where $p$ is an odd prime and $1\le w<p$. Indeed, first for all integers $k$, we determine exact values of the $k$-error linear complexity over the finite field $\F_2$ for these binary sequences under the assumption of f2 being a primitive root modulo $p^2$, and then we determine their $k$-error linear complexity over the finite field $\F_p$ for either $0\le k<p$ when $w=1$ or $0\le k<p-1$ when $2\le w<p$. Theoretical results obtained indicate that such sequences possess `good' error linear complexity.
On Complexities of Minus Domination
Venue: arXiv cs.DM 2013
Year: 2013

A function f: V \rightarrow \{-1,0,1\} is a minus-domination function of a graph G=(V,E) if the values over the vertices in each closed neighborhood sum to a positive number. The weight of f is the sum of f(x) over all vertices x \in V. The minus-domination number γ^{-}(G) is the minimum weight over all minus-domination functions. The size of a minus domination is the number of vertices that are assigned 1. In this paper we show that the minus-domination problem is fixed-parameter tractable for d-degenerate graphs when parameterized by the size of the minus-dominating set and by d. The minus-domination problem is polynomial for graphs of bounded rankwidth and for strongly chordal graphs. It is NP-complete for splitgraphs. Unless P=NP there is no fixed-parameter algorithm for minus-domination. 79,1 5%
Composing a Publication List for Individual Researcher Assessment by Merging Information from Different Sources
Venue: arXiv cs.DL 2013
Year: 2013

Citation and publication profiles are gaining importance for the evaluation of top researchers when it comes to the appropriation of funding for excellence programs or career promotion judgments. Indicators like the Normalized Mean Citation Rate, the hindex or other distinguishing measures are increasingly used to picture the characteristics of individual scholars. Using bibliometric techniques for individual assessment is known to be particularly delicate, as the chance of errors being averaged away becomes smaller whereas a minor incompleteness can have a significant influence on the evaluation outcome. The quality of the data becomes as such crucial to the legitimacy of the methods used.
Impact Vitality - A Measure for Excellent Scientists
Venue: arXiv cs.DL 2013
Year: 2013

In many countries and at European level, research policy increasingly focuses on 'excellent' researchers. The concept of excellence however is complex and multidimensional. For individual scholars it involves talents for innovative knowledge creation and successful transmission to peers, as well as management capacities. Excellence is also a comparative concept, implying the ability to surpass others [TIJSSEN, 2003]. Grants are in general awarded based on assessments by expert committees. While peer review is a widely accepted practice, it nevertheless is also subject to criticism. At higher aggregation levels, peer assessments are often supported by quantitative measures. At individual level, most of these measures are much less appropriate and there is a need for new, dedicated indicators.
Quality related publication categories in social sciences and humanities, based on a university's peer review assessments
Venue: arXiv cs.DL 2013
Year: 2013

Bibliometric analysis has firmly conquered its place as an instrument for evaluation and international comparison of performance levels. Consequently, differences in coverage by standard bibliometric databases installed a dichotomy between on the one hand the well covered 'exact' sciences, and on the other hand most of the social sciences and humanities with a more limited coverage (Nederhof, 2006). Also the latter domains need to be able to soundly demonstrate their level of performance and claim or legitimate funding accordingly. An important part of the output volume in social sciences appears as books, book chapters and national literature (Hicks, 2004). To proceed from publication data to performance measurement, quantitative publication counts need to be combined with qualitative information, for example from peer assessment or validation (European Expert Group on Assessment of University-Based Research, 2010), to identify those categories that represent research quality as perceived by peers. An accurate focus is crucial in order to stimulate, recognize and reward high quality achievements only. This paper demonstrates how such a selection of publication categories can be based on correlations with peer judgments. It is also illustrated that the selection should be sufficiently precise, to avoid subcategories negatively correlated with peer judgments. The findings indicate that, also in social sciences and humanities, publications in journals with an international referee system are the most important category for evaluating quality. Book chapters with international referee system and contributions in international conference proceedings follow them.
Optimal Top-k Document Retrieval
Venue: arXiv cs.DS 2013
Year: 2013

Let $\mathcal{D}$ be a collection of $D$ documents, which are strings over an alphabet of size $σ$, of total length $n$. We describe a data structure that uses linear space and and reports $k$ most relevant documents that contain a query pattern $P$, which is a string of length $p$, in time $O(p/\log_σn+k)$, which is optimal in the RAM model in the general case where $\lg D = Θ(\log n)$, and involves a novel RAM-optimal suffix tree search. Our construction supports an ample set of important relevance measures... [clip] When $\lg D = o(\log n)$, we show how to reduce the space of the data structure from $O(n\log n)$ to $O(n(\logσ+\log D+\log\log n))$ bits... [clip] We also consider the dynamic scenario, where documents can be inserted and deleted from the collection. We obtain linear space and query time $O(p(\log\log n)^2/\log_σn+\log n + k\log\log k)$, whereas insertions and deletions require $O(\log^{1+ε} n)$ time per symbol, for any constant $ε>0$. Finally, we consider an extended static scenario where an extra parameter $par(P,d)$ is defined, and the query must retrieve only documents $d$ such that $par(P,d)\in [τ_1,τ_2]$, where this range is specified at query time. We solve these queries using linear space and $O(p/\log_σn + \log^{1+ε} n + k\log^εn)$ time, for any constant $ε>0$. Our technique is to translate these top-$k$ problems into multidimensional geometric search problems. As an additional bonus, we describe some improvements to those problems.
A gradient descent technique coupled with a dynamic simulation to determine the near optimum orientation of floor plan designs
Venue: arXiv cs.CE 2013
Year: 2013

A prototype tool to assist architects during the early design stage of floor plans has been developed, consisting of an Evolutionary Program for the Space Allocation Problem (EPSAP), which generates sets of floor plan alternatives according to the architect's preferences; and a Floor Plan Performance Optimization Program (FPOP), which optimizes the selected solutions according to thermal performance criteria. The design variables subject to optimization are window position and size, overhangs, fins, wall positioning, and building orientation. A procedure using a transformation operator with gradient descent, such as behavior, coupled with a dynamic simulation engine was developed for the thermal evaluation and optimization process. However, the need to evaluate all possible alternatives regarding designing variables being used during the optimization process leads to an intensive use of thermal simulation, which dramatically increases the simulation time, rendering it unpractical. An alternative approach is a smart optimization approach, which utilizes an oriented and adaptive search technique to efficiently find the near optimum solution. This paper presents the search methodology for the building orientation of floor plan designs, and the corresponding efficiency and effectiveness indicators. The calculations are based on 100 floor plan designs generated by EPSAP. All floor plans have the same design program, location, and weather data, changing only their geometry. Dynamic simulation of buildings was effectively used together with the optimization procedure in this approach to significantly improve the designs. The use of the orientation variable has been included in the algorithm.
Google Scholar Metrics 2013: nothing new under the sun
Venue: arXiv cs.DL 2013
Year: 2013

Main characteristics of Google Scholar Metrics new version (july 2013) are presented. We outline the novelties and the weaknesses detected after a first analysis. As main conclusion, we remark the lack of new functionalities with respect to last editions, as the only modification is the update of the timeframe (2008-2012). Hence, problems pointed out in our last reviews still remain active. Finally, it seems Google Scholar Metrics will be updated in a yearly basis
Comprehending Kademlia Routing - A Theoretical Framework for the Hop Count Distribution
Venue: arXiv cs.NI 2013
Year: 2013

The family of Kademlia-type systems represents the most efficient and most widely deployed class of internet-scale distributed systems. Its success has caused plenty of large scale measurements and simulation studies, and several improvements have been introduced. Its character of parallel and non-deterministic lookups, however, so far has prevented any concise formal analysis. This paper introduces the first comprehensive formal model of the routing of the entire family of systems that is validated against previous measurements. It sheds light on the overall hop distribution and lookup delays of the different variations of the original protocol. It additionally shows that several of the recent improvements to the protocol in fact have been counter-productive and identifies preferable designs with regard to routing overhead and resilience.
Multi-view Laplacian Support Vector Machines
Venue: arXiv cs.LG 2013
Year: 2013

We propose a new approach, multi-view Laplacian support vector machines (SVMs), for semi-supervised learning under the multi-view scenario. It integrates manifold regularization and multi-view regularization into the usual formulation of SVMs and is a natural extension of SVMs from supervised learning to multi-view semi-supervised learning. The function optimization problem in a reproducing kernel Hilbert space is converted to an optimization in a finite-dimensional Euclidean space. After providing a theoretical bound for the generalization performance of the proposed method, we further give a formulation of the empirical Rademacher complexity which affects the bound significantly. From this bound and the empirical Rademacher complexity, we can gain insights into the roles played by different regularization terms to the generalization performance. Experimental results on synthetic and real-world data sets are presented, which validate the effectiveness of the proposed multi-view Laplacian SVMs approach.