Showing 1 to 100 of 238 matching Articles
Results per page:
Export (CSV)
By
Barradas, Héctor Ruíz; Bert, Didier
Post to Citeulike
We present a fixpoint semantics of event systems. The semantics is presented in a general framework without concerns of fairness. Soundness and completeness of rules for deriving leadsto properties are proved in this general framework. The general framework is instantiated to minimal progress and weak fairness assumptions and similar results are obtained. We show the power of these results by deriving sufficient conditions for leadsto under minimal progress proving soundness of proof obligations without reasoning over statetraces.
more …
By
Sanvicente–Sánchez, Héctor; Frausto–Solís, Juan; Imperial–Valenzuela, Froilán
Post to Citeulike
Since the apparition of Simulated Annealing algorithm (SA) it has shown to be an efficient method to solve combinatorial optimization problems. Due to this, new algorithms based on two looped cycles (temperatures and Markov chain) have emerged, one of them have been called Threshold Accepting (TA). Classical algorithms based on TA usually use the same Markov chain length for each temperature cycle, these methods spend a lot of time at high temperatures where the Markov chain length is supposed to be small. In this paper we propose a method based on the neighborhood structure to get the Markov chain length in a dynamic way for each temperature cycle. We implemented two TA algorithms (classical or TACM and proposed or TADM) for SAT. Experimentation shows that the proposed method is more efficient than the classical one since it obtain the same quality of the final solution with less processing time.
more …
By
Gafni, Eli; Rajsbaum, Sergio
Post to Citeulike
3 Citations
We propose the musical benches problem to model a waitfree coordination difficulty that is orthogonal to previously studied ones such as agreement or symmetry breaking (leader election or renaming). A bench is the usual binary consensus problem for 2 processes. Assume n+1 processes want to sit in n benches as follows. Each one starts with a preference, consisting of a bench and one place (left or right) in the bench where it wants to sit. Each process should produce as output the place of the bench where it decides to sit. It is required that no two processes sit in different places of the same bench. Upon the observance of a conflict in one of the benches an undecided process can “abandon” its initial bench and place and try to sit in another bench at another place.
The musical benches problem is so called because processes jump from bench to bench trying to find one in which they may be alone or not in conflict with one another. If at most one process starts in each bench, the problem is trivially solvable– each process stays in its place. We show that if there is just one bench where two processes rather than one, start, the problem is waitfree unsolvable in read/write shared memory. This impossibility establishes a new connection between distributed computing and topology, via the BorsukUlam theorem.
The musical benches problem seems like just a collection of consensus problems, where by the pigeon hole principle at least one of them will have to be solved by two processes. Consequently, one is tempted to try to find a bivalency impossibility proof of the FLP style. Our second result shows that there is no such proof: We present an algorithm to solve the musical benches problem using set agreement, a primitive stronger than read/write registers, but weaker than consensus. Thus, an FLPstyle impossibility for musical benches will imply an FLPstyle impossibility of setconsensus.
The musical benches problem can be generalized by considering benches other than consensus, such as set agreement or renaming, leading to a very interesting class of new problems.
more …
By
CristóbalSalas, Alfredo; Chernykh, Andrey; RodríguezAlcantar, Edelmira; Gaudiot, JeanLuc
Show all (4)
Post to Citeulike
The messagepassing paradigm is now widely accepted and used mainly for interprocess communication in distributed memory parallel systems. However, one of its disadvantages is the high cost associated with the data exchange. Therefore, in this paper, we describe a messagepassing optimization technique based on the exploitation of singleassignment and constant information properties to reduce the number of communications. Similar to the more general partial evaluation approach, technique evaluates local and remote memory operations when only part of the input is known or available; it further specializes the program with respect to the input data. It is applied to the programs, which use a distributed singleassignment memory system. Experimental results show a considerable speedup in programs running in computer systems with slow interconnection networks. We also show that single assignment memory systems can have better network latency tolerance and the overhead introduced by its management can be hidden.
more …
By
Pérez, Cynthia B.; Olague, Gustavo; Fernandez, Francisco; Lutton, Evelyne
Show all (4)
Post to Citeulike
2 Citations
This work presents an evolutionary approach to improve the infection algorithm to solve the problem of dense stereo matching. Dense stereo matching is used for 3D reconstruction in stereo vision in order to achieve fine texture detail about a scene. The algorithm presented in this paper incorporates two different epidemic automata applied to the correspondence of two images. These two epidemic automata provide two different behaviours which construct a different matching. Our aim is to provide with a new strategy inspired on evolutionary computation, which combines the behaviours of both automata into a single correspondence process. The new algorithm will decide which epidemic automata to use based on inheritance and mutation, as well as the attributes, texture and geometry, of the input images. Finally, we show experiments in a real stereo pair to show how the new algorithm works.
more …
By
Gómez Soriano, José Manuel; Montes y Gómez, Manuel; Sanchis Arnal, Emilio; Rosso, Paolo
Show all (4)
Post to Citeulike
6 Citations
In this paper we present a new method to improve the coverage of Passage Retrieval (PR) systems when these systems are employed for the Question Answering (QA) tasks. The ranking of passages obtained by the PR system is rearranged to emphasize those passages with more probability to contain the answer. The new ranking is based on finding the ngram structures of the question that are presented in the passage, and the weight of the passages increases when they contain longer ngrams structures of the question. The results we present show that the application of this method improves notably the coverage of the classical PR system based on the Space Vectorial Model.
more …
By
GómezSoriano, José Manuel; MontesyGómez, Manuel; SanchisArnal, Emilio; VillaseñorPineda, Luis; Rosso, Paolo
Show all (5)
Post to Citeulike
1 Citations
Passage Retrieval (PR) is typically used as the first step in current Question Answering (QA) systems. Most methods are based on the vector space model allowing the finding of relevant passages for general user needs, but failing on selecting pertinent passages for specific user questions. This paper describes a simple PR method specially suited for the QA task. This method considers the structure of the question, favoring the passages that contain the longer ngram structures from the question. Experimental results of this method on Spanish, French and Italian show that this approach can be useful for multilingual question answering systems.
more …
By
Stephens, Christopher R.; Zamora, Adolfo; Wright, Alden H.
Post to Citeulike
Although much progress has been made in recent years in the theory of GAs and GP, there is still a conspicuous lack of tools with which to derive systematic, approximate solutions to their dynamics. In this article we propose and study perturbation theory as a potential tool to fill this gap. We concentrate mainly on selectionmutation systems, showing different implementations of the perturbative framework, developing, for example, perturbative expansions for the eigenvalues and eigenvectors of the transition matrix. The main focus however, is on diagrammatic methods, taken from physics, where we show how approximations can be built up using a pictorial representation generated by a simple set of rules, and how the renormalization group can be used to systematically improve the perturbation theory.
more …
By
Fraigniaud, Pierre; Ilcinkas, David; Rajsbaum, Sergio; Tixeuil, Sébastien
Show all (4)
Post to Citeulike
1 Citations
We consider the task of exploring graphs with anonymous nodes by a team of noncooperative robots modeled as finite automata. These robots have no a priori knowledge of the topology of the graph, or of its size. Each edge has to be traversed by at least one robot. We first show that, for any set of q noncooperative Kstate robots, there exists a graph of size O(qK) that no robot of this set can explore. This improves the O(K^{O(q)}) bound by Rollik (1980). Our main result is an application of this improvement. It concerns exploration with stop, in which one robot has to explore and stop after completing exploration. For this task, the robot is provided with a pebble, that it can use to mark nodes. We prove that exploration with stop requires Ω(log n) bits for the family of graphs with at most n nodes. On the other hand, we prove that there exists an exploration with stop algorithm using a robot with O(D log Δ) bits of memory to explore all graphs of diameter at most D and degree at most Δ.
more …
By
Bolshakov, Igor A.
Post to Citeulike
14 Citations
A method is proposed of the automatic concealment of digital information in rather long orthographically and semantically correct texts. The method does not change the meaning of the source text; it only replaces some words by their synonyms. Groups of absolute synonyms are used in a context independent manner, while the groups of relative synonyms are previously tested for semantic compatibility with the collocations containing the word to be replaced. A specific replacement is determined by the hidden information. The collocations are syntactically connected and semantically compatible pairs of content words; they are massively gathered beforehand, with a wide diversity in their stability and idiomacity. Thus the necessary linguistic resources are a specific synonymy dictionary and a very large database of collocations. The steganographic algorithm is informally outlined. An example of hiding binary information in a Russian text fragment is manually traced, with a rough evaluation of the steganographic bandwidth.
more …
By
Fraire H., Héctor; Castilla V., Guadalupe; Hernández R., Arturo; Gómez S., Claudia; Mora O., Graciela; Godoy V., Arquimedes
Show all (6)
Post to Citeulike
In this paper we approach the solution of large instances of the distribution design problem. Traditional approaches do not consider that the size of the instances can significantly affect the efficiency of the solution process. This paper shows the feasibility to solve large scale instances of the distribution design problem by compressing the instance to be solved. The goal of the compression is to obtain a reduction in the amount of resources needed to solve the original instance, without significantly reducing the quality of its solution. In order to preserve the solution quality, the compression summarizes the access pattern of the original instance using clustering techniques. In order to validate the approach we tested it on a new model of the replicated version of the distribution design problem that incorporates generalized database objects. The experimental results show that our approach permits to reduce the computational resources needed for solving large instances, using an efficient clustering algorithm. We present experimental evidence of the clustering efficiency of the algorithm.
more …
By
Alexandrov, Mikhail; Gelbukh, Alexander; Rosso, Paolo
Post to Citeulike
8 Citations
Free access to fulltext scientific papers in major digital libraries and other web repositories is limited to only their abstracts consisting of no more than several dozens of words. Current keywordbased techniques allow for clustering such type of short texts only when the data set is multicategory, e.g., some documents are devoted to sport, others to medicine, others to politics, etc. However, they fail on narrow domainoriented libraries, e.g., those containing all documents only on physics, or all on geology, or all on computational linguistics, etc. Nevertheless, just such data sets are the most frequent and most interesting ones. We propose simple procedure to cluster abstracts, which consists in grouping keywords and using more adequate document similarity measure. We use Stein’s MajorClust method for clustering both keywords and documents. We illustrate our approach on the texts from the Proceedings of a narrowtopic conference. Limitations of our approach are also discussed. Our preliminary experiments show that abstracts cannot be clustered with the same quality as full texts, though the achieved quality is adequate for many applications; accordingly, we suggest Makagonov’s proposal that digital libraries should provide document images of full texts of the papers (and not only abstracts) for open access via Internet, in order to help in search, classification, clustering, selection, and proper referencing of the papers.
more …
By
Vallejo, Edgar E.; Taylor, Charles E.
Post to Citeulike
This paper presents a computational framework for studying the influence of learning on the evolution of avian communication. We conducted computer simulations for exploring the effects of different learning strategies on the evolution of bird song. Experimental results show the genetic assimilation of song repertoires as a consequence of interactions between learning and evolution.
more …
By
Paredes, Rodrigo; Chávez, Edgar
Post to Citeulike
9 Citations
Proximity searching consists in retrieving from a database, objects that are close to a query. For this type of searching problem, the most general model is the metric space, where proximity is defined in terms of a distance function. A solution for this problem consists in building an offline index to quickly satisfy online queries. The ultimate goal is to use as few distance computations as possible to satisfy queries, since the distance is considered expensive to compute. Proximity searching is central to several applications, ranging from multimedia indexing and querying to data compression and clustering.
In this paper we present a new approach to solve the proximity searching problem. Our solution is based on indexing the database with the knearest neighbor graph (knng), which is a directed graph connecting each element to its k closest neighbors.
We present two search algorithms for both range and nearest neighbor queries which use navigational and metrical features of the knng graph. We show that our approach is competitive against current ones. For instance, in the document metric space our nearest neighbor search algorithms perform 30% more distance evaluations than AESA using only a 0.25% of its space requirement. In the same space, the pivotbased technique is completely useless.
more …
By
Mendoza, Sonia; Decouchant, Dominique; Morán, Alberto L.; Enríquez, Ana María Martínez; Favela, Jesus
Show all (5)
Post to Citeulike
In order to facilitate and improve collaboration among coauthors, working in the Web environment, documents must be made seamlessly available to them. Web documents may contain multimedia resources, whose management raises important issues due to the constraints and limits imposed by Web technology. This paper proposes an adaptive support for distributing shared Web documents and multimedia resources across authoring group sites. Our goal is to provide an efficient use of costly Web resources. Distribution is based on the current arrangement of the participating sites, the roles granted to the coauthors and the site capabilities. We formalize key concepts to ensure that system’s properties are fulfilled under the specified conditions and to characterize distribution at a given moment. The proposed support has been integrated into the PIÑAS platform, which allows an authoring group to collaboratively and consistently produce shared Web documents.
more …
By
Sakai, T.; Nara, C.; Urrutia, J.
Post to Citeulike
In this paper, we consider the problem of packing two or more equal area polygons with disjoint interiors into a convex body K in E^{2} such that each of them has at most a given number of sides. We show that for a convex quadrilateral K of area 1, there exist n internally disjoint triangles of equal area such that the sum of their areas is at least
$\frac {4n} {4n+1}$
. We also prove results for other types of convex polygons K. Furthermore we show that in any centrally symmetric convex body K of area 1, we can place two internally disjoint ngons of equal area such that the sum of their areas is at least
$\frac {n1}{\pi} sin \frac {\pi}{n1}$
. We conjecture that this result is true for any convex bodies.
more …
By
Michener, William; Beach, James; Bowers, Shawn; Downey, Laura; Jones, Matthew; Ludäscher, Bertram; Pennington, Deana; Rajasekar, Arcot; Romanello, Samantha; Schildhauer, Mark; Vieglais, Dave; Zhang, Jianting
Show all (12)
Post to Citeulike
8 Citations
The Science Environment for Ecological Knowledge (SEEK) is designed to help ecologists overcome data integration and synthesis challenges. The SEEK environment enables ecologists to efficiently capture, organize, and search for data and analytical processes. We describe SEEK and discuss how it can benefit ecological niche modeling in which biodiversity scientists require access and integration of regional and global data as well as significant analytical resources.
more …
By
Ayala, Gerardo; Ortiz, Magdalena; Osorio, Mauricio
Post to Citeulike
This paper presents the pertinence of the use of the Answer Set Programming (ASP) formalism for developing a computational model of a software agent for Computer Supported Collaborative Learning (CSCL) environments. This analytic model is based on a representation of for agent’s beliefs about the learner and the domain, together with the corresponding inference system with the appropriate rules to derive new beliefs about the capabilities of the learner, and its use in order to support effective collaboration and maintain learning possibilities for the group members. The model provides a representation of the structural knowledge frontier and the social knowledge frontier of the learner, which are the components for the definition of the learner’s zone of proximal development (zpd). Based on the zpd of its learner the agent can propose her a learning task and maintain the zpd for the learner in the group. The complete code of the model is presented in the declarative language of DLV, a logic programming language for implementing ASP models.
more …
By
NegreteMartínez, José
Post to Citeulike
In a previous paper the author posited that a sapient system would be a robot that performs abductions on a classification of concepts. In the present work, I propose the three steps that would be required for a robot to reach an initial state of sapience. Each step begins with improved mechatronics, continues with improvements in pattern recognition and ends with improvements in symbol manipulation. The first step starts with an anthropomorphic robot. I propose that if in the last step we implement adductive reasoning we have arrived at an initial sapient system. A low level robot showing the first stage evolution of a simple robot is presented. The implementation evinces many features of biological evolution such as misfitness, adaptation, exaptation, mutation, and coevolution.
more …
By
Akiyama, Jin; Hirata, Koichi; Ruiz, MariJo P.; Urrutia, Jorge
Show all (4)
Post to Citeulike
1 Citations
A folding of a simple polygon into a convex polyhedron is accomplished by glueing portions of the perimeter of the polygon together to form a polyhedron. A polygon Q is a flat nfolding of a polygon P if P can be folded to exactly cover the surface of Qn times, with no part of the surface of P left over. In this paper we focus on a specific type of flat 2foldings, flat 2foldings that wrapQ ; that is, foldings of P that cover both sides of Q exactly once. We determine, for any n, all the possible flat 2foldings of a regular ngon. We finish our paper studying the set of polygons that are flat 2foldable to regular polygons.
more …
By
Bolshakov, Igor A.; GaliciaHaro, Sofia N.
Post to Citeulike
Stable coordinate pairs (SCP) like comentarios y sugerencias ‘comments and suggestions’ or sano y salvo ‘safe and sound’ are rather frequent in texts in Spanish, though there are only few thousands of them in language. We characterize SCPs statistically by a numerical Stable Connection Index and reveal its unimodal distribution. We also propose lexical, morphologic, syntactic, and semantic categories for SCP structural description — for both a whole SCP and its components. It is argued that database containing a set of categorized SCPs facilitates several tasks of automatic NLP.. The research is based on a set of ca. 2200 Spanish coordinate pairs.
more …
By
Buscaldi, Davide; Rosso, Paolo; Gómez, Manuel Montes y
Post to Citeulike
The resolution of the lexical ambiguity, which is commonly referred to as Word Sense Disambiguation, is still an open problem in the field of Natural Language Processing. An approach to Word Sense Disambiguation based on Conceptual Density, a measure of the correlation between concepts, obtained good results with small context windows. This paper presents a method to integrate global knowledge, expressed as global keywords, in this approach. Global keywords are extracted from documents using a model based on term frequency and distribution. Preliminary results show that a slight improvement in recall can be obtained over the base system.
more …
By
Ortega, Joaquin Perez; Rangel, Rodolfo A. Pazos; Florez, Jose A. Martinez; Barbosa, J. Javier Gonzalez; Diaz, E. Alejandor Macias; Villanueva, J. David Teran
Show all (6)
Post to Citeulike
In this paper we approach the solution of large instances of the distribution design problem. The traditional approaches do not consider that the size of the instances can significantly reduce the efficiency of the solution process, which only involves a model of the problem and a solution algorithm. We propose a new approach that incorporates multiple models and algorithms and mechanisms for instance compression, for increasing the scalability of the solution process. In order to validate the approach we tested it on a new model of the replicated version of the distribution design problem which incorporates generalized database objects, and a method for instance compression that uses clustering techniques. The experimental results, utilizing typical Internet usage loads, show that our approach permits to reduce at least 65% the computational resources needed for solving large instances, without significantly reducing the quality of its solution.
more …
By
PérezCoutiño, M.; Solorio, T.; MontesyGómez, M.; LópezLópez, A.; VillaseñorPineda, L.
Show all (5)
Post to Citeulike
This paper describes the prototype developed by the Language Technologies Laboratory at INAOE for Spanish monolingual QA evaluation task at CLEF 2004. Our approach is centered on the use of context at a lexical level in order to identify possible answers to factoid questions. This method is supported by an alternative one based on pattern recognition in order to identify candidate answers to definition questions. We describe the methods applied at different stages of the system and our prototype architecture for question answering. The paper shows and discusses the results we achieved with this approach.
more …
By
TéllezValero, Alberto; MontesyGómez, Manuel; VillaseñorPineda, Luis
Post to Citeulike
Information extraction is concerned with applying natural language processing to automatically extract the essential details from text documents. A great disadvantage of current approaches is their intrinsic dependence to the application domain and the target language. Several machine learning techniques have been applied in order to facilitate the portability of the information extraction systems. This paper describes a general method for building an information extraction system using regular expressions along with supervised learning algorithms. In this method, the extraction decisions are lead by a set of classifiers instead of sophisticated linguistic analyses. The paper also shows a system called TOPO that allows to extract the information related with natural disasters from newspaper articles in Spanish language. Experimental results of this system indicate that the proposed method can be a practical solution for building information extraction systems reaching an Fmeasure as high as 72%.
more …
By
OlveraLópez, José A.; CarrascoOchoa, J. Ariel; MartínezTrinidad, José Fco.
Post to Citeulike
1 Citations
The edition process is an important task in supervised classification because it helps to reduce the size of the training sample. On the other hand, InstanceBased classifiers store all the training set indiscriminately, which in almost all times, contains useless or harmful objects, for the classification process. Therefore it is important to delete unnecessary objects to increase both classification speed and accuracy. In this paper, we propose an edition method based on sequential search and we present an empirical comparison between it and some other decremental edition methods.
more …
By
Zúñiga, Fabiel; Ramos, Félix; Piza, H. Ivan
Post to Citeulike
2 Citations
This paper presents a method to specify agent’s goals using process algebras. Formal specification of agent’s goal is important in goal oriented works because it allows more detailed description about what we want an agent to do and also is possible to detect possible problems. In this paper we present the method we use to specify formally agent’s goals in GeDA3D a platform useful to implement distributed applications where a 3D interface is useful.
more …
By
García, Edscott Wilson; MoralesLuna, Guillermo
Post to Citeulike
In the case of desktop grids, a single hardwaredetermined latency and constant bandwidth between processors cannot be assumed without incurring in unnecessary error. The actual network topology is determined not only by the physical hardware, but also by the instantaneous bandwidth availability for parallel processes to communicate. In this paper we present a novel task assignment scheme which takes the dynamic network topology into consideration along with the traditionally evaluated variables such as processor availability and potential. The method performs increasingly better as the grid size increases.
more …
By
GarcíaPerera, L. Paola; NolazcoFlores, Juan A.; MexPerera, Carlos
Post to Citeulike
In this paper an improvement in the generation of the cryptographicspeechkey by optimising the number of parameters is presented. It involves the selection of the number of dimensions with the best performance for each of the phonemes. First, the Mel frequency cepstral coefficients, (first and second derivatives) of the speech signal are calculated. Then, an Automatic Speech Recogniser, which models are previously trained, is used to detect the phoneme limits in the speech utterance. Afterwards, the feature vectors are built using both the phonemespeech models and the information obtained from the phoneme segmentation. Finally, the Support Vector Machines classifier, relying on an RBF kernel, computes the cryptographic key. By optimising the number of parameters our results show an improvement of 19.88%, 17.08%, 14.91% for 10, 20 and 30 speakers respectively, employing the YOHO database.
more …
By
FloresBecerra, G.; Garcia, Victor M.; Vidal, Antonio M.
Post to Citeulike
The work presented here is an experimental study of four iterative algorithms for solving the Inverse Additive Singular Value Problem (IASVP). The algorithms are analyzed and evaluated with respect to different points of view: memory requirements, convergence, accuracy and execution time, in order to observe their behaviour with different problem sizes and to identify those capable to solve the problem efficiently.
more …
By
OlveraLópez, J. Arturo; MartínezTrinidad, J. Fco.; CarrascoOchoa, J. Ariel
Post to Citeulike
1 Citations
Edition is an important and useful task in supervised classification specifically for instancebased classifiers because edition discards from the training set those useless or harmful objects for the classification accuracy and it helps to reduce the size of the original training sample and to increase both the classification speed and accuracy. In this paper, we propose two edition schemes that combine edition methods and sequential search for instance selection. In addition, we present an empirical comparison between these schemes and some other edition methods.
more …
By
Sánchez, Vianey Guadalupe Cruz; Salgado, Gerardo Reyes; Villegas, Osslan Osiris Vergara; Ortega, Joaquín Perez; Rendón, Azucena Montes
Show all (5)
Post to Citeulike
The development of Artificial Intelligence (AI) research has followed mainly two directions: the use of symbolic and connectionist (artificial neural networks) methods. These two approaches have been applied separately in the solution of problems that require tasks of knowledge acquisition and learning. We present the results of implementing a NeuroSymbolic Hybrid System (NSHS) that allows unifying these two types of knowledge representation. For this, we have developed a compiler or translator of symbolic rules which takes as an input a group of rules of the type IF ... THEN..., converting them into a connectionist representation. Obtained the compiled artificial neural network this is used as an initial neural network in a learning process that will allow the “refinement” of the knowledge. To prove the refinement of the hybrid approach, we carried out a group of tests that show that it is possible to improve in a connectionist way the symbolic knowledge.
more …
By
Pérez, Jesús Fabián López
Post to Citeulike
Our problem is about a routing of a vehicle with product pickup and delivery and with time window constraints. This problem requires to be attended with instances of medium scale (nodes ≥ 100). A strong active time window exists (≥90%) with a large factor of amplitude (≥75%). This problem is NPhard and for such motive the application of an exact method is limited by the computational time. This paper proposes a specialized genetic algorithm. We report good solutions in computational times below 5 minutes.
more …
By
Cauich, Enrique; Gómez Cárdenas, Roberto; Watanabe, Ryouske
Post to Citeulike
7 Citations
Steganography is defined as the art and science of hiding information, it takes one piece of information and hides it within another. The piece more used to hide information are the digital images. In this paper we present a way to use unused fields in the IP header of TCP/IP packets in order to send information between to nodes over Internet.
more …
By
Salamah, Salamah; Gates, Ann; Roach, Steve; Mondragon, Oscar
Show all (4)
Post to Citeulike
1 Citations
The Specification Pattern System (SPS) and the Property Specification (Prospec) tool assist a user in generating formal specifications in Linear Temporal Logic (LTL), as well as other languages, from property patterns and scopes. Patterns are highlevel abstractions that provide descriptions of common properties, and scopes describe the extent of program execution over which the property holds. The purpose of the work presented in this paper is to verify that the generated LTL formulas match the natural language descriptions, timelines, and traces of computation that describe the pattern and scope. The LTL formulas were verified using the Spin model checker on test cases developed using boundary value analysis and equivalence class testing strategies. A test case is an LTL formula and a sequence of Boolean valuations. The LTL formulas were those generated from SPS and Prospec. The Boolean valuations of propositions in the LTL formula are generated by a deterministic, singlethreaded Promela program that was run using the software modelchecker Spin. For each pattern, a suite of test cases was. The experiments uncovered several errors in both the SPSgenerated and the Prospecgenerated formulas.
more …
By
GarcíaMartinez, Christian P.; GarcíaMacías, J. Antonio
Post to Citeulike
As mobile devices roam between wireless cells, performing handovers, mobility is managed by protocols like Mobile IP and micromobility protocols. However, these protocols do not manage how to transfer context from cell to cell as the devices move. Context transfer mechanisms aim for performance improvements in the process of handover, so that the applications running on mobile nodes can operate with minimal disruption, thus allowing seamless mobility. In this paper we propose mechanisms that enable context transfer between access routers offering internet connectivity for mobile nodes; we use an actual implementation to test the performance of context transfer for different services and analyze the benefits that can be obtained using these mechanisms.
more …
By
Bose, Prosenjit; Hurtado, Ferran; RiveraCampo, Eduardo; Wood, David R.
Show all (4)
Post to Citeulike
Consider the following open problem: does every complete geometric graph K_{2n} have a partition of its edge set into n plane spanning trees? We approach this problem from three directions. First, we study the case of convex geometric graphs. It is well known that the complete convex graph K_{2n} has a partition into n plane spanning trees. We characterise all such partitions. Second, we give a sufficient condition, which generalises the convex case, for a complete geometric graph to have a partition into plane spanning trees. Finally, we consider a relaxation of the problem in which the trees of the partition are not necessarily spanning. We prove that every complete geometric graph K_{n} can be partitioned into at most
$n\sqrt{n/12}$
plane trees.
more …
By
Leaños, J.; Merino, C.; Salazar, G.; Urrutia, J.
Show all (4)
Post to Citeulike
Kano et al. proved that if P_{0}, P_{1}, ..., P_{k − − 1} are pairwise disjoint collections of points in general position, then there exist spanning trees T_{0}, T_{1}, ..., T_{k − − 1}, of P_{0}, P_{1}, ..., P_{k − − 1}, respectively, such that the edges of T_{0} ∪ T_{1} ∪ ... ∪ T_{k − 1} intersect in at most (k – 1)n – k(k – 1)/2 points. In this paper we show that this result is asymptotically tight within a factor of 3/2. To prove this, we consider alternating collections, that is, collections such that the points in P: = P_{0} ∪ P_{1} ∪ ... ∪ P_{k − 1} are in convex position, and the points of the P_{i}’s alternate in the convex hull of P.
more …
By
AcevesPérez, Rita; VillaseñorPineda, Luis; MontesyGomez, Manuel
Post to Citeulike
1 Citations
This paper explores the feasibility of a multilingual question answering approach based on the Web redundancy. The paper introduces a system prototype that combines a translation machine with a statistical QA method. The main advantage of this proposal is its small dependence to a given language. The experimental results, obtained from a test set of 165 factual questions, demostrated the great potential of the approach, and gave interesting insights about the redundancy of the web and the online translators.
more …
By
Sierra, Margarita Reyes; Coello Coello, Carlos A.
Post to Citeulike
155 Citations
In this paper, we propose a new MultiObjective Particle Swarm Optimizer, which is based on Pareto dominance and the use of a crowding factor to filter out the list of available leaders. We also propose the use of different mutation (or turbulence) operators which act on different subdivisions of the swarm. Finally, the proposed approach also incorporates the ∈dominance concept to fix the size of the set of final solutions produced by the algorithm. Our approach is compared against five stateoftheart algorithms, including three PSObased approaches recently proposed. The results indicate that the proposed approach is highly competitive, being able to approximate the front even in cases where all the other PSObased approaches fail.
more …
By
Korzhik, Valery; MoralesLuna, Guillermo; Lee, Moon Ho
Post to Citeulike
6 Citations
There are several steganography techniques (e.g. linguistic or least significant bit embedding) that provide security but no robustness against an active adversary. On the other hand it is rather well known that the spreadspectrum based technique is robust against an active adversary but it seems to be insecure against a statistical detection of stegosignal. We prove in this paper that actually this is not the case and that there exists an stegosystem that is asymptotically both secure to statistical detection and robust against a jamming of stegosignal by an active adversary. We call such stegosystems quasiperfect whereas we call them perfect if in addition the data rate of secret information is asymptotically constant. We prove that perfect stegosystems do not exist for both blind and informed decoders. Some examples using the simplex and the ReedMuller codes jointly with stegosystems are given.
more …
By
Brizuela, Carlos A.; Gutiérrez, Everardo
Post to Citeulike
3 Citations
This paper introduces a new algorithm to deal with multiobjective combinatorial and continuous problems. The algorithm is an extension of a previous one designed to deal with single objective combinatorial problems. The original purpose of the single objective version was to study in a rigorous way the properties the search graph of a particular problem needs to hold so that a randomized local search heuristic can find the optimum with high probability. The extension of these results to better understand multiobjective combinatorial problems seems to be a promising line of research. The work presented here is a first small step in this direction. A detailed description of the multiobjective version is presented along with preliminary experimental results on a well known combinatorial problem. The results show that the algorithm has the desired characteristics.
more …
By
AriasTorres, Dante; GarcíaMacías, J. Antonio
Post to Citeulike
In recent years, diverse solutions for service discovery in mobile ad hoc networks have been proposed. These solutions basically follow two approaches: the first one considers routing and service discovery as separate activities (i.e. implementing independent protocols for each activity); the second one integrates routing and service discovery into a single protocol. Based on this second approach we extend the AODV routing protocol to also perform service discovery. We analyze and compare the performance of both approaches. The results show that the integration of routing and service discovery reduces the amount of traffic generated and the time necessary to find a service.
more …
By
Godínez, Fernando; Hutter, Dieter; Monroy, Raúl
Post to Citeulike
Abstract
Current IDSs can be easily overwhelmed by the the amount of information they ought to analyse. By preprocessing the information, this paper aims both to alleviate the computational overhead involved in intrusion detection and to make IDSs scalable. Regardless whether it is a sequence of network packets or a sequence of system calls, the information an IDS analyses is often redundant in at least two respects: first, every entry in the sequence may contain spurious information; second, any sequence may contain redundant subsequences. By using Rough Sets we have identified key attributes for every entry eliminating spurious information, without missing chief details. Using ngram theory we have identified the most redundant subsequences within a sequence, and then substituting them with a fresh tag, resulting in a sequence length reduction. To make an IDS scalable we have proposed to structure the IDS as a collection of sensors, each of which is specialised to a particular service, i.e. telnet, smtp, etc. To approach service selection, we suggest the use of Hidden Markov Models, trained to detect an specific service described by a family of ngrams. Our results are encouraging, we have obtained an average reduction factor of 12. Using the service discriminator we have also written a simple, yet effective, misuse IDS. The impact over detection and false alarm ratio using reduced sequences is negligible.
Keywords: Dimensionality Reduction, Object Reduction, Intrusion Detection, Misuse Detection
more …
By
MoralesLuna, Guillermo
Post to Citeulike
#kSAT is a complex problem equivalent to calculate the cardinalities of the null sets of conjunctive forms consisting of clauses with an uniform length. Each such null set is the union of linear varieties of uniform dimension in the hypercube. Here we study the class of sets in the hypercube that can be realized as such null sets. We look toward to characterize their cardinalities and the number of ways that they can be expressed as unions of linear varieties of uniform dimension. Using combinatorial and graph theory argumentations, we give such characterizations for very extremal values of k, either when it is very small or close to the hypercube dimension, and of the number of clauses appearing in an instance, either of value 2, or big enough to get a contradiction.
more …
By
Olmos, Ivan; Gonzalez, Jesus A.; Osorio, Mauricio
Post to Citeulike
1 Citations
Finding common patterns is an important problem for several computer science subfields such as Machine Learning (ML) and Data Mining (DM). When we use graphbased representations, we need the Subgraph Isomorphism (SI) operation for finding common patterns. In this research we present a new approach to find a SI using a list code based representation without candidate generation. We implement a step by step expansion model with a widthdepth search. The proposed approach is suitable to work with labeled and unlabeled graphs, with directed and undirected edges. Our experiments show a promising method to be used with scalable graph matching.
more …
By
Godínez, Fernando; Hutter, Dieter; Monroy, Raúl
Post to Citeulike
An intrusion detection system (IDS) usually has to analyse Gigabytes of audit information. In the case of anomaly IDS, the information is used to build a user profile characterising normal behaviour. Whereas for misuse IDSs, it is used to test against known attacks. Probabilistic methods, e.g. hidden Markov models, have proved to be suitable to profile formation but are prohibitively expensive. To bring these methods into practise, this paper aims to reduce the audit information by folding up subsequences that commonly occur within it. Using ngrams language models, we have been able to successfully identify the ngrams that appear most frequently. The main contribution of this paper is a ngram extraction and identification process that significantly reduces an input log file keeping key information for intrusion detection. We reduced log files by a factor of 3.6 in the worst case and 4.8 in the best case. We also tested reduced data using hidden Markov models (HMMs) for intrusion detection. The time needed to train the HMMs is greatly reduced by using our reduced log files, but most importantly, the impact on both the detection and false positive ratios are negligible.
more …
By
Ibarra Orozco, Rodolfo E.; HernándezGress, Neil; FraustoSolís, Juan; Mora Vargas, Jaime
Show all (4)
Post to Citeulike
1 Citations
The Support Vector Machine (SVM) is a well known method used for classification, regression and density estimation. Training a SVM consists in solving a Quadratic Programming (QP) problem. The QP problem is very resource consuming (computational time and computational memory), because the quadratic form is dense and the memory requirements grow square the number of data points. The support vectors found in the training of SVM’s represent a small subgroup of the training patterns. If an algorithm could make an approximation beforehand of the points standing for support vectors, we could train the SVM only with those data and the same results could be obtained as trained using the entire data base.
This paper introduces an original initialization by the Zoutendijk method, called ZQP, to train SVM’s faster than classical ones. The ZQP method first makes a fast approximation to the solution using the Zoutendijk algorithm. As result of this approximation, a reduced number of training patterns is obtained. Finally, a QP algorithm makes the training with this subset of data. Results show the improvement of the methodology in comparison to QP algorithm and chunking with QP algorithm.
The ideas presented here can be extended to another problems such as resource allocation, considering that allocation as a combinatorial problem, that could be solved using some artificial intelligent technique such as Genetic algorithms or simulated annealing. In such approach ZQP would be used as a measure for effective fitness.
more …
By
Pérez O., Joaquín; Pazos R., Rodolfo A.; FraustoSolís, Juan; Reyes S., Gerardo; Santaolaya S., Rene; Fraire H., Héctor J.; Cruz R., Laura
Show all (7)
Post to Citeulike
1 Citations
In this paper we deal with the solution of very large instances of the design distribution problem for distributed databases. Traditionally the capacity for solving large scale instances of NPhard problems has been limited by the available computing resources and the efficiency of the solution algorithms. In contrast, in this paper we present a new solution approach that permits to solve larger instances using the same resources. This approach consists of the application of a systematic method for transforming an instance A into a smaller instance A’ that has a large representativeness of instance A. For validating our approach we used a mathematical model developed by us, whose solution yields the design of a distributed database that minimizes its communication costs. The tests showed that the solution quality of the transformed instances was on the average 10.51% worse than the optimal solution; however, the size reduction was 97.81% on the average. We consider that the principles used in the proposed approach can be applied to the solution of very large instances of NPhard problems of other problem types.
more …
By
Sierra, Margarita Reyes; Coello, Carlos A. Coello
Post to Citeulike
We propose a new version of a multiobjective coevolutionary algorithm. The main idea of the proposed approach is to concentrate the search effort on promising regions that arise during the evolutionary process as a product of a clustering mechanism applied on the set of decision variables corresponding to the known Pareto front. The proposed approach is validated using several test functions taken from the specialized literature and it is compared with respect to its previous version and another approach that is representative of the stateoftheart in evolutionary multiobjective optimization.
more …
By
CruzCortés, Nareli; TrejoPérez, Daniel; Coello, Carlos A. Coello
Post to Citeulike
13 Citations
In this paper, we present a study of the use of an artificial immune system (CLONALG) for solving constrained global optimization problems. As part of this study, we evaluate the performance of the algorithm both with binary encoding and with realnumbers encoding. Additionally, we also evaluate the impact of the mutation operator in the performance of the approach by comparing Cauchy and Gaussian mutations. Finally, we propose a new mutation operator which significantly improves the performance of CLONALG in constrained optimization.
more …
By
Heinze, Mikael; OrtizArroyo, Daniel; Larsen, Henrik Legind; RodriguezHenriquez, Francisco
Show all (4)
Post to Citeulike
2 Citations
In this paper we investigate the effectiveness of applying fuzzy controllers to create strong computer player programs in the domain of backgammon. Fuzzeval, our proposed mechanism, consists of a fuzzy controller that dynamically evaluates the perceived strength of the board configurations it receives. Fuzzeval employs an evaluation function that adjusts the membership functions linked to the linguistic variables employed in the knowledge base. The membership functions are aligned to the average crisp input that was successfully used in the past winning games. Fuzzeval mechanisms are adaptive and have the simplicity associated with fuzzy controllers. Our experiments show that Fuzzeval improves its performance up to 42% after a match of only one hundred backgammon games played against Pubeval, a strong intermediate level program.
more …
By
Alexandrov, Mikhail; Sanchis Arnal, Emilio; Rosso, Paolo
Post to Citeulike
2 Citations
Cluster analysis of dialogs with transport directory service allows revealing the typical scenarios of dialogs, which is useful for designing automatic dialog systems. We show how to parameterize dialogs and how to control the process of clustering. The parameters include both data of transport service and features of passenger s behavior. Control of clustering consists in manipulating the parameter s weights and checking stability of the results. This technique resembles Makagonov s approach to the analysis of dweller s complaints to city administration. We shortly describe B. Stein s new MajorClust method and demonstrate its work on real persontoperson dialogs provided by Spanish railway service.
more …
By
GarcíaPerera, L. Paola; NolazcoFlores, Juan A.; MexPerera, Carlos
Post to Citeulike
In this work we show a performance improvement of our system by taking into account the weights of the mixture of Gaussians of the Hidden Markov Model. Furthermore and independently tunning of each of the phoneme Support Vector Machine (SVM) parameters is performed. In our system the user utters a pass phrase and the phoneme waveform segments are found using the Automatic Speech Recognition Technology. Given the speech model and the phoneme information in the segments, a set of features are created to train an SVM that could generate a cryptographic key. Applying our method to a set of 10, 20, and 30 speakers from the YOHO database, the results show a good improvement compared with our last configuration, improving the robustness in the generation of the cryptographic key.
more …
By
Grosan, Crina; Abraham, Ajith; Han, Sangyong; Gelbukh, Alexander
Show all (4)
Post to Citeulike
4 Citations
Particle Swarm Optimization (PSO) technique has proved its ability to deal with very complicated optimization and search problems. Several variants of the original algorithm have been proposed. This paper proposes a novel hybrid PSO – evolutionary algorithm for solving the well known geometrical place problems. Finding the geometrical place could be sometimes a hard task. In almost all situations the geometrical place consists more than one single point. The performance of the newly proposed PSO algorithm is compared with evolutionary algorithms. The main advantage of the PSO technique is its speed of convergence. Also, we propose a hybrid algorithm, combining PSO and evolutionary algorithms. The hybrid combination is able to detect the geometrical place very fast for which the evolutionary algorithms required more time and the conventional PSO approach even failed to find the real geometrical place.
more …
By
Domínguez, Jesús Héctor; Fernández, Luis Marcelo; Aguirre, José Luis; Garrido, Leonardo; Brena, Ramón
Show all (5)
Post to Citeulike
The present document explores how air pollution can be assessed from a multiagent point of view. In order to do so, a traffic system was simulated using agents as a way to measure if air pollution levels go down when the traffic lights employ a multigent cooperative system that negotiates the green light duration of each traffic light, in order to minimize the time a car has to wait to be served in an intersection. The findings after running some experiments where lanes of each direction are congested incrementally showed, that using this technique, there is a significant decrease in air pollution over the simulated area which means that traffic lights controlled by the multiagent system do improve the levels of air pollution.
more …
By
Gyves, Victor Polo; GuzmanArenas, Adolfo; Levachkine, Serguei
Post to Citeulike
A hierarchy is an arrangement of qualitative values in a tree with certain properties. Hierarchies allow to define the confusion conf(r, s) in using qualitative value r instead of the intended or correct value s. From here, “predicate P holds for object o”, written P(o), is generalized to “P holds for o within confusion ε”, written P_{ε}(o). These precisioncontrolled predicates are useful to retrieve approximate answers, where the error (confusion) is known.
The predicates are implemented through an extended SQL that uses confusion to retrieve information from a database. We show how to extend any database for precisioncontrolled retrieval. Limiting the total error is also useful, and this is achieved by predicate P^{e}. Examples are given.
more …
By
BuenabadChávez, Jorge; DomínguezDomínguez, Santiago
Post to Citeulike
The data diffusion space (DDS) is an allsoftware shared address space for parallel computing on distributed memory platforms. It is an extra address space to that of each process running a parallel application under the SPMD (Single Program Multiple Data) model. The size of DDS can be up to 2^{64} bytes, either on 32 or on 64bit architectures. Data laid on DDS diffuses, or migrates and replicates, in the memory of each processor using the data. This data is used through an interface similar to that used to access data in files.
We have implemented DDS for PC clusters with Linux. However, being allsoftware, DDS should require little change to make it immediately usable in other distributed memory platforms and operating systems. We present experimental results on the performance of two applications both under DDS and under MPI (Message Passing Interface). DDS tends to perform better in larger processor counts, and is simpler to use than MPI for both incore and outofcore computation.
more …
By
Quintero, Rolando; Torres, Marco; Moreno, Miguel; Guzmán, Giovanni
Show all (4)
Post to Citeulike
1 Citations
We present a collaborativeapplication to the National Center of Disaster Prevention in Mexico (CENAPRED), which is focused on helping in the decision making process during the radiological disasters, related to “Laguna Verde” nuclear plant. This application coordinates the activities of External Plan of Radiological Emergency (PERE) that has been generated for this purpose. In addition, the application is based on a Geographical Information System (GIS) into a collaborative architecture to support the interaction from several entities, which work with special training groups in a virtual reality environment. The architecture consists of a collaboration model and it generates a schema of components to find out the independence and standardization of the system so that it can be implemented in any GISplatform.
more …
By
Oca, Marco Antonio Montes; Garrido, Leonardo; Aguirre, José Luis
Post to Citeulike
1 Citations
Communication among agents in swarm intelligent systems and more generally in multiagent systems, is crucial in order to coordinate agents’ activities so that a particular goal at the collective level is achieved. From an agent’s perspective, the problem consists in establishing communication policies that determine what, when, and how to communicate with others. In general, communication policies will depend on the nature of the problem being solved. This means that the solvability of problems by swarm intelligent systems depends, among other things, on the agents’ communication policies, and setting an incorrect set of policies into the agents may result in finding poor solutions or even in the unsolvability of problems. As a case study, this paper focus on the effects of letting agents use different communication policies in antbased clustering algorithms. Our results show the effects of using different communication policies on the final outcome of these algorithms.
more …
By
GaliciaHaro, Sofía N.; Gelbukh, Alexander
Post to Citeulike
We evaluate the possibility to learn, in an unsupervised manner, a list of idiomatic word combinations of the type preposition + noun phrase + preposition (P NP P), namely, such groups with three or more simple forms that behave as a whole lexical unit and have semantic and syntactic properties not deducible from the corresponding properties of each simple form, e.g., by means of, in order to, in front of. We show that idiomatic P NP P combinations have some statistical properties distinct from those of usual idiomatic collocations. In particular, we found that most frequent P NP P trigrams tend to be idiomatic. Of other statistical measures, loglikelihood performs almost as good as frequency for detecting idiomatic expressions of this type, while chisquare and pointwise mutual information perform very poor. We experiment on Spanish material.
more …
By
Rosso, Paolo; MontesyGómez, Manuel; Buscaldi, Davide; PancardoRodríguez, Aarón; Pineda, Luis Villaseñor
Show all (5)
Post to Citeulike
2 Citations
The problem of the resolution of the lexical ambiguity seems to be stuck because of the knowledge acquisition bottleneck. Therefore, it is worthwhile to investigate the possibility of using the Web as a lexical resource. This paper explores two attempts of using Web counts collected through a search engine. The first approach calculates the hits of each possible synonym of the noun to disambiguate together with the nouns of the context. In the second approach the disambiguation of a noun uses a modifier adjective as supporting evidence. A better precision than the baseline was obtained using adjectivenoun pairs, even if with a low recall. A comprehensive set of weighting formulae for combining Web counts was investigated in order to give a complete picture of what are the various possibilities, and what are the formulae that work best. The comparison across different search engines was also useful: Web counts, and consequently disambiguation results, were almost identical. Moreover, the Web seems to be more effective than the WordNet Domains lexical resource if integrated rather than standalone.
more …
By
Starostenko, Oleg; ChávezAragón, Alberto; Sánchez, J. Alfredo; Ostróvskaya, Yulia
Show all (4)
Post to Citeulike
This paper presents a novel approach for image retrieval from digital collections. Specifically, we describe IRONS (Image Retrieval with Ontological Descriptions of Shapes), a system based on the application of several novel algorithms that combine lowlevel image analysis techniques with automatic shape extraction and indexing. In order to speed up preprocessing, we have proposed and implemented the convex regions algorithm and discrete curve evolution approach. The image indexing module of IRONS is addressed using two proposed algorithms: the tangent space and the twosegment turning function for shapes representation invariant to rotation and scale. Another goal of the proposed method is the integration of useroriented descriptions, which leads to more complete retrieval by accelerating the convergence to the expected result. For the definition of image semantics, ontology annotation of subregions has been used.
more …
By
AyaquicaMartínez, I. O.; MartínezTrinidad, J. F.; CarrascoOchoa, J. A.
Post to Citeulike
1 Citations
The conceptual kmeans algorithm consists of two steps. In the first step the clusters are obtained (aggregation step) and in the second one the concepts or properties for those clusters are generated (characterization step). We consider the conceptual kmeans management of mixed, qualitative and quantitative, features is inappropriate. Therefore, in this paper, a new conceptual kmeans algorithm using similarity functions is proposed. In the aggregation step we propose to use a different clustering strategy, which allows working in a more natural way with object descriptions in terms of quantitative and qualitative features. In addition, an improvement of the characterization step and a new quality measure for the generated concepts are presented. Some results obtained after applying both, the original and the modified algorithms on different databases are shown. Also, they are compared using the proposed quality measure.
more …
By
Peña, Sergio Ivvan Valdez; Rionda, Salvador Botello; Aguirre, Arturo Hernández
Post to Citeulike
1 Citations
We propose a new approach for multiobjective shape optimization based on the estimation of probability distributions. The algorithm improves search space exploration by capturing landscape information into the probability distribution of the population. Correlation among design variables is also used for the computation of probability distributions. The algorithm uses finite element method to evaluate objective functions and constraints. We provide several design problems and we show Pareto front examples. The design goals are: minimum weight and minimum nodal displacement, without holes or unconnected elements in the structure.
more …
By
Calvo, Hiram; Gelbukh, Alexander; Kilgarriff, Adam
Post to Citeulike
1 Citations
Prepositional Phrase (PP) attachment can be addressed by considering frequency counts of dependency triples seen in a nonannotated corpus. However, not all triples appear even in very big corpora. To solve this problem, several techniques have been used. We evaluate two different backoff methods, one based on WordNet and the other on a distributional (automatically created) thesaurus. We work on Spanish. The thesaurus is created using the dependency triples found in the same corpus used for counting the frequency of unambiguous triples. The training corpus used for both methods is an encyclopaedia. The method based on a distributional thesaurus has higher coverage but lower precision than the WordNet method.
more …
By
Zavala, Angel E. Muñoz; Aguirre, Arturo Hernández; Diharce, Enrique R. Villa
Post to Citeulike
1 Citations
We introduce the PESO (Particle Evolutionary Swarm Optimization) algorithm for solving single objective constrained optimization problems. PESO algorithm proposes two perturbation operators: “cperturbation” and “mperturbation”. The goal of these operators is to prevent premature convergence and the poor diversity issues observed in Particle Swarm Optimization (PSO) implementations. Constraint handling is based on simple feasibility rules, enhanced with a dynamic εtolerance approach applicable to equality constraints. PESO is compared and outperforms highly competitive algorithms representative of the state of the art.
more …
By
ReyesGalaviz, Orion F.; Verduzco, Antonio; ArchTirado, Emilio; ReyesGarcía, Carlos A.
Show all (4)
Post to Citeulike
9 Citations
This work presents the development and analysis of an automatic recognizer of infant cry, with the objective of classifying three classes, normal, hypo acoustics and asphyxia. We use acoustic feature extraction techniques like MFCC, for the acoustic processing of the cry’s sound wave, and a Feed Forward Input Delay neural network with training based on Gradient Descent with Adaptive BackPropagation for classification. We also use principal component analysis (PCA) in order to reduce vector’s size and to improve training time. The complete infant cry database is represented by plain text vector files, which allows the files to be easily processed in any programming environment. The paper describes the design, implementation as well as experimentation processes, and the analysis of results of each type of experiment performed.
more …
By
Gómez Cárdenas, Roberto; Sánchez, Erika Mata
Post to Citeulike
5 Citations
Security considerations play an increasingly important role for distributed computing. In today’s Internet age, academia requires sharing, distributing, merging, changing information, linking applications and other resources within and among universities and other related organizations. Because elearning systems are open, distributed and interconnected, then security becomes an important challenge in order to insure that interested actors only have access to the right information at the appropriate time. The purpose of this paper is to give an indepth understanding of most important security challenges that can be relevant for distributed elearning systems.
more …
By
Brena, Ramon F.; Martinez, Emmanuel
Post to Citeulike
In highly dynamic environments with uncertainty the elaboration of long or rigid plans is useless because the constructed plans are frequently dismissed by the arrival or new unexpected situations; in these cases, a “secondbest” plan could rescue the situation. We present a new realtime planning method where we take into consideration the number and quality of future options of the next action to choose, in contrast to most planning methods that just take into account the intrinsic value of the chosen plan or the maximum valued future option. We apply our method to the Robocup simulated soccer competition, which is indeed highly dynamic and involves uncertainty. We propose a specific architecture for implementing this method in the context of a player agent in the Robocup competition, and we present experimental evidence showing the potential of our method.
more …
By
Balogh, József; Salazar, Gelasio
Post to Citeulike
We use circular sequences to give an improved lower bound on the minimum number of (≤ k)sets in a set of points in general position. We then use this to show that if S is a set of n points in general position, then the number □(S) of convex quadrilaterals determined by the points in S is at least
$0.37553\binom{n}{4} + O(n^3)$
. This in turn implies that the rectilinear crossing number
$\overline{\hbox{\rm cr}}(K_n)$
of the complete graph K_{n} is at least
$0.37553\binom{n}{4} + O(n^3)$
. These improved bounds refine results recently obtained by Ábrego and FernándezMerchant, and by Lovász, Vesztergombi, Wagner and Welzl.
more …
By
CamargoSantacruz, Francisco; FraustoSolís, Juan; RamosQuintana, Fernando
Post to Citeulike
1 Citations
The dynamic nature of cooperative information systems (CIS) makes considerably more difficult the task of modeling interactions among agents. One of the most difficult problems related to the dynamic of a system is how to model and control simultaneously multiple interactions among agents in a friendly way. So far, traditional approaches deal with the problem of modeling interactions in static conditions and commonly with only two agents participating concurrently in cooperative tasks. Consequently, expressiveness becomes a problem related with the representation of multiple interactions in a satisfactory way, particularly in dynamic environments, such as ebusiness. The paper illustrates the application of a methodology based on Coloured Petri Nets (CP nets) in order to model the interaction mechanism in a CIS in an expressive way. This reduces the associated complexity in the representation of the dynamic of the system in a contact center environment, which is the start point to customer service, where concurrent interactions among users, technical people, process center and the contact center constitute a dynamic process that needs to be permanently monitored and controlled. The methodology provides us important advantages in the representation and reasoning for the interaction mechanism modeled in CIS. The use of CP nets allows analyzing the behavior of the system in the dynamic model using the individual and structural model.
more …
By
GonzálezMendoza, Miguel; HernándezGress, Neil; Titli, André
Post to Citeulike
This paper presents a study of the Quadratic optimization Problem (QP) lying on the learning process of Support Vector Machines (SVM). Taking the KarushKuhnTucker (KKT) optimality conditions, we present the strategy of implementation of the SVMQP following two classical approaches: i) active set, also divided in primal and dual spaces, methods and ii) interior point methods. We also present the general extension to treat large scale applications consisting in a general decomposition of the QP problem into smaller ones. In the same manner, we discuss some considerations to take into account to start the general learning process. We compare the performances of the optimization strategies using some wellknown benchmark databases.
more …
By
PeñaCabrera, Mario; LópezJuárez, Ismael; RiosCabrera, Reyes; CoronaCastuera, Jorge; Osorio, Roman
Show all (5)
Post to Citeulike
This paper shows a methodology for online recognition and classification of pieces in robotic assembly tasks and its application into an intelligent manufacturing cell. The performance of industrial robots working in unstructured environments can be improved using visual perception and learning techniques. The object recognition is accomplished using an Artificial Neural Network (ANN) architecture which receives a descriptive vector called CFD&POSE as the input. This vector represents an innovative methodology for classification and identification of pieces in robotic tasks, every stage of the methodology is described and the proposed algorithms explained. The vector compresses 3D object data from assembly parts and it is invariant to scale, rotation and orientation, and it also supports a wide range of illumination levels. The approach in combination with the fast learning capability of ART networks indicates the suitability for industrial robot applications as it is demonstrated through experimental results.
more …
By
AvilaRosas, Arturo
Post to Citeulike
Because Virtual Organisations (VOs) essentially involve cooperating two or more organisations or agents to pursue a common objective, satisfactory cooperation is vital to their success. However, before an agent made the decision to go ahead with the VO, it needs to be confident that the rest of the potential partners will be act cooperatively. We show that reputation is a basic ingredient in the formation of VOs. Reputation is computed using an adaptive algorithm, so agents can learn and adapt their reputation models of their partners according to their recent behaviour. Our approach is especially powerful if the agent participates in a VO in which the members can change their behaviour to exploit their partners. The reputation model presented in this paper deals with the questions of deception and fraud that have been ignored in current models of VO formation.
more …
By
Gomez, Juan Carlos; Fuentes, Olac; Puerari, Ivanio
Post to Citeulike
Fitting brightness profiles of galaxies in one dimension is frequently done because it suffices for some applications and is simple to implement, but many studies now resort to twodimensional fitting, because many wellresolved, nearby galaxies are often poorly fitted by standard onedimensional models. For the fitting we use a model based on de Vaucoleurs and exponential functions that is represented as a set of concentric generalized ellipses that fit the brightness profile of the image. In the end, we have an artificial image that represents the light distribution in the real image, then we make a comparison between such artificial image and the original to measure how close the model is to the real image. The problem can be seen as an optimization problem because we need to minimize the difference between the original optical image and the model, following a normalized Euclidean distance.
In this work we present a solution to such problem from a point of view of optimization using a hybrid algorithm, based on the combination of Evolution Strategies and the QuasiNewton method. Results presented here show that the hybrid algorithm is very well suited to solve the problem, because it can find the solutions in almost all the cases and with a relatively low cost.
more …
By
GarcíaPerera, Paola L.; MexPerera, Carlos; NolazcoFlores, Juan A.
Post to Citeulike
In this research we propose a new scheme for generating binary vectors, which can be used as keys for cryptographic purposes. These vectors are obtained from the speech signal and from the spoken user passphrase. The key bits are built using the Automatic Speech Recognition Technology to detect the phoneme limits in the speech utterance and the Support Vector Machines technique for classification. Linear prediction cepstral coefficients, (first and second derivatives) of the speech signal are calculated to create a 39dimensional hyperspace. Then a hyperplane is created using an RBF kernel, and the SVM classifies the user’s phonemes. Applying our method to a set of 10, 20, 30 and 50 speakers from the YOHO database, the results show that this method is sufficiently robust to reliably regenerate the cryptographic key.
more …
By
Chesñevar, Carlos I.; Brena, Ramón F.; Aguirre, Jose L.
Post to Citeulike
Distributing pieces of knowledge in large, usually distributed organizations is a central problem in Knowledge and Organization Management. Policies for distributing knowledge and information are very often incomplete, or conflict with each other. As a consequence, decision processes for information distribution may be difficult to formalize on the basis of a rationally justified procedure.
This paper presents an argumentative approach to cope with the above problem based on Defeasible Logic Programming, a logic programming formalism for defeasible argumentation. Conflicts among policies are solved on the basis of a dialectical analysis whose outcome determines to which specific users different pieces of knowledge are to be delivered.
more …
By
Muhammad, Aslam; Enríquez, Ana María Martínez; Decouchant, Dominique
Post to Citeulike
This paper presents our approach to design and provide elaborated awareness coordination functions for cooperative production of complex Web shared documents. We designed a Group Awareness Inference Engine (GAIE) that catches working focus of collaborators and then deduces some of their potential interests for communication to enhance coordination and cooperative production.
more …
By
AlvarezGallegos, Jaime; Villar, Carlos Alberto Cruz; Flores, Edgar Alfredo Portilla
Post to Citeulike
4 Citations
This paper presents a dynamic optimization approach based on the differential evolution (DE) strategy which is applied to the concurrent optimal design of a continuously variable transmission (CVT). The structurecontrol integration approach is used to state the concurrent optimal design as a dynamic optimization problem which is solved using the Constraint Handling Differential Evolution (CHDE) algorithm. The DE strategy is compared with the sequential approach. The results presented here demonstrate that the DE strategy is less expensive than the sequential approach from the computational implementation point of view.
more …
By
Fernandez, Luis Paster Sanchez; Pogrebnyak, Oleksiy; Marquez, Cornelio Yanez
Post to Citeulike
1 Citations
The goal of this paper is to introduce an efficient predictive supervisory method for the trending of variables of technological processes and devices, with low runtime, for periodic analysis of high frequency, relatively (periods smaller than a second). This method allows to predict the time in which a process variable will arrive to an abnormal or important values. The data obtained in real time for each variable are used to estimate the parameters of a mathematical model. This model is continuous and of firstorder or secondorder (critically damped, overdamped or underdamped). An optimization algorithm is used for estimating the parameters. Before performing the estimation, the most appropriate model is determined by means of a feedforward neural network.
more …
By
HernándezAguirre, A.
Post to Citeulike
Summary
This chapter is about the synthesis of combinational logic circuits using evolvable hardware. The chapter introduces several approaches recently followed by a number of researchers to tackle this problem. Research trends, immediate and for years to come, are presented.
more …
By
Bolshakov, Igor A.
Post to Citeulike
1 Citations
Malapropism is a type of semantic errors. It replaces one content word by another content word similar in sound but semantically incompatible with the context and thus destructing text cohesion. We propose to signal a malapropism when a pair of syntactically linked content words in a text exhibits the value of a specially defined Semantic Compatibility Index (SCI) lower than a predetermined threshold. SCI is computed through the web statistics of occurrences of words got together and apart. A malapropism detected, all possible candidates for correction of both words are taken from precompiled dictionaries of paronyms, i.e. words distant a letter or a few prefixes or suffixes from one another. Heuristic rules are proposed to retain only a few highly SCIranked candidates for the user’s decision. The experiment on malapropism detection and correction is done for a hundred Russian text fragments—mainly from the web newswire—in both correct and falsified form, as well as for several hundreds of correction candidates. The raw statistics of occurrences is taken from the web searcher Yandex. Within certain limitations, the experiment gave very promising results.
more …
By
HernándezGarcía, Josué A.; PérezMeana, Héctor; NakanoMiyatake, Mariko
Post to Citeulike
Several video detection systems that use a simple system of motion detection (if something moves, is generated an alarm) have been proposed, for this reason we trust part of the process to the human interpretation. Recent studies have demonstrated that a person is almost impossible to kindly watch a static scene in a monitor more than 20 minutes, doing that traditional systems of video monitoring as CCTV systems are little reliable, also, it is necessary to add numerous and annoying the false alarms generated by the few elimination of irrelevant information (color, light, shade, etc.) within the scene. The artificial vision nowadays allows having an automatic system of monitoring with the capacities to identify real threats and alert of security at the same time that they are happening. This paper presents a method of video motion detection that bases its use on an algorithm of discrimination able to eliminate the irrelevant information caused by natural effects (sun, moon, wind, etc.) or animals, maintaining the maximum of details on the image, allowing a better detection of motion through the distance of Hamming doubly justified, reducing in this way rate of false alarms, obtaining a method of motion detection automatic and reliable. In this paper is mentioned the comparison with other techniques, demonstrating itself that the proposed method gives better results. The obtained results show the basic characteristics of this method of detection.
more …
By
RodriguezTello, Eduardo; Hao, JinKao; TorresJimenez, Jose
Post to Citeulike
In this paper the Minimum Linear Arrangement (MinLA) problem is studied within the framework of memetic algorithms (MA). A new dedicated recombination operator called Trajectory Crossover (TX) is introduced and its performance is compared with four previous crossover operators. It is shown that the TX crossover induces a better population diversity. The MA using TX is evaluated on a set of wellknown benchmark instances and is compared with several stateofart MinLA algorithms.
more …
By
AcostaElias, Jesús; Reyes, B. Pineda; Leos, E. Chavez; OchoaCardiel, Alejandro; Recio, Mario; GutierrezNavarro, Omar
Show all (6)
Post to Citeulike
In this paper we evaluate our own weak consistency algorithm, which is called the ”Fast Consistency Algorithm”, and whose main aim is optimizing the propagation of changes introducing a preference for nodes and zones of the network which have greatest demand. Weak consistency algorithms allow us to propagate changes in a large, arbitrary changing storage network in a selforganizing way. These algorithms generate very little traffic overhead; they have low latency and are scalable, in addition to being fault tolerant. The algorithm has been simulated over ns2, and measured its performance for complex spatial distributions of demand, including Internet like selfsimilar fractal distributions of demand. The impulse response of the algorithm has been characterized. We conclude that considering application parameters such as demand in the event or change propagation mechanism to: 1) prioritize probabilistic interactions with neighbors with higher demand, and 2) including little changes on the logical topology (leader interconnection in hierarchical topology ), gives a surprising improvement in the speed of change propagation perceived by most users. In other words, it satisfies the greatest demand in the shortest amount of time.
more …
By
Valle, Gerardo; Gómez Cárdenas, Roberto
Post to Citeulike
The aim of this paper is to show some solutions for key management in ad hoc networks. The major problem in providing security services in such infrastructure less networks is how to manage the cryptographic keys that are needed. In order to design practical and sufficient key management systems it is necessary to understand the characteristics of ad hoc networks and why traditional key management systems cannot be used.
more …
By
NolazcoFlores, Juan Arturo
Post to Citeulike
In this work, we propose to use as source of speech information the ShortMelfrequencyCepstra Time Transform (SMCTT), c_{τ}(t). The SMCTT studies the time properties at quefrency τ. Since the SMCTT signal, c_{τ}(t), comes from a nonlinear transformation of the speech signal, s(t), it makes the STMCTT a potential signal with new properties in time, frequency, quefrency, etc. The goal of this work is to present the performance of the SMCTT signal when the SMCTT is applied to an Automatic Speech Recognition (ASR) task. Our experiment results show that important information is given by this SMCTT waveform, c_{τ}(t).
more …
By
Jian, Bing; Vemuri, Baba C.; Marroquin, José L.
Post to Citeulike
7 Citations
Automatic multimodal image registration is central to numerous tasks in medical imaging today and has a vast range of applications e.g., image guidance, atlas construction, etc. In this paper, we present a novel multimodal 3D nonrigid registration algorithm where in 3D images to be registered are represented by their corresponding local frequency maps efficiently computed using the Riesz transform as opposed to the popularly used Gabor filters. The nonrigid registration between these local frequency maps is formulated in a statistically robust framework involving the minimization of the integral squared error a.k.a. L_{2}E (L_{2} error). This error is expressed as the squared difference between the true density of the residual (which is the squared difference between the nonrigidly transformed reference and the target local frequency representations) and a Gaussian or mixture of Gaussians density approximation of the same. The nonrigid transformation is expressed in a Bspline basis to achieve the desired smoothness in the transformation as well as computational efficiency.
The key contributions of this work are (i) the use of Riesz transform to achieve better efficiency in computing the local frequency representation in comparison to Gabor filterbased approaches, (ii) new mathematical model for localfrequency based nonrigid registration, (iii) analytic computation of the gradient of the robust nonrigid registration cost function to achieve efficient and accurate registration. The proposed nonrigid L_{2}Ebased registration is a significant extension of research reported in literature to date. We present experimental results for registering several real data sets with synthetic and real nonrigid misalignments.
more …
By
Sobczyk, Garret; Erlebacher, Gordon
Post to Citeulike
1 Citations
The structures of matrix algebra and geometric algebra are completely compatible and in many ways complimentary, each having their own advantages and disadvantages. We present a detailed study of the hybrid 2 × 2 matrix geometric algebra M(2,IG) with elements in the 8 dimensional geometric algebra IG=IG_{3} of Euclidean space. The resulting hybrid structure, isomorphic to the geometric algebra IG_{4,1} of de Sitter space, combines the simplicity of 2× 2 matrices and the clear geometric interpretation of the elements of IG. It is well known that the geometric algebra IG(4,1) contains the 3dimensional affine, projective, and conformal spaces of Möbius transformations, together with the 3dimensional horosphere which has attracted the attention of computer scientists and engineers as well as mathematicians and physicists. In the last section, we describe a sophisticated computer software package, based on Wolfram’s Mathematica, designed specifically to facilitate computations in the hybrid algebra.
more …
By
RiveraRovelo, Jorge; BayroCorrochano, Eduardo
Post to Citeulike
This paper presents three different tasks: segmentation of medical images, volume representation and nonrigid registration. The first task is a necessary step before volume representation ant it is done with a simple but effective strategy using tomographic images, combining texture and boundary information in a region growing strategy, obtaining good results. For the second task, we present a new approach to model 2D surfaces and 3D volumetric data based on marching cubes idea using however spheres (modeling the surface of an object using spheres allows us to reduce the number of primitives representing it and to benefit from such reduction the registration process of two objects). We compare our approach based on marching cubes idea with other one using Delaunay tetrahedrization, and the results show that our proposed approach reduces considerably the number of spheres. Finally, we show how to do nonrigid registration of two volumetric data represented as sets of spheres using 5dimensional vectors in conformal geometric algebra.
more …
By
Muñoz Zavala, Angel E.; Villa Diharce, Enrique R.; Hernández Aguirre, Arturo
Post to Citeulike
4 Citations
This papers proposes an enhanced Particle Swarm Optimization algorithm with multiobjective optimization concepts to handle constraints, and operators to keep diversity and exploration. Our approach, PESDRO, is found robust at solving redundancy and reliability allocation problems with two objective functions: reliability and cost. The approach uses redundancy of components, diversity of suppliers, and incorporates a new concept called Distribution Optimization. The goal is the optimal design for reliability of coherent systems. The new technique is compared against algorithms representative of the stateoftheart in the area by using a wellknown benchmark. The experiments indicate that the proposed approach matches and often outperforms such methods.
more …
By
Vázquez, Roberto Antonio; Sossa, Humberto; Barrón, Ricardo
Post to Citeulike
Object recognition under occlusions is an important problem in computer vision, not yet completely solved. In this note we describe a simple but effective technique for the recognition objects under occlusions. The proposal uses the most distinctive parts of the objects for their further detection. During training, the proposal, first detects the distinctive parts of each object. For each of these parts an invariant description in terms of invariants features is next computed. With these invariant descriptions a specially designed set of associative memories (AMs) is trained. During object detection, the proposal, first looks for the important parts of the objects by means of the already trained AM. The proposal is tested with a bank of images of real objects and compared with other similar reported techniques.
more …
By
GaliciaHaro, Sofía N.; Gelbukh, Alexander
Post to Citeulike
The objective of this work is to automatically determine, in an unsupervised manner, Spanish prepositional phrases of the type preposition – nominal phrase – preposition (P(NP(P) that behave in a sentence as a lexical unit and their semantic and syntactic properties cannot be deduced from the corresponding properties of each simple form, e.g., por medio de (by means of), a fin de (in order to), con respecto a (with respect to). We show that idiomatic P(NP(P combinations have some statistical properties distinct from those of usual idiomatic collocations. We also explore a way to differentiate P(NP(P combinations that could perform either as a regular prepositional phrase or as idiomatic prepositional phrase.
more …
By
Coello Coello, Carlos A.
Post to Citeulike
5 Citations
This paper provides a brief introduction to evolutionary algorithms including some of their applications. Our discussion includes short descriptions of genetic algorithms, evolution strategies, evolutionary programming and genetic programming. Then, a few case studies involving applications of evolutionary algorithms in realworld problems are analyzed. In the final part of the paper, some of the current research directions in this area are provided.
more …
