Brazil

Adding self-loops at each vertex of a graph improves the performance of quantum walks algorithms over loopless algorithms. Many works approach quantum walks to search for a single marked vertex. In this article, we experimentally address several problems related to quantum walk in the hypercube with self-loops to search for multiple marked vertices. We first investigate the quantum walk in the loopless hypercube. We saw that neighbor vertices are also amplified and that approximately $1/2$ of the system energy is concentrated in them. We show that the optimal value of $l$ for a single marked vertex is not optimal for multiple marked vertices. We define a new value of $l = (n/N)\cdot k$ to search multiple marked vertices. Next, we use this new value of $l$ found to analyze the search for multiple marked vertices non-adjacent and show that the probability of success is close to $1$. We also use the new value of $l$ found to analyze the search for several marked vertices that are adjacent and show that the probability of success is directly proportional to the density of marked vertices in the neighborhood. We also show that, in the case where neighbors are marked, if there is at least one non-adjacent marked vertex, the probability of success increases to close to $1$. The results found show that the self-loop value for the quantum walk in the hypercube to search for several marked vertices is $l = (n / N) \cdot k $.

BRACIS 2021

Lackadaisical quantum walk in the hypercube to search for multiple marked vertices

quantum search algorithm

quantum walk

quantum computing

The 9th Brazilian Conference on Intelligent Systems (BRACIS), the 16h Encontro Nacional de Inteligência Artificial e Computacional (ENIAC), and the 12th Concurso de Teses e Dissertações em Inteligência Artificial e Computacional (CTDIAC) was held from 20 to 23 October, 2020.

BRACIS originated from the combination of the two most important scientific events in Brazil in Artificial Intelligence (AI) and Computational Intelligence (CI): the Brazilian Symposium on Artificial Intelligence - SBIA (22 editions), and the Brazilian Symposium on Neural Networks - SBRN (13 editions). ENIAC is a national forum for researchers, practitioners, educators and students to present and discuss innovations, trends, experiences, developments and work in progress in the fields of Artificial and Computational Intelligence. CTDIAC is a satellite event whose goals are to disseminate and award the best dissertations and theses (MSc and PhDs concluded in Brazilian universities from June 2018 to May 2020) in Artificial and Computational Intelligence areas.

In this year, the Symposium on Knowledge Discovery, Mining and Learning (KDMiLe) will be held in conjunction with BRACIS 2020. This sysposium aims at integrating researchers, practitioners, developers, students and users to present their research results, to discuss ideas, and to exchange techniques, tools, and practical experiences – related to the Data Mining and Machine Learning areas.

BRACIS 2020

technical paper

**BRACIS** originated from the combination of the two most important scientific events in Brazil in Artificial Intelligence (AI) and Computational Intelligence (CI): the Brazilian Symposium on Artificial Intelligence – **SBIA** (22 editions), and the Brazilian Symposium on Neural Networks – **SBRN** (13 editions). **ENIAC** is a national forum for researchers, practitioners, educators and students to present and discuss innovations, trends, experiences, developments and work in progress in the fields of Artificial and Computational Intelligence. **STIL** is the bi-annual Language Technology event.
All events are supported by the Brazilian Computer Society – Special Interest Groups: **CE-IA**, **CE-IC** and **CE-PLN**.

To access the 10th Brazilian Conference on Intelligent Systems (**BRACIS**), you need to register for the conference.  Please visit the Conference official site to register

[Register now](http://c4ai.inova.usp.br/bracis2021/)

Register now

BRACIS originated from the combination of the two most important scientific events in Brazil in Artificial Intelligence (AI) and Computational Intelligence (CI): the Brazilian Symposium on Artificial Intelligence – SBIA (22 editions), and the Brazilian Symposium on Neural Networks – SBRN (13 editions). 
ENIAC is a national forum for researchers, practitioners, educators and students to present and discuss innovations, trends, experiences, developments and work in progress in the fields of Artificial and Computational Intelligence. 
STIL is the bi-annual Language Technology event.
All events are supported by the Brazilian Computer Society – Special Interest Groups: CE-IA, CE-IC and CE-PLN

Co-clustering is a specific type of clustering that addresses the problem of simultaneously clustering objects and attributes of a data matrix. Although general clustering techniques find non-overlapping co-clusters, finding possible overlaps between co-clusters can reveal embedded patterns in the data that the disjoint clusters cannot discover. The overlapping co-clustering approaches proposed in the literature focus on finding global overlapped co-clusters and they might overlook interesting local patterns that are not necessarily identified as global co-clusters. Discovering such local co-clusters increases the granularity of the analysis, and therefore more specific patterns can be captured. This is the objective of the present paper, which proposes the new Overlapped Co-Clustering (OCoClus) method for finding overlapped co-clusters on binary data, including both global and local patterns. This is a non-exhaustive method based on the co-occurrence of attributes and objects in the data. Another novelty of this method is that it is driven by an objective cost function that can automatically determine the number of co-clusters. We evaluate the proposed approach on publicly available datasets, both real and synthetic data, and compare the results with a number of baselines. Our approach shows better results than the baseline methods on synthetic data and demonstrates its efficacy in real data.

A Co-occurrence Based Approach for Mining Overlapped Co-clusters in Binary Data

Numerous problems in machine learning require some type of dimensionality reduction. Unsupervised metric learning deals with the definition of intrinsic and adaptive distance functions of a dataset. Locally linear embedding (LLE) consists of a widely used manifold learning algorithm that applies dimensionality reduction to find a more compact and meaningful representation of the observed data through the capturing of the local geometry of the patches. In order to overcome relevant limitations of the LLE approach, we introduce the LLE Kullback–Leibler (LLE-KL) method. The proposed method employs the KL divergence between patches of the $k$-nearest neighbors (KNN) graph instead of the pointwise Euclidean metric. Our objective with such a methodological modification is to increase the robustness of the LLE to the presence of noise or outliers in the data. Our empirical results using several real-world datasets indicate that the proposed method delivers a superior clustering allocation compared to state-of-the-art methods of dimensionality reduction-based metric learning.

A Kullback-Leibler divergence-based locally linear embedding method: a novel parametric approach for cluster analysis

In this presentation, we show our approach that seeks to apply computer vision to assist robots in classifying the target team's organizational structure faced with a group of malicious target agents. Thus, robots can select the most appropriate strategy among the containment strategies implemented for each organizational structure or continue with the method proposed by literature for cases where the targets are not organized.

Intelligent Agents for Observation and Containment of Malicious Targets Organizations

Question answering (QA) systems aim to answer human questions made in natural language. This type of functionality can be very useful in the most diverse application domains, such as the biomedical and clinical. Considering the clinical context, where we have a growing volume of information stored in electronic health records, answering questions about the patient status can improve the decision-making and optimize the patient care. In this work, we carried out the first experiments to develop a QA model for clinical texts in portuguese. To overcome the lack of corpora for the required language and context, we used a transfer learning approach supported by pre-trained attention-based models from the Transformers library. We fine-tuned the BioBERTpt model with a translated version of the SQuAD dataset. The evaluation showed promising results when evaluated in different clinical scenarios, even without the application of a clinical QA corpus to support a training process. The developed model is publicly available to the scientific community.

Experiments on Portuguese Clinical Question Answering

The de-identification of clinical notes is crucial for the reuse of electronic clinical data and is a common Named Entity Recognition (NER) task. Neural language models provide a great improvement in Natural Language Processing (NLP) tasks, such as NER, when they are integrated with neural network methods. This paper evaluates the use of current state-of-the-art deep learning methods (Bi-LSTM-CRF) in the task of identifying patient names in clinical notes, for de-identification purposes. We used two corpora and three language models to evaluate which combination delivers the best performance. In our experiments, the specific corpus for the de-identification of clinical notes and a contextualized embedding with word embeddings achieved the best result: an F-measure of 0.94.

De-identification of Clinical Notes Using Contextualized Language Models and a Token Classifier

Inertial Measurement Unit (IMU) sensors are present in everyday devices such as smartphones and fitness watches. As a result, the array of health-related research and applications that tap onto this data has been growing, but little attention has been devoted to the prediction of an individual's heart rate (HR) from IMU data, when undergoing a physical activity. Would that be even possible? If so, this could be used to design personalized sets of aerobic exercises, for instance. In this work, we show that it is viable to obtain accurate HR predictions from IMU data using Recurrent Neural Networks, provided only access to HR and IMU data from a short-lived, previously executed activity. We propose a novel method for initializing an RNN's hidden state vectors, using a specialized network that attempts to extract an embedding of the physical conditioning (PCE) of a subject. We show that using a discriminator in the training phase to help the model learn whether two PCEs belong to the same individual further reduces the prediction error. We evaluate the proposed model when predicting the HR of 23 subjects performing a variety of physical activities from IMU data available in public datasets (PAMAP2, PPG-DaLiA). For comparison, we use as baselines the only model specifically proposed for this task and an adapted state-of-the-art model for Human Activity Recognition (HAR), a closely related task. Our method, PCE-LSTM, yields over 10% lower mean absolute error. We demonstrate empirically that this error reduction is in part due to the use of the PCE. Last, we use the two datasets (PPG-DaLiA, WESAD) to show that PCE-LSTM can also be successfully applied when photoplethysmography (PPG) sensors are available, outperforming the state-of-the-art deep learning baselines by more than 30%.

Encoding Physical Conditioning from Inertial Sensors for Multi-step Heart Rate Estimation

This work investigates the use of a Deep Neural Network (DNN) to perform an estimation of the Weapon Engagement Zone (WEZ) maximum launch range. The WEZ allows the pilot to identify an airspace in which the available missile has a more significant probability of successfully engaging a particular target, i.e., a hypothetical area surrounding an aircraft in which an adversary is vulnerable to a shot. We propose an approach to determine the WEZ of a given missile using 50,000 simulated launches in variate conditions. These simulations are used to train a DNN that can predict the WEZ when the aircraft finds itself on different firing conditions, with a coefficient of determination of 0.99. It provides another procedure concerning preceding research since it employs a non-discretized model, i.e., it considers all directions of the WEZ at once, which has not been done previously. Additionally, the proposed method uses an experimental design that allows for fewer simulation runs, providing faster model training.

Weapon Engagement Zone Maximum Launch Range Estimation Using Deep Neural Network

Recently, Brazil's National Council of Justice (CNJ) highlighted the importance of robust solutions to perform automated lawsuit classification. A correct lawsuit classification substantially improves the assertiveness of (i) distribution, (ii) organization of the agenda of court hearing and sessions, (iii) classification of urgent measures and evidence, (iv) identification of prescription and (v) prevention. This paper investigates different text classification methods and different combinations of embeddings, extracted from Portuguese language models, and information about legislation cited in the initial documents. The models were trained with a Golden Collection of 16 thousand initial petitions and indictments from the Court of Justice of the State of Ceará, in Brazil, whose lawsuits were classified in the five more representative CNJ's classes - Common Civil Procedure, Execution of Extrajudicial Title, Criminal Action - Ordinary Procedure, Special Civil Court Procedure, and Tax Enforcement. Our best result was obtained by the BERT model, achieving 0.88 of F1 score (macro), in the experiment scenario that represents the lawsuit in an embedding formed by concatenating the texts of all the petitions that contain at least one citation to one legislation. Legal documents have specific characteristics such as long documents, specialized vocabulary, formal syntax, semantics based on a broad specific domain of knowledge, and citations to laws. Our interpretation is that the representation of the document through contextual embeddings generated by BERT, as well as the architecture of the model with bidirectional contexts, makes it possible to capture the specific context of the domain of legal documents.

Text Classification in Legal Documents Extracted from Lawsuits in Brazilian Courts

Bloat is a common issue regarding Genetic Programming (GP), specially noted in Symbolic Regression (SR) problems. Due to this, GP tends to generate a huge amount of ineffective code that could be avoided or removed. Code editing is one of many approaches to avoid bloat. The objective in this strategy is to mutate or remove subtrees which do not contribute to the final solution. Two known methods of redundant code removal, the Rule Based Simplification (RBS) and Equivalent Decision Simplification (EDS) are extended in a new operator presented in this paper, called Dynamic Operator with RBS and EDS (DORE). This operator gives the algebraic simplification table used by RBS the potential to learn from reductions performed by EDS. An initial benchmark highlighted how the RBS table can grow as much as 86% with DORE, and reducing the time spent on simplification by 16.83%. Experiments with the other three SR problems were performed showing a considerable improvement on fitness of the generated programs, besides a slight reduction in the population of the average tree size.

Improving Rule Based and Equivalent Decision Simplifications for Bloat Control in Genetic Programming Using a Dynamic Operator

In the Steiner Tree Problem in Graphs, a subset of nodes, called terminals, must be efficiently interconnected. The graph is undirected and weighted, and candidate solutions can include additional nodes called Steiner vertices. The problem is NP-complete, and optimization algorithms based on population metaheuristics, e.g., Genetic Algorithms (GAs), have been proposed. However, traditional recombination operators may produce inefficient solutions for graph-based problems. We propose a new recombination operator for the Steiner Tree Problem based on the graph representation. The new operator is a kind of partition crossover: it breaks the graph formed by the union of two parents solutions and decomposes the evaluation function by finding connected subgraphs. We also investigate two soft-repair operators that produce small changes in candidate solutions: an MST transformation and a pruning repair. The GA with the proposed crossover operator was able to find the global optimum solution for all tested instances and has a success rate of 28\% in the worst case. The experiments with the proposed crossover presented a quick convergence to optimal solutions, and an average solution cost lower in most cases than other approaches.

Premium content

Lackadaisical quantum walk in the hypercube to search for multiple marked vertices

Downloads

Next from BRACIS 2021

A Co-occurrence Based Approach for Mining Overlapped Co-clusters in Binary Data

Similar lecture

Impacts of Multiple Solutions on the Lackadaisical Quantum Walk Search Algorithm

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES