Abstract

Negotiation is an important component of the interaction process among humans. With increasing automation, autonomous agents are expected to takeover a lot of this interaction process. Much of automated negotiation literature focuses on agents having a static and known reservation value. Furthermore, a good part of these works focus on negotiation between two agents. In situations involving dynamic environments with multiple agents involved e.g., an agent negotiating on behalf of a human regarding a meeting, agents can have a Reservation Value (RV) that is a function of time. This leads to a different set of challenges that may need additional reasoning about the concession behavior. In this thesis, we build upon Negotiation algorithms such as ONAC (Optimal Non-Adaptive Concession), Time Dependent Techniques such as Boulware and OptimalBidder which work on settings where the reservation value of the agent is fixed and known. Although these algorithms can encode dynamic RV, their concession behavior and hence the properties they were expected to display would be different from when the RV is static, even though the underlying negotiation algorithm remains the same. We therefore propose to use one of Counter, Bayesian Learning with Regression Analysis or LSTM model on top of each algorithm to develop the PredictRV strategy and show that PredictRV indeed performs better on two different metrics tested on two different domains on a variety of parameter settings. We present results for two settings: (a) One involving negotiations between two agents i.e, one agent that use ONAC or Boulware and other with one of these algorithms in combination with one of the PredictRV models leading to 8 (2+2*3) possible agent models and (b) The second for heterogeneous parties of four and five agents i.e., agents that use one of OptimalBidder or Boulware strategies or these two algorithms in combination with one of the 3 PredictRV models leading to 8 (2+2*3) possible agent models .

Abstract

Stereo vision is a technique for depth estimation using two input images taken from slightly displaced cameras at the same time. This has many applications in areas such as robotics, driver-less cars, and 3D scene reconstruction. Semi-Global Matching method for stereo vision is quite popular as it is computationally tractable when compared with other global methods and accurate at the same time. In this thesis, we propose a fully parallel and pipelined architecture for Semi-Global Matching with Census Transform being used underneath. Further, we extend the above streaming architecture so that multiple pixels can be processed in a data parallel fashion. We expose this data parallelism through dependency relaxation. This establishes a trade-off between accuracy and throughput of the hardware. We tested the proposed architecture on Virtex-7 FPGA using KITTI 2012 and KITTI 2015 datasets. On images of resolution 1280x960, with 64 disparity levels, we are able to run our hardware design at 100 MHz. At this frequency, our design is able to process 322 frames per second which is 1.6 times faster than the state-of-the-art SGM implementation on FPGA. Our system can be scaled to a higher resolution image.

Abstract

Image processing has various real-life applications in the world, ranging from agriculture, multimedia security, remote sensing, computer vision, medical applications, biometric verification, and many more. In today’s world, applications like biometric verification or object detection are processed on hardware accelerators to facilitate their real-time needs. While some applications are processed in data centers, others are required to be processed on edge due to security, overall latency, and other issues associated with data centers. With their high speeds, very low power consumption compared to other technologies, and reprogrammability, FPGAs provide a sustainable high-speed solution that can be deployed both in data centers and on edge. Therefore, FPGAs are considered very favorable for accelerating image processing algorithms as they are processed both on edge and in data centers. Not only are they supported by the above claims they also are very capable of exploiting the spatial parallelism (data level) and temporal parallelism (task level) [9] [2] which are inherent in image processing tasks. This thesis will focus on the hardware implementation of Local Laplacian filters used for tone and detail manipulation in images on FPGAs. The algorithm uses simple Gaussian and Laplacian pyramids that can be processed in parallel to speed up it’s processing, making it a strong candidate for acceleration on an FPGA. We propose using the LUTs present on the board to reduce complex computations involved in the algorithm, helping save hardware resources and improve latency. We propose a novel 3-stage pipelined convolution engine to exploit the massive parallelism that the algorithm has to offer. The above proposals help us achieve a good speed up as compared to the original baseline multicore-CPU implementation. We also compare our implementation’s accuracy with the original implementation and find the SNR above 40dB for all cases. To analyze our implementation’s resource usage efficiency, we compute the percentage of active and inactive cycles. We find that because of the design’s low resource utilization, it can be run on lower-end boards like ZedBoard.

Abstract

Millimeter Wave (mmWave) communication is considered as one of the important frontiers in the suite of technologies for next generation wireless communication, as it offers a huge unlicensed spectrum and can accommodate ever-increasing data traffic and user demands. However, these potential benefits are accompanied by many challenges that include path loss, loss due to blockages, limited coverage, and absorption and penetration losses. Highly directional beamforming and advanced beamforming techniques are considered as potential ways to overcome these losses. The small wavelength of mmWaves allows the packing of a large number of antenna elements in small volumes, thus enabling MIMO implementation and resulting in large beamforming gains from MIMO. Here, we focus on the design of mmWave communication systems to overcome some of the key challenges encountered while exploiting the benefits of MIMO. The high cost and power consumption of mixed signal components at mmWave frequencies make the practical implementation of MIMO beamformers difficult. Hybrid beamforming, which offers a trade-off between analog and fully-digital beamforming, is a potential technique to overcome this challenge. In this thesis, low-complexity hybrid beamforming architecture is adopted in all the proposed mmWave communication system designs in order to achieve practical feasibility. In particular, to address the underlying challenges, we propose the design of hybrid transceivers for MIMO equipped mmWave systems in different communication scenarios: (i) multi-user MIMO downlink communication, (ii) multi-user MIMO interference channel-based communication, and (iii) MIMO amplify-forward (AF) relay-assisted cooperative communication. For all the considered communication scenarios, we propose low-complexity hybrid transceiver designs. To obtain these, first, the fully-digital filters are derived by solving a specifically designed optimization problem, which is then decomposed into RF/baseband hybrid filters using sparse approximation techniques. The distinguishing factor among these scenarios is the difference in the optimization problem considered to address related communication challenges. Specifically, the first scenario considers that the base-station (BS) is simultaneously communicating with multiple user-equipments (UEs) over a MIMO downlink channel. A sum-meansquare-error (SMSE) minimization problem is formulated under a constraint on the total transmit power. This is a non-convex problem and a closed-form solution is hard to achieve. We propose a joint iterative algorithm for a reliable solution towards this problem. The second scenario, which is a multi-user MIMO interference channel-based scenario, considers a complex network, wherein several mmWave transmitters are simultaneously communicating with their intended receivers. The signal from all remaining transmitters is co-channel interference at each intended receiver. Three different designs are obtained for this scenario. First, an overall SMSE is minimized under total transmit power constraint for all the transceiver pairs to obtain the low-complexity mmWave system design. Later, its dual problem, i.e., minimization of transmit power at the transmitting units while achieving the desired quality-ofservice (QoS) criterion (in terms of SMSE), is addressed. The solution to both the SMSE minimization and its dual problem is derived by an iterative algorithm. At last, the maximization of signal-to-leakageplus-noise-ratio (SLNR) under a constraint on the transmit power is considered. The proposed leakagebased problem results in a set of decoupled sub-problems and hence admits a closed-form solution. This leads to reduction in computation complexity as compared to the first two iterative solutions obtained for this scenario. The third scenario considers a MIMO AF relay-assisted communication system design in which two UEs are communicating with each other via an AF relay. This case addresses the short-range and non-line-of-sight (NLOS) communication challenges of mmWaves. Again, an SMSE minimization problem is considered with a constraint on the total relay transmit power. Two design solutions are obtained based on the operating mode viz., half-duplex (HD) mode and in-band full-duplex (FD) mode, of all the communicating nodes. First, a transceiver and relay-filter design are proposed considering the HD AF relay and HD UEs. Further, this design is extended to in-band FD mode where all the nodes operate in FD mode and utilize the same frequency resources. In in-band FD communication, due to simultaneous transmission and reception, the problem of loopback-self-interference (LSI) prevails. The LSI can be mitigated using the existing cancellation techniques. However, these do not provide perfect cancellation and hence some residual LSI still remains. This residual LSI accumulates over time and hugely affects the overall system performance. In the pro

Abstract

With the rise in popularity of social networks, news is no longer monopolized by newspapers, TV and the radio. Most young people get their information about daily events from Twitter’s Trending page or Facebook’s News Updates and other such online forums. Traditional print media no longer remains the preferred way to get access to information anymore. However, this leads us to an unprecedented problem of content verification. While social media platforms have empowered many, by giving voices to people in remote corners of the world, it has also become a double edged sword. Anyone can now tweet or post whatever they want without any factual evidence or proof online. Such posts can gain traction and lead to a lot of misleading information and confusion for an unsuspecting reader. Taking just the case of Twitter, a popular social media website, Twitter sees an average of around 6000 Tweets per second. This translates to nearly 500 million tweets per day. Manually fact checking data on such a scale is an impossible task, and this is just for one such social media platform. Hence we turn towards automated approaches to the problem. While the sheer quantity already poses a huge challenge, this problem is compounded by the problem of the spread of fake news. A study by Sinan Aral, at the MIT Sloan School of Management, showed that falsehood diffused significantly farther, faster, deeper and more broader than the truth in social media platforms like Twitter. This echoes the quote from Mark Twain that ”a lie can travel halfway around the world, while the truth is putting on its shoes.” This makes the problem of automated detection harder as we need not only an accurate system but a fast one as well, as this becomes a time sensitive problem. With the recent advances and breakthroughs in the field of Machine Learning and Deep learning, we have been seeing great results for classification problems. We leverage these innovations to explore their use and effectiveness in the problem of fake news and misinformation. In this thesis, we build a novel architecture for fast and accurate fake news detection in T 3N. T 3N (Text and Temporal Tree Network), leverages deep learning based architectures to encode text, user and tree information in a temporal-aware manner. In Chapter 4, we also look at the identification of fake news spreaders in social media. Empirical observations showed that tweets shared are significant in identifying if the author is a spreader of fake news or other wise and hence we look at identification of fake news spreaders based vi vii on the content shared by them. Chapter 5 studies multi-modal fake news which consist of text and corresponding images and looks at the relationship between images corresponding to a sample and the text. Finally in Chapter 6, we look at the problem in the Indian context. India a country of 122 Major languages and 1599 other languages, is bound see a problem of fake news in regional languages. We try to put forward a first Indian Language dataset for fake news and see if it can be used to help push the frontier for work in regional languages.

Abstract

Recent studies in neuroscience suggest that a unique individual-specific functional connectivity pattern, or brain signature exists in individuals which can be identified by capturing correlated brain activity using functional Magnetic Resonance Imaging (fMRI). All the previous research done in this subject, brief as it is, has utilized some sort of unsupervised similarity measure to identify the individuals, along with mostly using only a static functional connectivity measure. The objective of our thesis is to utilize the functional connectivity patterns to identify an individual using a supervised machine learning based classification approach. To this end, we use the results of static and dynamic functional connectivity (sFC and dFC, respectively) measures on different fMRI datasets as feature sets for different linear and non-linear classification models to evaluate how well the individuals can be identified. For this, we utilize two previously published datasets comprising of naturalistic music listening task-based fMRI response and resting-state fMRI response. We also aimed to find the neural correlates to the brain signatures for identifying the individuals. We found that the classification models using dynamic FC outperform their counterpart, more specifically, the Instantaneous Phase Synchrony (IPS) method of dFC analysis works better than correlation-based windowed analysis. we also found homotopic connectivities of various regions in brain to be an important part of the brain networks used to identify individuals, while the Olfactory Cortex came up repeatedly as an important brain region as well. For the next part of our study, we observed the effects of band-pass filtering and changing the sample size on identifying individuals using the IPS method of dFC analysis by utilizing the minimally preprocessed HCP dataset. We found that performing a band-pass filter greatly boosts the classification accuracy, which stays stable even when the sample size of individuals is increased. Overall, this study shows a lot of promise on using a machine learning approach to identify individuals while using IPS as a dFC measure and presents a novel direction to investigate further

Abstract

Over the years, Earthquake has been one of the leading cause of life loss and destruction of properties. Man-made structures like buildings, roads, dams and bridges are severely affected due to earthquakes. Bhuj earthquake of 2001 killed nearly 15,000 people and damaged around 3.5 lakh buildings. The major contributors to the loss of so many buildings were the poor construction and maintenance practices. To address the deficiencies that lead to such catastrophic damage, major reforms have been introduced to the Indian Standard codes and numerous studies have been conducted to prescribe methods to curtail the damages further. These studies can broadly be classified into earthquake prediction studies and earthquake preparedness studies. Earthquake prediction studies can be used to minimize the loss to life. But over the years, the research on earthquake prediction hasn’t provided satisfactory results, and Earthquake prevention looks like a far-fetched dream. Hence, earthquake preparedness is of utmost importance to minimize earthquake damage. Earthquake preparedness involves the construction of new buildings in compliance with the latest building construction codes of the country as well as fixing the deficiencies of the existing buildings. Hence, identifying the vulnerabilities in a building is a very crucial step towards earthquake risk mitigation. When the vulnerable buildings of a region are identified, the seismic risk of the region can be determined, and actions to mitigate these risks can be taken. But the identification of vulnerable buildings in a region is a very resource and time-intensive process. A quick method to identify vulnerabilities in the buildings of a particular region is Rapid Visual Screening (RVS). This method can be used to find common vulnerabilities in the buildings, and the entire process of RVS of a building can be completed within 30 minutes by a single, trained person. But many buildings may require a detailed investigation in order to assess its safety. Detailed investigation requires the modelling and analysis of the building in finite element software. This requires the time and energy of people who are proficient in such software along with powerful machines to run such software. These problems make detailed investigation, time and resource-intensive process as well as very expensive. Hence, there is a need for an efficient and effective method to perform this task.

Abstract

The problem of multi-objective decision making has been an important one in the field of database management systems. Establishing dominance relationships among different data points has useful applications in industries such as tourism & sports. Given a dataset D with c points, a point pi dominates another point pj if it is better than or equal to pj in all the dimensions in space S and better than pj in at least one dimension. The set of such points which dominate all other data points in the dataset is referred to as the skyline set of points. The skyline operator suffers from the curse of dimensionality which means as the number of dimensions increase the number of skyline points become large and difficult to compute. With data growing at exponential rate in today's information age traditional algorithms designed for skyline query computation over limited resource standalone computers will not fare too well. Scaling up systems in terms of computing power & memory has traditionally proven to be expensive. Therefore, there is a need to leverage a cluster of cheap commodity hardware to efficiently compute skylines of large datasets. Thus the data needs to be divided into multiple smaller datasets which can be used to compute individual skylines across the smaller datasets and merged to form the overall skyline of the entire dataset by using a divide and conquer approach. The curse of dimensionality is even more amplified on large datasets hence making the problem of computing skyline even more complex, thus motivating us to use techniques which do not require us to eliminate points already in the computed skyline by points encountered afterwards. We achieve this by approaching points along the Z-order curve which provides us a monotonic access order of data points thus identifying skyline points earlier. The Z-address of a point in multi-dimensions is simply calculated by interleaving the binary representations of its coordinate values. In this thesis, we address the problem of efficient computation of skyline for large datasets using the Map-Reduce programming paradigm. Our approach is to map multi dimensional data to one dimension while preserving the locality of the data points using Z-order curve and exploiting the sort phase of a typical Map-Reduce job to receive these points in the Reduce job automatically sorted in the requisite order. Our results show a reduction of up to 31% in execution time for skyline computation over a Map-Reduce framework using our algorithm as compared to existing methods.

Abstract

Automated Question Answering (AQA) is an attractive variation in search engines where the QA system automatically returns a passage, which answers the user’s question instead of providing several links and letting the user explore for an answer. These AQA systems are an integral part of search engines and voice assistants such as Amazon Alexa, Apple Siri, Microsoft Cortona, Google Assistant, etc., Due to the recent growth in AQA systems, the research in this field has seen a tremendous improvement. Ranking the passages is an important step in an AQA system, where the candidate passages are identified for a question and scored as likely to contain an answer. To explore the various practical approaches for this problem, Microsoft has released a large scale dataset called as Microsoft MAchine Reading & COmprehension (MS MARCO) in 2016. Using the subset of the MS MARCO dataset, it has also organized a challenge called Microsoft AI Challenge India (MSAIC) to provide a platform for researchers and AI practitioners across the country to contribute to this area. In this thesis, we propose different approaches based on biLSTM that we used during our participation in Microsoft AI Challenge India. We show that our best model, based on the biLSTM encoder with coattention mechanism (which we call as coattention encoder), has significantly outperformed the shared baselines and benchmark models. In the second part of this thesis, we discuss and address the two limitations of the coattention encoder. We first extend the coattention encoder to n-grams to make it capture the local context. We further improve the coattention encoder by proposing a simple attention pooling using the query to refine the passage’s representation. We perform all our methods on the MS MARCO passage ranking task and demonstrate that these two methods yields a relative increase of 8.04% in Mean Reciprocal Rank (MRR@10) compared to the naive coattention encoder. It is the best non-transformer model and is competitive to the BERT base while only having fewer parameters. Additionally, when compared to BERT, our model has a very low ranking latencies.

Abstract

Blockchain technology has been one of the most disruptive innovations in the last decade. Blockchain is a decentralized, append-only trustworthy distributed database. It was invented to build Bitcoin – to democratize financial systems, in particular, currency. However, soon the researchers learned the power of blockchain to build smart contracts, programs that can execute and validate contracts, which otherwise were traditionally done through legal contracts. Since then, there are a plethora of applications has been envisioned using blockchain. At the backend, miners are the ones who maintain the blockchain in anticipation of fair rewards. Bitcoin offers two types of rewards for the miners: (i) block rewards that halve every four years and (ii) transaction fees. Halving block rewards is done by making currency inflation-free. Transaction fees are optional. This can lead to stagnation of transactions and unprofitability for miners. Another challenge with Bitcoin or many other blockchains, to build real-world applications, is performance. Many times, improving performance in blockchain leads to different security issues. In this thesis, we address both research challenges: (C1), how to configure the Bitcoin reward structure to maintain its ecosystem healthily as well as inflation-free. (C2), how to design a blockchain that is performant as well as secure. Towards C1, we propose BitcoinF, a simple modification to Bitcoin rewards that ensures fairness to the miners. We analyze it game theoretically. Towards C2, we propose QuickSync, a novel blockchain protocol that is faster than most of the secure blockchain protocols such as Bitcoin and Ourborous and retains all the security properties. We do security analysis for different attacks such as Sybil attacks and prove the robustness of QuickSync towards the attacks we studied