Vol. 48, No. 3,
Mar. 2021
Digital Library
Parallel Implementation of the Order-Preserving Multiple Pattern Matching Algorithm using the Karp-Rabin Algorithm
Kyung Bin Park, Youngho Kim, Jeong Seop Sim
http://doi.org/10.5626/JOK.2021.48.3.249
When two strings of the same length have the same relative orders, they are called order-isomorphic. Given a text T(｜T｜=n)and a set of patterns P̃={P₁,P₂,...,Pk}, the order-preserving multiple pattern matching problem is to find all substrings of T that are order-isomorphic to any pattern in P̃ . Let m be the length of the shortest pattern, m̅ be the length of the longest pattern, and M be the sum of lengths of all the patterns in P̃. When M is polynomial with respect to m, an order-preserving multiple pattern matching algorithm using the Karp-Rabin algorithm was presented whose searching step runs in O(n) time on average. In this paper, we implemented an order-preserving multiple pattern matching algorithm using the Karp-Rabin algorithm in parallel. It runs in O(m̅) time on average using O(M) threads in the preprocessing step and runs in O(m) time on average using O(n) threads in the searching step. The experimental results for random strings as input showed that our parallel implementation performed approximately 201.5 times faster than the existing sequential algorithm when n=1,000,000, k=1,000, m=5.
Analyzing the Effects of API Calls in Android Malware Detection Using Machine Learning
Seonghyun Park, Munyeong Kang, Jihyeon Park, Seong-je Cho, Sangchul Han
http://doi.org/10.5626/JOK.2021.48.3.257
This paper evaluates the effect of preprocessing and representing API call information on the accuracy of the system to detect malicious Android apps. We extract API calls that access or control sensitive data from target apps, and use the calls in machine learning algorithms to detect malicious apps. We then determine which expression of the API calls is most effective in classifying the apps as malicious or benign. Four ways of representing each API call are considered: class/method name with and without arguments/return type, and its presence (whether an API is called or not) and its frequency if called. The detection system has performed slightly better when the arguments/return type and the frequency of each API call were considered together. Its feature size was most efficient when considering the class/method name and the presence of each API call.
Efficient and Robust Implementation of the Algorithms for Parity-Constrained k-Center and Facility Location
http://doi.org/10.5626/JOK.2021.48.3.264
In this paper, we present heuristics for improving the exact and approximation algorithms for parity-constrained k -center and facility location problems, along with their computational evaluations. For the theoretical and practical relevance of these problems, constant-factor approximation algorithms are known for both problems. Unfortunately, few studies have been conducted to obtain a practically adequate implementation of exact and/or approximation algorithms for either problem. This paper fills in this gap by devising heuristics to improve the running time, solution quality, and numerical errors of the algorithms for both problems and measuring their performance. We also evaluate the known constant-factor approximation algorithms in comparison to exact algorithms.
Evaluating of Korean Machine Reading Comprehension Generalization Performance via Cross-, Blind and Open-Domain QA Dataset Assessment
http://doi.org/10.5626/JOK.2021.48.3.275
Machine reading comprehension (MRC) entails identification of the correct answer in a paragraph when a natural language question and paragraph are provided. Recently, fine-tuning based on a pre-trained language model yields the best performance. In this study, we evaluated the ability of machine-reading comprehension method to generalize question and paragraph pairs, rather than similar training sets. Towards this end, the cross-evaluation between datasets and blind evaluation was performed. The results showed a correlation between generalization performance and datasets such as answer length and overlap ratio between question and paragraph. As a result of blind evaluation, the evaluation dataset with the long answer and low lexical overlap between the questions and paragraphs resulted in less than 80% performance. Finally, the generalized performance of the MRC model under the open domain QA environment was evaluated, and the performance of the MRC using the searched paragraph was found to be degraded. According to the MRC task characteristics, the difficulty and differences in generalization performance depend on the relationship between the question and the answer, suggesting the need for analysis of different evaluation sets.
An Evaluation Method for Generalization Errors of CNN using Training Data
http://doi.org/10.5626/JOK.2021.48.3.284
Even with high-performance CNNs, generalization errors, which are the errors on test datasets that are expected in the real world, are often high. This generalization error must be reduced so that the model can maintain its learned performance in the real world. This paper defines a response set as a neuron set that is frequently activated for each model class learned from the training dataset with high data diversity. Also, the differences in generalization errors due to the data diversity of the test dataset are considered. The difference is defined as a relative generalization error. In the current work, an evaluation method for CNN generalization error using only the training dataset is proposed by using the relationship between the CNN class response set and the relative generalization error. The case study confirms that the response set ratio is related to the relative generalization error and demonstrates the effectiveness of the evaluation method for generalization errors of CNN using training data.
A BIT Named Entity Format Suitable for Low Resource Environments
Ho Yoon, Chang-Hyun Kim, Min-ah Cheon, Ho-min Park, Young Namgoong, Min-seok Choi, Jae-kyun Kim, Jae-Hoon Kim
http://doi.org/10.5626/JOK.2021.48.3.293
Named entity recognition (NER) seeks to locate and classify named entities into predefined categories such as person names, organization, location, and others. Most name entities consist of more than one word and so the multitude of annotated corpora for NER are encoded by the BIO (short for Beginning, Inside, and Outside) format: A “B-” prefix before a tag indicates that the tag is the beginning of a named entity, and an “I-” prefix before a tag indicates that the tag is inside the named entity. An “O” tag indicates that a word belongs to no named entity. In this format, words with “O” tags in the corpora amount to more than about 90% of the words and thus, can cause two problems: the high perplexity of words with “O” tags and imbalance learning. In this paper, we propose a novel format to represent the NER corpus called the BIT format, which uses “T (short for POS Tags)” tags in place of “O” tags. Experiments have shown that the BIT format outperforms the BIO format when the meaning projection of the word representation is unreliable, namely, when word embedding is trained through a relatively small number of words.
Color Scheme Extraction Based on Image Segmentation and Saliency Map
http://doi.org/10.5626/JOK.2021.48.3.302
Color is the primary visual element that has the greatest amount of influence on the recognition of images. A color scheme is arranged through selection of a certain number of colors. Color schemes are used in various visual fields, such as fashion, cosmetics, interior design, media, and the arts. In this study, we introduce a method of automatically extracting color schemes from images. To overcome the shortcomings of previous methods, our method extracts a color scheme based on image segmentation and saliency map extraction. It also has the advantage of scalability, as it extracts schemes depending on their relative levels of importance in the image.
Research on Social Information Processing using the Augmented Reality Device: Comparison with Real-World Human Interaction
Jaehwan You, Jiwoong Heo, Enjoo Kim, Kwanguk Kim
http://doi.org/10.5626/JOK.2021.48.3.308
Research on augmented reality (AR) has focused on the development of technologies and its task performances. However, the effect of AR technologies on social interaction is yet to be rigorously examined. Social interaction is one of the key components of human learning and cognitive developments. In this study, we compared initiating and responding joint attention with the social information processing task, and each participant conducted both AR and real-world conditions. Thirty-three participants were enrolled in the current study, and dependent measures included accuracies of target, non-target, and novel pictures, and total head-movements. The results suggested that there were no significant differences in information processing of target and novel pictures, but we found that accuracies of non-target pictures and total head-movements were significantly different between AR and real-world conditions. These results suggested that AR devices can be used for social information processing tasks, but they need improvements, which are discussed in the current study.
Boosting Image Caption Generation with Parts of Speech
Philgoo Kang, Yubin Lim, Hyoungjoo Kim
http://doi.org/10.5626/JOK.2021.48.3.317
With the integration of smart devices and reliance on AI into our daily lives, the ability to generate image caption is becoming increasingly important in various fields such as guidance for visually-impaired individuals, human-computer interaction and so on. In this paper, we propose a novel approach based on parts of speech (POS), such as nouns and verbs extracted from image to enhance the image caption generation. The proposed model exploits multiple CNN encoders, which were specifically trained to identify features related to POS, and feed them into an LSTM decoder to generate image captions. We conducted experiments involving both Flickr30k and MS-COCO datasets using several text metrics and additional human surveys to validate the practical effectiveness of the proposed model.
Feature Pyramid Network-based Long-Distance Drone Detection Method
Jeongin Kwon, Sohee Son, Jinwoo Jeon, Injae Lee, Jihun Cha, Haechul Choi
http://doi.org/10.5626/JOK.2021.48.3.325
With the rapid development in the field of drones, the need for a surveillance system to prevent accidents caused by drones has increased. Considering the high speed of drones, they must be detected from a distance. In long-distance images, the target size is very small and the background can be complex. Even if a deep learning technique is used for object detection the false detection rate remains very high. This paper introduces a multi-frame based post-processing method that can effectively reduce the false detection rate of feature pyramid network (FPN), which works well for tiny-object detection. The proposed post-processing method indexes detected objects and compares the distance and size difference concerning the corresponding objects of the previous frame to determine whether it is a false positive (FP) or not. FPN is trained on 44,986 images with annotations from 360 image sequences taken by hand. Experimental results show that the proposed method reduces the FP rate overall evaluation sequences by more than 80% and also increases the F-measure.
Generative Adversarial Networks Using Pre-trained Generator for Effective Auditory Noise Suppression
http://doi.org/10.5626/JOK.2021.48.3.334
Speech enhancement GAN (SEGAN) is one of the models showing good performance in removing acoustic noise based on the genrative adversarial network, which is one of the deep learning models. However, there is a problem that the generator is easily unstable while learning non-stationary noise with a very wide distribution with one genrator. In this paper, to improve this problem, we propose an adversarial learning method using a pre-trained generator. The output of the learned generator in the same way as the autoencoder is used as the input of the adversarial learning generator. It improve stability and alleviate the difficulty of the problem, through the primary reduced noisy signal. In this paper, the Scale Invariant Signal to Noise Ratio (SI-SNR) evaluation index was used to objectively evaluate the performance of the model. As a result of the experiment, the SI-SNR increased by about 4.08 compared to the noisy speech, confirming that the proposed method is useful for removing noise.
Self-revising Transformer with Multi-view for Image Captioning
Jieun Lee, Jinuk Park, Sanghyun Park
http://doi.org/10.5626/JOK.2021.48.3.340
Image captioning is a task of automatically describing a scene by identifying an object element from a given image. In prior research, information has mainly been captured from the image using a single feature extractor, and captions have then been generated by a recurrent neural network-based decoder. However, multi-view image information is not available with this method because of the use of a single feature extractor, and the use of a recurrent neural network-based decoder causes a long-term dependency problem. To address these issues, the proposed model employs a multi-view encoder using a couple of feature extractors that provide processed image information from various view. In addition, to supplement the limits of the recurrent neural network, we propose a self-revising transformer that increases the completeness of sentences by revising the generated sentences by focusing additional multi-head attention in the transformer-based decoder layer. To present the proposed model, we verify its superiority through quantitative and qualitative evaluations with various comparative experiments using MSCOCO datasets.
On Equi-LR automata
http://doi.org/10.5626/JOK.2021.48.3.352
LR parsing is a representative bottom-up parsing method, and LR automata have been used as the essential frame for the construction of LR parser. This paper defines an equivalence class of classical LR items, which is called Equi-LR class and defines Equi-LR automata by using Equi-LR class instead of classical LR items. This paper shows that Equi-LR automata have the advantage of reduced construction time over classical LR automata, and the size complexity of LR parser in the frame of Equi-LR automata is tighter compared with the frame of classical LR automata.
A Sort and Merge Method for Genome Variant Call Format (GVCF) Files using Parallel and Distributed Computing
JinWoo Lee, Jung-Im Won, JeeHee Yoon
http://doi.org/10.5626/JOK.2021.48.3.358
With the development of next-generation sequencing (NGS) techniques, a large volume of genomic data is being produced and accumulated, and parallel and distributed computing has become an essential tool. Generally, NGS data processing entails two main steps: obtaining read alignment results in BAM format and extracting variant information in genome variant call format (GVCF) or variant call format (VCF). However, each step requires a long execution time due to the size of the data. In this study, we propose a new GVCF file sorting/merging module using distributed parallel clusters to shorten the execution time. In the proposed algorithm, Spark is used as a distributed parallel cluster. The sorting/merge process is performed in two steps according to the structural characteristics of the GVCF file in order to use the resources in the cluster efficiently. The performance was evaluated by comparing our method with the GATK"s CombineGVCFs module based on sorting and merging execution time of multiple GVCF files. The outcomes suggest the effectiveness of the proposed method in reducing execution time. The method can be used as a scalable and powerful distributed computing tool to solve the GVCF file sorting/merge problem.
Search
Journal of KIISE
- ISSN : 2383-630X(Print)
- ISSN : 2383-6296(Electronic)
- KCI Accredited Journal
Editorial Office
- Tel. +82-2-588-9240
- Fax. +82-2-521-1352
- E-mail. chwoo@kiise.or.kr