Abstract

Automatic speech summarization is the task of generating a concise summary of a speech signal using a digital computer. The existing speech summarization systems rely on automatic speech recognition (ASR) transcripts and gold standard human summaries to generate summaries of speech signals. The limitations with these approaches are, ASR errors make summaries less usable by humans, also ASR systems are not available for all languages, especially for less resource languages and it takes considerable resources and effort in building one. Gold standard human summaries are not available for all speech signals and building them is tedious and time consuming task. In this work, we propose two techniques for summarization: 1) Exploiting anchor speaker role in broadcast news (BN) show to construct summaries, 2) A generalized ranking of speech segments based on prominence values of syllables in them. By analyzing manual summaries of news shows, it was found that anchor speaker segments are mostly picked in manual summaries. Therefore it is desirable for automatic summaries to exhibit this characteristic. We proposed two techniques to perform anchor speaker tracking, based on auto associative neural network model and Bayesian information criterion method. Audio summaries are generated for desired summary length by concatenating anchor speaker segments based on their positional features. These summaries are evaluated with the help of ROUGE, an automatic text summarization evaluation pack age by transcribing the audio summary into text. ROUGE-N metric measures the N-gram overlap between human reference summaries and the automatic summary. The f-measure scores of the proposed system for ROUGE-1 and ROUGE-2 metrics are 0.561 and 0.392 respectively. These scores showed that the system is capable of generating summaries that are as good as supervised speech summarization system trained using gold standard human summaries which achieved 0.553 and 0.382 for ROUGE-1 and ROUGE-2 metrics respectively. Also, we performed a task based evaluation where, humans were asked to listen to the summary and answer questions regarding the contents of a news show. The percentage of questions answered by the humans was 71 % for the proposed system which is better than 60.2 % of the supervised speech summarization system. The coherence of the summaries was also evaluated by asking the users to rate the summaries on a scale of 1-5 where 1 corresponds to very bad and 5 corresponds to very good. The mean opinion scores (MOS) of these ratings for the proposed method and the supervised speech summarization system are 4.05 and 3.2 respectively. The task based evaluation of these summaries by humans showed that, they prefer the summaries generated by the proposed techniques over the summaries generated by standard speech summarization methods. In other part of the work, a technique to rank segments in a speech signal using prosodic features that indicate importance is proposed. When humans convey message through speech, they attract listeners’ attention to information bearing parts of speech through variations in pitch, amplitude, duration and stress. Speakers make some words prominent and reduce other words. The proposed method computes syllable level prominence values as a function of syllable nucleus duration, sub-band energy (300-2200 Hz), and pitch variation and these values are used to obtain a segment level score, which is used for ranking the segment for summarization. It is shown that this type of scoring captures the prosodic information relevant to summarization in an unsupervised framework. We have also proposed a method to combine lexical and positional features with the prominence based scoring when text transcripts of speech signals are available. The proposed prominence based scoring captures complimentary information to lexical features derived from text transcripts of speech signals. The combination of these features perform better than the individual features. The proposed method was evaluated on two types of speech data; read style news speech and spontaneous telephone conversations. The proposed system based on prominence scoring achieved ROUGE-1 and ROUGE-2 f-measure scores of 0.508, 0.341 on read style news speech and 0.666, 0.464 on spontaneous conversations respectively. In read style speech the basic unit of extraction was obtained based on pause based segmentation which does not give semantically meaningful segments, where as in spontaneous telephone conversations we have considered speaker turns which are semantically meaningful units as basic unit of extraction.

Abstract

Conventional CMOS logic circuit design approaches rely on charging the output capacitive nodes to the power supply Vdd or discharging it to ground. This design approach has been widely used. For Low power applications, although there are many techniques both at circuit level and system level, a very fundamental source of energy dissipation is the discharge of the capacitor to ground. Every time a capacitor is discharged to ground, an amount of energy = 12 CV 2 stored in the capacitor is lost. This loss of energy can be prevented if instead of discharging the capacitor to ground, the charge or energy stored can be recycled. Another way of reducing the power consumption is to design the circuit in such a way that the charging of the capacitive node takes place very slowly. It has been observed that slowly charging the capacitor requires lesser energy than abrupt charging. Adiabatic circuits use the above two methods viz. slow charging and discharging, and charge recycling to minimize the power consumed. Several Adiabatic designs have been proposed in literature. Most of them achieve significant power savings in comparison to conventional circuits. Drawbacks of these circuits include complex circuit design for achieving simple operations, requirement of multiple clocks and/or requirement of complimentary input signals for controlling the charging/discharging process. The Current work is based on an existing adiabatic logic style known as GFCAL (Glitch Free and Cascadable Adiabatic Logic )which is simple and does not require complimentary signals or complex clocking. The GFCAL has a drawback that it uses junction diodes for controlling the charging and discharging of output nodal capacitance. Junction diodes are difficult to fabricate in a CMOS process and they are responsible for power dissipation due to the cut-in voltage drop across them. This work improves the circuit by replacing the diodes with transistors that control the charging and discharging process. The efficiency has gone up from 50% for GFCAL to about 60% for the modified circuit in comparison to conventional CMOS logic circuits. The modified design is found to work satisfactorily, is cascadable and simple block level implementations like adders have been demonstrated and verified to work with lower power consumption than conventional CMOS circuits.

Abstract

The technology evolution and complexity of new circuit applications involve emerging reliability problems and even more, sensitivity of integrated circuits (ICs) to electrostatic discharge (ESD) and Overvoltage stress-induced damage. Regardless of the aggressive evolution in downscaling and subsequent improvement in applications’ performance, ICs still should comply with minimum standards of failure robustness in order to be commercially viable. Although the topic of IC Protection from ESD and Over voltage induced damages has received attention industry-wide, the design of robust protection structures and circuits remains challenging because the failure mechanisms continue to become more acute and design windows less flexible. The sensitivity of smaller devices, along with a limited understanding of the ESD phenomena and the resulting empirical approach to solving the problem have yielded time consuming, costly and unpredictable design procedures. As turnaround design cycles in new technologies continue to decrease, the traditional trial-and-error design strategy is no longer acceptable, and better analysis capabilities and a systematic design approach are essential to accomplish the increasingly difficult task of adequate protection against IC failures. This dissertation presents comprehensive design methodology for implementing on-chip ESD protection for LNA and a circuit design technique to overcome Reliability issues in Mixed Voltage IOs. Firstly the various failure mechanisms in Integrated circuits is revised. In the next chapter, the ESD topic in the semiconductor industry is described, as well as ESD standards and commonly used schemes to provide ESD protection in ICs. The general ESD protection approach is illustrated and discussed using different types of protection components and the concept of the ESD design window. The problem associated with capacitive loading of ESD protection device in LNAs is addressed next. A better methodology for implementing greater level of ESD protection by making use of ON chip inductors is proposed. The passives used in the design of RF Receiver blocks also influence the ESD robustness of LNA. Inductors and capacitors in RF circuits can be implemented either ON chip or OFF chip. In earlier technologies where the passives used to be OFF chip the ESD immunity of the LNA was totally determined by the robustness of ESD protection device. However in modern RF ICs the focus is on full integration to reduce system cost and area. So the passives appear ON chip. In RF ESD Protection it is common practice where capacitors and inductors in the circuit used for matching and frequency selection, are used to tune out ESD frequencies. In a Cascode LNA with inductive degeneration where ON chip inductors are used they can be used for ESD protection. Two cases are considered. In the first case a common design practice where the ESD device is positioned at the gate of LNA is considered as shown in Figure 1.1 and it is shown that the level of ESD protection is very much limited as the frequency of operation increases. In the second case we shift the ESD device away from the gate of LNA and make use of ON chip inductors to enhance the level of ESD protection. This method also has been shown to that the advantage that the capacitive effects are reduced as we move away from the gate of LNA. Consider the topology in Figure 1.1 (a).As the frequency increases the capacitive reactance decreases and the ESD device begin to shunt more signal power to the ground. With this topology around 5GHz frequency of operation the achievable level of ESD protection may be reduced to 500V HBM which leads to early failure of the circuit.The proposed methodology for providing ESD protection for LNA using ON chip inductors is shown in Figure1.1 (b).By shifting the ESD protection device away from the gate of LNA and towards antenna the capacitive effects are reduced which means that the degradation of power gain and noise figure is less for given ESD device size. Also the required matching of 50Ω for maximum power transfer can achieved by varying both gate inductor Lg and source inductor Ls providing higher degree of freedom. Also the presence of gate inductor suppress steep current transients. With the proposed methodology upto 4KV HBM ESD protection is shown to be possible without much degrading the LNA performance parameters where as with the existing approach maximum protection of 2KV HBM was possible at 2.1GHz. The analysis is validated by simulation for 2.1GHz LNA with ON chip Spiral inductors and ESD protection in Cadence Design Suite using IBM CSOI7TF 180nm RF Technology. The Overvoltage protection issues in Mixed Voltage IOs is addressed next. When two digital logic devices having different power supply levels are coupled an interface is generally required to prevent damage to transistors in the device having the lower power supply level. In the mixed-voltage I/O buffers, that interface t

Abstract

Robot localization is the problem of estimating a robot’s coordinates relative to an external reference frame, say a map. Given a map of its environment, the robot has to localize itself relative to this map by consulting its sensor data. The task of the robot is to find out where it is, through sensing and motion. Localization has proved to be the most critical aspect of mobile robot navigation. There are different forms of the localization problem: Position tracking, which seeks to compensate small dead reckoning errors (odometry errors) under the assumption that the initial robot pose is known, and global self- localization, which addresses the problem of localization with no apriori information i.e. a robot is not told its initial pose but instead has to determine it from scratch. In environments which possess relatively few features that enable a robot to unambiguously deter- mine its location, global localization algorithms can result in multiple hypotheses about the location of a robot. This is inevitable as the local environment seen by a robot repeats at several parts of the map. Such a situation occurs commonly in indoor navigation such as in corridors and office rooms. For effec- tive localization the robot has to be actively guided to those locations where there is a maximum chance of eliminating most of the ambiguous states. This task is often referred to as ‘active localization’. Active localization is based on the decision of ‘where to move’ and ‘where to look’ so as to best localize the robot. These actions mainly comprise of moving towards unique features in the map (e.g., distinct obsta- cles in a static environment), such that the sensor readings become unique and hence the robot localizes. This thesis presents a learning framework for implementing active localization. In a given map, the framework should be able to determine what actions to execute in a state, such that localization is ac- celerated. Since global localization poses the problem of perceptual aliasing, a belief state instead of a state is used to describe a robot’s position in the map. A belief-state MDP (Markov Decision Process) is used to capture the mapping between the robot’s belief state(s) and action(s) which will maximize the expected discounted rewards. The novelty of this work lies in the fact that it proposes a hierarchical belief state framework for the MDP to perform the active localization task. Markov localization is used typically to estimate a belief-state from a given set of robot’s sensor readings. This belief-state space being extensive is represented by a yet another hierarchical belief-state space, which makes the MDP more tractable. Hence the framework enables to perform localization with accuracy of fine grid granu- larity ( as in Markov localization) without having to handle large state space MDP(s). A mathematical formulation in detail for the framework has been provided. The feasibility of this framework is shown by testing it for different aspects of active localization task . It is used to perform multi-robot active localization, where the framework not only learns to seek out unique features in the map, but also learns to detect other robots, thereby facilitating localization even in the absence of map features. It is observed that multi-robot localization algorithm proves to be an intuitive, semi-distributed algorithm which is able to attain an autonomy with respect to the number of robots. That is to say, unlike a centralized algorithm that requires re-calculation from the scratch with the change in the number of agents involved, this algorithm can be re-used without re-training for a range of number of robots. The analysis of localization performance is done by comparing it with a learning framework which uses random walk. The framework is also used to perform transfer of the learned localization policy from a robot with higher sensor capabilities to the one with the lower sensor capabilities, thereby enabling the possibil- ity of accelerating localization in a setup with heterogenous robots. The change in the sensor range is considered as the change in observation function in MDP context and a transfer policy is designed to transfer the knowledge between the two belief states MDP(s). The localization performance with transfer is analyzed by comparing with performance , when learning is done from the scratch without any transfer. It is observed that transfer leads to a better learning rate as the performance reaches an optimum in lower number of training iterations. One of the observation also shows the effect of map type on transfer and suggests the fact that the advantages of transfer is more pre-dominant in the case of sparse maps than the dense maps. The contribution here lies in attempting transfer across belief states MDP(s), since transfer has been limited to just MDP(s) till now. Also the transfer aspect is

Abstract

Symmetry breaking is a fundamental operation in distributed computing. It has applications to several important and fundamental problems such as graph vertex and edge coloring, maximal independent sets and the like. Although this area has been studied for over 3 decades now, deterministic algorithms for symmetry breaking that run in poly-logarithmic number of rounds are not known. However, randomized algorithms that run in poly-logarithmic number of rounds are known starting from Luby’s algorithm. Recently, orientation on edges was considered and it was shown that an O(
) coloring of the vertices of a given oriented graph can be arrived at using essentially O(log
+ √log n) bits of communication. In our work, we further demonstrate the power of orientation of edges in symmetry-breaking. We present efficient algorithms to construct fractional independent sets in constant degree graphs using very low order communication between the vertices. For instance, we show that in bounded degree graphs and planar graphs, it is possible to construct a fractional independent set by exchanging O(1) bits. Further, we present algorithms to construct maximal independent sets in bounded degree graphs and oriented trees. Our algorithm for constructing an MIS of an oriented tree uses only O(log n) bits of communication. We also aim at an empirical analysis of distributed vertex coloring algorithms. To this end, we compare the empirical performance of the recently proposed distributed vertex coloring algorithm which uses orientation with that of Luby’s algorithm. To get a good coverage we look at the cycle graph on n vertices, cliques, and random graphs from the family G(n, p) by controlling n, p and np. The results of our experiments fairly demonstrate the improvement in the bit complexity of the algorithm proposed by the authors of the oriented coloring algorithm. vi

Abstract

Automatic speaker verification (ASV) is the task of verifying a person’s claimed identity from his/her voice using a digital computer. The existing ASV systems perform with high accuracy of verification when the speech signal is collected close to the mouth of the speaker (< 1 ft). However, the performance of the ASV systems reduces significantly for speech signals collected at a distance from the speaker (2-6 ft). The objective of this work is to address some research issues in the processing of speech signals collected at a distance from the speaker, for text-dependent ASV system. The distant speech signal is collected using single channel microphone. An acoustic feature derived from short segments of speech signals is proposed for ASV task. The key idea is to exploit the high signal-to-noise nature of short segments of speech in the vicinity of impulse-like excitations. We demonstrate that the proposed feature suffers lesser degradation with distance when compared to the widely used Mel-frequency cepstral coefficients (MFCCs), and also yields better performance of speaker verification than MFCCs. We propose a method of begin-end detection based on the strength of the spectral peaks. A score normalization method is proposed by considering only the robust regions of speech signal. In addition, the regions of speech signal with high signal-to-reverberation ratio are identified, and greater weightage is given to these regions. These modifications are shown to result in a systematic improvement in the performance of the speaker verification system. The use of additional features of duration and pitch is shown to further improve the performance of speaker verification system for distant speech. Keywords: automatic speaker verification, text-dependent, distant speech, high signal-to-noise ratio, pitch, duration. iii

Abstract

When humans modify speaking rate they do not perform a simple expansion or compression of the speech signal. In order to maintain the intelligibility and naturalness of the speech, they modify some of the characteristics of the speech production mechanism in a complex way. This causes the acoustic features extracted from the speech signal to change in a complex way. These changes affect the performance of speech systems like speech recognition, speaker recognition etc. Most of the studies on the effect of speaking rate on acoustic features focus on features at segmental and suprasegmental level. The present work focuses on analysis of the effects of speaking rate on features at subsegmental level. Three features at subsegmental level, namely, instantaneous fundamental frequency, strength of excitation of epoch and perceived loudness are chosen, and their variation with speaking rate is studied. It was observed that instantaneous fundamental frequency increases with increase in speaking rate, but when speaking rate is decreased the changes in the instantaneous fundamental frequency is speaker-specific. Similar observations have been found in the case of strength of excitation at epoch. Strength of excitation decreases with increase in speaking rate, and the change in strength of excitation is speaker-specific when speaking rate is decreased. The effect of speaking rate on the perception of loudness is also studied using perceptual loudness studies. It was observed that fast speech was perceived louder than normal speech for majority of speakers, whereas the difference between perception of loudness of normal and slow speech is speaker-specific. It was also observed that speaking rate does not have significant affect on objective loudness measure. A modified measure of loudness in the case of speech at different speaking rates is proposed, and its variations correlate with results from perceptual loudness tests. The variations of subsegmental level features with speaking rate are incorporated in a non-uniform duration modification method. Subjective studies on the synthesized speech showed that incorporation of the subsegmental variation improved the quality of speech at different speaking rates. Keywords: Speaking rate, spontaneous speech, segmental features, instantaneous fundamental frequency, strength of excitation, perceived loudness and duration modification.

Abstract

Graph coloring is a fundamental problem in Computer Science. Despite its status as a computation- ally hard problem, it is still an active area of research. Depending on the specific area of requirement or an application, there are several variants of coloring. One such variant of graph coloring is Acyclic Graph Coloring. This requires that after a graph has been colored there should not exist any cycle that runs on vertices that are colored by only two colors. Such a cycle is called a bichromatic cycle. When a coloring does not present itself with a bichromatic cycle, it is said to have acyclically colored the given graph. As with the case of proper coloring of graphs, acyclic coloring can either be on vertex set or the edge set of a graph. When such a coloring is performed on the edges of a graph, a bichromatic cycle is said to be one that runs on the edges that are colored by only two colors. In absence of such a bichromatic cycle, an edge coloring is said to be an acyclic edge coloring of that graph. The smallest number of colors required to acyclically vertex color a graph is called its acyclic chro- matic number and is denoted by a(G). Similarly, the smallest number of colors required to acyclically edge colors a graph is called its acyclic edge chromatic number and is denoted by a′ (G). There are several applications of acyclic coloring of a graph which include Hessian computation, applications in coding theory as well as other theoretical problems such as Minimim Feedback Vertex Set. In addition to this, acyclic chromatic numbers are closely related to several other types to colorings of a graph each of which are applicable in several other fields of interest. A notable example among these is the star chromatic number of a graph and star arboricity. Star graphs are used to model star network topologies that have applications in computer networks and distributed computing. The problems of finding the acyclic chromatic number or acyclic edge chromatic number of a graph are known be NP-hard. Also, there is a very little knowledge about such a characteristic of a graph even for the most simple classes of graphs like complete graphs. This thesis is dedicated to explore some common classes of graphs for which the acyclic chromatic number or the acyclic edge chromatic number can be found out. We also try to strengthen our results by providing contructive bounds and efficient linear time algorithms for the graphs that we study. In this respect, we have presented appreciable results for acyclic edge chromatic number of complete graphs when the number of vertices can be represented as a certain product of a prime and numbers one less than a prime. Another class of graphs that we have considered are the grid-like graphs. The name implies that these graphs are structurally similar to a standard grid graph. More specifically, these graphs can be represented as a product of certain simple class of graphs such as a path or a cycle. In this case, we have successfully acyclically vertex colored some specific cases of these graphs. Lastly, we mention here that through out this work, we have provided elaborate intuition on how we arrived at our coloring schemes and how such schemes are helpful in gaining an understanding of the structure of the graphs in question. This intuition can be very helpful for gaining an overall understanding of this work apart from the mathematical proofs. It should also be an important asset in any possible extension of our work.

Abstract

The area of graph mining deals with mining frequent subgraph patterns, graph classication, graph clustering, graph partitioning, graph indexing and so on. In this thesis, we focus only on the area of frequent subgraph mining and more precisely on maximal frequent subgraph mining. MARGIN is a maximal subgraph mining algorithm that moves among promising nodes of the search space along the “border” of the infrequent and frequent subgraphs. This drastically reduces the number of candidate patterns in the search space.

Abstract

Contracts play a major role in establishing binding relationships between various business units and also between businesses and their customers. A contract consists of numerous activities that have to be carried out by the involved parties and contract clauses that address specific concerns in the business process interaction. An e-contract is a contract modeled, specified, executed and deployed (controlled and monitored) by a software system (such as a workflow system). As contracts are complex, their deployment is predominantly established and fulfilled with significant human involvement. This necessitates a comprehensive framework for generic fulfillment of e-contracts. So, the goal of e-contracting is to transform a traditional contract document into an executable e-contract.