Showing 1 to 100 of 287 matching Articles
Results per page:
Export (CSV)
By
Chakraborty, Debrup; Nandi, Mridul
10 Citations
HCTR was proposed by Wang, Feng and Wu in 2005. It is a mode of operation which provides a tweakable strong pseudorandom permutation. Though HCTR is quite an efficient mode, the authors showed a cubic security bound for HCTR which makes it unsuitable for applications where tweakable strong pseudorandom permutations are required. In this paper we show that HCTR has a better security bound than what the authors showed. We prove that the distinguishing advantage of an adversary in distinguishing HCTR and its inverse from a random permutation and its inverse is bounded above by 4.5 σ^{2}/2^{n}, where n is the blocklength of the blockcipher and σ is the number of nblock queries made by the adversary (including the tweak).
more …
By
Beuchat, JeanLuc; Brisebarre, Nicolas; Detrey, Jérémie; Okamoto, Eiji; RodríguezHenríquez, Francisco
Show all (5)
18 Citations
In this article we propose a study of the modified Tate pairing in characteristics two and three. Starting from the η_{T} pairing introduced by Barreto et al. [1], we detail various algorithmic improvements in the case of characteristic two. As far as characteristic three is concerned, we refer to the survey by Beuchat et al. [5]. We then show how to get back to the modified Tate pairing at almost no extra cost. Finally, we explore the tradeoffs involved in the hardware implementation of this pairing for both characteristics two and three. From our experiments, characteristic three appears to have a slight advantage over characteristic two.
more …
By
Chang, Donghoon; Nandi, Mridul
22 Citations
The classical design principle MerkleDamgård [13,6] is scrutinized by many ways such as Joux’s multicollision attack, KelseySchneier second preimage attack etc. In TCC’04, Maurer et al. introduced a strong security notion called as “indifferentiability” for a hash function based on a compression function. The classical design principle is also insecure against this strong security notion whereas chopMD hash is secure with the security bound roughly σ^{2}/2^{s} where s is the number of chopped bits and σ is the total number of message blocks queried by a distinguisher. In case of n = 2s where n is the output size of a compression function, the value σ to get a significant bound is 2^{s/2} which is the birthday complexity, where the hash output size is sbit. In this paper, we present an improved security bound for chopMD. The improved bound shown in this paper is (3(n − s) + 1)q/2^{s} + q/2^{n − s − 1} + σ^{2}/2^{n + 1} where q is the total number of queries. In case of n = 2s, chopMD is indifferentiablysecure if q = O(2^{s}/(3s + 1)) and σ = O(2^{n/2}) which are beyond the birthday complexity. We also present a design principle for an nbit hash function based on a compression function
$f : {0,1}^{2n+b} {\Rightarrow} {0,1}^n$
and show that the indifferentiability security bound for this hash function is roughly (3n + 1)σ/2^{n}. So, the new design of hash function is secondpreimage and rmulticollision secure as long as the query complexity (the number of message blocks queried) of an attacker is less than 2^{n}/(3n + 1) or 2^{n(r − 1)/r} respectively.
more …
By
Marron, Mark; Hermenegildo, Manuel; Kapur, Deepak; Stefanovic, Darko
Show all (4)
9 Citations
The performance of heap analysis techniques has a significant impact on their utility in an optimizing compiler. Most shape analysis techniques perform interprocedural dataflow analysis in a contextsensitive manner, which can result in analyzing each procedure body many times (causing significant increases in runtime even if the analysis results are memoized). To improve the effectiveness of memoization (and thus speed up the analysis) project/extend operations are used to remove portions of the heap model that cannot be affected by the called procedure (effectively reducing the number of different contexts that a procedure needs to be analyzed with). This paper introduces project/extend operations that are capable of accurately modeling properties that are important when analyzing nontrivial programs (sharing, nullity information, destructive recursive functions, and composite data structures). The techniques we introduce are able to handle these features while significantly improving the effectiveness of memoizing analysis results (and thus improving analysis performance). Using a range of well known benchmarks (many of which have not been successfully analyzed using other existing shape analysis methods) we demonstrate that our approach results in significant improvements in both accuracy and efficiency over a baseline analysis.
more …
By
García, Vicente; Mollineda, Ramón A.; Sánchez, J. Salvador
2 Citations
In this paper, we introduce a new approach to evaluate and visualize the classifier performance in twoclass imbalanced domains. This method defines a twodimensional space by combining the geometric mean of class accuracies and a new metric that gives an indication of how balanced they are. A given point in this space represents a certain tradeoff between those two measures, which will be expressed as a trapezoidal function. Besides, this evaluation function has the interesting property that it allows to emphasize the correct predictions on the minority class, which is often considered as the most important class. Experiments demonstrate the consistency and validity of the evaluation method here proposed.
more …
By
Ledeneva, Yulia
1 Citations
The task of extractive summarization consists in producing a text summary by extracting a subset of text segments, such as sentences, and concatenating them to form a summary of the original text. The selection of sentences is based on terms they contain, which can be single words or multiword expressions. In a previous work, we have suggested socalled Maximal Frequent Sequences as such terms. In this paper, we investigate the effect of preprocessing on the process of selecting such sequences. Our results suggest that the accuracy of the method is, contrary to expectations, not seriously affected by preprocessing—which is both bad and good news, as we show.
more …
By
Ledeneva, Yulia; Gelbukh, Alexander; GarcíaHernández, René Arnulfo
10 Citations
Automatic text summarization helps the user to quickly understand large volumes of information. We present a language and domainindependent statisticalbased method for singledocument extractive summarization, i.e., to produce a text summary by extracting some sentences from the given text. We show experimentally that words that are parts of bigrams that repeat more than once in the text are good terms to describe the text’s contents, and so are also socalled maximal frequent sentences. We also show that the frequency of the term as term weight gives good results (while we only count the occurrences of a term in repeating bigrams).
more …
By
Nebro, Antonio Jesús; Durillo, Juan José; Coello Coello, Carlos A.; Luna, Francisco; Alba, Enrique
Show all (5)
15 Citations
An open issue in multiobjective optimization is designing metaheuristics that reach the Pareto front using a low number of function evaluations. In this paper, we adopt a benchmark composed of three wellknown problem families (ZDT, DTLZ, and WFG) and analyze the behavior of six stateoftheart multiobjective metaheuristics, namely, NSGAII, SPEA2, PAES, OMOPSO, AbYSS, and MOCell, according to their convergence speed, i.e., the number of evaluations required to obtain an accurate Pareto front. By using the hypervolume as a quality indicator, we measure the algorithms converging faster, as well as their hit rate over 100 independent runs. Our study reveals that modern multiobjective metaheuristics such as MOCell, OMOPSO, and AbYSS provide the best overall performance, while NSGAII and MOCell achieve the best hit rates.
more …
By
HernándezRodríguez, Selene; CarrascoOchoa, J. A.; MartínezTrinidad, J. Fco.
The k nearest neighbor (kNN) classifier has been extensively used as a nonparametric technique in Pattern Recognition. However, in some applications where the training set is large, the exhaustive kNN classifier becomes impractical. Therefore, many fast kNN classifiers have been developed to avoid this problem. Most of these classifiers rely on metric properties, usually the triangle inequality, to reduce the number of prototype comparisons. However, in soft sciences, the prototypes are usually described by qualitative and quantitative features (mixed data), and sometimes the comparison function does not satisfy the triangle inequality. Therefore, in this work, a fast k most similar neighbor (kMSN) classifier, which uses a Tree structure and an Approximating and Eliminating approach for Mixed Data, not based on metric properties (Tree AEMD), is introduced. The proposed classifier is compared against other fast kNN classifiers.
more …
By
OlmedoAguirre, José Oscar; Rosa, Mónica Rivera; MoralesLuna, Guillermo
System modeling, analysis and visualization are becoming a common practice for the design of distributed intelligent systems since the wide adoption of the Unified Modeling Language (UML). However, UML cannot describe important behavioral properties such as context awareness as required for ubiquitous computing. In this paper, we present Context Aware UML Sequence diagrams (CA UMLS), an experimental visual programming language that extends UML sequence diagrams with data/ object spaces to represent computational context awareness. The programming language provides the means to describe the eventconditionaction (ECA) rules that govern complex nomadic user behavior and to visualize their effect. The ECA rules are compiled into common concurrent programming abstractions by introducing structuring notions of object creation, synchronization, and communication, along with sequential and selective composition of simpler rules. The contribution of this work is in providing programming abstractions that facilitate the design of contextaware applications for ubiquitous and nomadic computing.
more …
By
Ingaramo, Diego; Pinto, David; Rosso, Paolo; Errecalde, Marcelo
Show all (4)
7 Citations
Short texts clustering is one of the most difficult tasks in natural language processing due to the low frequencies of the document terms. We are interested in analysing these kind of corpora in order to develop novel techniques that may be used to improve results obtained by classical clustering algorithms. In this paper we are presenting an evaluation of different internal clustering validity measures in order to determine the possible correlation between these measures and that of the FMeasure, a wellknown external clustering measure used to calculate the performance of clustering algorithms. We have used several shorttext corpora in the experiments carried out. The obtained correlation with a particular set of internal validity measures let us to conclude that some of them may be used to improve the performance of text clustering algorithms.
more …
By
German, Ernesto; Sheremetov, Leonid
2 Citations
Interaction engineering is a key issue to effectively build MultiAgent Systems. It requires software abstractions, components and control structures to manage interactions among agents and to improve infrastructures at runtime. We propose a framework for automatic processing of interactions generated using FIPAACL, a language widely accepted for agent platforms. This framework includes three elements: i) an agent interaction architecture to systematize interaction processing tasks, ii) interaction models to build reusable validated code used to check different phases of interaction processing associated with message semantics, and iii) components and control structures implementing interaction architecture for a particular agent platform. The paper describes the implementation details of the proposed approach developed within the CAPNET agent platform and illustrates it by example.
more …
By
RuizVanoye, Jorge A.; DíazParra, Ocotlán; N., Vanesa Landero
In this paper we propose: (1) the use of discriminant analysis as a means for predictive learning (datamining techniques) aiming at selecting metaheuristic algorithms and (2) the use of a metric for improving the selection of the algorithms that best solve a given instance of the Asymmetric Traveling Salesman Problem (ATSP). The only metric that had existed so far to determine the best algorithm for solving an ATSP instance is based on the number of cities; nevertheless, it is not sufficiently adequate for discriminating the best algorithm for solving an ATSP instance, thus the necessity for devising a new metric through the use of datamining techniques.
more …
By
Esponda, Fernando
6 Citations
In this paper we present a method for hiding a list of data by mixing it with a large amount of superfluous items. The technique uses a device known as a negative database which stores the complement of a set rather that the set itself to include an arbitrary number of garbage entries efficiently. The resulting structure effectively hides the data, without encrypting it, and obfuscates the number of data items hidden; it prevents arbitrary data lookups, while supporting simple membership queries; and can be manipulated to reflect relational algebra operations on the original data.
more …
By
Cho, Eunjung; Bourgeois, Anu G.; FernándezZepeda, José Alberto
A Molecular Dynamics (MD) system is defined by the position and momentum of particles and their interactions. The dynamics of a system can be evaluated by an Nbody problem and the simulation is continued until the energy reaches equilibrium. Many applications use MD for biomolecular simulations and the simulations are performed in multiscale of time and length. The simulations of the relevant scales require strong and fast computing power, but it is even beyond the reach of current fastest supercomputers. In this paper, we design RMesh Algorithms that require O(N) time complexity for the Direct method for MD simulations and O(r)+O(logM) time complexity for the Multigrid method, where r is N/M and M is the size of RMesh. Our work supports the theory that reconfigurable models are a good direction for biological studies which require high computing power.
more …
By
Czyzowicz, J.; Dobrev, S.; GonzálezAguilar, H.; Kralovic, R.; Kranakis, E.; Opatrny, J.; Stacho, L.; Urrutia, J.
Show all (8)
4 Citations
The problem of computing locally a coloring of an arbitrary planar subgraph of a unit disk graph is studied. Each vertex knows its coordinates in the plane, can directly communicate with all its neighbors within unit distance. Using this setting, first a simple algorithm is given whereby each vertex can compute its color in a 9coloring of the planar graph using only information on the subgraph located within at most 9 hops away from it in the original unit disk graph. A more complicated algorithm is then presented whereby each vertex can compute its color in a 7coloring of the planar graph using only information on the subgraph located within a constant number of hops away from it.
more …
By
GaliciaHaro, Sofía N.
1 Citations
We consider temporal expressions formed by a noun of time reinforced by an adverb of time, in order to extend the range of annotation of temporal expressions. Fro this, we analyze some groups to build finite state automata to automatically determine such type of expressions. To determine the extent of annotation, we present a method for obtaining the most preferable variants from Internet. We analyze some groups to capture their meaning.
more …
By
Cruz Reyes, Laura; Delgado Orta, José F.; González Barbosa, Juan J.; Torres Jimenez, José; Fraire Huacuja, Héctor J.; Arrañaga Cruz, Bárbara A.
Show all (6)
7 Citations
This work presents a methodology of solution for the wellknown vehicle routing problem (VRP) based on an ant colony system heuristic algorithm (ACS), which is applied to optimize the delivery process of RoSLoP (RoutingSchedulingLoading Problem) identified in the company case of study. A first version of this algorithm models six variants of VRP and its solution satisfies the 100% of demands of the customers. The new version of the algorithm can solve 11 variants of VRP as a rich VRP. Experiments were carried out with real instances. The new algorithm shows a saving of two vehicles with regard to the first version, reducing the operation costs of the company. These results prove the viability of using heuristic methods and optimization techniques to develop new software applications.
more …
By
Wiederhold, Petra; Morales, Sandino
9 Citations
This paper deals with a thinning algorithm proposed in 2001 by Kovalevsky, for 2D binary images modelled by cell complexes, or, equivalently, by Alexandroff T_{0} spaces. We apply the general proposal of Kovalevsky to cell complexes corresponding to the three possible normal tilings of congruent convex polygons in the plane: the quadratic, the triangular, and the hexagonal tilings. For this case, we give a theoretical foundation of Kovalevsky’s thinning algorithm: We prove that for any cell, local simplicity is sufficient to satisfy simplicity, and that both are equivalent for certain cells. Moreover, we show that the parallel realization of the algorithm preserves topology, in the sense that the numbers of connected components both of the object and of the background, remain the same. The paper presents examples of skeletons obtained from the implementation of the algorithm for each of the three cell complexes under consideration.
more …
By
HernándezRodríguez, Selene; CarrascoOchoa, J. Ariel; MartínezTrinidad, J. Fco.
1 Citations
The k nearest neighbor (kNN) classifier has been a widely used nonparametric technique in Pattern Recognition. In order to decide the class of a new prototype, the kNN classifier performs an exhaustive comparison between the prototype to classify (query) and the prototypes in the training set T. However, when T is large, the exhaustive comparison is expensive. To avoid this problem, many fast kNN algorithms have been developed. Some of these algorithms are based on ApproximatingEliminating search. In this case, the Approximating and Eliminating steps rely on the triangle inequality. However, in soft sciences, the prototypes are usually described by qualitative and quantitative features (mixed data), and sometimes the comparison function does not satisfy the triangle inequality. Therefore, in this work, a fast k most similar neighbour classifier for mixed data (AEMD) is presented. This classifier consists of two phases. In the first phase, a binary similarity matrix among the prototypes in T is stored. In the second phase, new Approximating and Eliminating steps, which are not based on the triangle inequality, are presented. The proposed classifier is compared against other fast kNN algorithms, which are adapted to work with mixed data. Some experiments with real datasets are presented.
more …
By
TéllezValero, Alberto; MontesyGómez, Manuel; VillaseñorPineda, Luis; Peñas, Anselmo
Show all (4)
1 Citations
Nowadays there exist several kinds of question answering systems. According to recent evaluation results, most of these systems are complementary (i.e., each one is better than the others in answering some specific type of questions). This fact indicates that a pertinent combination of various systems may allow improving the best individual result. This paper focuses on this problem. It proposes using an answer validation method to handle this combination. The main advantage of this approach is that it does not rely on internal system’s features nor depend on external answer’s redundancies. Experimental results confirm the appropriateness of our proposal. They mainly show that it outperforms individual system’s results as well as the precision obtained by a redundancybased combination strategy.
more …
By
Escalante, H. Jair; Montes, Manuel; Sucar, L. Enrique
2 Citations
Accuracy of current automatic image labeling methods is under the requirements of annotationbased image retrieval systems. The performance of most of these labeling methods is poor if we just consider the most relevant label for a given region. However, if we look within the set of the top− k candidate labels for a given region, accuracy of most of these systems is improved. In this paper we take advantage of this fact and propose a method (NBI) based on word cooccurrences that uses the naïve Bayes formulation for improving automatic image annotation methods. Our approach utilizes cooccurrence information of the candidate labels for a region with those candidate labels for the other surrounding regions, within the same image, for selecting the correct label. Cooccurrence information is obtained from an external collection of manually annotated images: the IAPRTC12 benchmark. Experimental results using a k −nearest neighbors method as our annotation system, give evidence of significant improvements after applying the NBI method. NBI is efficient since the cooccurrence information was obtained offline. Furthermore, our method can be applied to any other annotation system that ranks labels by their relevance.
more …
By
FraustoSolis, Juan; MartinezRios, Felix
1 Citations
Satisfiability (SAT) Problem is an NPComplete problem which means no deterministic algorithm is able to solve it in a polynomial time. Simulated Annealing (SA) can find very good solutions of SAT instances if its control parameters are correctly tuned. SA can be tuned experimentally or by using a Markov approach; the latter has been shown to be the most efficient one. Moreover Golden Ratio (GR) is an unconventional technique used to solve many problems. In this paper a new algorithm named Golden Ratio for Simulated Annealing (GRSA) is presented; it is tuned for three different cooling schemes. GRSA uses GR to dynamically decrease the SA temperature and a Markov Model to tune its parameters. Two SA tuned versions are compared in this paper: GRSA and a classical SA. Experimentation shows that the former is much more efficient than the latter.
more …
By
GarcíaBañuelos, Luciano
8 Citations
BPMN is a notation for business process modeling. Process models can be complex, for instance, with unstructured (cyclic) topologies. BPEL, on the other hand, is the choice for web service orchestration. This paper presents an approach to systematically identifying and classifying subgraphs in a BPMN model that may be translated to BPEL code. Most of existing methods rely on exhaustive search. In contrast, we partition the BPMN model into singleentry singleexit regions which are then classified according to control flow information. This information is gathered by using a reachability analysis based on dataflow equations.
more …
By
GutiérrezGarcía, J. Octavio; Koning, JeanLuc; RamosCorchado, Félix F.
2 Citations
The achievement of common objectives in multiagent systems is only possible through interaction and coordination; in order to implement both aspects in a effective manner, rules to direct the behavior of a group of agents are necessary, however, existing rules are usually static, inflexible, and inappropriate for large systems, where dynamic interaction takes place. We propose modeling agent behavior by means of obligations, utilized as social norms, delineating agents’ roles as independent components, which can be grouped into organizational structures. Moreover, such organizations can be deployed on a service oriented platform, where the composition of organizations leads to the creation of new services.
more …
By
Schütze, Oliver; Vasile, Massimiliano; Coello Coello, Carlos A.
6 Citations
In this paper, we address multiobjective space mission design problems. We argue that it makes sense from the practical point of view to consider in addition to the ‘optimal’ trajectories (in the Pareto sense) also approximate or nearly optimal solutions since this can lead to a significant larger variety for the decision maker. For this, we suggest a novel MOEA which is a modification of the wellknown NSGAII algorithm equipped with a recently proposed archiving strategy which aims for the storage of the set of approximate solution of a given MOP. Using this algorithm we will examine several space missions and demonstrate the benefit of the novel approach.
more …
By
Rajsbaum, Sergio; Raynal, Michel; Travers, Corentin
13 Citations
In the Iterated Immediate Snapshot model (
${\mathit{IIS}}$
) the memory consists of a sequence of oneshot Immediate Snapshot (
$\mathit{IS}$
) objects. Processes access the sequence of
$\mathit{IS}$
objects, onebyone, asynchronously, in a waitfree manner; any number of processes can crash. Its interest lies in the elegant recursive structure of its runs, hence of the ease to analyze it round by round. In a very interesting way, Borowsky and Gafni have shown that the
${\mathit{IIS}}$
model and the read/write model are equivalent for the waitfree solvability of decision tasks.
This paper extends the benefits of the
$\mathit{IIS}$
model to partially synchronous systems. Given a shared memory model enriched with a failure detector, what is an equivalent
$\mathit{IIS}$
model? The paper shows that an elegant way of capturing the power of a failure detector and other partially synchronous systems in the
${\mathit{IIS}}$
model is by restricting appropriately its set of runs, giving rise to the Iterated Restricted Immediate Snapshot model (
$\mathit{IRIS}$
).
more …
By
Martínez, Alicia; Pastor, Oscar; Mylopoulos, John; Giorgini, Paolo
Show all (4)
2 Citations
The Software Engineering community is placing increasing emphasis on understanding the organizational context of a new software system before its development. In this context, several research projects focus on mechanisms that facilitate the generation of a software system from early requirements specifications. However, none of these has proposed so far a systematic process for transforming an organizational model into a late requirements one. This paper presents a methodological approach to precisely this problem. In the proposed method, business goals constitute the basis for determining the relevant plans to be supported by the systemtobe. A pattern language is then used to systematically carry out the transformation from an organizational model into a late requirements model. The Tropos framework serves as baseline for this work. However, our work extends Tropos by proposing rules that support the model transformation process, thereby making organizational modeling an integral part of the software development process.
more …
By
Korzhik, Valery; Imai, Hideki; Shikata, Junji; MoralesLuna, Guillermo; Gerling, Ekaterina
Show all (5)
4 Citations
It is very common to use the notion of relative entropy (or KullbackLeibler divergence) as a measure for the discrimination difficulty among the hypotheses testing of presence and absence within a steganographic system. Relative entropy is not a symmetric function and sometimes it is very hard to compute its values. We propose to customize the notion of Bhattacharyya distance to the solution of the same problem. The main properties of Bhattacharyya distance are presented. We show applications of this new steganographic system security criterion within the model with a Gaussian colored covertext and within spreadspectrum watermarking by a white Gaussian sequence.
more …
By
AldapePérez, Mario; YáñezMárquez, Cornelio; ArgüellesCruz, Amadeo José
1 Citations
Associative memories have a number of properties, including a rapid, compute efficient bestmatch and intrinsic noise tolerance that make them ideal for many applications. However, a significant bottleneck to the use of associative memories in realtime systems is the amount of data that requires processing. Notwithstanding, AlphaBeta Associative Memories have been widely used for color matching in industrial processes [1], text translation [2] and image retrieval applications [3]. The aim of this paper is to present the work that produced a dedicated hardware design, implemented on a field programmable gate array (FPGA) that applies the AlphaBeta Associative Memories model for fingerprint verification tasks. Along the experimental phase, performance of the proposed associative memory architecture is measured by learning large sequences of symbols and recalling them successfully. As a result, a simple but efficient embedded processing architecture that overcomes various challenges involved in pattern recognition tasks is implemented on a Xilinx Spartan3 FPGA.
more …
By
Vega, Gerardo
Sufficient conditions for the construction of a twoweight cyclic code by means of the direct sum of two oneweight cyclic codes, were recently presented in [4]. On the other hand, an explicit formula for the number of oneweight cyclic codes, when the length and dimension are given, was proved in [3]. By imposing some conditions on the finite field, we now combine both results in order to give a lower bound for the number of twoweight cyclic codes with composite paritycheck polynomials.
more …
By
Pérez, Joaquín; Cruz, Laura; Pazos, Rodolfo; Landero, Vanesa; Reyes, Gerardo; Fraire, Héctor; Frausto, Juan
Show all (7)
The problem of algorithm selection for solving NP problems arises with the appearance of a variety of heuristic algorithms. The first works claimed the supremacy of some algorithm for a given problem. Subsequent works revealed the supremacy of algorithms only applied to a subset of instances. However, it was not explained why an algorithm solved better a subset of instances. In this respect, this work approaches the problem of explaining through causal model the interrelations between instances characteristics and the inner workings of algorithms. For validating the results of the proposed approach, a set of experiments was carried out in a study case of the Threshold Accepting algorithm to solve the Bin Packing problem. Finally, the proposed approach can be useful for redesigning the logic of heuristic algorithms and for justifying the use of an algorithm to solve an instance subset. This information could contribute to algorithm selection for NP problems.
more …
By
Czyzowicz, J.; Dobrev, S.; Fevens, T.; GonzálezAguilar, H.; Kranakis, E.; Opatrny, J.; Urrutia, J.
Show all (7)
8 Citations
Many protocols in adhoc networks use dominating and connected dominating sets, for example for broadcasting and routing. For large ad hoc networks the construction of such sets should be local in the sense that each node of the network should make decisions based only on the information obtained from nodes located a constant number of hops from it. In this paper we use the location awareness of the network, i.e. the knowledge of position of nodes in the plane to provide local, constant approximation, deterministic algorithms for the construction of dominating and connected dominating sets of a Unit Disk Graph (UDG). The size of the constructed set, in the case of the dominating set, is shown to be 5 times the optimal, while for the connected dominating set 7.453 + ε the optimal, for any arbitrarily small ε> 0. These are to our knowledge the first local algorithms whose time complexities and approximation bounds are independent of the size of the network.
more …
By
Deselaers, Thomas; Hanbury, Allan; Viitaniemi, Ville; Benczúr, András; Brendel, Mátyás; Daróczy, Bálint; Escalante Balderas, Hugo Jair; Gevers, Theo; Hernández Gracidas, Carlos Arturo; Hoi, Steven C. H.; Laaksonen, Jorma; Li, Mingjing; Marín Castro, Heidy Marisol; Ney, Hermann; Rui, Xiaoguang; Sebe, Nicu; Stöttinger, Julian; Wu, Lei
Show all (18)
3 Citations
We describe the object retrieval task of ImageCLEF 2007, give an overview of the methods of the participating groups, and present and discuss the results.
The task was based on the widely used PASCAL object recognition data to train object recognition methods and on the IAPR TC12 benchmark dataset from which images of objects of the ten different classes bicycles, buses, cars, motorbikes, cats, cows, dogs, horses, sheep, and persons had to be retrieved.
Seven international groups participated using a wide variety of methods. The results of the evaluation show that the task was very challenging and that different methods for relevance assessment can have a strong influence on the results of an evaluation.
more …
By
Schütze, Oliver; Laumanns, Marco; Coello, Carlos A. Coello
13 Citations
In this paper we address the problem of approximating the ’knee’ of a biobjective optimization problem with stochastic search algorithms. Knees or entire kneeregions are of particular interest since such solutions are often preferred by the decision makers in many applications. Here we propose and investigate two update strategies which can be used in combination with stochastic multiobjective search algorithms (e.g., evolutionary algorithms) and aim for the computation of the knee and the kneeregion, respectively. Finally, we demonstrate the applicability of the approach on two examples.
more …
By
FrankBolton, Pablo; AlvaradoGonzález, Alicia Montserrat; Aguilar, Wendy; Frauel, Yann
Show all (4)
1 Citations
A robot localization scheme is presented in which a mobile robot finds its position within a known environment through image comparison. The images being compared are those taken by the robot throughout its reconnaissance trip and those stored in an image database that contains views taken from strategic positions within the environment, and that also contain position and orientation information. Image comparison is carried out using a scaledependent keypointmatching technique based on SIFT features, followed by a graphbased outlier elimination technique known as Graph Transformation Matching. Two techniques for position and orientation estimation are tested (epipolar geometry and clustering), followed by a probabilistic approach to position tracking (based on Monte Carlo localization).
more …
By
MezuraMontes, Efrén; ReyesSierra, Margarita; Coello, Carlos A. Coello
64 Citations
Summary
Differential Evolution is currently one of the most popular heuristics to solve singleobjective optimization problems in continuous search spaces. Due to this success, its use has been extended to other types of problems, such as multiobjective optimization. In this chapter, we present a survey of algorithms based on differential evolution which have been used to solve multiobjective optimization problems. Their main features are described and, based precisely on them, we propose a taxonomy of approaches. Some theoretical work found in the specialized literature is also provided. To conclude, based on our findings, we suggest some topics that we consider to be promising paths for future research in this area.
more …
By
FraustoSolís, Juan; AlonsoPecina, Federico; MoraVargas, Jaime
1 Citations
Course Timetabling Problem (CTP) is a well known NP hard problem. Many classical randomized algorithms (as Genetic Algorithms, Simulated Annealing and Tabu Search) have been devised for this problem. For the previous PATAT benchmark, many of these old algorithms were able to find not only feasible solutions but even the optimal one. However, new harder CTP instances have recently proposed, which to obtain a feasible solution is a very hard challenge, and the previous algorithms do not perform well with these instances. Therefore, new algorithms for CTP should be devised. In this paper a new Simulating Annealing (SA) algorithm for CTP is presented. The algorithm shows a good performance not only with the old CTP instances but also with the new ones. This new SA implementation is able to find a feasible solution in instances where no other algorithm in the literature has been reported a success.
more …
By
LandaBecerra, Ricardo; Fraga, Luis G.
Triangulation is one step in Computer Vision where the 3D points are calculated from 2D point correspondences over 2D images. When these 2D points are free of noise, the triangulation is the intersection point of two lines, but in the presence of noise this intersection does not occur and then the best solution must be estimated. We propose in this article a fast algorithm that uses Differential Evolution to calculate the optimal triangulation.
more …
By
Vázquez Espinoza de los Monteros, Roberto A.; Sossa Azuela, Juan Humberto
26 Citations
The brain is not a huge fixed neural network, but a dynamic, changing neural network that continuously adapts to meet the demands of communication and computational needs. In classical neural networks approaches, particularly associative memory models, synapses are only adjusted during the training phase. After this phase, synapses are no longer adjusted. In this paper we describe a new dynamical model where synapses of the associative memory could be adjusted even after the training phase as a response to an input stimulus. We provide some propositions that guarantee perfect and robust recall of the fundamental set of associations. In addition, we describe the behavior of the proposed associative model under noisy versions of the patterns. At last, we present some experiments aimed to show the accuracy of the proposed model.
more …
By
Goins, Edray; Luca, Florian; Togbé, Alain
2 Citations
In this paper, we find all the solutions of the Diophantine equation x^{2} + 2^{α} 5^{β} 13^{γ} = y^{n} in nonnegative integers x, y,α, β, γ, n ≥ 3 with x and y coprime. In fact, for n = 3, 4, 6, 8, 12, we transform the above equation into several elliptic equations written in cubic or quartic models for which we determine all their {2, 5, 13}integer points. For n ≥ 5, we apply a method that uses primitive divisors of Lucas sequences. Again we are able to obtain several elliptic equations written in cubic models for which we find all their {2, 5, 13}integer points. All the computations are done with MAGMA [12].
more …
By
GuzmánObando, Javier; Rosa, Josep Lluís; Aciar, Silvana; Montaner, Miquel; Castán, José A.; Laria, Julio
Show all (6)
The main objective of this paper aims at developing a methodology that takes into account the human factor extracted from the several information sources of the organization of the recommender systems. This methodology is capable of extracting the Human Values Scale from the user, with reference to his/her features, in order to improve the adaptation of the Recommender Systems. This research is focused on the analysis of human values scale using the Portrait Values Questionnaire of Schwartz, which can take advantage of the several information sources of the organization through its attributes to define the methodology that response with more exactitude to preferences and interests of the user. This paper presents a demonstration of how the Human Values Scale of a user can be extracted from several information sources of the organization. A case study is presented to apply the methodology, in an effort to extract the user human values scale from bank domains.
more …
By
Alejo, R.; Sotoca, J. M.; Casañ, G. A.
4 Citations
The latest research in neural networks demonstrates that the class imbalance problem is a critical factor in the classifiers performance when working with multiclass datasets. This occurs when the number of samples of some classes is much smaller compared to other classes. In this work, four different options to reduce the influence of the class imbalance problem in the neural networks are studied. These options consist of introducing several cost functions in the learning algorithm in order to improve the generalization ability of the networks and speed up the convergence process.
more …
By
RamosQuintana, Fernando; SámanoGalindo, Josefina; ZárateSilva, Víctor H.
2 Citations
Selfdirected learning has been one of the main objectives in the education domain. A learning model can drive a selfdirected learning if an adequate educational environment is built. We propose an educational environment to encourage the selfdirected learning, which is composed of a computer collaborative tool that uses dialogues and the concept of ill structured problems. The knowledge being learned is represented by a network of concepts built by the students through the exchanged messages. The network of concepts expressed the relation between the main concepts of the topic being learned. A coherent network is the tangible proof that the process of selfdirected learning has been correctly achieved. Two topics of computer sciences are reported: Object Oriented Programming and Case Based Reasoning. The results have proven that along with the knowledge acquired, selfdirected learning contributes directly to the development of skills for solving problems and attitudes of collaborative work.
more …
By
Gasca, Eduardo; Favela, Jesus; Tentori, Monica
3 Citations
The World Health Organization has declared obesity a worldwide epidemic. People with obesity have a higher risk to attain chronic diseases, high risk of premature death and a reduced quality of life. Recent studies have shown that persuasive technologies and virtual communities can promote healthy lifestyles. In this article, we describe the development of a Persuasive Ecosystem aimed at promoting a healthy lifestyle in patients with a chronic disease that participate in a support group. The study was inspired in the results of a case study conducted in a hospital responsible for running this group. The results of a preliminary evaluation show an increased engagement of the patients with the program due to the use of the system.
more …
By
Gago Alonso, Andrés; Medina Pagola, José Eladio; CarrascoOchoa, Jesús Ariel; MartínezTrinidad, José Fco.
Show all (4)
5 Citations
In this paper, a new algorithm for mining frequent connected subgraphs called gRed (graph Candidate Reduction Miner) is presented. This algorithm is based on the gSpan algorithm proposed by Yan and Jan. In this method, the mining process is optimized introducing new heuristics to reduce the number of candidates. The performance of gRed is compared against two of the most popular and efficient algorithms available in the literature (gSpan and Gaston). The experimentation on real world databases shows the performance of our proposal overcoming gSpan, and achieving better performance than Gaston for low minimal support when databases are large.
more …
By
Vázquez, Roberto A.; Sossa, Humberto
1 Citations
An associative memory is a particular type of neural network for recalling output patterns from input patterns that might be altered by noise. During the last 50 years, several associative models have emerged and they only have been applied to solve problems where input patterns are images. Most of these models have several constraints that limit their applicability in complex problems. Recently in [13] it was introduced a new associative model based on some aspects of the human brain. This model is robust under different type of noises and image transformations, and useful in complex problems such as face and 3d object recognition. In this paper we adopt this model and apply it to problems that not involve images patterns, we applied to speech recognition problems. In this paper it is described a novel application where an associative memory works as a voice translator device performing a speech recognition process. In order to achieve this, the associative memory is trained using a corpus of 40 English words with their corresponding translation to Spanish. Each association used during training phase is composed by a voice signal in English and a voice signal in Spanish. Once trained our EnglishSpanish translator, when a voice signal in English is used to stimulate the associative memory we expect that the memory recalls the corresponding voice signal in Spanish. In order to test the accuracy of the proposal, a benchmark of 14500 altered versions of the original voice signals were used.
more …
By
Avilés, Héctor H.; Aguilar, Wendy; Pineda, Luis A.
1 Citations
Previous evaluations of gesture recognition techniques have been focused on classification performance, while ignoring other relevant issues such as knowledge description, feature selection, error distribution and learning performance. In this paper, we present an empirical comparison of decision trees, neural networks and hidden Markov models for visual gesture recognition following these criteria. Our results show that none of these techniques is a definitive alternative for all these issues. While neural nets and hidden Markov models show the highest recognition rates, they sacrifice clarity of its knowledge; decision trees, on the other hand, are easy to create and analyze. Moreover, error dispersion is higher with neural nets. This information could be useful to develop a general computational theory of gestures. For the experiments, a database of 9 gestures with more than 7000 samples taken from 15 people was used.
more …
By
Yaurima, Victor; Burtseva, Larisa; Tchernykh, Andrei
1 Citations
This paper presents a genetic algorithm for a scheduling problem frequent in printed circuit board manufacturing: a hybrid flowshop with unrelated machines, sequence dependent setup time and machine availability constraints. The proposed genetic algorithm is a modified version of previously proposed genetic algorithms for the same problem. Experimental results show the advantages of using new crossover operator. Furthermore, statistical tests confirm the superiority of the proposed variant over the stateoftheart heuristics.
more …
By
CruzBarbosa, Raúl; Vellido, Alfredo
4 Citations
Nonlinear dimensionality reduction (NLDR) methods aim to provide a faithful lowdimensional representation of multivariate data. The manifold learning family of NLDR methods, in particular, do this by defining lowdimensional manifolds embedded in the observed data space. Generative Topographic Mapping (GTM) is one such manifold learning method for multivariate data clustering and visualization. The nonlinearity of the mapping it generates makes it prone to trustworthiness and continuity errors that would reduce the faithfulness of the data representation, especially for datasets of convoluted geometry. In this study, the GTM is modified to prioritize neighbourhood relationships along the generated manifold. This is accomplished through penalizing divergences between the Euclidean distances from the data points to the model prototypes and the corresponding geodesic distances along the manifold. The resulting Geodesic GTM model is shown to improve not only the continuity and trustworthiness of the representation generated by the model, but also its resilience in the presence of noise.
more …
By
Azhmyakov, Vadim; Attia, Sid Ahmed; Raisch, Jörg
15 Citations
In this contribution, we consider a class of hybrid systems with continuous dynamics and jumps in the continuous state (impulsive hybrid systems). By using a newly elaborated version of the Pontryagintype Maximum Principle (MP) for optimal control processes governed by hybrid dynamics with autonomous location transitions, we extend the necessary optimality conditions to a class of Impulsive Hybrid Optimal Control Problems (IHOCPs). For these problems, we obtain a concise characterization of the Impulsive Hybrid MP (IHMP), namely, the corresponding boundaryvalue problem and some additional relations. As in the classical case, the proposed IHMP provides a basis for diverse computational algorithms for the treatment of IHOCPs.
more …
By
Romero, David; Galeano, Nathalie; Molina, Arturo
6 Citations
Collaboration is essential to develop successful Collaborative Networked Organizations (CNOs). In order to know if an organization is ready and has the needed characteristics for collaborate and participate in a CNO, either a Virtual Breeding Environment (VBE) or a Virtual Organization (VO), a set of specific elements should be evaluated. These evaluation elements are referred as Readiness for Collaboration Assessments and are the main topic of this paper. Main elements that should be considered in these assessments, especially for an organization that wants to become a VBE member are presented as a first approach that can be implemented in different Virtual Breeding Environments.
more …
By
Trujillo, Leonardo; Olague, Gustavo; Fernández de Vega, Francisco; Lutton, Evelyne
Show all (4)
The basic problem for a mobile vision system is determining where it is located within the world. In this paper, a recognition system is presented that is capable of identifying known places such as rooms and corridors. The system relies on a bag of features approach using locally prominent image regions. Realworld locations are modeled using a mixture of Gaussians representation, thus allowing for a multimodal scene characterization. Local regions are represented by a set of 108 statistical descriptors computed from different modes of information. From this set the system needs to determine which subset of descriptors captures regularities between image regions of the same location, and also discriminates between regions of different places. A genetic algorithm is used to solve this selection task, using a fitness measure that promotes: 1) a high classification accuracy; 2) the selection of a minimal subset of descriptors; and 3) a high separation among place models. The approach is tested on two real world examples: a) using a sequence of still images with 4 different locations; and b) a sequence that contains 8 different locations. Results confirm the ability of the system to identify previously seen places in a realworld setting.
more …
By
TorresHuitzil, Cesar; Girau, Bernard; AriasEstrada, Miguel
This paper presents a biologically inspired modular hardware implementation of a cortical model of orientation selectivity of the visual stimuli in the primary visual cortex targeted to a Field Programmable Gate Array (FPGA) device. The architecture mimics the functionality and organization of neurons through spatial Gaborlike filtering and the socalled cortical hypercolumnar organization. A systolic array and a suitable image addressing scheme are used to partially overcome the von Neumann bottleneck of monolithic memory organization in conventional microprocessorbased system by processing small and local amounts of sensory information (image tiles) in an incremental way. A realtime FPGA implementation is presented for 8 different orientations and aspects such as flexibility, scalability, performance and precision are discussed to show the plausibility of implementing biologicallyinspired processing for early visual perception in digital devices.
more …
By
Marquez, J.; Ramirez, W.; Boyer, L.; Delmas, P.
Show all (4)
4 Citations
We report current work on methods for robust fitting of ellipsoids to the shape of the human head in threedimensional models built from laser scanner acquisitions. A starting ellipsoid is obtained from Principal Component Analysis from mesh vertices; those regions far from the surface of the ellipsoid are penalized (outlier rejection and/or damping). A first method consists in recalculating iteratively the ellipsoid by PCA, adjusting scales. Another method projects the outliers into the ellipsoid. A third method uses a morphologicalerror approach, via the difference of the distance fields of the head and its fitting ellipsoid. The ellipsoid orientation, position and scales are then changed in search for a set of parameters minimizing the morphological error. To speedup calculations, only a few orthogonal planes are sampled and the distance field is obtained directly from the triangular mesh elements. Among the intended applications, the restoration of the skullcap is presented.
more …
By
ZatarainCabada, Ramon; BarrónEstrada, M. L.; OsorioVelásquez, J. Moisés; ZepedaSánchez, L.; ReyesGarcía, Carlos A.
Show all (5)
L2Code is an Intelligent Tutoring System used for teaching programming courses for different paradigms under a hybrid or blinded environment. It was designed and implemented to work with diverse types of modules oriented to certain ways of learning using principles of Multiple Intelligences. The author tool facilitates the creation of adaptive or personalized learning material to be used in multipleparadigm programming language courses applying an artificial intelligence approach. The Tutoring System works with a predictive engine that uses a Naive Bayes classifier which operates in real time with the knowledge of the historical performance of the student. We show results of the tool.
more …
By
ReyesBarragán, M. Alejandro; VillaseñorPineda, Luis; MontesyGómez, Manuel
1 Citations
Current storage and processing facilities have caused the emergence of many multimedia repositories and, consequently, they have also triggered the necessity of new approaches for information retrieval. In particular, spoken document retrieval is a very complex task since existing speech recognition systems tend to generate several transcription errors (such as word substitutions, insertions and deletions). In order to deal with these errors, this paper proposes an enriched document representation based on a phonetic codification of the automatic transcriptions. This representation aims to reduce the impact of the transcription errors by representing words with similar pronunciations through the same phonetic code. Experimental results on the CLSR corpus from the CLEF 2007 (which includes 33 test topics and 8,104 English interviews) are encouraging; our method achieved a mean average precision of 0.0795, outperforming all except one of the evaluated systems at this forum.
more …
By
GuerraHernández, Alejandro; CastroManzano, José Martín; ElFallahSeghrouchni, Amal
1 Citations
This work is about the commitment strategies used by rational agents programmed in AgentSpeak(L) and the relationship between singleminded commitment and intentional learning. Although agent oriented languages were proposed to reduce the gap between theory and practice of MultiAgent Systems, it has been difficult to prove BDI properties of the agents programmed in such languages. For this reason, we introduce some ideas to reason temporally about the intentional state of rational agents in order to prove what kind of commitment strategy is used by AgentSpeak(L) agents, based on the operational semantics of the programming language. This enables us to prove that any agent programmed in this language follows by default a limited form of singleminded commitment. Then we analyze how intentional learning can enhance this commitment strategy allowing preemptive abandon of intentions.
more …
By
Téllez, Alberto; Juárez, Antonio; Hernández, Gustavo; Denicia, Claudia; Villatoro, Esaú; Montes, Manuel; Villaseñor, Luis
Show all (7)
This paper discusses our system’s results at the Spanish Question Answering task of CLEF 2007. Our system is centered in a full datadriven approach that combines information retrieval and machine learning techniques. It mainly relies on the use of lexical information and avoids any complex language processing procedure. Evaluation results indicate that this approach is very effective for answering definition questions from Wikipedia. In contrast, they also reveal that it is very difficult to respond factoid questions from this resource solely based on the use of lexical overlaps and redundancy.
more …
By
MorenoMoreno, Prudenciano; YáñezMárquez, Cornelio
The current paper is focused on the evolution and future of discussions on the application of Information Technologies on education and pedagogy from a conceptual perspective. The analyzed debate revolves around those who back New Communication and Information Technologies (NCITs) as a technicalfunctional expression of modernity (the Accolatory); and the opposites (the Dismissive), both postmodern —simply critics and skeptics— and antimodern, decidedly contrary to the use of NCITs. Finally, we conclude with a proposal of conciliation of all the above positions into a new educative vision, transmodern or metamodern, based on the advances of the socalled “Integral Theory of the Whole”.
more …
By
OlivaresMercado, Jesus; Hotta, Kazuhiro; Takahashi, Haruhisa; PerezMeana, Hector; Miyatake, Mariko Nakano; SanchezPerez, Gabriel
Show all (6)
This paper proposes a robust faces recognition method based on the Normalization and the Phase Spectrum of the Local Part of an Image. The Principal Components Analysis (PCA) and the Support Vector Machine (SVM) are used in the classification stage. We evaluate how the proposed method is robust to illumination, occlusion and expressions using ‘‘AR Face Database’’, which includes the face images of 109 subjects (60 males and 49 females) under illumination changes, expression changes and partial occlusion. The proposed method provides results with a correct recognition rate more than 96.7%.
more …
By
TerolVillalobos, Iván R.; MoralesHernández, Luis A.; HerreraRuiz, Gilberto
In the present paper a morphological approach for segmenting directional structures is proposed. This approach is based on the concept of the linesegment and orientation functions. The linesegment function is computed from the supremum of directional erosions. This function contains the sizes of the longest lines that can be included in the structure. To determine the directions of the line segments, the orientation function which contains the angles of the line segments it is built when the linesegment function is computed. Next, by combining both functions, a weighted partition is built using the watershed transformation. Finally, the elements of the partition are merged according to some directional and size criteria for computing the desired segmentation of the image using a RAG structure.
more …
By
Ramos, Fernando; Ayanegui, Huberto
Three of the most important open research areas in multiagent cooperative systems are the construction of models related with the communication between agents, the multiple interactions and the behaviors adopted by agents during a task [5] . This work deals with the discovery of behaviors in multiagent teams, more precisely in soccer teams. It is an extension of a previous work presented in [1] . The extension is focused on the discovery of tactical plays adopted by socceragents during a match within the context of formations. Due to the nature of team work in socceragent domains, the discovery of tactical behaviors should be done within the context of team formations. Nevertheless, the dynamic nature and the multiple interactions between players at each instant of the game difficult the tracking of formations, which at the same time difficult the discovery of tactical plays. In this work is proposed an original and efficient way of discovering tactical plays supported by a robust tracking of formations, even though they are submitted to dynamic changes of the world, based on the construction of topological structures. Successful results, derived from the analysis of an important number of matches of the RoboCup Simulation league matches, valid the efficiency of the model presented in this work.
more …
By
ArceSantana, Edgar Román; Alba, Alfonso
2 Citations
Image Registration is central to different applications such as medical analysis, biomedical systems, image guidance, etc. In this paper we propose a new algorithm for multimodal image registration. A Bayesian formulation is presented in which a likelihood term is defined using an observation model based on linear intensity transformation functions. The coefficients of these transformations are represented as prior information by means of Markov random fields. This probabilistic approach allows one to find optimal estimators by minimizing an energy function in terms of both the parameters that control the affine transformation of one of the images and the coefficient fields of the intensity transformations for each pixel.
more …
By
GuzmánCabrera, Rafael; MontesyGómez, Manuel; Rosso, Paolo; VillaseñorPineda, Luis
Show all (4)
4 Citations
As any other text categorization task, authorship attribution requires a large number of training examples. These examples, which are easily obtained for most of the tasks, are particularly difficult to obtain for this case. Based on this fact, in this paper we investigate the possibility of using Webbased text mining methods for the identification of the author of a given poem. In particular, we propose a semisupervised method that is specially suited to work with justfew training examples in order to tackle the problem of the lack of data with the same writing style. The method considers the automatic extraction of the unlabeled examples from the Web and its iterative integration into the training data set. To the knowledge of the authors, a semisupervised method which makes use of the Web as support lexical resource has not been previously employed in this task. The results obtained on poem categorization show that this method may improve the classification accuracy and it is appropriate to handle the attribution of short documents.
more …
By
Fraga, Luis G.; ViteSilva, Israel
1 Citations
In this work we propose the use of Differential Evolution as a numerical method to estimate directly the orientation and position of several views taken by a same camera. First, from two views, the camera parameters are estimated and also the other parameters (orientation and position) for both views. We can estimate 3D points in this configuration and then, in a second step, new views, and also new 3D points, are added to the initial reconstruction calculated in the first step. We tested our approach with a simulation using four views. The results clearly show the good performance of the proposed approach.
more …
By
Cairó, Osvaldo; Guardati, Silvia
This paper presents an approach to automatic translation in two steps. The first one is recognition (syntactic) and the last one is interpretation (semantic). In the recognition phase, we use volatile grammars. They represent an innovation to logicbased grammars. For the interpretation phase, we use componential analysis and the laws of integrity. Componential analysis defines the sense of the lexical parts. The rules of integrity, on the other hand, are in charge of refining, improving and optimizing translation. We applied this framework for general analysis of romance languages and for the automatic translation of texts from Spanish into other neoLatin languages and vice versa.
more …
By
RomeroMoreno, M.; MartínezTrinidad, J. Fco.; CarrascoOchoa, J. A.
1 Citations
Gait Recognition is a noninvasive biometric technique for identifying persons through the way they walk. Currently there are many Gait Recognition methods, most of them based on a similarity function. In this paper, we propose two new methods for Gait Recognition based on silhouette and contour, using a classifier ensemble. Experimental results on a public standard database are shown and compared against others Gait Recognition methods.
more …
By
TorresHuitzil, Cesar; Girau, Bernard
4 Citations
This paper proposes an embedded system on a chip to generate locomotion patterns of periodic rhythmic movements inspired by biological neural networks called Central Pattern Generators (CPGs) found in animal nervous system. The proposed system contains a custom digital module, attached to an embedded processor, that mimics the functionality and organization of the fundamental AmariHopfield CPG. In order to reduce the CPG hardware integration complexity as well as to provide flexibility, an embedded linux operating system running on a processor is used to deal with the CPG interfacing in a high level transparent way for application development. The system is implemented on a Field Programmable Gate Array (FPGA) device providing a compact, flexible and expandable solution for generating periodic rhythmic patterns in robot control applications. Results show that the obtained waveforms from the FPGA implementation agree with software simulations and preserve the easiness of CPG parameter setting for adaptive behavior.
more …
By
Sánchez, Christian; Sheremetov, Leonid
Recently, the market of information technologies has witnessed the explosive interest in Web services (WS), which provide several critical characteristics for development of enterprise information systems. The WS discovery, aiming in finding services meeting user’s request, is an open problem yet since most of the current works both centered in syntactic (like UDDI) and semantic service descriptions, focus on finding a service with an exact match, which is not always possible. This paper presents two algorithms inspired in the query expansion of Web search engines, which expand client service descriptions (specified in OWLS) to similar service descriptions, extending the matching types to exact, leftover and missing information. These algorithms are further used for dynamic service composition. The proposed model works with the current syntactic UDDI systems. Described algorithms are illustrated by example. The characteristics of the algorithms are studied grounded in analysis of WS and ontologies to calculate the number of service descriptions generated by the algorithm, according to a user request.
more …
By
Santana Tapia, Roberto; Daneva, Maya; Eck, Pascal; Castro Cárdenas, NicteHá; Oene, Leida
Show all (5)
2 Citations
Applying principles for businessIT alignment in networked organizations seems to be key for their survival in competitive environments. In this paper, we present a qualitative multiple case study conducted in three collaborative networked organizations: (i) an outsourcing relation between an international IT and business integrator and a massmarketed service provider, (ii) an interorganizational collaboration among governmental departments of the state of Tamaulipas in Mexico, and (iii) a networked organization between the province Overijssel, the municipalities Zwolle and Enschede, the water board district Regge & Dinkel and Royal Grolsch N.V. in the Netherlands. Drawing from this case study, we derive four principles that networked organizations seem to adhere to when striving for alignment at a certain level of maturity.
more …
By
Rendón, Eréndira; Sánchez, J. Salvador; Garcia, Rene A.; Abundez, Itzel; Gutierrez, Citlalih; Gasca, Eduardo
Show all (6)
Categorical data clustering constitutes an important part of data mining; its relevance has recently drawn attention from several researchers. As a step in data mining, however, clustering encounters the problem of large amount of data to be processed. This article offers a solution for categorical clustering algorithms when working with high volumes of data by means of a method that summarizes the database. This is done using a structure called CMtree. In order to test our method, the KModes and Click clustering algorithms were used with several databases. Experiments demonstrate that the proposed summarization method improves execution time, without losing clustering quality.
more …
By
OlveraLópez, J. Arturo; CarrascoOchoa, J. Ariel; MartínezTrinidad, J. Fco.
6 Citations
In Pattern recognition, the supervised classifiers use a training set T for classifying new prototypes. In practice, not all information in T is useful for classification therefore it is necessary to discard irrelevant prototypes from T. This process is known as prototype selection, which is an important task for classifiers since through this process the time in the training and/or classification stages could be reduced. Several prototype selection methods have been proposed following the Nearest Neighbor (NN) rule; in this work, we propose a new prototype selection method based on the prototype relevance and border prototypes, which is faster (over large datasets) than the other tested prototype selection methods. We report experimental results showing the effectiveness of our method and compare accuracy and runtimes against other prototype selection methods.
more …
By
Lopez, Miguel; Melin, Patricia; Castillo, Oscar
8 Citations
We describe in this paper a new method for response integration in ensemble neural networks with Type1 Fuzzy Logic and Type2 Fuzzy Logic using Genetic Algorithms (GA’s) for optimization. In this paper we consider pattern recognition with ensemble neural networks for the case of fingerprints. An ensemble neural network of three modules is used. Each module is a local expert on person recognition based on their biometric measure (Pattern recognition for fingerprints). The Response Integration method of the ensemble neural networks has the goal of combining the responses of the modules to improve the recognition rate of the individual modules. Using GA’s to optimize the Membership Functions of The Type1 Fuzzy System and Type2 Fuzzy System we can improve the results of the fuzzy systems. We show in this paper the results of a type2 approach for response integration that improves performance over the type1 logic approaches.
more …
By
Alba, Alfonso; ArceSantana, Edgar
A visualization methodology for the analysis of dynamic synchronization in electroencephalographic signals is presented here. The proposed method is based on a seeded regiongrowing segmentation of the timefrequency space in terms of spatial connectivity patterns, a process that can be fully automated by cleverly choosing the seeds. A Bayesian regularization technique is applied to further improve the results. Finally, preliminary results from the analysis of a high electrodedensity dataset with 120 channels are shown.
more …
By
Bravo, Maricela; Velazquez, José
2 Citations
A multiagent system (MAS) consists of a set of autonomous agents, capable of interacting among each other with cooperation or coordination purposes. To achieve their goals, all agents in a MAS must exchange messages following a interaction protocol. Currently there are research efforts to provide standard mechanisms to achieve cooperation between multiple heterogeneous MAS. However, there are still some issues that must be solved in order to fully automate integration and interoperation among them. In this paper we present a novel approach for discovering pragmatic similarity among multiple agent interaction protocols, our objective is to support system developers and integrators generating a set of pragmatic relations between pairs of agent interaction protocols and a numerical measure which represents the similarity among them. We describe an example to show the applicability of our approach.
more …
By
Calvo, Hiram
This paper presents an algorithm for Word Sense Discrimination that divides the global representation of a word into a number of classes by determining for any two occurrences whether they belong to the same sense or not. We rely on the notion that words that are used in similar contexts will have the same or a closely related meaning, thus, given a target word, we group its dependency cooccurrences in a Word Space Model. Each cluster represents a distinct meaning or sense of that word. We experiment with augmenting the bag of words of each cluster of cooccurrences, the dictionary of sense definition, and augmenting both. Then we count the number of intersections of each word of the bag of clustered senses and the bag of the dictionary of senses following the Lesk method. We find an increase in recall and a decrease in precision when augmenting. However, the best resulting Fmeasure is for the option of augmenting the both dictionary of senses and the bag of words from the clusters.
more …
By
CruzBarbosa, Raúl; Vellido, Alfredo
1 Citations
Manifold learning methods model highdimensional data through lowdimensional manifolds embedded in the observed data space. This simplification implies that their are prone to trustworthiness and continuity errors. Generative Topographic Mapping (GTM) is one such manifold learning method for multivariate data clustering and visualization, defined within a probabilistic framework. In the original formulation, GTM is optimized by minimization of an error that is a function of Euclidean distances, making it vulnerable to the aforementioned errors, especially for datasets of convoluted geometry. Here, we modify GTM to penalize divergences between the Euclidean distances from the data points to the model prototypes and the corresponding geodesic distances along the manifold. Several experiments with artificial data show that this strategy improves the continuity and trustworthiness of the data representation generated by the model.
more …
By
Vázquez, C. Renato; Ramírez, Antonio; Recalde, Laura; Silva, Manuel
Show all (4)
5 Citations
Continuous Petri Nets is a subclass of hybrid models representing relaxed views of discrete events systems, in which timing may adopt different semantics. Even if no semantics is strictly superior, we proved in [1] that for an important subclass of models infinite server semantics provides always a better approximation of the underlying discrete model than finite server. This paper then concentrates on controllability under this semantics. First we propose a notion of controllability over subsets of the reachable polytope, and provide a necessary and sufficient condition for markings with no null elements (interior points); later the transformation of an arbitrary initial marking into an interior one is done. The technically more involved part of the paper is the extension of those results to the case in which some transitions are non controllable. An interesting point is that all characterizations depend only on the structure and firing speeds of the timed continuous net.
more …
By
Gelbukh, Alexander; Sidorov, Grigori; LaraReyes, Diego; ChanonaHernandez, Liliana
Show all (4)
We discuss an unsupervised technique for determining morpheme structure of words in an inflective language, with Spanish as a case study. For this, we use a global optimization (implemented with a genetic algorithm), while most of the previous works are based on heuristics calculated using conditional probabilities of word parts. Thus, we deal with complete space of solutions and do not reduce it with the risk to eliminate some correct solutions beforehand. Also, we are working at the derivative level as contrasted with the more traditional grammatical level interested only in flexions. The algorithm works as follows. The input data is a wordlist built on the base of a large dictionary or corpus in the given language and the output data is the same wordlist with each word divided into morphemes. First, we build a redundant list of all strings that might possibly be prefixes, suffixes, and stems of the words in the wordlist. Then, we detect possible paradigms in this set and filter out all items from the lists of possible prefixes and suffixes (though not stems) that do not participate in such paradigms. Finally, a subset of those lists of possible prefixes, stems, and suffixes is chosen using the genetic algorithm. The fitness function is based on the ideas of minimum length description, i.e. we choose the minimum number of elements that are necessary for covering all the words. The obtained subset is used for dividing the words from the wordlist. Algorithm parameters are presented. Preliminary evaluation of the experimental results for a dictionary of Spanish is given.
more …
By
Guzmán, Enrique; Pogrebnyak, Oleksiy; Fernández, Luis Sánchez; YáñezMárquez, Cornelio
Show all (4)
4 Citations
One of the most serious problems in vector quantization is the high computational complexity at the encoding phase. This paper presents a new fast search algorithm for vector quantization based on Extended Associative Memories (FSAEAM). In order to obtain the FSAEAM, first, we used the Extended Associative Memories (EAM) to create an EAMcodebook applying the EAM training stage to the codebook produced by the LBG algorithm. The result of this stage is an associative network whose goal is to establish a relation between training set and the codebook generated by the LBG algorithm. This associative network is EAMcodebook which is used by the FSAEAM. The FSAEAM VQ process is performed using the recalling stage of EAM. This process generates a set of the class indices to which each input vector belongs. With respect to the LBG algorithm, the main advantage offered by the proposed algorithm is high processing speed and low demand of resources (system memory), while the encoding quality remains competitive.
more …
By
Lara, Carlos; Flores, Juan J.; Calderón, Félix
7 Citations
The timetabling problem consists in fixing a sequence of meetings between teachers and students in a given period of time, satisfying a set of different constraints. This paper shows the implementation of a Bee Algorithm (BA) to solve the Scholar Timetabling Problem. In the implemented BA, scout bees find feasible solutions while collector bees search in their neighborhood to find better solutions. While other algorithms evaluate every plausible assignment, the implemented algorithm only evaluates feasible solutions. This approach seems to be helpful to manage constrained problems. We propose a new measurement for replacing population that considers the evolutionary history of the bees as well as their fitness. Experimental results are presented for two real schools, where the algorithm shows promising results.
more …
By
Messeguer, Roc; DamiánReyes, Pedro; Favela, Jesus; Navarro, Leandro
Show all (4)
2 Citations
Context awareness is a necessary feature for mobile collocated collaborative learning. In this paper we describe how requirements for contextaware cooperative learning activities are derived from the jigsaw technique augmented with the use of mobile devices, applications to support the activities of groups, and tools to provide contextawareness to detect group formation. The emergence of groups is detected based on the location of the students within the classroom, but this information has to be careful filtered to evaluate the degree of uncertainty and protect from erroneous estimations. A threephase strategy to manage uncertainty by identifying possible sources of uncertainty, representing uncertain information, and determining how to proceed under the presence of uncertainty is used for this propose. These requirements are validated and confirmed in experiments with students working together in the classroom, measuring neutral or positive effects on learning and the usefulness of introducing mobile devices, group support applications, and context awareness. The ratio of unwanted interruptions to users made by the system is used to evaluate the utility of the system. Results show that by managing uncertainty, location estimation becomes more reliable, thus increasing the usefulness of the learning application.
more …
By
FloresMendoza, Jorge Isacc; MezuraMontes, Efrén
2 Citations
In this paper, the behavior of different Particle Swarm Optimization (PSO) variants is analyzed when solving a set of wellknown numerical constrained optimization problems. After identifying the most competitive one, some improvements are proposed to this variant regarding the parameter control and the constrainthandling mechanism. Furthermore, the online behavior of the improved PSO and some of the most competitive original variants are studied. Two performance measures are used to analyze the capabilities of each PSO to generate feasible solutions and to improve feasible solutions previously found i.e. how able is to move inside the feasible region of the search space. Finally, the performance of this improved PSO is compared against stateoftheart PSObased algorithms. Some conclusions regarding the behavior of PSO in constrained search spaces and the improved results presented by the modified PSO are given and the future work is established.
more …
By
Pérez, Joaquín; Cruz, Laura; Pazos, Rodolfo; Landero, Vanesa; Reyes, Gerardo; Zavala, Crispín; Fraire, Héctor; Pérez, Verónica
Show all (8)
1 Citations
The problem of algorithm selection for solving NP problems arises with the appearance of a variety of heuristic algorithms. The first works claimed the supremacy of some algorithm for a given problem. Subsequent works revealed that the supremacy of algorithms only applied to a subset of instances. However, it was not explained why an algorithm solved better an instances subset. In this respect, this work approaches the problem of explaining through causal modeling the interrelations between instances characteristics and the inner workings of algorithms. For validating the results of the proposed approach, a set of experiments was carried out in a study case of the Tabu Search algorithm applied to the Bin Packing problem. Finally, the proposed approach can be useful for redesigning the logic of heuristic algorithms and for justifying the use of an algorithm to solve an instance subset. This information could contribute to algorithm selection for NPhard problems.
more …
By
Romero, David; Galeano, Nathalie; Molina, Arturo
10 Citations
Virtual Breeding Environments (VBEs) are longterm strategic alliances of organisations aimed at offering the conditions to support the rapid and fluid configuration of Virtual Organisations (VOs). VBE reference models play a guiding role to conceptualise a set of business processes to enhance the responsiveness and flexibility of networks to react to a collaboration opportunity through a collection of collaborative drivers and enablers. VBE reference models serve as a reference guide for the implementation of breeding environments in different domains and application environments. This paper presents an instantiation methodology as a controlled process, addressing systematically a set of steps, supported by different mechanisms and methodologies needed to establish and characterize the management functionalities and running of a VBE that also addresses activities during its entire lifecycle basedon a VBE reference model proposed.
more …
By
Bravo, Maricela; Velazquez, José
1 Citations
Communication between multiple agents is essential to achieve goals, cooperation, and negotiation to take decisions for mutual benefit. Nowadays there is a growing interest in automating communication processes between different agents in dynamic Webbased environments. However, when agents are deployed and integrated in open and dynamic environments, detailed syntax and semantics of their particular language implementations differ, causing the problem of communication heterogeneity. Therefore, it is necessary to measure heterogeneity among all participating agents and the number of required translations when heterogeneous agents are involved in communications. In this paper we present a set of measures with the objective to evaluate the minimal computational requirements before implementing a translation approach. Our measures are based on set theory, which has proved to be a good representation formalism in other areas. We showed how to use the set of measures for two highly heterogeneous set of agents.
more …
By
Pazos, Rodolfo; Santaolalaya S., René; Rojas P., Juan C.; Pérez O., Joaquín
Show all (4)
1 Citations
A natural language interface to databases (NLIDB) without help mechanisms that permit clarifying queries is prone to incorrect query translation. In this paper we draw attention to a problem in NLIDBs that has been overlooked and has not been dealt with systematically: word economy; i.e., the omission of words when expressing a query in natural language (NL). In order to get an idea of the magnitude of this problem, we conducted experiments on EnglishQuery when applied to a corpora of economizedwording queries. The results show that the percentage of correctly answered queries is 18%, which is substantially lower than those obtained with corpora of regular queries (53%–83%). In this paper we describe a typification of problems found in economizedwording queries, which has been used to implement domainindependent dialog processes for an NLIDB in Spanish. The incorporation of dialog processes in an NLIDB permits users to clarify queries in NL, thus improving the percentage of correctly answered queries. This paper presents the tests of a dialog manager that deals with four types of query problems, which permits to improve the percentage of correctly answered queries from 60% to 91%. Due to the generality of our approach, we claim that it can be applied to other domaindependent or domainindependent NLIDBs, as well as other NLs such as English, French, Italian, etc.
more …
By
FrancoArcega, Anilu; CarrascoOchoa, J. Ariel; SánchezDíaz, Guillermo; MartínezTrinidad, J. Fco
Show all (4)
1 Citations
Several algorithms for induction of decision trees have been developed to solve problems with large datasets, however some of them have spatial and/or runtime problems using the whole training sample for building the tree and others do not take into account the whole training set. In this paper, we introduce a new algorithm for inducing decision trees for large numerical datasets, called IIMDT, which builds the tree in an incremental way and therefore it is not necesary to keep in main memory the whole training set. A comparison between IIMDT and ICE, an algorithm for inducing decision trees for large datasets, is shown.
more …
By
MezuraMontes, Efrén; MuñozDávila, Lucía; Coello, Carlos A. Coello
5 Citations
This document presents a proposal to incorporate a fitness inheritance mechanism into an Evolution Strategy used to solve the general nonlinear programming problem. The aim is to find a tradeoff between a lower number of evaluations of each solution and a good performance of the approach. A set of test problems taken from the specialized literature was used to test the capabilities of the proposed approach to save evaluations and to maintain a competitive performance.
more …
By
Uribe, Diego
In this paper we define a measure for textual entailment recognition based on structural isomorphism theory applied to lexical dependency information. We describe the experiments carried out to estimate measure’s parameters with logistic regression and SVM. The results obtained show how a model constructed around lexical relationships is a plausible alternative for textual entailment recognition.
more …
By
Fernando, Zacarías F.; Rosalba, Cuapa C.; Francisco, Lozano T.; Andres, Vazquez F.; Dionicio, Zacarías F.
Show all (5)
1 Citations
The Learning of the century XXI demand ubiquitous characteristics that allow to learner not only to have information available in any place, in any time and in any way. But rather, to have the information in right time, in the right place and in right way [3]. An ubiquitous learning environment should allow the learner to have these three characteristics at your disposal in all moment. Considering that a lot of people have access to cell phone technology and it would be fantastic to use this technology as a learning tool. We have developed an ubiquitous learning system (on cellular phones) that also it combines web technologies and cell phone. Our system shows that this novel form of learning is completely accepted and it increases the learning level significantly.
more …
By
MartínezDiaz, Saul; Kober, Vitaly; Ovseyevich, I. A.
Adaptive composite nonlinear filters for reliable illuminationinvariant pattern recognition are proposed. The information about objects to be recognized, false objects, and a background to be rejected is utilized in an iterative training procedure to design a nonlinear adaptive correlation filter with a given value of discrimination capability. The designed filter during recognition process adapts its parameters to local statistics of the input image. Computer simulation results obtained with the proposed filters in test nonuniform illuminated scenes are discussed and compared with those of linear composite correlation filters in terms of recognition performance.
more …
By
Rojo Ruiz, Arturo; Sánchez Fernandez, Luis P.; FelipeRiverón, Edgardo; Suárez Guerra, Sergio
Show all (4)
2 Citations
This paper presents a novel computational multimodal model designed for pattern recognition of aircrafts’ noise in real environments; with an 88.5% of effectiveness, it considers 13 different categories of aircrafts. This method includes measurements of signals of the noise produced during the takeoff at 25,000 samples per second and with a resolution of 24 bits, an spectral analysis made by means of an autoregressive model, an octave analysis, a normalization method created specifically for this work and two feedforward neural networks. All the signals used for the design and evaluation of the results were obtained by means of field measurements.
more …
By
García, V.; Mollineda, R. A.; Sánchez, J. S.
90 Citations
A twoclass data set is said to be imbalanced when one (minority) class is heavily underrepresented with respect to the other (majority) class. In the presence of a significant overlapping, the task of learning from imbalanced data can be a very difficult problem. Additionally, if the overall imbalance ratio is different from local imbalance ratios in overlap regions, the task can become in a major challenge. This paper explains the behaviour of the knearest neighbour (kNN) rule when learning from such a complex scenario. This local model is compared to other machine learning algorithms, attending to how their behaviour depends on a number of data complexity features (global imbalance, size of overlap region, and its local imbalance). As a result, several conclusions useful for classifier design are inferred.
more …
By
MachuchoCadena, Ruben; CruzRodríguez, Sergio; BayroCorrochano, Eduardo
2 Citations
We present an approach for reconstructing the 3D shape of brain tumors for applications in neurosurgery from 2D ultrasound (US) images. We record simultaneously endoscopic and ultrasonic images, and the pose of the endoscopic camera by an optical tracking system. The 3D pose of the ultrasound probe is determined by tracking the 2D position of the ultrasound probe in successive endoscopic images by image processing techniques (Hough Transform, Particle Filtering) and finally the 3D position is computed by the known camera geometry and multiple view geometry using conformal geometric algebra. When the 3D US probe position is calculated, we compound multiple 2D US images into a 3D volume.
more …
By
Guzmán, Francisco; Garrido, Leonardo
In this paper we present an analysis of a phrasebased machine translation methodology that integrates paraphrases obtained from an intermediary language (French) for translations between Spanish and English. The purpose of the research presented in this document is to find out how much extra information (i.e. improvements in translation quality) can be found when using Translation Paraphrases (TPs). In this document we present an extensive statistical analysis to support conclusions.
more …
