Archives for 2010

Today I read a paper titled “Improving Local Search for Fuzzy Scheduling Problems”

The abstract is:
The integration of fuzzy set theory and fuzzy logic into scheduling is a rather new aspect with growing importance for manufacturing applications, resulting in various unsolved aspects.

In the current paper, we investigate an improved local search technique for fuzzy scheduling problems with fitness plateaus, using a multi criteria formulation of the problem.

We especially address the problem of changing job priorities over time as studied at the Sherwood Press Ltd, a Nottingham based printing company, who is a collaborator on the project.

Today I read a paper titled “An Independent Evaluation of Subspace Face Recognition Algorithms”

The abstract is:
This paper explores a comparative study of both the linear and kernel implementations of three of the most popular Appearance-based Face Recognition projection classes, these being the methodologies of Principal Component Analysis, Linear Discriminant Analysis and Independent Component Analysis.

The experimental procedure provides a platform of equal working conditions and examines the ten algorithms in the categories of expression, illumination, occlusion and temporal delay.

The results are then evaluated based on a sequential combination of assessment tools that facilitate both intuitive and statistical decisiveness among the intra and interclass comparisons.

The best categorical algorithms are then incorporated into a hybrid methodology, where the advantageous effects of fusion strategies are considered.

Today I read a paper titled “Double Sided Watermark Embedding and Detection with Perceptual Analysis”

The abstract is:
In our previous work, we introduced a double-sided technique that utilizes but not reject the host interference.

Due to its nice property of utilizing but not rejecting the host interference, it has a big advantage over the host interference schemes in that the perceptual analysis can be easily implemented for our scheme to achieve the locally bounded maximum embedding strength.

Thus, in this work, we detail how to implement the perceptual analysis in our double-sided schemes since the perceptual analysis is very important for improving the fidelity of watermarked contents.

Through the extensive performance comparisons, we can further validate the performance advantage of our double-sided schemes.

Today I read a paper titled “Establishing A Minimum Generic Skill Set For Risk Management Teaching In A Spreadsheet Training Course”

The abstract is:
Past research shows that spreadsheet models are prone to such a high frequency of errors and data security implications that the risk management of spreadsheet development and spreadsheet use is of great importance to both industry and academia.

The underlying rationale for this paper is that spreadsheet training courses should specifically address risk management in the development process both from a generic and a domain-specific viewpoint.

This research specifically focuses on one of these namely those generic issues of risk management that should be present in a training course that attempts to meet good-practice within industry.

A pilot questionnaire was constructed showing a possible minimum set of risk management issues and sent to academics and industry practitioners for feedback.

The findings from this pilot survey will be used to refine the questionnaire for sending to a larger body of possible respondents.

It is expected these findings will form the basis of a risk management teaching approach to be trialled in a number of selected ongoing spreadsheet training courses.

Today I read a paper titled “A Walk in Facebook: Uniform Sampling of Users in Online Social Networks”

The abstract is:
Our goal in this paper is to develop a practical framework for obtaining a uniform sample of users in an online social network (OSN) by crawling its social graph.

Such a sample allows to estimate any user property and some topological properties as well.

To this end, first, we consider and compare several candidate crawling techniques.

Two approaches that can produce approximately uniform samples are the Metropolis-Hasting random walk (MHRW) and a re-weighted random walk (RWRW).

Both have pros and cons, which we demonstrate through a comparison to each other as well as to the “ground truth.” In contrast, using Breadth-First-Search (BFS) or an unadjusted Random Walk (RW) leads to substantially biased results.

Second, and in addition to offline performance assessment, we introduce online formal convergence diagnostics to assess sample quality during the data collection process.

We show how these diagnostics can be used to effectively determine when a random walk sample is of adequate size and quality.

Third, as a case study, we apply the above methods to Facebook and we collect the first, to the best of our knowledge, representative sample of Facebook users.

We make it publicly available and employ it to characterize several key properties of Facebook.

Today I read a paper titled “New Intelligent Transmission Concept for Hybrid Mobile Robot Speed Control”

The abstract is:
This paper presents a new concept of a mobile robot speed control by using two degree of freedom gear transmission.

The developed intelligent speed controller utilizes a gear box which comprises of epicyclic gear train with two inputs, one coupled with the engine shaft and another with the shaft of a variable speed dc motor.

The net output speed is a combination of the two input speeds and is governed by the transmission ratio of the planetary gear train.

This new approach eliminates the use of a torque converter which is otherwise an indispensable part of all available automatic transmissions, thereby reducing the power loss that occurs in the box during the fluid coupling.

By gradually varying the speed of the dc motor a stepless transmission has been achieved.

The other advantages of the developed controller are pulling over and reversing the vehicle, implemented by intelligent mixing of the dc motor and engine speeds.

This approach eliminates traditional braking system in entire vehicle design.

The use of two power sources, IC engine and battery driven DC motor, utilizes the modern idea of hybrid vehicles.

The new mobile robot speed controller is capable of driving the vehicle even in extreme case of IC engine failure, for example, due to gas depletion.

Today I read a paper titled “Spatiotemporal sensistivity and visual attention for efficient rendering of dynamic environments”

The abstract is:
We present a method to accelerate global illumination computation in dynamic environments by taking advantage of limitations of the human visual system.

A model of visual attention is used to locate regions of interest in a scene and to modulate spatiotemporal sensitivity.

The method is applied in the form of a spatiotemporal error tolerance map.

Perceptual acceleration combined with good sampling protocols provide a global illumination solution feasible for use in animation.

Results indicate an order of magnitude improvement in computational speed.

The method is adaptable and can also be used in image-based rendering, geometry level of detail selection, realistic image synthesis, video telephony and video compression.

Today I read a paper titled “Modular Traffic Sign Recognition applied to on-vehicle real-time visual detection of American and European speed limit signs”

The abstract is:
We present a new modular traffic signs recognition system, successfully applied to both American and European speed limit signs.

Our sign detection step is based only on shape-detection (rectangles or circles).

This enables it to work on grayscale images, contrary to most European competitors, which eases robustness to illumination conditions (notably night operation).

Speed sign candidates are classified (or rejected) by segmenting potential digits inside them (which is rather original and has several advantages), and then applying a neural digit recognition.

The global detection rate is ~90% for both (standard) U.S.

and E.U.

speed signs, with a misclassification rate <1%, and no validated false alarm in >150 minutes of video.

The system processes in real-time ~20 frames/s on a standard high-end laptop.

Today I read a paper titled “Image Authentication Based on Neural Networks”

The abstract is:
Neural network has been attracting more and more researchers since the past decades.

The properties, such as parameter sensitivity, random similarity, learning ability, etc., make it suitable for information protection, such as data encryption, data authentication, intrusion detection, etc.

In this paper, by investigating neural networks’ properties, the low-cost authentication method based on neural networks is proposed and used to authenticate images or videos.

The authentication method can detect whether the images or videos are modified maliciously.

Firstly, this chapter introduces neural networks’ properties, such as parameter sensitivity, random similarity, diffusion property, confusion property, one-way property, etc.

Secondly, the chapter gives an introduction to neural network based protection methods.

Thirdly, an image or video authentication scheme based on neural networks is presented, and its performances, including security, robustness and efficiency, are analyzed.

Finally, conclusions are drawn, and some open issues in this field are presented.

Today I read a paper titled “Strip Packing vs. Bin Packing”

The abstract is:
In this paper we establish a general algorithmic framework between bin packing and strip packing, with which we achieve the same asymptotic bounds by applying bin packing algorithms to strip packing.

More precisely we obtain the following results: (1) Any offline bin packing algorithm can be applied to strip packing maintaining the same asymptotic worst-case ratio.

Thus using FFD (MFFD) as a subroutine, we get a practical (simple and fast) algorithm for strip packing with an upper bound 11/9 (71/60).

A simple AFPTAS for strip packing immediately follows.

(2) A class of Harmonic-based algorithms for bin packing can be applied to online strip packing maintaining the same asymptotic competitive ratio.

It implies online strip packing admits an upper bound of 1.58889 on the asymptotic competitive ratio, which is very close to the lower bound 1.5401 and significantly improves the previously best bound of 1.6910 and affirmatively answers an open question posed by Csirik et.

al.

Today I read a paper titled “Competition for Popularity in Bipartite Networks”

The abstract is:
We present a dynamical model for rewiring and attachment in bipartite networks in which edges are added between nodes that belong to catalogs that can either be fixed in size or growing in size.

The model is motivated by an empirical study of data from the video rental service Netflix, which invites its users to give ratings to the videos available in its catalog.

We find that the distribution of the number of ratings given by users and that of the number of ratings received by videos both follow a power law with an exponential cutoff.

We also examine the activity patterns of Netflix users and find bursts of intense video-rating activity followed by long periods of inactivity.

We derive ordinary differential equations to model the acquisition of edges by the nodes over time and obtain the corresponding time-dependent degree distributions.

We then compare our results with the Netflix data and find good agreement.

We conclude with a discussion of how catalog models can be used to study systems in which agents are forced to choose, rate, or prioritize their interactions from a very large set of options.

Today I read a paper titled “Towards the characterization of individual users through Web analytics”

The abstract is:
We perform an analysis of the way individual users navigate in the Web.

We focus primarily in the temporal patterns of they return to a given page.

The return probability as a function of time as well as the distribution of time intervals between consecutive visits are measured and found to be independent of the level of activity of single users.

The results indicate a rich variety of individual behaviors and seem to preclude the possibility of defining a characteristic frequency for each user in his/her visits to a single site.

Today I read a paper titled “A Richer Understanding of the Complexity of Election Systems”

The abstract is:
We provide an overview of some recent progress on the complexity of election systems.

The issues studied include the complexity of the winner, manipulation, bribery, and control problems.

Today I read a paper titled “Stream Computing”

The abstract is:
Stream computing is the use of multiple autonomic and parallel modules together with integrative processors at a higher level of abstraction to embody “intelligent” processing.

The biological basis of this computing is sketched and the matter of learning is examined.

Today I read a paper titled “An Agent-based Simulation of the Effectiveness of Creative Leadership”

The abstract is:
This paper investigates the effectiveness of creative versus uncreative leadership using EVOC, an agent-based model of cultural evolution.

Each iteration, each agent in the artificial society invents a new action, or imitates a neighbor’s action.

Only the leader’s actions can be imitated by all other agents, referred to as followers.

Two measures of creativity were used: (1) invention-to-imitation ratio, iLeader, which measures how often an agent invents, and (2) rate of conceptual change, cLeader, which measures how creative an invention is.

High iLeader increased mean fitness of ideas, but only when creativity of followers was low.

High iLeader was associated with greater diversity of ideas in the early stage of idea generation only.

High cLeader increased mean fitness of ideas in the early stage of idea generation; in the later stage it decreased idea fitness.

Reasons for these findings and tentative implications for creative leadership in human society are discussed.

Today I read a paper titled “Learning from Scarce Experience”

The abstract is:
Searching the space of policies directly for the optimal policy has been one popular method for solving partially observable reinforcement learning problems.

Typically, with each change of the target policy, its value is estimated from the results of following that very policy.

This requires a large number of interactions with the environment as different polices are considered.

We present a family of algorithms based on likelihood ratio estimation that use data gathered when executing one policy (or collection of policies) to estimate the value of a different policy.

The algorithms combine estimation and optimization stages.

The former utilizes experience to build a non-parametric representation of an optimized function.

The latter performs optimization on this estimate.

We show positive empirical results and provide the sample complexity bound.

Today I read a paper titled “Off-line Optimization for Earley-style HPSG Processing”

The abstract is:
A novel approach to HPSG based natural language processing is described that uses an off-line compiler to automatically prime a declarative grammar for generation or parsing, and inputs the primed grammar to an advanced Earley-style processor.

This way we provide an elegant solution to the problems with empty heads and efficient bidirectional processing which is illustrated for the special case of HPSG generation.

Extensive testing with a large HPSG grammar revealed some important constraints on the form of the grammar..

Today I read a paper titled “New Algorithms for Regular Expression Matching”

The abstract is:
In this paper we revisit the classical regular expression matching problem, namely, given a regular expression R and a string Q, decide if Q matches one of the strings specified by R.