CAS: Computer Science: Scholarly Papers

Permanent URI for this collection

https://hdl.handle.net/2144/1240

Browse

Now showing 1 - 20 of 328

Sublinear-time computation in the presence of online erasures
({Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, 2022-01-31) Kalemaj, Iden; Raskhodnikova, Sofya; Varma, Nithin
We initiate the study of sublinear-time algorithms that access their input via an online adversarial erasure oracle. After answering each query to the input object, such an oracle can erase t input values. Our goal is to understand the complexity of basic computational tasks in extremely adversarial situations, where the algorithm’s access to data is blocked during the execution of the algorithm in response to its actions. Specifically, we focus on property testing in the model with online erasures. We show that two fundamental properties of functions, linearity and quadraticity, can be tested for constant t with asymptotically the same complexity as in the standard property testing model. For linearity testing, we prove tight bounds in terms of t, showing that the query complexity is Θ(log t). In contrast to linearity and quadraticity, some other properties, including sortedness and the Lipschitz property of sequences, cannot be tested at all, even for t = 1. Our investigation leads to a deeper understanding of the structure of violations of linearity and other widely studied properties.
On facility location problem in the local differential privacy model
(2022-03-28) Cohen-Addad, Vincent; Esencayi, Yunus; Fan, Chenglin; Gaboardi, Marco; Li, Shi; Wang, Di
In this paper we study the uncapacitated facility location problem in the model of differential privacy (DP) with uniform facility cost. Specifically, we first show that, under the hierarchically well-separated tree (HST) metrics and the super-set output setting that was introduced in [8], there is an ∊-DP algorithm that achieves an O (¹/∊) expected multiplicative) approximation ratio; this implies an O( ^log n/_∊) approximation ratio for the general metric case, where n is the size of the input metric. These bounds improve the best-known results given by [8]. In particular, our approximation ratio for HST-metrics is independent of n, and the ratio for general metrics is independent of the aspect ratio of the input metric. On the negative side, we show that the approximation ratio of any ∊-DP algorithm is lower bounded by Ω (1/√∊), even for instances on HST metrics with uniform facility cost, under the super-set output setting. The lower bound shows that the dependence of the approximation ratio for HST metrics on ∊ can not be removed or greatly improved. Our novel methods and techniques for both the upper and lower bound may find additional applications.
Towards general-purpose neural network computing
(IEEE COMPUTER SOC, 2015-10) Eldridge, S.; Waterland, A.; Seltzer, M.; Appavoo, Jonathan; Joshi, Ajay
EbbRT: a framework for building per-application library operating systems
(USENIX Association, 2016-12) Krieger, O.; Keeton, Kimberly; Roscoe, Timothy
General purpose operating systems sacrifice per-application performance in order to preserve generality. On the other hand, substantial effort is required to customize or construct an operating system to meet the needs of an application. This paper describes the design and implementation of the Elastic Building Block Runtime (EbbRT), a framework for building per-application library operating systems. EbbRT reduces the effort required to construct and maintain library operating systems without hindering the degree of specialization required for high performance. We combine several techniques in order to achieve this, including a distributed OS architecture, a low-overhead component model, a lightweight event-driven runtime, and many language level primitives. EbbRT is able to simultaneously enable performance specialization, support for a broad range of applications, and ease the burden of systems development. An EbbRT prototype demonstrates the degree of customization made possible by our framework approach. In an evaluation of memcached, EbbRT and is able to attain 2:08 higher throughput than Linux. The node.js runtime, ported to EbbRT, demonstrates the broad applicability and ease of development enabled by our approach
Learning mixtures of Markov Chains with quality guarantees
Spaeh, Fabian Christian; Tsourakakis, Charalampos
CAESAR: coherence-aided elective and seamless alternative routing via on-chip FPGA
(IEEE, 2022-12) Roozkhosh, Shahin; Hoornaert, Denis; Mancuso, Renato
Prompted by the ever-growing demand for high-performance System-on-Chip (SoC) and the plateauing of CPU frequencies, the SoC design landscape is shifting. In a quest to offer programmable specialization, the adoption of tightly-coupled FPGAs co-located with traditional compute clusters has been embraced by major vendors. This CPU+FPGA architectural paradigm opens the door to novel hardware/software co-design opportunities. The key principle is that CPU-originated memory traffic can be re-routed through the FPGA for analysis and management purposes. Albeit promising, the side-effect of this approach is that time-critical operations—such as cache-line refills—are fulfilled by moving data over slower interconnects meant for I/O traffic. In this article, we introduce a novel principle named Cache Coherence Backstabbing to precisely tackle these shortcomings. The technique leverages the ability to include the FGPA in the same coherence domain as the core processing elements. Importantly, this enables Coherence-Aided Elective and Seamless Alternative Routing (CAESAR), i.e., seamless inspection and routing of memory transactions, especially cache-line refills, through the FPGA. CAESAR allows the definition of new memory programming paradigms. We discuss the intrinsic potentials of the approach and evaluate it with a full-stack prototype implementation on a commercial platform. Our experiments show an improvement of up to 29% in read bandwidth, 23% in latency, and 13% in pragmatic workloads over the state of the art. Furthermore, we showcase the first in-coherence-domain run-time profiler design as a use-case of the CAESAR approach.
Know your enemy: benchmarking and experimenting with insight as a goal
(2022-12-05) Nicolella, Mattia; Hoornaert, Denis; Roozkhosh, Shahin; Bastoni, Andrea; Mancuso, Renato
Available benchmark suites are used to provide realistic workloads and to understand their run-time characteristics. However, they do not necessarily target the same platforms and often offer a diverse set of metrics, leading to the lack of a knowledge base that could be used for both systems and theoretical research. RT-Bench, a new benchmark framework environment, tries to address these issues by providing a uniform interface and metrics while maintaining portability. This demo illustrates how to leverage this framework and its recently added features to improve the understanding of the benchmarks’ interaction with its system.
Hardware data re-organization engine for real-time systems
(2022-12-05) Roozkhosh, Shahin; Hoornaert, Denis; Mancuso, Renato; Athanassoulis, Manos
Access patterns and cache utilization play a key role in the analyzability of data-intensive applications. In this demo, we re-examine our previous research on software-hardware codesign to push data transformation closer to memory from a real-time perspective. Deployed in modern CPU+FPGA systems, our design enables efficient and cache-friendly access to large data by only moving relevant bytes from the target memory. This (1) compresses the cache footprint and (2) reorganizes complex memory access patterns into sequential and predictable patterns.
On the interplay of computation and memory regulation in multicore real-time systems
(2022-07-05) Hoornaert, Denis; Ghaemi, Golsana; Bastoni, Andrea; Mancuso, Renato; Caccamo, Marco; Corradi, Giulio
The ever-increasing demand for high performance in the time-critical embedded domain has pushed the adoption of powerful yet unpredictable heterogeneous Systems-on-a-Chip. The shared memory subsystem, which is known to be a major source of unpredictability, has been extensively studied, and many mitigation techniques have been proposed. Among them, performance-counter-based regulation techniques have seen widespread adoption. However, the problem of combining performance-based regulation with time-domain isolation has not received enough attention. In this article, we discuss our current work-in-progress on SHCReg (Software Hardware Co-design Regulator). First, we assess the limitations and benefits of combined CPU and memory budgeting. Next, we outline a full-stack hardware/software codesign architecture that aims at improving the interplay between CPU and memory isolation for mixed-criticality tasks running on the same core.
Using artificial intelligence to interpret pneumonia CXR (chest X ray) findings in children with a phone application platform
(2022-04-27) Thompson, Russell; Li, Jason; Wang, Kaihong; Etter, Lauren; Camelo, Ingrid; Castro-Aragon, Ilse; Setty, Bindu; Chang, Hailey; Betke, Margrit; Pieciak, Rachel; Gill, Christopher
Feature analysis and extraction for post aphasia recovery prediction
(2022-07-27) Chennuri, Saurav; Billot, Anne; Lai, Sha; Ishwar, Prakash; Betke, Margrit; Kiran, Swathi
3D multimodal dataset and token-based pose optimization
(2022-06-19) Patel, Mahir; Gu, Yiwen; Carstensen, Lucas; Hasselmo, Michael E.; Betke, Margrit
BU-NEmo: news and emotions dataset
(2022-06-20) Reardon, Carley; Paik, Sejin; Gao, Ge; Parekh, Meet; Zhao, Yanling; Guo, Lei; Betke, Margrit; Wijaya, D.
BU-NEmo is a multimodal affective dataset of gun violence news content. BU-NEmo extends the Gun Violence Framing Corpus (GVFC) proposed by Liu et. al (2019) and Tourni et. al (2021), which contains pairs of news headlines and lead images and their "frames" (view points) from gun violence-related articles. The extension concerns the results of an annotation experiment that evaluates the effect of the news content on the emotions of news consumers. The data in BU-NEmo are annotated with three types of affective annotations: (1) The emotion the annotator feels from looking at the content, out of the following 8 classes: Amusement, Awe, Contentment, Excitement, Fear, Sadness, Anger, Disgust. (2) The intensity of the annotator's emotional response, on a scale from 1-5 (5 being the most intense). (3) A free-text written response explaining their emotional response, structured as "I feel because." These annotations were collected in three experimental conditions: only the headline text was presented, only the image, and text and image together. By comparing the annotations across these three conditions, the relationship between news modality, frames, and emotional response can be studied.
Multimodal neural and behavioral data predict response to rehabilitation in chronic post-stroke aphasia
(American Heart Association, 2022-01-26) Billot, Anne; Lai, Sha; Varkanitsa, Maria; Braun, Emily Jane; Rapp, Brenda; Parrish, Todd; Higgins, James; Kurani, Ajay; Caplan, David; Thompson, Cynthia; Ishwar, Prakash; Betke, Margrit; Kiran, Swathi
BACKGROUND: Poststroke recovery depends on multiple factors and varies greatly across individuals. Using machine learning models, this study investigated the independent and complementary prognostic role of different patient-related factors in predicting response to language rehabilitation after a stroke. METHODS: Fifty-five individuals with chronic poststroke aphasia underwent a battery of standardized assessments and structural and functional magnetic resonance imaging scans, and received 12 weeks of language treatment. Support vector machine and random forest models were constructed to predict responsiveness to treatment using pretreatment behavioral, demographic, and structural and functional neuroimaging data. RESULTS: The best prediction performance was achieved by a support vector machine model trained on aphasia severity, demographics, measures of anatomic integrity and resting-state functional connectivity (F1=0.94). This model resulted in a significantly superior prediction performance compared with support vector machine models trained on all feature sets (F1=0.82, P<0.001) or a single feature set (F1 range=0.68–0.84, P<0.001). Across random forest models, training on resting-state functional magnetic resonance imaging connectivity data yielded the best F1 score (F1=0.87). CONCLUSIONS: While behavioral, multimodal neuroimaging data and demographic information carry complementary information in predicting response to rehabilitation in chronic poststroke aphasia, functional connectivity of the brain at rest after stroke is a particularly important predictor of responsiveness to treatment, both alone and combined with other patient-related factors.
ATL-BP: a student engagement dataset and model for affect transfer learning for behavior prediction
(Institute of Electrical and Electronics Engineers (IEEE), 2022) Ruiz, Nataniel; Yu, Hao; Allessio, Danielle A.; Jalal, Mona; Joshi, Ajjen; Murray, Tom; Magee, John J.; Delgado, Kevin; Ablavsky, Vitaly; Sclaroff, Stan; Arroyo, Ivon; Woolf, Beverly P.; Bargal, Sarah Adel; Betke, Margrit
A unified framework for domain adaptive pose estimation
(Springer Nature Switzerland, 2022-10-23) Kim, Donghyun; Wang, Kaihong; Saenko, K.; Betke, Margrit; Sclaroff, S.
While pose estimation is an important computer vision task, it requires expensive annotation and suffers from domain shift. In this paper, we investigate the problem of domain adaptive 2D pose estimation that transfers knowledge learned on a synthetic source domain to a target domain without supervision. While several domain adaptive pose estimation models have been proposed recently, they are not generic but only focus on either human pose or animal pose estimation, and thus their effectiveness is somewhat limited to specific scenarios. In this work, we propose a unified framework that generalizes well on various domain adaptive pose estimation problems. We propose to align representations using both input-level and output-level cues (pixels and pose labels, respectively), which facilitates the knowledge transfer from the source domain to the unlabeled target domain. Our experiments show that our method achieves state-of-the-art performance under various domain shifts. Our method outperforms existing baselines on human pose estimation by up to 4.5 percent points (pp), hand pose estimation by up to 7.4 pp, and animal pose estimation by up to 4.8 pp for dogs and 3.3 pp for sheep. These results suggest that our method is able to mitigate domain shift on diverse tasks and even unseen domains and objects (e.g., trained on horse and tested on dog). Our code will be publicly available at: https://github.com/VisionLearningGroup/UDA_PoseEstimation.
Revealing and protecting labels in distributed training
(2021-12-14) Chin, Sang Peter; Dang, Trung; Thakkar, Om; Ramaswamy, Swaroop; Mathews, Rajiv; Beaufays, Françoise
Distributed learning paradigms such as federated learning often involve transmission of model updates, or gradients, over a network, thereby avoiding transmission of private data. However, it is possible for sensitive information about the training data to be revealed from such gradients. Prior works have demonstrated that labels can be revealed analytically from the last layer of certain models (e.g., ResNet), or they can be reconstructed jointly with model inputs by using Gradients Matching [1] with additional knowledge about the current state of the model. In this work, we propose a method to discover the set of labels of training samples from only the gradient of the last layer and the id to label mapping. Our method is applicable to a wide variety of model architectures across multiple domains. We demonstrate the effectiveness of our method for model training in two domains - image classification, and automatic speech recognition. Furthermore, we show that existing reconstruction techniques improve their efficacy when used in conjunction with our method. Conversely, we demonstrate that gradient quantization and sparsification can significantly reduce the success of the attack.
NEmo – news that triggers emotions, an affectively-annotated dataset of gun violence news
(2022-06-20) Reardon, Carley; Paik, Sejin; Gao, Ge; Parekh, Meet; Zhao, Yanling; Guo, Lei; Betke, Margrit; Wijaya, Derry
Given our society’s increased exposure to multimedia formats on social media platforms, efforts to understand how digital content impacts people’s emotions are burgeoning. As such, we introduce a U.S. gun violence news dataset that contains news headline and image pairings from 840 news articles with 15K high-quality, crowdsourced annotations on emotional responses to the news pairings. We created three experimental conditions for the annotation process: two with a single modality (headline or image only), and one multimodal (headline and image together). In contrast to prior works on affectively-annotated data, our dataset includes annotations on the dominant emotion experienced with the content, the intensity of the selected emotion and an open-ended, written component. By collecting annotations on different modalities of the same news content pairings, we explore the relationship between image and text influence on human emotional response. We offer initial analysis on our dataset, showing the nuanced affective differences that appear due to modality and individual factors such as political leaning and media consumption habits. Our dataset is made publicly available to facilitate future research in affective computing.
Community detection of the framing element network: proposing and assessing a new computational framing analysis approach
(2022-08-03) Jiang, Y.; Lai, S.; Guo, Lei; Ishwar, Prakash; Wijaya, Derry; Betke, Margrit
The evolving computational news framing detection has been a prominent yet contested field among mass communication scholars. This study explores a new approach to identifying frames as clusters of framing elements including actors (i.e., individual and organizational entities) and topics in news articles based on the community detection algorithm. Our approach highlights the fundamental importance of considering individual and organizational actors mentioned in news articles as components of frames, which is overlooked in previous research that uses a similar unsupervised approach. We evaluate the performance of our method by comparing it with one of the most popular unsupervised methods--LDA topic modeling--and a state-of-art deep learning method, BERT, based on 2,900 US gun violence news articles.
An unsupervised approach to discover media frames
(2022-06-01) Lai, Sha; Jiang, Yanru; Guo, Lei; Betke, Margrit; Wijaya, Derry T.
Media framing refers to highlighting certain aspect of an issue in the news to promote a particular interpretation to the audience. Supervised learning has often been used to recognize frames in news articles, requiring a known pool of frames for a particular issue, which must be identified by communication researchers through thorough manual content analysis. In this work, we devise an unsupervised learning approach to discover the frames in news articles automatically. Given a set of news articles for a given issue, e.g., gun violence, our method first extracts frame elements from these articles using related Wikipedia articles and the Wikipedia category system. It then uses a community detection approach to identify frames from these frame elements. We discuss the effectiveness of our approach by comparing the frames it generates in an unsupervised manner to the domain-expert-derived frames for the issue of gun violence, for which a supervised learning model for frame recognition exists.

Browse

Recent Submissions