Yuanzhi Ke

The Minimum Hitting Set (MinHS) problem is a classic NP-hard problem in combinatorial optimization, widely applied across fields such as artificial intelligence diagnosis, bioinformatics, and network monitoring. This paper proposes a local search algorithm with Dual-evaluation mode, named DemHS (Dual-evaluation mode search algorithm), tailored for large-scale hitting set instances. The evaluation employs two types of functions: strong and weak. Strong evaluation accurately calculates the exchange gain by introducing a cross-correction term within the local neighborhood defined by an inserted vertex; meanwhile, weak evaluation quickly estimates the gain through global random sampling to broaden the search scope. These two functions synergistically guide the search process. Furthermore, we introduce an age strategy to break ties and enhance the diversity of the search path. When no improvements are made for extended iterations, a large-scale random perturbation is executed to help the algorithm escape local stagnation. Comparative experiments were conducted using 200 public hitting set instances (100 metaheuristic and 100 exact cases) from PACE-2025. The results show that, in the metaheuristic case group, DemHS improves the record on 62 instances and in the precise case group, DemHS obtains optimal solutions across all tested instances. The ablation studies demonstrate a significant positive gain from the dual-evaluation neighborhood structure on optimization results.

Argumentation has become one of the important fields of artificial intelligence. This paper proposes a dual-neighborhood tabu search (DNTS) method specifically designed to find a single stable extension in abstract argumentation frameworks. The proposed algorithm implements an improved dual-neighborhood strategy incorporating a fast neighborhood evaluation method. In addition, by introducing techniques such as tabu and perturbation, this algorithm is able to jump out of the local optimum, which significantly improves the performance of the algorithm. In order to evaluate the effectiveness of the method, the performance of the algorithm on more than 300 randomly generated benchmark datasets was studied and compared with the algorithm in the literature. In the experiment, DNTS outperforms the other method regarding time consumption in more than 50 instances and surpasses the other meta-heuristic method in the number of solved cases. Further analysis shows that the initialization method, the tabu strategy, and the perturbation technique help guarantee the efficiency of the proposed DNTS.

This paper presents an algorithm for effectively maintaining the minimum spanning tree in dynamic weighted undirected graphs. The algorithm efficiently updates the minimum spanning tree when the underlying graph structure changes. By identifying the portion of the original tree that can be preserved in the updated tree, our algorithm avoids recalculating the minimum spanning tree from scratch. We provide proof of correctness for the proposed algorithm and analyze its time complexity. In general scenarios, the time complexity of our algorithm is comparable to that of Kruskal’s algorithm. However, the experimental results demonstrate that our algorithm outperforms the approach of recomputing the minimum spanning tree by using Kruskal’s algorithm, especially in medium- and large-scale dynamic graphs where the graph undergoes iterative changes.

Named entity recognition (NER) is particularly challenging for medical texts due to the high domain specificity, abundance of technical terms, and sparsity of data in this field. In this work, we propose a novel attention layer, called the “ontology attention layer”, that enhances the NER performance of a language model for clinical text by utilizing an ontology consisting of conceptual classes related to the target entity set. The proposed layer computes the relevance between each input token and the classes in the ontology and then fuses the encoded token vectors and the class vectors to enhance the token vectors by explicit superior knowledge. In our experiments, we apply the proposed layer to various language models for an NER task based on a Chinese clinical dataset to evaluate the performance of the layer. We also investigate the influence of the granularity of the classes utilized in the ontology attention layer. The experimental results show that the proposed ontology attention layer improved F1 scores by 0.4% to 0.5%. The results suggest that the proposed method is an effective approach to improving the NER performance of existing language models for clinical datasets.

Yuanzhi Ke, Zhangju Yin, Xinyun Wu, Caiquan Xiong. Proceedings of The 9th Social Media Mining for Health Research and Applications (SMM4H 2024) Workshop and Shared Tasks. 2024.

Yuanzhi Ke, Hanbo Jin, Xinyun Wu, Caiquan Xiong. Proceedings of The 9th Social Media Mining for Health Research and Applications (SMM4H 2024) Workshop and Shared Tasks. 2024.

The character vocabulary can be very large in non-alphabetic languages such as Chinese and Japanese, which makes neural network models huge to process such languages. We explored a model for sentiment classification that takes the embeddings of the radicals of the Chinese characters, i.e, hanzi of Chinese and kanji of Japanese. Our model is composed of a CNN word feature encoder and a bi-directional RNN document feature encoder. The results achieved are on par with the character embedding-based models, and close to the state-of-the-art word embedding-based models, with 90% smaller vocabulary, and at least 13% and 80% fewer parameters than the character embedding-based models and word embedding-based models respectively. The results suggest that the radical embedding-based approach is cost-effective for machine learning on Chinese and Japanese.

Though there are some works on improving distributed word representations using lexicons, the improper over-fitting of the words that have multiple meanings is a remaining issue deteriorating the learning when lexicons are used, which needs to be solved. An alternative method is to allocate a vector per sense instead of a vector per word. However, the word representations estimated in the former way are not as easy to use as the latter one. Our previous work uses a probabilistic method to alleviate the overfitting, but it is not robust with a small corpus. In this paper, we propose a new neural network to estimate distributed word representations using a lexicon and a corpus. We add a lexicon layer in the continuous bag-of-words model and a threshold node after the output of the lexicon layer. The threshold rejects the unreliable outputs of the lexicon layer that are less likely to be the same with their inputs. In this way, it alleviates the overfitting of the polysemous words. The proposed neural network can be trained using negative sampling, which maximizing the log probabilities of target words given the context words, by distinguishing the target words from random noises. We compare the proposed neural network with the continuous bag-of-words model, the other works improving it, and the previous works estimating distributed word representations using both a lexicon and a corpus. The experimental results show that the proposed neural network is more efficient and balanced for both semantic tasks and syntactic tasks than the previous works, and robust to the size of the corpus.