-
Learning Sampling Distribution and Safety Filter for Autonomous Driving with VQ-VAE and Differentiable Optimization
Authors:
Simon Idoko,
Basant Sharma,
Arun Kumar Singh
Abstract:
Sampling trajectories from a distribution followed by ranking them based on a specified cost function is a common approach in autonomous driving. Typically, the sampling distribution is hand-crafted (e.g a Gaussian, or a grid). Recently, there have been efforts towards learning the sampling distribution through generative models such as Conditional Variational Autoencoder (CVAE). However, these ap…
▽ More
Sampling trajectories from a distribution followed by ranking them based on a specified cost function is a common approach in autonomous driving. Typically, the sampling distribution is hand-crafted (e.g a Gaussian, or a grid). Recently, there have been efforts towards learning the sampling distribution through generative models such as Conditional Variational Autoencoder (CVAE). However, these approaches fail to capture the multi-modality of the driving behaviour due to the Gaussian latent prior of the CVAE. Thus, in this paper, we re-imagine the distribution learning through vector quantized variational autoencoder (VQ-VAE), whose discrete latent-space is well equipped to capture multi-modal sampling distribution. The VQ-VAE is trained with demonstration data of optimal trajectories. We further propose a differentiable optimization based safety filter to minimally correct the VQVAE sampled trajectories to ensure collision avoidance. We use backpropagation through the optimization layers in a self-supervised learning set-up to learn good initialization and optimal parameters of the safety filter. We perform extensive comparisons with state-of-the-art CVAE-based baseline in dense and aggressive traffic scenarios and show a reduction of up to 12 times in collision-rate while being competitive in driving speeds.
△ Less
Submitted 25 April, 2024; v1 submitted 28 March, 2024;
originally announced March 2024.
-
A Note On Lookahead In Real Life And Computing
Authors:
Burle Sharma,
Rakesh Mohanty,
Sucheta Panda
Abstract:
Past, Present and Future are considered to be three temporal and logical concepts which are well defined by human beings for their existence and growth. We, as human beings, have the privilege of using our intelligence to mentally execute an activity before physical occurrence of the same in the real world. Knowledge of the past, aplomb of present and visualisation for the future correspond to thr…
▽ More
Past, Present and Future are considered to be three temporal and logical concepts which are well defined by human beings for their existence and growth. We, as human beings, have the privilege of using our intelligence to mentally execute an activity before physical occurrence of the same in the real world. Knowledge of the past, aplomb of present and visualisation for the future correspond to three concepts such as look-back, look-at and look-ahead respectively in real life as well as in diversified domains of computing. Look-Ahead(LA) deals with the future prediction of information and processing of input to produce the output in advance. In this article, our main objective is to learn, understand and explore the concept of LA and design novel models as solution for real world problems. We present three well known algorithmic frameworks used in practice based on availability of input information such as offline, online and semi-online. We introduce interesting real life applications and well known computing problems where LA plays a significant role for making a process, system or algorithm efficient. We define new types of LA and propose a taxonomy for LA based on literature review for designing novel LA models in future. Using the concept of LA, We identify and present many interesting and non-trivial research challenges as future potential research directions. Intuitively, we observe that LA can be used as a powerful tool and framework for future researchers in design of efficient computational models and algorithms for solving non-trivial and challenging optimization problems.
△ Less
Submitted 2 February, 2024;
originally announced March 2024.
-
Smart Textile-Driven Soft Spine Exosuit for Lifting Tasks in Industrial Applications
Authors:
Kefan Zhu,
Bibhu Sharma,
Phuoc Thien Phan,
James Davies,
Mai Thanh Thai,
Trung Thien Hoang,
Chi Cong Nguyen,
Adrienne Ji,
Emanuele Nicotra,
Nigel H. Lovell,
Thanh Nho Do
Abstract:
Work related musculoskeletal disorders (WMSDs) are often caused by repetitive lifting, making them a significant concern in occupational health. Although wearable assist devices have become the norm for mitigating the risk of back pain, most spinal assist devices still possess a partially rigid structure that impacts the user comfort and flexibility. This paper addresses this issue by presenting a…
▽ More
Work related musculoskeletal disorders (WMSDs) are often caused by repetitive lifting, making them a significant concern in occupational health. Although wearable assist devices have become the norm for mitigating the risk of back pain, most spinal assist devices still possess a partially rigid structure that impacts the user comfort and flexibility. This paper addresses this issue by presenting a smart textile actuated spine assistance robotic exosuit (SARE), which can conform to the back seamlessly without impeding the user movement and is incredibly lightweight. The SARE can assist the human erector spinae to complete any action with virtually infinite degrees of freedom. To detect the strain on the spine and to control the smart textile automatically, a soft knitting sensor which utilizes fluid pressure as sensing element is used. The new device is validated experimentally with human subjects where it reduces peak electromyography (EMG) signals of lumbar erector spinae by around 32 percent in loaded and around 22 percent in unloaded conditions. Moreover, the integrated EMG decreased by around 24.2 percent under loaded condition and around 23.6 percent under unloaded condition. In summary, the artificial muscle wearable device represents an anatomical solution to reduce the risk of muscle strain, metabolic energy cost and back pain associated with repetitive lifting tasks.
△ Less
Submitted 3 February, 2024;
originally announced February 2024.
-
End-to-End Learning of Behavioural Inputs for Autonomous Driving in Dense Traffic
Authors:
Jatan Shrestha,
Simon Idoko,
Basant Sharma,
Arun Kumar Singh
Abstract:
Trajectory sampling in the Frenet(road-aligned) frame, is one of the most popular methods for motion planning of autonomous vehicles. It operates by sampling a set of behavioural inputs, such as lane offset and forward speed, before solving a trajectory optimization problem conditioned on the sampled inputs. The sampling is handcrafted based on simple heuristics, does not adapt to driving scenario…
▽ More
Trajectory sampling in the Frenet(road-aligned) frame, is one of the most popular methods for motion planning of autonomous vehicles. It operates by sampling a set of behavioural inputs, such as lane offset and forward speed, before solving a trajectory optimization problem conditioned on the sampled inputs. The sampling is handcrafted based on simple heuristics, does not adapt to driving scenarios, and is oblivious to the capabilities of downstream trajectory planners. In this paper, we propose an end-to-end learning of behavioural input distribution from expert demonstrations or in a self-supervised manner. Our core novelty lies in embedding a custom differentiable trajectory optimizer as a layer in neural networks, allowing us to update behavioural inputs by considering the optimizer's feedback. Moreover, our end-to-end approach also ensures that the learned behavioural inputs aid the convergence of the optimizer. We improve the state-of-the-art in the following aspects. First, we show that learned behavioural inputs substantially decrease collision rate while improving driving efficiency over handcrafted approaches. Second, our approach outperforms model predictive control methods based on sampling-based optimization.
△ Less
Submitted 23 October, 2023;
originally announced October 2023.
-
Hilbert Space Embedding-based Trajectory Optimization for Multi-Modal Uncertain Obstacle Trajectory Prediction
Authors:
Basant Sharma,
Aditya Sharma,
K. Madhava Krishna,
Arun Kumar Singh
Abstract:
Safe autonomous driving critically depends on how well the ego-vehicle can predict the trajectories of neighboring vehicles. To this end, several trajectory prediction algorithms have been presented in the existing literature. Many of these approaches output a multi-modal distribution of obstacle trajectories instead of a single deterministic prediction to account for the underlying uncertainty. H…
▽ More
Safe autonomous driving critically depends on how well the ego-vehicle can predict the trajectories of neighboring vehicles. To this end, several trajectory prediction algorithms have been presented in the existing literature. Many of these approaches output a multi-modal distribution of obstacle trajectories instead of a single deterministic prediction to account for the underlying uncertainty. However, existing planners cannot handle the multi-modality based on just sample-level information of the predictions. With this motivation, this paper proposes a trajectory optimizer that can leverage the distributional aspects of the prediction in a computationally tractable and sample-efficient manner. Our optimizer can work with arbitrarily complex distributions and thus can be used with output distribution represented as a deep neural network. The core of our approach is built on embedding distribution in Reproducing Kernel Hilbert Space (RKHS), which we leverage in two ways. First, we propose an RKHS embedding approach to select probable samples from the obstacle trajectory distribution. Second, we rephrase chance-constrained optimization as distribution matching in RKHS and propose a novel sampling-based optimizer for its solution. We validate our approach with hand-crafted and neural network-based predictors trained on real-world datasets and show improvement over the existing stochastic optimization approaches in safety metrics.
△ Less
Submitted 12 October, 2023;
originally announced October 2023.
-
PRIEST: Projection Guided Sampling-Based Optimization For Autonomous Navigation
Authors:
Fatemeh Rastgar,
Houman Masnavi,
Basant Sharma,
Alvo Aabloo,
Jan Swevers,
Arun Kumar Singh
Abstract:
Efficient navigation in unknown and dynamic environments is crucial for expanding the application domain of mobile robots. The core challenge stems from the nonavailability of a feasible global path for guiding optimization-based local planners. As a result, existing local planners often get trapped in poor local minima. In this paper, we present a novel optimizer that can explore multiple homotop…
▽ More
Efficient navigation in unknown and dynamic environments is crucial for expanding the application domain of mobile robots. The core challenge stems from the nonavailability of a feasible global path for guiding optimization-based local planners. As a result, existing local planners often get trapped in poor local minima. In this paper, we present a novel optimizer that can explore multiple homotopies to plan high-quality trajectories over long horizons while still being fast enough for real-time applications. We build on the gradient-free paradigm by augmenting the trajectory sampling strategy with a projection optimization that guides the samples toward a feasible region. As a result, our approach can recover from the frequently encountered pathological cases wherein all the sampled trajectories lie in the high-cost region. Furthermore, we also show that our projection optimization has a highly parallelizable structure that can be easily accelerated over GPUs. We push the state-of-the-art in the following respects. Over the navigation stack of the Robot Operating System (ROS), we show an improvement of 7-13% in success rate and up to two times in total travel time metric. On the same benchmarks and metrics, our approach achieves up to 44% improvement over MPPI and its recent variants. On simple point-to-point navigation tasks, our optimizer is up to two times more reliable than SOTA gradient-based solvers, as well as sampling-based approaches such as the Cross-Entropy Method (CEM) and VPSTO. Codes: https://github.com/fatemeh-rastgar/PRIEST
△ Less
Submitted 15 September, 2023;
originally announced September 2023.
-
Improving Factuality of Abstractive Summarization via Contrastive Reward Learning
Authors:
I-Chun Chern,
Zhiruo Wang,
Sanjan Das,
Bhavuk Sharma,
Pengfei Liu,
Graham Neubig
Abstract:
Modern abstractive summarization models often generate summaries that contain hallucinated or contradictory information. In this paper, we propose a simple but effective contrastive learning framework that incorporates recent developments in reward learning and factuality metrics. Empirical studies demonstrate that the proposed framework enables summarization models to learn from feedback of factu…
▽ More
Modern abstractive summarization models often generate summaries that contain hallucinated or contradictory information. In this paper, we propose a simple but effective contrastive learning framework that incorporates recent developments in reward learning and factuality metrics. Empirical studies demonstrate that the proposed framework enables summarization models to learn from feedback of factuality metrics using contrastive reward learning, leading to more factual summaries by human evaluations. This suggests that further advances in learning and evaluation algorithms can feed directly into providing more factual summaries.
△ Less
Submitted 10 July, 2023;
originally announced July 2023.
-
UAP-BEV: Uncertainty Aware Planning using Bird's Eye View generated from Surround Monocular Images
Authors:
Vikrant Dewangan,
Basant Sharma,
Tushar Choudhary,
Sarthak Sharma,
Aakash Aanegola,
Arun K. Singh,
K. Madhava Krishna
Abstract:
Autonomous driving requires accurate reasoning of the location of objects from raw sensor data. Recent end-to-end learning methods go from raw sensor data to a trajectory output via Bird's Eye View(BEV) segmentation as an interpretable intermediate representation. Motion planning over cost maps generated via Birds Eye View (BEV) segmentation has emerged as a prominent approach in autonomous drivin…
▽ More
Autonomous driving requires accurate reasoning of the location of objects from raw sensor data. Recent end-to-end learning methods go from raw sensor data to a trajectory output via Bird's Eye View(BEV) segmentation as an interpretable intermediate representation. Motion planning over cost maps generated via Birds Eye View (BEV) segmentation has emerged as a prominent approach in autonomous driving. However, the current approaches have two critical gaps. First, the optimization process is simplistic and involves just evaluating a fixed set of trajectories over the cost map. The trajectory samples are not adapted based on their associated cost values. Second, the existing cost maps do not account for the uncertainty in the cost maps that can arise due to noise in RGB images, and BEV annotations. As a result, these approaches can struggle in challenging scenarios where there is abrupt cut-in, stopping, overtaking, merging, etc from the neighboring vehicles.
In this paper, we propose UAP-BEV: A novel approach that models the noise in Spatio-Temporal BEV predictions to create an uncertainty-aware occupancy grid map. Using queries of the distance to the closest occupied cell, we obtain a sample estimate of the collision probability of the ego-vehicle. Subsequently, our approach uses gradient-free sampling-based optimization to compute low-cost trajectories over the cost map. Importantly, the sampling distribution is adapted based on the optimal cost values of the sampled trajectories. By explicitly modeling probabilistic collision avoidance in the BEV space, our approach is able to outperform the cost-map-based baselines in collision avoidance, route completion, time to completion, and smoothness. To further validate our method, we also show results on the real-world dataset NuScenes, where we report improvements in collision avoidance and smoothness.
△ Less
Submitted 8 June, 2023;
originally announced June 2023.
-
Multi-Task Training with In-Domain Language Models for Diagnostic Reasoning
Authors:
Brihat Sharma,
Yanjun Gao,
Timothy Miller,
Matthew M. Churpek,
Majid Afshar,
Dmitriy Dligach
Abstract:
Generative artificial intelligence (AI) is a promising direction for augmenting clinical diagnostic decision support and reducing diagnostic errors, a leading contributor to medical errors. To further the development of clinical AI systems, the Diagnostic Reasoning Benchmark (DR.BENCH) was introduced as a comprehensive generative AI framework, comprised of six tasks representing key components in…
▽ More
Generative artificial intelligence (AI) is a promising direction for augmenting clinical diagnostic decision support and reducing diagnostic errors, a leading contributor to medical errors. To further the development of clinical AI systems, the Diagnostic Reasoning Benchmark (DR.BENCH) was introduced as a comprehensive generative AI framework, comprised of six tasks representing key components in clinical reasoning. We present a comparative analysis of in-domain versus out-of-domain language models as well as multi-task versus single task training with a focus on the problem summarization task in DR.BENCH (Gao et al., 2023). We demonstrate that a multi-task, clinically trained language model outperforms its general domain counterpart by a large margin, establishing a new state-of-the-art performance, with a ROUGE-L score of 28.55. This research underscores the value of domain-specific training for optimizing clinical diagnostic reasoning tasks.
△ Less
Submitted 13 June, 2023; v1 submitted 7 June, 2023;
originally announced June 2023.
-
Effectiveness of Text, Acoustic, and Lattice-based representations in Spoken Language Understanding tasks
Authors:
Esaú Villatoro-Tello,
Srikanth Madikeri,
Juan Zuluaga-Gomez,
Bidisha Sharma,
Seyyed Saeed Sarfjoo,
Iuliia Nigmatulina,
Petr Motlicek,
Alexei V. Ivanov,
Aravind Ganapathiraju
Abstract:
In this paper, we perform an exhaustive evaluation of different representations to address the intent classification problem in a Spoken Language Understanding (SLU) setup. We benchmark three types of systems to perform the SLU intent detection task: 1) text-based, 2) lattice-based, and a novel 3) multimodal approach. Our work provides a comprehensive analysis of what could be the achievable perfo…
▽ More
In this paper, we perform an exhaustive evaluation of different representations to address the intent classification problem in a Spoken Language Understanding (SLU) setup. We benchmark three types of systems to perform the SLU intent detection task: 1) text-based, 2) lattice-based, and a novel 3) multimodal approach. Our work provides a comprehensive analysis of what could be the achievable performance of different state-of-the-art SLU systems under different circumstances, e.g., automatically- vs. manually-generated transcripts. We evaluate the systems on the publicly available SLURP spoken language resource corpus. Our results indicate that using richer forms of Automatic Speech Recognition (ASR) outputs, namely word-consensus-networks, allows the SLU system to improve in comparison to the 1-best setup (5.5% relative improvement). However, crossmodal approaches, i.e., learning from acoustic and text embeddings, obtains performance similar to the oracle setup, a relative improvement of 17.8% over the 1-best configuration, being a recommended alternative to overcome the limitations of working with automatically generated transcripts.
△ Less
Submitted 17 March, 2023; v1 submitted 16 December, 2022;
originally announced December 2022.
-
DR.BENCH: Diagnostic Reasoning Benchmark for Clinical Natural Language Processing
Authors:
Yanjun Gao,
Dmitriy Dligach,
Timothy Miller,
John Caskey,
Brihat Sharma,
Matthew M Churpek,
Majid Afshar
Abstract:
The meaningful use of electronic health records (EHR) continues to progress in the digital era with clinical decision support systems augmented by artificial intelligence. A priority in improving provider experience is to overcome information overload and reduce the cognitive burden so fewer medical errors and cognitive biases are introduced during patient care. One major type of medical error is…
▽ More
The meaningful use of electronic health records (EHR) continues to progress in the digital era with clinical decision support systems augmented by artificial intelligence. A priority in improving provider experience is to overcome information overload and reduce the cognitive burden so fewer medical errors and cognitive biases are introduced during patient care. One major type of medical error is diagnostic error due to systematic or predictable errors in judgment that rely on heuristics. The potential for clinical natural language processing (cNLP) to model diagnostic reasoning in humans with forward reasoning from data to diagnosis and potentially reduce the cognitive burden and medical error has not been investigated. Existing tasks to advance the science in cNLP have largely focused on information extraction and named entity recognition through classification tasks. We introduce a novel suite of tasks coined as Diagnostic Reasoning Benchmarks, DR.BENCH, as a new benchmark for developing and evaluating cNLP models with clinical diagnostic reasoning ability. The suite includes six tasks from ten publicly available datasets addressing clinical text understanding, medical knowledge reasoning, and diagnosis generation. DR.BENCH is the first clinical suite of tasks designed to be a natural language generation framework to evaluate pre-trained language models. Experiments with state-of-the-art pre-trained generative language models using large general domain models and models that were continually trained on a medical corpus demonstrate opportunities for improvement when evaluated in DR. BENCH. We share DR. BENCH as a publicly available GitLab repository with a systematic approach to load and evaluate models for the cNLP community.
△ Less
Submitted 13 December, 2022; v1 submitted 29 September, 2022;
originally announced September 2022.
-
Machine Learning-based Automatic Annotation and Detection of COVID-19 Fake News
Authors:
Mohammad Majid Akhtar,
Bibhas Sharma,
Ishan Karunanayake,
Rahat Masood,
Muhammad Ikram,
Salil S. Kanhere
Abstract:
COVID-19 impacted every part of the world, although the misinformation about the outbreak traveled faster than the virus. Misinformation spread through online social networks (OSN) often misled people from following correct medical practices. In particular, OSN bots have been a primary source of disseminating false information and initiating cyber propaganda. Existing work neglects the presence of…
▽ More
COVID-19 impacted every part of the world, although the misinformation about the outbreak traveled faster than the virus. Misinformation spread through online social networks (OSN) often misled people from following correct medical practices. In particular, OSN bots have been a primary source of disseminating false information and initiating cyber propaganda. Existing work neglects the presence of bots that act as a catalyst in the spread and focuses on fake news detection in 'articles shared in posts' rather than the post (textual) content. Most work on misinformation detection uses manually labeled datasets that are hard to scale for building their predictive models. In this research, we overcome this challenge of data scarcity by proposing an automated approach for labeling data using verified fact-checked statements on a Twitter dataset. In addition, we combine textual features with user-level features (such as followers count and friends count) and tweet-level features (such as number of mentions, hashtags and urls in a tweet) to act as additional indicators to detect misinformation. Moreover, we analyzed the presence of bots in tweets and show that bots change their behavior over time and are most active during the misinformation campaign. We collected 10.22 Million COVID-19 related tweets and used our annotation model to build an extensive and original ground truth dataset for classification purposes. We utilize various machine learning models to accurately detect misinformation and our best classification model achieves precision (82%), recall (96%), and false positive rate (3.58%). Also, our bot analysis indicates that bots generated approximately 10% of misinformation tweets. Our methodology results in substantial exposure of false information, thus improving the trustworthiness of information disseminated through social media platforms.
△ Less
Submitted 7 September, 2022;
originally announced September 2022.
-
Interference and Need Aware Workload Colocation in Hyperscale Datacenters
Authors:
Sayak Chakraborti,
Brian Coutinho,
Sandhya Dwarkadas,
Parth Malani,
Bikash Sharma
Abstract:
Datacenters suffer from resource utilization inefficiencies due to the conflicting goals of service owners and platform providers. Service owners intending to maintain Service Level Objectives (SLO) for themselves typically request a conservative amount of resources. Platform providers want to increase operational efficiency to reduce capital and operating costs. Achieving both operational efficie…
▽ More
Datacenters suffer from resource utilization inefficiencies due to the conflicting goals of service owners and platform providers. Service owners intending to maintain Service Level Objectives (SLO) for themselves typically request a conservative amount of resources. Platform providers want to increase operational efficiency to reduce capital and operating costs. Achieving both operational efficiency and SLO for individual services at the same time is challenging due to the diversity in service workload characteristics, resource usage patterns that are dependent on input load, heterogeneity in platform, memory, I/O, and network architecture, and resource bundling.
This paper presents a tunable approach to resource allocation that accounts for both dynamic service resource needs and platform heterogeneity. In addition, an online K-Means-based service classification method is used in conjunction with an offline sensitivity component. Our tunable approach allows trading resource utilization efficiency for absolute SLO guarantees based on the service owners' sensitivity to its SLO. We evaluate our tunable resource allocator at scale in a private cloud environment with mostly latency-critical workloads. When tuning for operational efficiency, we demonstrate up to ~50% reduction in required machines; ~40% reduction in Total-Cost-of-Ownership (TCO); and ~60% reduction in CPU and memory fragmentation, but at the cost of increasing the number of tasks experiencing degradation of SLO by up to ~25% compared to the baseline. When tuning for SLO, by introducing interference-aware colocation, we can tune the solver to reduce tasks experiencing degradation of SLO by up to ~22% compared to the baseline, but at an additional cost of ~30% in terms of the number of hosts. We highlight this trade-off between TCO and SLO violations, and offer tuning based on the requirements of the platform owners.
△ Less
Submitted 25 July, 2022;
originally announced July 2022.
-
Don't be a Victim During a Pandemic! Analysing Security and Privacy Threats in Twitter During COVID-19
Authors:
Bibhas Sharma,
Ishan Karunanayake,
Rahat Masood,
Muhammad Ikram
Abstract:
There has been a huge spike in the usage of social media platforms during the COVID-19 lockdowns. These lockdown periods have resulted in a set of new cybercrimes, thereby allowing attackers to victimise social media users with a range of threats. This paper performs a large-scale study to investigate the impact of a pandemic and the lockdown periods on the security and privacy of social media use…
▽ More
There has been a huge spike in the usage of social media platforms during the COVID-19 lockdowns. These lockdown periods have resulted in a set of new cybercrimes, thereby allowing attackers to victimise social media users with a range of threats. This paper performs a large-scale study to investigate the impact of a pandemic and the lockdown periods on the security and privacy of social media users. We analyse 10.6 Million COVID-related tweets from 533 days of data crawling and investigate users' security and privacy behaviour in three different periods (i.e., before, during, and after the lockdown). Our study shows that users unintentionally share more personal identifiable information when writing about the pandemic situation (e.g., sharing nearby coronavirus testing locations) in their tweets. The privacy risk reaches 100% if a user posts three or more sensitive tweets about the pandemic. We investigate the number of suspicious domains shared on social media during different phases of the pandemic. Our analysis reveals an increase in the number of suspicious domains during the lockdown compared to other lockdown phases. We observe that IT, Search Engines, and Businesses are the top three categories that contain suspicious domains. Our analysis reveals that adversaries' strategies to instigate malicious activities change with the country's pandemic situation.
△ Less
Submitted 26 March, 2023; v1 submitted 21 February, 2022;
originally announced February 2022.
-
Exploring Teacher-Student Learning Approach for Multi-lingual Speech-to-Intent Classification
Authors:
Bidisha Sharma,
Maulik Madhavi,
Xuehao Zhou,
Haizhou Li
Abstract:
End-to-end speech-to-intent classification has shown its advantage in harvesting information from both text and speech. In this paper, we study a technique to develop such an end-to-end system that supports multiple languages. To overcome the scarcity of multi-lingual speech corpus, we exploit knowledge from a pre-trained multi-lingual natural language processing model. Multi-lingual bidirectional…
▽ More
End-to-end speech-to-intent classification has shown its advantage in harvesting information from both text and speech. In this paper, we study a technique to develop such an end-to-end system that supports multiple languages. To overcome the scarcity of multi-lingual speech corpus, we exploit knowledge from a pre-trained multi-lingual natural language processing model. Multi-lingual bidirectional encoder representations from transformers (mBERT) models are trained on multiple languages and hence expected to perform well in the multi-lingual scenario. In this work, we employ a teacher-student learning approach to sufficiently extract information from an mBERT model to train a multi-lingual speech model. In particular, we use synthesized speech generated from an English-Mandarin text corpus for analysis and training of a multi-lingual intent classification model. We also demonstrate that the teacher-student learning approach obtains an improved performance (91.02%) over the traditional end-to-end (89.40%) intent classification approach in a practical multi-lingual scenario.
△ Less
Submitted 28 September, 2021;
originally announced September 2021.
-
On the performance of GPU accelerated q-LSKUM based meshfree solvers in Fortran, C++, Python, and Julia
Authors:
Nischay Ram Mamidi,
Kumar Prasun,
Dhruv Saxena,
Anil Nemili,
Bharatkumar Sharma,
S. M. Deshpande
Abstract:
This report presents a comprehensive analysis of the performance of GPU accelerated meshfree CFD solvers for two-dimensional compressible flows in Fortran, C++, Python, and Julia. The programming model CUDA is used to develop the GPU codes. The meshfree solver is based on the least squares kinetic upwind method with entropy variables (q-LSKUM). To assess the computational efficiency of the GPU sol…
▽ More
This report presents a comprehensive analysis of the performance of GPU accelerated meshfree CFD solvers for two-dimensional compressible flows in Fortran, C++, Python, and Julia. The programming model CUDA is used to develop the GPU codes. The meshfree solver is based on the least squares kinetic upwind method with entropy variables (q-LSKUM). To assess the computational efficiency of the GPU solvers and to compare their relative performance, benchmark calculations are performed on seven levels of point distribution. To analyse the difference in their run-times, the computationally intensive kernel is profiled. Various performance metrics are investigated from the profiled data to determine the cause of observed variation in run-times. To address some of the performance related issues, various optimisation strategies are employed. The optimised GPU codes are compared with the naive codes, and conclusions are drawn from their performance.
△ Less
Submitted 16 August, 2021;
originally announced August 2021.
-
Knowledge Distillation from BERT Transformer to Speech Transformer for Intent Classification
Authors:
Yidi Jiang,
Bidisha Sharma,
Maulik Madhavi,
Haizhou Li
Abstract:
End-to-end intent classification using speech has numerous advantages compared to the conventional pipeline approach using automatic speech recognition (ASR), followed by natural language processing modules. It attempts to predict intent from speech without using an intermediate ASR module. However, such end-to-end framework suffers from the unavailability of large speech resources with higher aco…
▽ More
End-to-end intent classification using speech has numerous advantages compared to the conventional pipeline approach using automatic speech recognition (ASR), followed by natural language processing modules. It attempts to predict intent from speech without using an intermediate ASR module. However, such end-to-end framework suffers from the unavailability of large speech resources with higher acoustic variation in spoken language understanding. In this work, we exploit the scope of the transformer distillation method that is specifically designed for knowledge distillation from a transformer based language model to a transformer based speech model. In this regard, we leverage the reliable and widely used bidirectional encoder representations from transformers (BERT) model as a language model and transfer the knowledge to build an acoustic model for intent classification using the speech. In particular, a multilevel transformer based teacher-student model is designed, and knowledge distillation is performed across attention and hidden sub-layers of different transformer layers of the student and teacher models. We achieve an intent classification accuracy of 99.10% and 88.79% for Fluent speech corpus and ATIS database, respectively. Further, the proposed method demonstrates better performance and robustness in acoustically degraded condition compared to the baseline method.
△ Less
Submitted 5 August, 2021;
originally announced August 2021.
-
SLoClas: A Database for Joint Sound Localization and Classification
Authors:
Xinyuan Qian,
Bidisha Sharma,
Amine El Abridi,
Haizhou Li
Abstract:
In this work, we present the development of a new database, namely Sound Localization and Classification (SLoClas) corpus, for studying and analyzing sound localization and classification. The corpus contains a total of 23.27 hours of data recorded using a 4-channel microphone array. 10 classes of sounds are played over a loudspeaker at 1.5 meters distance from the array by varying the Direction-o…
▽ More
In this work, we present the development of a new database, namely Sound Localization and Classification (SLoClas) corpus, for studying and analyzing sound localization and classification. The corpus contains a total of 23.27 hours of data recorded using a 4-channel microphone array. 10 classes of sounds are played over a loudspeaker at 1.5 meters distance from the array by varying the Direction-of-Arrival (DoA) from 1 degree to 360 degree at an interval of 5 degree. To facilitate the study of noise robustness, 6 types of outdoor noise are recorded at 4 DoAs, using the same devices. Moreover, we propose a baseline method, namely Sound Localization and Classification Network (SLCnet) and present the experimental results and analysis conducted on the collected SLoClas database. We achieve the accuracy of 95.21% and 80.01% for sound localization and classification, respectively. We publicly release this database and the source code for research purpose.
△ Less
Submitted 5 August, 2021;
originally announced August 2021.
-
Sonority Measurement Using System, Source, and Suprasegmental Information
Authors:
Bidisha Sharma,
S. R. Mahadeva Prasanna
Abstract:
Sonorant sounds are characterized by regions with prominent formant structure, high energy and high degree of periodicity. In this work, the vocal-tract system, excitation source and suprasegmental features derived from the speech signal are analyzed to measure the sonority information present in each of them. Vocal-tract system information is extracted from the Hilbert envelope of numerator of gr…
▽ More
Sonorant sounds are characterized by regions with prominent formant structure, high energy and high degree of periodicity. In this work, the vocal-tract system, excitation source and suprasegmental features derived from the speech signal are analyzed to measure the sonority information present in each of them. Vocal-tract system information is extracted from the Hilbert envelope of numerator of group delay function. It is derived from zero time windowed speech signal that provides better resolution of the formants. A five-dimensional feature set is computed from the estimated formants to measure the prominence of the spectral peaks. A feature representing strength of excitation is derived from the Hilbert envelope of linear prediction residual, which represents the source information. Correlation of speech over ten consecutive pitch periods is used as the suprasegmental feature representing periodicity information. The combination of evidences from the three different aspects of speech provides better discrimination among different sonorant classes, compared to the baseline MFCC features. The usefulness of the proposed sonority feature is demonstrated in the tasks of phoneme recognition and sonorant classification.
△ Less
Submitted 1 July, 2021;
originally announced July 2021.
-
Leveraging Acoustic and Linguistic Embeddings from Pretrained speech and language Models for Intent Classification
Authors:
Bidisha Sharma,
Maulik Madhavi,
Haizhou Li
Abstract:
Intent classification is a task in spoken language understanding. An intent classification system is usually implemented as a pipeline process, with a speech recognition module followed by text processing that classifies the intents. There are also studies of end-to-end system that takes acoustic features as input and classifies the intents directly. Such systems don't take advantage of relevant l…
▽ More
Intent classification is a task in spoken language understanding. An intent classification system is usually implemented as a pipeline process, with a speech recognition module followed by text processing that classifies the intents. There are also studies of end-to-end system that takes acoustic features as input and classifies the intents directly. Such systems don't take advantage of relevant linguistic information, and suffer from limited training data. In this work, we propose a novel intent classification framework that employs acoustic features extracted from a pretrained speech recognition system and linguistic features learned from a pretrained language model. We use knowledge distillation technique to map the acoustic embeddings towards linguistic embeddings. We perform fusion of both acoustic and linguistic embeddings through cross-attention approach to classify intents. With the proposed method, we achieve 90.86% and 99.07% accuracy on ATIS and Fluent speech corpus, respectively.
△ Less
Submitted 15 February, 2021;
originally announced February 2021.
-
NHSS: A Speech and Singing Parallel Database
Authors:
Bidisha Sharma,
Xiaoxue Gao,
Karthika Vijayan,
Xiaohai Tian,
Haizhou Li
Abstract:
We present a database of parallel recordings of speech and singing, collected and released by the Human Language Technology (HLT) laboratory at the National University of Singapore (NUS), that is called NUS-HLT Speak-Sing (NHSS) database. We release this database to the public to support research activities, that include, but not limited to comparative studies of acoustic attributes of speech and…
▽ More
We present a database of parallel recordings of speech and singing, collected and released by the Human Language Technology (HLT) laboratory at the National University of Singapore (NUS), that is called NUS-HLT Speak-Sing (NHSS) database. We release this database to the public to support research activities, that include, but not limited to comparative studies of acoustic attributes of speech and singing signals, cooperative synthesis of speech and singing voices, and speech-to-singing conversion. This database consists of recordings of sung vocals of English pop songs, the spoken counterpart of lyrics of the songs read by the singers in their natural reading manner, and manually prepared utterance-level and word-level annotations. The audio recordings in the NHSS database correspond to 100 songs sung and spoken by 10 singers, resulting in a total of 7 hours of audio data. There are 5 male and 5 female singers, singing and reading the lyrics of 10 songs each. In this paper, we discuss the design methodology of the database, analyse the similarities and dissimilarities in characteristics of speech and singing voices, and provide some strategies to address relationships between these characteristics for converting one to another. We develop benchmark systems, which can be used as reference for speech-to-singing alignment, spectral mapping, and conversion using the NHSS database.
△ Less
Submitted 5 August, 2021; v1 submitted 1 December, 2020;
originally announced December 2020.
-
Explaining Chemical Toxicity using Missing Features
Authors:
Kar Wai Lim,
Bhanushee Sharma,
Payel Das,
Vijil Chenthamarakshan,
Jonathan S. Dordick
Abstract:
Chemical toxicity prediction using machine learning is important in drug development to reduce repeated animal and human testing, thus saving cost and time. It is highly recommended that the predictions of computational toxicology models are mechanistically explainable. Current state of the art machine learning classifiers are based on deep neural networks, which tend to be complex and harder to i…
▽ More
Chemical toxicity prediction using machine learning is important in drug development to reduce repeated animal and human testing, thus saving cost and time. It is highly recommended that the predictions of computational toxicology models are mechanistically explainable. Current state of the art machine learning classifiers are based on deep neural networks, which tend to be complex and harder to interpret. In this paper, we apply a recently developed method named contrastive explanations method (CEM) to explain why a chemical or molecule is predicted to be toxic or not. In contrast to popular methods that provide explanations based on what features are present in the molecule, the CEM provides additional explanation on what features are missing from the molecule that is crucial for the prediction, known as the pertinent negative. The CEM does this by optimizing for the minimum perturbation to the model using a projected fast iterative shrinkage-thresholding algorithm (FISTA). We verified that the explanation from CEM matches known toxicophores and findings from other work.
△ Less
Submitted 23 September, 2020;
originally announced September 2020.
-
Data-Driven Investigative Journalism For Connectas Dataset
Authors:
Aniket Jain,
Bhavya Sharma,
Paridhi Choudhary,
Rohan Sangave,
William Yang
Abstract:
The following paper explores the possibility of using Machine Learning algorithms to detect the cases of corruption and malpractice by governments. The dataset used by the authors contains information about several government contracts in Colombia from year 2007 to 2012. The authors begin with exploring and cleaning the data, followed by which they perform feature engineering before finally implem…
▽ More
The following paper explores the possibility of using Machine Learning algorithms to detect the cases of corruption and malpractice by governments. The dataset used by the authors contains information about several government contracts in Colombia from year 2007 to 2012. The authors begin with exploring and cleaning the data, followed by which they perform feature engineering before finally implementing Machine Learning models to detect anomalies in the given dataset.
△ Less
Submitted 23 April, 2018;
originally announced April 2018.
-
Using ECC DRAM to Adaptively Increase Memory Capacity
Authors:
Yixin Luo,
Saugata Ghose,
Tianshi Li,
Sriram Govindan,
Bikash Sharma,
Bryan Kelly,
Amirali Boroumand,
Onur Mutlu
Abstract:
Modern DRAM modules are often equipped with hardware error correction capabilities, especially for DRAM deployed in large-scale data centers, as process technology scaling has increased the susceptibility of these devices to errors. To provide fast error detection and correction, error-correcting codes (ECC) are placed on an additional DRAM chip in a DRAM module. This additional chip expands the r…
▽ More
Modern DRAM modules are often equipped with hardware error correction capabilities, especially for DRAM deployed in large-scale data centers, as process technology scaling has increased the susceptibility of these devices to errors. To provide fast error detection and correction, error-correcting codes (ECC) are placed on an additional DRAM chip in a DRAM module. This additional chip expands the raw capacity of a DRAM module by 12.5%, but the applications are unable to use any of this extra capacity, as it is used exclusively to provide reliability for all data. In reality, there are a number of applications that do not need such strong reliability for all their data regions (e.g., some user batch jobs executing on a public cloud), and can instead benefit from using additional DRAM capacity to store extra data. Our goal in this work is to provide the additional capacity within an ECC DRAM module to applications when they do not need the high reliability of error correction.
In this paper, we propose Capacity- and Reliability-Adaptive Memory (CREAM), a hardware mechanism that adapts error correcting DRAM modules to offer multiple levels of error protection, and provides the capacity saved from using weaker protection to applications. For regions of memory that do not require strong error correction, we either provide no ECC protection or provide error detection using multibit parity. We evaluate several layouts for arranging the data within ECC DRAM in these reduced-protection modes, taking into account the various trade-offs exposed from exploiting the extra chip. Our experiments show that the increased capacity provided by CREAM improves performance by 23.0% for a memory caching workload, and by 37.3% for a commercial web search workload executing production query traces. In addition, CREAM can increase bank-level parallelism within DRAM, offering further performance improvements.
△ Less
Submitted 28 June, 2017; v1 submitted 27 June, 2017;
originally announced June 2017.
-
Heterogeneous-Reliability Memory: Exploiting Application-Level Memory Error Tolerance
Authors:
Yixin Luo,
Sriram Govindan,
Bikash Sharma,
Mark Santaniello,
Justin Meza,
Aman Kansal,
Jie Liu,
Badriddine Khessib,
Kushagra Vaid,
Onur Mutlu
Abstract:
This paper summarizes our work on characterizing application memory error vulnerability to optimize datacenter cost via Heterogeneous-Reliability Memory (HRM), which was published in DSN 2014, and examines the work's significance and future potential. Memory devices represent a key component of datacenter total cost of ownership (TCO), and techniques used to reduce errors that occur on these devic…
▽ More
This paper summarizes our work on characterizing application memory error vulnerability to optimize datacenter cost via Heterogeneous-Reliability Memory (HRM), which was published in DSN 2014, and examines the work's significance and future potential. Memory devices represent a key component of datacenter total cost of ownership (TCO), and techniques used to reduce errors that occur on these devices increase this cost. Existing approaches to providing reliability for memory devices pessimistically treat all data as equally vulnerable to memory errors. Our key insight is that there exists a diverse spectrum of tolerance to memory errors in new data-intensive applications, and that traditional one-size-fits-all memory reliability techniques are inefficient in terms of cost. This presents an opportunity to greatly reduce server hardware cost by provisioning the right amount of memory reliability for different applications.
Toward this end, in our DSN 2014 paper, we make three main contributions to enable highly-reliable servers at low datacenter cost. First, we develop a new methodology to quantify the tolerance of applications to memory errors. Second, using our methodology, we perform a case study of three new data-intensive workloads (an interactive web search application, an in-memory key--value store, and a graph mining framework) to identify new insights into the nature of application memory error vulnerability. Third, based on our insights, we propose several new hardware/software heterogeneous-reliability memory system designs to lower datacenter cost while achieving high reliability and discuss their trade-offs. We show that our new techniques can reduce server hardware cost by 4.7% while achieving 99.90% single server availability.
△ Less
Submitted 10 May, 2018; v1 submitted 1 February, 2016;
originally announced February 2016.
-
Word Sense Disambiguation using WSD specific Wordnet of Polysemy Words
Authors:
Udaya Raj Dhungana,
Subarna Shakya,
Kabita Baral,
Bharat Sharma
Abstract:
This paper presents a new model of WordNet that is used to disambiguate the correct sense of polysemy word based on the clue words. The related words for each sense of a polysemy word as well as single sense word are referred to as the clue words. The conventional WordNet organizes nouns, verbs, adjectives and adverbs together into sets of synonyms called synsets each expressing a different concep…
▽ More
This paper presents a new model of WordNet that is used to disambiguate the correct sense of polysemy word based on the clue words. The related words for each sense of a polysemy word as well as single sense word are referred to as the clue words. The conventional WordNet organizes nouns, verbs, adjectives and adverbs together into sets of synonyms called synsets each expressing a different concept. In contrast to the structure of WordNet, we developed a new model of WordNet that organizes the different senses of polysemy words as well as the single sense words based on the clue words. These clue words for each sense of a polysemy word as well as for single sense word are used to disambiguate the correct meaning of the polysemy word in the given context using knowledge based Word Sense Disambiguation (WSD) algorithms. The clue word can be a noun, verb, adjective or adverb.
△ Less
Submitted 10 September, 2014;
originally announced September 2014.
-
DEM Registration and Error Analysis using ASCII values
Authors:
Suma Dawn,
Vikas Saxena,
Bhu Dev Sharma
Abstract:
Digital Elevation Model (DEM), while providing a bare earth look, is heavily used in many applications including construction modeling, visualization, and GIS. Their registration techniques have not been explored much. Methods like Coarse-to-fine or pyramid making are common in DEM-to-image or DEM-to-map registration. Self-consistency measure is used to detect any change in terrain elevation and h…
▽ More
Digital Elevation Model (DEM), while providing a bare earth look, is heavily used in many applications including construction modeling, visualization, and GIS. Their registration techniques have not been explored much. Methods like Coarse-to-fine or pyramid making are common in DEM-to-image or DEM-to-map registration. Self-consistency measure is used to detect any change in terrain elevation and hence was used for DEM-to-DEM registration. But these methods apart from being time and complexity intensive, lack in error matrix evaluation. This paper gives a method of registration of DEMs using specified height values as control points by initially converting these DEMs to ASCII files. These control points may be found by two mannerisms - either by direct detection of appropriate height data in ASCII files or by edge matching along congruous quadrangle of the control point, followed by sub-graph matching. Error analysis for the same has also been done.
△ Less
Submitted 30 May, 2014;
originally announced May 2014.
-
Cognitive-mapping and contextual pyramid based Digital Elevation Model Registration and its effective storage using fractal based compression
Authors:
Suma Dawn,
Vikas Saxena,
Bhudev Sharma
Abstract:
Digital Elevation models (DEM) are images having terrain information embedded into them. Using cognitive mapping concepts for DEM registration, has evolved from this basic idea of using the mapping between the space to objects and defining their relationships to form the basic landmarks that need to be marked, stored and manipulated in and about the environment or other candidate environments, nam…
▽ More
Digital Elevation models (DEM) are images having terrain information embedded into them. Using cognitive mapping concepts for DEM registration, has evolved from this basic idea of using the mapping between the space to objects and defining their relationships to form the basic landmarks that need to be marked, stored and manipulated in and about the environment or other candidate environments, namely, in our case, the DEMs. The progressive two-level encapsulation of methods of geo-spatial cognition includes landmark knowledge and layout knowledge and can be useful for DEM registration. Space-based approach, that emphasizes on explicit extent of the environment under consideration, and object-based approach, that emphasizes on the relationships between objects in the local environment being the two paradigms of cognitive mapping can be methodically integrated in this three-architecture for DEM registration. Initially, P-model based segmentation is performed followed by landmark formation for contextual mapping that uses contextual pyramid formation. Apart from landmarks being used for registration key-point finding, Euclidean distance based deformation calculation has been used for transformation and change detection. Landmarks have been categorized to belong to either being flat-plain areas without much variation in the land heights; peaks that can be found when there is gradual increase in height as compared to the flat areas; valleys, marked with gradual decrease in the height seen in DEM; and finally, ripple areas with very shallow crests and nadirs. Fractal based compression was used for storage of co-registered DEMs. This method may further be extended for DEM-topographic map and DEM-to-remote sensed image registration. Experimental results further cement the fact that DEM registration may be effectively done using the proposed method.
△ Less
Submitted 9 May, 2014;
originally announced May 2014.
-
TRANS outperforms MTF for two special types of request sequences without locality of reference
Authors:
Rakesh Mohanty,
Sangita Patel,
Shiba Prasad Dash,
Burle Sharma
Abstract:
Various list accessing algorithms have been proposed in the literature and their performances have been analyzed theoretically and experimentally. Move-To-Front (MTF) and Transpose (TRANS) are two well known primitive list accessing algorithms. MTF has been proved to be the best performing online algorithm till date in the literature for real life inputs and practical applications with locality of…
▽ More
Various list accessing algorithms have been proposed in the literature and their performances have been analyzed theoretically and experimentally. Move-To-Front (MTF) and Transpose (TRANS) are two well known primitive list accessing algorithms. MTF has been proved to be the best performing online algorithm till date in the literature for real life inputs and practical applications with locality of reference. It has been shown that when storage space is extremely limited and pointers for lists cannot be used, then array implementation of TRANS gives efficient reorganization. Use of MTF is extensive in the literature whereas, the use of TRANS is rare. As mentioned as an open problem in literature, direct bounds on the behavior and performance of various list accessing algorithms are needed to allow realistic comparisons. Since it has been shown that no single optimal permutation algorithm exists, it becomes necessary to characterize the circumstances that indicate the advantage in using a particular list accessing algorithm. Motivated by above challenging research issue, in this paper we have made an analytical study for evaluating the performance of TRANS list accessing algorithm using two special types of request sequences without locality of reference. We have compared the performance of TRANS with MTF and observed that TRANS outperforms MTF for these considered types of request sequences.
△ Less
Submitted 10 September, 2013;
originally announced September 2013.
-
Network Lifetime Analysis of AODV, DSR and ZRP at Different Network Parameters
Authors:
Niranjan Kumar Ray,
Harsh Bardhan Sharma,
Ashok Kumar Turuk
Abstract:
Enhancement of network lifetime is a key design criterion for most of the energy constrained networks as nodes are battery operated. In multi-hop wireless network, proper utilization of battery power is very much necessary to maintain network connectivity. If the battery power of a node drains quickly then its connectivity in its neighborhood will be lost. So the study of network lifetime is very…
▽ More
Enhancement of network lifetime is a key design criterion for most of the energy constrained networks as nodes are battery operated. In multi-hop wireless network, proper utilization of battery power is very much necessary to maintain network connectivity. If the battery power of a node drains quickly then its connectivity in its neighborhood will be lost. So the study of network lifetime is very much crucial as compared to other network parameters. Considering this importance we made an attempt to study the behaviour of three most common routing protocols in ad hoc network. Extensive simulations are done on AODV, DSR and ZRP to determine the network lifetime at different node mobility and at different network load. Simulation results suggest that AODV is the most energy efficient protocol as compared to other
△ Less
Submitted 11 July, 2012;
originally announced July 2012.
-
Some Novel Results From Analysis of Move To Front (MTF) List Accessing Algorithm
Authors:
Rakesh Mohanty,
Sangita Patel,
Shiba Prasad Dash,
Burle Sharma
Abstract:
List accessing problem has been studied as a problem of significant theoretical and practical interest in the context of linear search. Various list accessing algorithms have been proposed in the literature and their performances have been analyzed theoretically and experimentally. Move-To-Front(MTF),Transpose (TRANS) and Frequency Count (FC) are the three primitive and widely used list accessing…
▽ More
List accessing problem has been studied as a problem of significant theoretical and practical interest in the context of linear search. Various list accessing algorithms have been proposed in the literature and their performances have been analyzed theoretically and experimentally. Move-To-Front(MTF),Transpose (TRANS) and Frequency Count (FC) are the three primitive and widely used list accessing algorithms. Most of the other list accessing algorithms are the variants of these three algorithms. As mentioned in the literature as an open problem, direct bounds on the behavior and performance of these list accessing algorithms are needed to allow realistic comparisons. MTF has been proved to be the best performing online algorithm till date in the literature for real life inputs with locality of reference. Motivated by the above challenging research issue, in this paper, we have generated four types of input request sequences corresponding to real life inputs without locality of reference. Using these types of request sequences, we have made an analytical study for evaluating the performance of MTF list accessing algorithm to obtain some novel and interesting theoretical results.
△ Less
Submitted 27 June, 2012;
originally announced June 2012.
-
Performance Evaluation of A Proposed Variant of Frequency Count (VFC) List Accessing Algorithm
Authors:
Rakesh Mohanty,
Shiba Prasad Dash,
Burle Sharma,
Sangita Patel
Abstract:
Frequency Count (FC) algorithm is considered as the static optimal algorithm for the list accessing problem. In this paper, we have made a study of FC algorithm and explore its limitation. Using the concept of weak look ahead, we have proposed a novel Variant of Frequency Count (VFC) list accessing algorithm. We have evaluated the performance of FC and our proposed VFC algorithm experimentally usi…
▽ More
Frequency Count (FC) algorithm is considered as the static optimal algorithm for the list accessing problem. In this paper, we have made a study of FC algorithm and explore its limitation. Using the concept of weak look ahead, we have proposed a novel Variant of Frequency Count (VFC) list accessing algorithm. We have evaluated the performance of FC and our proposed VFC algorithm experimentally using input data set from Calgary Corpus. Our experiments show that for all request sequences and list generated from the above data set VFC performs better than FC.
△ Less
Submitted 27 June, 2012;
originally announced June 2012.
-
Characterization of Request Sequences for List Accessing Problem and New Theoretical Results for MTF Algorithm
Authors:
Rakesh Mohanty,
Burle Sharma,
Sasmita Tripathy
Abstract:
List Accessing Problem is a well studied research problem in the context of linear search. Input to the list accessing problem is an unsorted linear list of distinct elements along with a sequence of requests, where each request is an access operation on an element of the list. A list accessing algorithm reorganizes the list while processing a request sequence on the list in order to minimize the…
▽ More
List Accessing Problem is a well studied research problem in the context of linear search. Input to the list accessing problem is an unsorted linear list of distinct elements along with a sequence of requests, where each request is an access operation on an element of the list. A list accessing algorithm reorganizes the list while processing a request sequence on the list in order to minimize the access cost. Move-To-Front algorithm has been proved to be the best performing list accessing online algorithm till date in the literature. Characterization of the input request sequences corresponding to practical real life situations is a big challenge for the list accessing problem. As far as our knowledge is concerned, no characterization for the request sequences has been done in the literature till date for the list accessing problem. In this paper, we have characterized the request sequences for the list accessing problem based on several factors such as size of the list, size of the request sequence, ordering of elements and frequency of occurrence of elements in the request sequence. We have made a comprehensive study of MTF list accessing algorithm and obtained new theoretical results for our characterized special class of request sequences. Our characterization will open up a new direction of research for empirical analysis of list accessing algorithms for real life inputs.
△ Less
Submitted 10 September, 2011;
originally announced September 2011.
-
WiMAX Based 60 GHz Millimeter-Wave Communication for Intelligent Transport System Applications
Authors:
Rabindranath Bera,
Subir Kumar Sarkar,
Bikash Sharma,
Samarendra Nath Sur,
Debasish Bhaskar,
Soumyasree Bera
Abstract:
With the successful worldwide deployment of 3rd generation mobile communication, security aspects are ensured partly. Researchers are now looking for 4G mobile for its deployment with high data rate, enhanced security and reliability so that world should look for CALM, Continuous Air interface for Long and Medium range communication. This CALM will be a reliable high data rate secured mobile commu…
▽ More
With the successful worldwide deployment of 3rd generation mobile communication, security aspects are ensured partly. Researchers are now looking for 4G mobile for its deployment with high data rate, enhanced security and reliability so that world should look for CALM, Continuous Air interface for Long and Medium range communication. This CALM will be a reliable high data rate secured mobile communication to be deployed for car to car communication (C2C) for safety application. This paper reviewed the WiMAX ,& 60 GHz RF carrier for C2C. The system is tested at SMIT laboratory with multimedia transmission and reception. With proper deployment of this 60 GHz system on vehicles, the existing commercial products for 802.11P will be required to be replaced or updated soon .
△ Less
Submitted 2 May, 2011;
originally announced May 2011.
-
Approximating a Behavioural Pseudometric without Discount for<br> Probabilistic Systems
Authors:
Franck van Breugel,
Babita Sharma,
James Worrell
Abstract:
Desharnais, Gupta, Jagadeesan and Panangaden introduced a family of behavioural pseudometrics for probabilistic transition systems. These pseudometrics are a quantitative analogue of probabilistic bisimilarity. Distance zero captures probabilistic bisimilarity. Each pseudometric has a discount factor, a real number in the interval (0, 1]. The smaller the discount factor, the more the future is d…
▽ More
Desharnais, Gupta, Jagadeesan and Panangaden introduced a family of behavioural pseudometrics for probabilistic transition systems. These pseudometrics are a quantitative analogue of probabilistic bisimilarity. Distance zero captures probabilistic bisimilarity. Each pseudometric has a discount factor, a real number in the interval (0, 1]. The smaller the discount factor, the more the future is discounted. If the discount factor is one, then the future is not discounted at all. Desharnais et al. showed that the behavioural distances can be calculated up to any desired degree of accuracy if the discount factor is smaller than one. In this paper, we show that the distances can also be approximated if the future is not discounted. A key ingredient of our algorithm is Tarski's decision procedure for the first order theory over real closed fields. By exploiting the Kantorovich-Rubinstein duality theorem we can restrict to the existential fragment for which more efficient decision procedures exist.
△ Less
Submitted 9 April, 2008; v1 submitted 26 March, 2008;
originally announced March 2008.