Institute of Information Science
Current Research Results
"Building/environment Data/information Enabled Location Specificity and Indoor Positioning," IEEE Internet of Things Journal, To Appear.
Authors: C. C. Li, J. Su, E. T. H. Chu and J. W. S. Liu

Jane Win ShihLiuAbstract:

The building/environment data and information system (BeDIS) described here is a part of infrastructure needed to support location-specific, active emergency preparedness and responses within large buildings. BeDIPS (Building/environment Data and information based Indoor Positioning System) is one of its components. BeDIPS can provide people in large buildings with sufficiently accurate location data. It is scalable, disaster resilient and is easy to configure, deploy and maintain. BeDIPS works without Internet and serves both smart phones and most legacy Bluetooth devices. The other component of BeDIS is BeDi mist, a virtual repository of data and information on the building, interior layouts and facilities. The mist uses micro data servers and smart gateways to deliver fine-scale, location-specific decision support data on a timely basis to hundreds and thousands of active devices and mobile applications.

Current Research Results
"A Position-Aware Language Modeling Framework for Extractive Broadcast News Speech Summarization," ACM Transactions on Asian and Low-Resource Language Information Processing, August 2017.
Authors: Shih-Hung Liu, Kuan-Yu Chen, Yu-Lun Hsieh, Berlin Chen, Hsin-Min Wang, Hsu-Chun Yen, and Wen-Lian Hsu

Extractive summarization, a process that automatically picks exemplary sentences from a text (or spoken) document with the goal of concisely conveying key information therein, has seen a surge of attention from scholars and practitioners recently. Using a language modeling (LM) approach for sentence selection has been proven effective for performing unsupervised extractive summarization. However, one of the major difficulties facing the LM approach is to model sentences and estimate their parameters more accurately for each text (or spoken) document. We extend this line of research and make the following contributions in this work. First, we propose a position-aware language modeling framework using various granularities of position-specific information to better estimate the sentence models involved in the summarization process. Second, we explore disparate ways to integrate the positional cues into relevance models through a pseudo-relevance feedback procedure. Third, we extensively evaluate various models originated from our proposed framework and several well-established unsupervised methods. Empirical evaluation conducted on a broadcast news summarization task further demonstrates performance merits of the proposed summarization methods.
Current Research Results
Authors: Ling-Jyh Chen, Yao-Hua Ho, Hu-Cheng Lee, Hsuan-Cho Wu, Hao-Min Liu, Hsin-Hung Hsieh, Yu-Te Huang, and Shih-Chun Candice Lung

As the population in cities continues to increase rapidly, air pollution become a serious issue from public health to social economy.  Among all pollutants, fine particulate matters (PM2.5) directly related to various serious health concerns, e.g., lung cancer, premature death, asthma, cardiovascular and respiratory diseases. To enhance the quality of urban living, sensors are deployed to create smart cities. In this paper, we present a participatory urban sensing framework for PM2.5 monitoring with more than 2,500 devices deployed in Taiwan and 29 other countries.  It is one of the largest deployment project for PM2.5 monitor in the world as we know until May 2017. The key feature of the framework is its open system architecture, which is based on the principles of open hardware, open source software, and open data. To facilitate the deployment of the framework, we investigate the accuracy issue of low-cost particle sensors with a comprehensive set of comparison evaluations to identify the most reliable sensor. By working closely with government authorities, industry partners, and maker communities, we can construct an effective eco-system for participatory urban sensing of PM2.5 particles. Based on our deployment achievements to date, we provide a number of data services to improve environmental awareness, trigger on-demand responses, and assist future government policymaking. The proposed framework is highly scalable and sustainable with the potential to facilitate the Internet of Things, smart cities and citizen science in the future.
Current Research Results
"Mixture of Gaussian Blur Kernel Representation for Blind Image Restoration," IEEE Transactions on Computational Imaging, To Appear.
Authors: Chia-Chen Lee , Wen-Liang Hwang

Blind image restoration is a non-convex problem involving the restoration of images using unknown blur kernels. The success of the restoration process depends on three factors: 1) the amount of prior information concerning the image and blur kernel; 2) the algorithm used to perform restoration; and 3) the initial guesses made by the algorithm. Prior information of an image can often be used to restore the sharpness of edges. By contrast, there is no consensus concerning the use of prior information in the restoration of images from blur kernels, due to the complex nature of image blurring processes. In this paper, we model a blur kernel as a linear combination of basic 2-D patterns. To illustrate this process, we constructed a dictionary comprising atoms of Gaussian functions derived from the Kronecker product of 1-D Gaussian sequences. Our results show that the proposed method is more robust than other state-of-the-art methods in a noisy environment, due to its increased signal-to-noise ratio (ISNR). This approach also proved more stable than the other methods, due to the steady increase in ISNR as the number of iterations is increased.
"Automatic Music Video Generation Based on Simultaneous Soundtrack Recommendation and Video Editing," ACM Multimedia Conference 2017, October 2017.
Authors: Jen-Chun Lin, Wen-Li Wei, James Yang, Hsin-Min Wang, and Hong-Yuan Mark Liao

An automated process that can suggest a soundtrack to a user-generated video (UGV) and make the UGV a music-compliant professional-like video is challenging but desirable. To this end, this paper presents an automatic music video (MV) generation system that conducts soundtrack recommendation and video editing simultaneously. Given a long UGV, it is first divided into a sequence of fixed-length short (e.g., 2 seconds) segments, and then a multi-task deep neural network (MDNN) is applied to predict the pseudo acoustic (music) features (or called the pseudo song) from the visual (video) features of each video segment. In this way, the distance between any pair of video and music segments of same length can be computed in the music feature space. Second, the sequence of pseudo acoustic (music) features of the UGV and the sequence of the acoustic (music) features of each music track in the music collection are temporarily aligned by the dynamic time warping (DTW) algorithm with a pseudo-song-based deep similarity matching (PDSM) metric. Third, for each music track, the video editing module selects and concatenates the segments of the UGV based on the target and concatenation costs given by a pseudo-song-based deep concatenation cost (PDCC) metric according to the DTW-aligned result to generate a music-compliant professional-like video. Finally, all the generated MVs are ranked, and the best MV is recommended to the user. The MDNN for pseudo song prediction and the PDSM and PDCC metrics are trained by an annotated official music video (OMV) corpus. The results of objective and subjective experiments demonstrate that the proposed system performs well and can generate appealing MVs with better viewing and listening experiences.
"Exploiting Asymmetric SIMD Register Configurations in ARM-to-x86 Dynamic Binary Translation," The 26th International Conference on Parallel Architectures and Compilation Techniques (PACT), September 2017.
Authors: Yu-Ping Liu, Ding-Yong Hong, Jan-Jan Wu, Sheng-Yu Fu, Wei-Chung Hsu

Processor manufacturers have adopted SIMD for decades because of its superior performance and power efficiency. The configurations of SIMD registers (i.e., the number and width) have evolved and diverged rapidly through various ISA extensions on different architectures. However, migrating legacy or proprietary applications optimized for one guest ISA to another host ISA that has fewer but longer SIMD registers through binary translation raises the issues of asymmetric SIMD register configurations. To date, these issues have been overlooked. As a result, only a small fraction of the potential performance gain is realized due to underutilization of the host’s SIMD parallelism and register capacity. In this paper, we present a novel dynamic binary translation technique called spill-aware SLP (saSLP), which combines short ARMv8 NEON instructions and registers in guest binary loops to fully utilize the x86 AVX host’s parallelism as well as minimize register spilling. Our experiment results show that saSLP improves the performance by 1.6X (2.3X) across a number of benchmarks, and reduces spilling by 97% (99%) for ARMv8 NEON to x86 AVX2 (AVX-512) translation.
"Virtual Persistent Cache: Remedy the Long Latency Behavior of Host-Aware Shingled Magnetic Recording Drives," ACM/IEEE International Conference on Computer-Aided Design (ICCAD), November 2017.
Authors: Ming-Chang Yang, Yuan-Hao Chang, Fenggang Wu, Tei-Wei Kuo, and David Hung-Chang Du

This paper presents a Virtual Persistent Cache design to remedy the long latency behavior of the Host-Aware Shingled Magnetic Recording (HA-SMR) drive. Our design keeps the cost-effective model of the existing HA-SMR drives, but at the same time asks the great help from the host system for adaptively providing some computing and management resources to improve the drive performance when needed. The technical contribution is to trick the HA-SMR drives by smartly reshaping the access patterns to HA-SMR drives, so as to avoid the occurrences of long latencies in most cases and thus to ultimately improve the drive performance and responsiveness. We conduct experiments on real Seagate 8TB HA-SMR drives to demonstrate the advantages of \\textit{Virtual Persistent Cache} over the real workloads from Microsoft Research Cambridge. The results show that the proposed design can avoid at least 94.93% of long latencies and improve the drive performance by at least 58.11%, under the evaluated workloads.
Current Research Results
"Three TF Co-expression Modules Regulate Pressure-Overload Cardiac Hypertrophy in Male Mice," Scientific Reports, August 2017.
Authors: Yao-Ming Chang, Li Ling, Ya-Ting Chang, Yu-Wang Chang, Wen-Hsiung Li, Arthur Chun-Chieh Shih*, and Chien-Chang Chen*

Arthur Chun-ChiehShihAbstract:
Pathological cardiac hypertrophy, a dynamic remodeling process, is a major risk factor for heart failure. Although a number of key regulators and related genes have been identified, how the transcription factors (TFs) dynamically regulate the associated genes and control the morphological and electrophysiological changes during the hypertrophic process are still largely unknown. In this study, we obtained the time-course transcriptomes at five time points in four weeks from male murine hearts subjected to transverse aorta banding surgery. From a series of computational analyses, we identified three major co-expression modules of TF genes that may regulate the gene expression changes during the development of cardiac hypertrophy in mice. After pressure overload, the TF genes in Module 1 were up-regulated before the occurrence of significant morphological changes and one week later were down-regulated gradually, while those in Modules 2 and 3 took over the regulation as the heart size increased. Our analyses revealed that the TF genes up-regulated at the early stages likely initiated the cascading regulation and most of the well-known cardiac miRNAs were up-regulated at later stages for suppression. In addition, the constructed time-dependent regulatory network reveals some TFs including Egr2 as new candidate key regulators of cardiovascularassociated (CV) genes.
Current Research Results
"On Space Utilization Enhancement of File Systems for Embedded Storage Systems," ACM Transactions on Embedded Computing Systems (TECS), April 2017.
Authors: Tseng-Yi Chen, Yuan-Hao Chang, Shuo-Han Chen, Nien-I Hsu, Hsin-Wen Wei, and Wei-Kuan Shih

In the past decade, mobile/embedded computing systems conventionally have limited computing power, RAM space, and storage capacity due to the consideration of their cost, energy consumption, and physical size. Recently, some of these systems, such as mobile phone and embedded consumer electronics, have more powerful computing capability, so they manage their data in small flash storage devices  (e.g., eMMC and SD cards) with a simple file system. However, the existing file systems usually have low space utilization for managing small files and the tail data of large files. In this work, we thus propose a dynamic tail packing scheme to enhance the space utilization of file systems over flash storage devices in embedded computing systems by dynamically aggregating/packing the tail data of (small) files together. To evaluate the benefits and overheads of the proposed scheme, we theoretically formulate analysis equations for obtaining the best settings in the dynamic tail packing scheme. Additionally, the proposed scheme was implemented in the file system of Linux operating systems to evaluate its capability. The results demonstrate that the proposed scheme could significantly improve the space utilization of existing file systems.
Current Research Results
"Supervised Learning of Semantics-Preserving Hash via Deep Convolutional Neural Networks," IEEE Transactions on Pattern Analysis and Machine Intelligence, 2017.
Authors: Huei-Fang Yang, Kevin Lin, and Chu-Song Chen

This paper presents a simple yet effective supervised deep hash approach that constructs binary hash codes from labeled data for large-scale image search. We assume that the semantic labels are governed by several latent attributes with each attribute on or off, and classification relies on these attributes. Based on this assumption, our approach, dubbed supervised semantics-preserving deep hashing (SSDH), constructs hash functions as a latent layer in a deep network and the binary codes are learned by minimizing an objective function defined over classification error and other desirable hash codes properties. With this design, SSDH has a nice characteristic that classification and retrieval are unified in a single learning model. Moreover, SSDH performs joint learning of image representations, hash codes, and classification in a point-wised manner, and thus is scalable to large-scale datasets. SSDH is simple and can be realized by a slight enhancement of an existing deep architecture for classification; yet it is effective and outperforms other hashing approaches on several benchmarks and large datasets. Compared with state-of-the-art approaches, SSDH achieves higher retrieval accuracy, while the classification performance is not sacrificed.
"Recognizing Offensive Tactics in Broadcast Basketball Videos via Key Player Detection," IEEE International Conference on Image Processing, October 2017.
Authors: T.Y. Tsai, Y. Y. Lin, H.Y. Mark Liao, and S. K. Jeng

We address offensive tactic recognition in broadcast basket- ball videos. As a crucial component towards basketball video content understanding, tactic recognition is quite challenging because it involves multiple independent players, each of which has respective spatial and temporal variations. Motivated by the observation that most intra-class variations are caused by non-key players, we present an approach that integrates key player detection into tactic recognition. To save the annotation cost, our approach can work on training data with only video-level tactic annotation, instead of key players labeling. Specifically, this task is formulated as an MIL (multiple instance learning) problem where a video is treated as a bag with its instances corresponding to subsets of the five players. We also propose a representation to encode the spatio-temporal interaction among multiple players. It turns out that our approach not only effectively recognizes the tac- tics but also precisely detects the key players.
"Distributed Compressive Sensing: Performance Analysis with Diverse Signal Ensembles," European Signal Processing Conference (EUSIPCO), August 2017.
Authors: Sung-Hsien Hsieh, Wei-Jie, Liang, Chun-Shien Lu, and Soo-Chang Pei

Distributed compressive sensing is a framework considering jointly sparsity within signal ensembles along with multiple measurement vectors (MMVs). The current theoretical bound of performance for MMVs, however, is derived to be the same with that for single MV (SMV) because the characteristics of signal ensembles are ignored. In this work, we introduce a new factor called “Euclidean distances between signals” for the performance analysis of a deterministic signal model under MMVs framework. We show that, by taking the size of signal ensembles into consideration, MMVs indeed exhibit better performance than SMV. Although our concept can be broadly applied to CS algorithms with MMVs, the case study conducted on a well-known greedy solver called simultaneous orthogonal matching pursuit (SOMP) will be explored in this paper. We show that the performance of SOMP, when incorporated with our concept by modifying the steps of support detection and signal estimations, will be improved remarkably, especially when the Euclidean distances between signals are short. The performance of modified SOMP is verified to meet our theoretical prediction.
"A System Calibration Model for Mobile PM2.5 Sensing Using Low-Cost Sensors," IEEE International Conference on Internet of Things (iThings'17), June 2017.
Authors: Hao-Min Liu, Hsuan-Cho Wu, Hu-Chen Lee, Yao-Hua Ho, and Ling-Jyh Chen

In this paper, we present a system calibration model (SCM) for mobile PM2.5 sensing systems using COTS low-cost particle sensors. To implement such systems, we first assess the accuracy of low-cost dust sensors and identify the most reliable sensor through a comprehensive set of evaluations. We also investigate the inner working principle of the selected sensor. By conducting a set of lab-scale controlled experiments, we obtained a logarithmic regression model that models the impacts of mobility and ambient wind velocity on PM2.5 sensing results. Moreover, using a low-cost water flow sensor, we design a customized micro anemometer and apply a linear regression model to convert the flow rate readings from the sensor to wind velocity values. Finally, we conduct a field experiment to evaluate the proposed calibration model in a real-world setting. The results show that the accuracy of the PM2.5 measurement results improves significantly when the model is utilized. The calibration model is simple and effective, and it can be utilized by other mobile sensing applications that facilitate micro-scale environmental sensing on the move.
"Dynamic Translation of Structured Loads/Stores and Register Mapping for Architectures with SIMD Extensions," ACM SIGPLAN/SIGBED Conference on Languages, Compilers, Tools and Theory for Embedded Systems, June 2017.
Authors: Sheng-Yu Fu, Ding-Yong Hong, Yu-Ping Liu, Jan-Jan Wu, Wei-Chung Hsu

More and more modern processors have been supporting noncontiguous SIMD data accesses. However, translating such instructions has been overlooked in the Dynamic Binary Translation (DBT) area. For example, in the popular QEMU dynamic binary translator, guest memory instructions with strides are emulated by a sequence of scalar instructions, leaving a significant room for performance improvement when the host machines have SIMD instructions available. Structured loads/stores, such as VLDn/VSTn in ARM NEON, are one type of strided SIMD data access instructions. They are widely used in signal processing, multimedia, mathematical and 2D matrix transposition applications. Efficient translation of such structured loads/stores is a critical issue when migrating ARM executables to other ISAs. However, it is quite challenging since not only the translation of structured loads/stores is not trivial, but also the difference between guest and host register configurations must be taken into consideration. In this work, we present the design and implementation of translating structured loads/stores in DBT, including target code generation as well as efficient SIMD register mapping. Our proposed register mapping mechanisms are not limited to handling structured loads/stores, they can be extended to deal with normal SIMD instructions. On a set of OpenCV benchmarks, our QEMU-based system has achieved a maximum speedup of 5.41x, with an average improvement of 2.93x. On a set of BLAS benchmarks, our system has also obtained a maximum speedup of 2.19x and an average improvement of 1.63x.
Current Research Results
Authors: Chi-Han Lin, Kate Ching-Ju Lin, and W. T. Chen

Body area networks (BANs) enable wearable/implanted devices to exchange information or collect monitored data. The channel quality of a link in a BAN is typically highly dynamic, since sensors equipped on a human body usually move with gesture, posture, or mobility. Therefore, existing sleep-wake-up scheduling mechanisms used in traditional static sensor networks could be very inefficient in a BAN, because they do not consider channel fluctuation of body sensors. Sensors might be waked up to transmit during bad channel conditions, leading to transmission failures and energy waste. To remedy this inefficiency, this paper proposes a Channel-aware Polling-based MAC protocol CPMAC. Our design only wakes sensors up and triggers them to transmit when the channel is strong enough to ensure fast and reliable transmissions. We further analyze the energy consumption and derive a queueing model to estimate the probability of completing all data transmissions of all sensors in our CPMAC. Benefiting from these analyses, we are able to optimize energy efficiency of our CPMAC by adapting the number of polling periods in a superframe to dynamic traffic demands and channel fluctuation. Our simulation results show that, as compared with TDMA-based scheduling and the IEEE 802.15.6 CSMA/CA protocol, CPMAC significantly improves energy efficiency and, meanwhile, keeps the latency short.
Authors: Kunwoo Park, Meeyoung Cha, Haewoon Kwak, and Kuan-Ta Chen

Retaining players over an extended period of time is a long-standing challenge in game industry. Significant effort has been paid to understanding what motivates players enjoy games. While individuals may have varying reasons to play or abandon a game at different stages within the game, previous studies have looked at the retention problem from a snapshot view. This study, by analyzing in-game logs of 51,104 distinct individuals in an online multiplayer game, uniquely offers a multifaceted view of the retention problem over the players' virtual life phases. We find that key indicators of longevity change with the game level. Achievement features are important for players at the initial to the advanced phases, yet social features become the most predictive of longevity once players reach the highest level offered by the game. These findings have theoretical and practical implications for designing online games that are adaptive to meeting the players' needs.
"Towards a Better Learning of Near-Synonyms: Automatically Suggesting Example Sentences via Filling in the Blank," the 26th International World Wide Web Conference (WWW 2017), Digital Learning Track, 2017.
Authors: Chieh-Yang Huang, Mei-Hua Chen and Lun-Wei Ku

Language learners are confused by near-synonyms and often look for answers from the Web. However, there is little to aid them in sorting through the overwhelming load of information that is offered.  In this paper, we propose a new research problem:   suggesting  example  sentences  for  learning  word distinctions.  We focus on near-synonyms as the first step. Two kinds of one-class classifiers,  the GMM and BiLSTM models, are used to solve fill-in-the-blank (FITB) questions and further to select example sentences which best differentiate groups of near-synonyms. Experiments are conducted on both an open benchmark and a private dataset for the FITB task.  Experiments show that the proposed approach yields an accuracy of 73.05% and 83.59% respectively, comparable to state-of-the-art multi-class classifiers.  Learner study further  shows  the  results  of  the  example  sentence  suggestion by the learning effectiveness and demonstrates the proposed model  indeed  is  more  effective  in  learning  near-synonyms compared to the resource-based models.
Current Research Results
"Kart: a divide-and-conquer algorithm for NGS read alignment," Bioinformatics, To Appear.
Authors: Hsin-Nan Lin and Wen-Lian Hsu

Motivation: Next-generation sequencing (NGS) provides a great opportunity to investigate genome-wide variation at nucleotide resolution. Due to the huge amount of data, NGS applications require very fast and accurate alignment algorithms. Most existing algorithms for read mapping basically adopt seed-and-extend strategy, which is sequential in nature and take much longer time on longer reads.
Results: We develop a divide-and-conquer algorithm, called Kart, which can process long reads as fast as short reads by dividing a read into small fragments that can be aligned independently. Our experiment result indicates that the average size of fragments requiring gapped alignment is around 20bp regardless of the original read length. Furthermore, it can tolerate much higher error rates. The experiments show that Kart spends much less time on longer reads than other aligners and still produce reliable alignments even when the error rate is as high as 15%.
Availability: Kart is available at
Supplementary information: Supplementary data are available at Bioinformatics online.
Current Research Results
Authors: Wei-Jie, Liang, Gang-Xuan Lin, and Chun-Shien Lu

Cost-efficient compressive sensing of large-scale images with quickly reconstructed high-quality results is very challenging. In this paper, we present an algorithm to solve convex optimization via the tree structure sparsity pattern, which can be run in the operator to reduce computation cost and maintain good quality, especially for large-scale images. We also provide convergence analysis and convergence rate analysis for the proposed method. The feasibility of our method is verified through simulations and comparison with the state-of-the-art algorithms.
Current Research Results
"Systematic identification of anti-interferon function on hepatitis C virus genome reveals p7 as an immune evasion protein," Proceedings of the National Academy of Sciences of the United States of America (PNAS), January 2017.
Authors: Hangfei Qi, Virginia Chu, Nicholas C. Wu, Zugen Chen, Shawna Truong, Gurpreet Brar, Sheng-Yao Su, Yushen Du, Vaithilingaraja Arumugaswami, C. Anders Olson, Shu-Hua Chen, Chung-Yen Lin, Ting-Ting Wu, and Ren Sun

Understanding how viruses interact with their hosts, especially the mechanisms that restrict virus replication, will provide a molecular basis for vaccine development. However, the search for restriction factors is oftentimes difficult if the virus has already evolved to counteract the restriction. Here, we describe a systematic approach to identify such restriction and counterrestriction mechanisms. We constructed a library of mutant hepatitis C viruses, where each mutant has a 15-nt stretch randomly inserted on the genome. We aimed to identify mutations that lose the anti-IFN function, but maintain replication capacity. We have identified p7 as an immune evasion protein and further characterize the antiviral function of IFI6-16 against hepatitus C virus (HCV) replication.


Academia Sinica 資訊科學研究所 Academia Sinica