Abstract

Over the last few years, the amount of image and video data present over the internet, and in the personal collections has been increasing rapidly. Therefore, the need for organizing and searching these vast collections of data efficiently has also increased. This has led to the research in the areas of content based retrieval and recognition of scenes/objects in visual data. There has been lot of research in these areas over the last few years and are still not yet at a deployable stage for real-world usage. For these technologies to be deployable, these solutions should not only be accurate, but also efficient and scalable. For all these related problems of visual recognition, there are two major phases, namely feature extraction stage and learning stage. The feature extraction stage deals with building a representation for the image/video data and the learning stage deals with learning how a function which can distinguish the classes. In this thesis, we focus on building efficient methods for visual content recognition and detection in images and videos. We mainly propose new ideas for the learning stage. For this purpose we start from using the state-of-the-art techniques and then show how our proposed ideas influence the computational time and performance. Firstly, we show the utility of state of the art image representations and classification methods for the purpose of large scale semantic video retrieval. We demonstrate this on TRECVID 2008 and TRECVID 2009 datasets containing videos for the retrieval of various scenes, objects and actions. We use Support Vector Machines(SVMs) as classifiers, which have been the popular choice for classification tasks in many fields. They have become popular mainly because of their good generalization capability. For obtaining non-linear decision boundaries, SVMs use a kernel function. This kernel function helps in finding a linear classifier in some high dimensional feature space, without actually computing the higher dimensional vectors. In many situations, we need to use computationally expensive non-linear functions as kernels. On the other hand, Linear kernel is computationally inexpensive, however it gives poorer results in most of the cases. Another contribution of this thesis is a method for improving the performance of computationally inexpensive classifiers like linear SVM. For this purpose, we explore the utility of sub-categories, which are the sub groupings present in the feature space of each semantic class of data. We model these subcategories by using Structural SVM framework. Also, we analyze how the choice of the groupings effect the results and present a method to learn the optimal groupings. We investigate our methods on various synthetic two dimensional datasets and real world datasets namely, VOC 2007 and TRECVID 2008. vi vii Non-linear kernel methods yield state-of-the-art performance for image classification and object de-tection. However, large scale problems require machine learning techniques of at most linear complexity and these are usually limited to linear kernels. This unfortunately rules out gold-standard kernels such as the generalized RBF kernels (e.g. exponential-2). All the No-linear kernels help in computing the inner product in a high dimensional space different from the input space. This helps in overcoming the explicit computation of the high dimensional vectors. The function which can be used to compute this high dimensional feature vector is called the feature map. But this feature map is hard to compute and is very high dimensional. In the literature, explicit feature finite dimensional feature maps have been proposed to approximate the additive kernels (intersection, 2) by linear ones, thus enabling the use of fast machine learning technique in a non-linear context. Also, an analogous technique was proposed for the translation invariant RBF kernels. As a part of this thesis, we complete the construction and combine the two techniques to obtain explicit feature maps for the generalized RBF kernels. Further-more, we investigate a learning method using l1 regularization to encourage sparsity in the final vector representation, and thus reduce its dimension. We evaluate this technique on the VOC 2007 detection challenge, showing when it can improve on fast additive kernels, and the trade-offs in complexity and accuracy

Abstract

A skyline query on a set of k-dimensional data points gives a dominating subset of points (Skyline set, Pareto dominance) based on a given user criteria. The user criteria can be either max or min. Recent research work focused on developing efficient algorithms for computing the skyline points efficiently. There has been keen interest in developing different variations of the skyline queries like subspace skyline queries, Reverse Skyline Queries, Spatial Skyline queries and Dynamic skyline Queries. In addition, the existing techniques for the computation of skyline queries consider only the efficiency of the algorithm while the semantics of the skyline points retrieved remains an open problem. In this thesis, unlike the above we propose three variants of the skyline Queries (1) Inverse Skyline Queries, (2) Skyline Membership Queries and (3)Maximal Skyline Membership queries. All the above queries are used to answer “What features or dimensions of the given set of query points make them the skyline points if at all?” In case of inverse skyline queries, given a subset of data points Q, the problem is to identify the subspace and user criteria for which Q is a skyline set. We approach this problem by using a pre-computation based algorithm and later formulate two algorithms to compute the inverse skyline from the pre-computed input, considering both min and max criteria. In the case of skyline membership queries, given a subset of data points Q, the problem is to identify the subspace for which Q is a skyline set. The problem of skyline membership queries is formed by relaxing certain properties of inverse skyline queries. Skyline membership queries were first proposed in [16]. Motivated by the fact that the result of Skyline membership queries is sometimes f;g, we proposed Maximal skyline membership queries. The Maximal skyline membership problem is to identify the maximum set of points from the query set Q, which form skyline in each subspace of the k-dimensional space. To tackle the problem of Skyline membership queries and maximal skyline membership queries we proposed two algorithms based on top-down and bottomup approaches. We also proposed various pruning techniques to compute them efficiently. We demonstrate our results on both real-world datasets(e.g., Basket ball and Used car datasets) as well as synthetic datasets such as independent, anti-correlated and correlated datasets. The efficiency and scalability of the algorithms are also demonstrated by the results. Keywords: Subspace skyline, Inverse skyline query, Skyline membership queries, Maximal skyline membership queries, Bounded skyline region.

Abstract

In recent years, much research has gone into developing cognitive models of web-navigation. LICAI (LI nked model of Comprehension-based Action planning and I nstruction taking) was developed to simulate an expert user performing unfamiliar tasks on a Mac interface. CoLiDeS (Comprehension- based Linked model of Deliberate Search) builds upon LICAI by adding a parsing phase during which a user parses a web-page into high level schematic regions and selects a region that is most similar to the goal for further processing. CoLiDeS+ extends CoLiDeS by incorporating contex- tual information from previous clicks and modeling backtracking strate- gies. While CoLiDeS and CoLiDeS+ model navigation within a website, SNIF-ACT (Scent-based Navigation and I nformation Foraging in ACT- Architecture) and MESA (Method for Evaluating Site Architectures) were developed to model navigation behavior on the entire World Wide Web (WWW). All these models are inspired by the concept of information scent formulated by Information Foraging Theory (IFT). According to IFT, information scent is the imperfect perception of the val- ue/cost associated with a particular action, such as clicking on a hyperlink. A striking similarity between all the above models is that they operationalize information scent as the semantic similarity between the user-goal descrip- tion and the hyperlink text. They ignore all other content on a web-page, at least for computation. The central idea of this dissertation is that, not only semantic information from hyperlink text but also information from visual and graphical modality like semantic information from pictures must be ac- counted for in the models of web-navigation. Not much literature was found investigating the role of graphics on web-navigation. Drawing inspiration from Dual-Coding theory, Multimedia Learning theory, Cognitive Load the- ory and theories on visual search and visual attention, we conducted various experiments to ll this gap in web-navigation literature. We explored the role of graphics and text in locating web-page widgets, the role of text in main content in addition to hyperlinks in information retrieval tasks on the web, the impact of providing picture icons next to hyperlinks and the im- pact of relevance of pictures (high vs. low) on web-navigation. The results of our experiments indicated a strong positive in uence of pictures on web- navigation behavior (users took less time, less clicks, were less disoriented and were more accurate when both text and graphics were presented). This motivated us further towards developing a new cognitive model called CoLiDeS + Pic that augments CoLiDeS with additional semantic informa- tion from pictures. We gave a theoretical explanation as to how the cogni- tive processes could be running with pictures when navigating on the web. We presented three dierent scenarios and their consequences. We used a novel method of assessing semantic relevance of pictures with respect to the user-goal using Latent Semantic Analysis (LSA). The new model CoLiDeS + Pic was simulated with mock-up websites and later evaluated with actual user navigation behavior. We found that the new augmented model under high relevance picture condition not only predicts the correct hyperlink with higher frequency but also predicts actual user behavior more accurately. We made the rst steps towards developing a fully automatic support system for navigation on the web. The existing tools based on the cognitive models of web-navigation are meant for evaluators or designers and not for end users. We found strong positive eects of the model-generated support on navigation performance. Users took signicantly less time, less clicks, were less disoriented and were more accurate in the support condition. Also, the perception of the support system was very positive. We extended the scope of applications that the cognitive models of web- navigation can be applied to. By exploiting the fact that the cognitive processes during navigation in the online world and navigation in the real and 3D virtual worlds are largely the same, we used a cognitive model of web-navigation (CoLiDeS) to provide support to users with low spatial abilities to reach to a particular section in a simulated 3D virtual environment of a complex building (a hospital). We demonstrated how the tools developed for evaluating websites can also be used to evaluate the label wordings in a 3D virtual environment. In a nutshell, the main contributions of this dissertation are: 1. Filling a gap in literature on the in uence of graphics on web-navigation. 2. Development of a more accurate cognitive model of web-navigation that incorporates semantic information from two modalities: text and pictures. 3. Development of a small prototype that generates automatic support for a given user-goal and URL of a website. 4. Demonstrating the usefulness of cognitive m

Abstract

Human Computer Interaction and usability have become increasingly important with the advent of the Internet and its emergence as means of communication,e-commerce and social networking. A user friendly website will attract more readers thus increasing the number of loyal visitors. As a result, the need for presenting information in an attractive and usable manner is significant. Web usability of a website is a measure of how intuitive the presentation of its contents are. A variety of techniques like heuristic evaluation, expert reviews, performance evaluation have been developed to measure usability and correlate this to end-user results like increase/decrease in visitors, increase/decrease in errors performed while doing some tasks on the webpage etc. This thesis is a compendium of three different experiments each on webpage elements, navigation in music data and polarity of comments in blog articles respectively. Present experimental studies mainly focus on the semantic influence of text links and the impact of graphical conventions and layout locations. Comparatively, less work has been done on interaction in between web page elements. An experiment to test whether there exist any interdependencies in between location expectations of web widgets is conducted. This experiment also includes an eye-tracking study whose results can be used to determine the blind spots of each widget in a webpage. Based on the results obtained from this experiment, conclusions are made to establish the interdependencies. It is noticed that out of the 4 widgets (Search, Navigation pane, Ads and Login) that we’ve considered, location expectations of two of them (Navigation pane and Ads) are found to be independent of any other widget whereas the other two (Search and Login) are found to be dependent on main content and navigation pane of the page respectively. Such findings when followed as heuristics can be used in developing new websites to help users search for dependent widgets when the location of a widget is known. Another study includes the design,implementation and evaluation of a web model that helps in searching and browsing through huge music data catalog. The fundamentals of faceted navigation are used to build this model which groups the music data based on the similarity in their features rather than metadata. We named this web model as REM which expands to Ray Exploration Model. As the name suggests, it conceptualizes the depth of each attribute in the data and breadth across the attributes in an easily navigable sun model with its rays. Together suns and rays form a network using relations between the values of attributes. REM caters to search needs of a user without the limitations of the popular keyword based search approaches. This model is implemented using Raphael JS graphics and is evaluated using a usability evaluation method called ‘performance measurement’. Results from this vii viii evaluation are used to know the user satisfaction with the model and suggestions/improvements that can be made. The usability evaluation of our model shows that users were majorly happy with its functionality and aesthetic appearance of the interface. Suggestions on navigating back to a page were noted and these changes are made to the model so that it complies with them. A final study includes an experiment to test the effect of polarity of social interaction history on users reading blogs. Previous studies report that the number of comments on a blog article play a role in attracting readers- users’ interest in an article increases with the number of comments . The type of comments that contribute to the total number is not considered. It is hypothesized that the type of comments (polarity) on a blog post effect the user’s interest in a blog. In the main experiment, the participants were asked to read a set of posts belonging to four different categories in two conditionspresence and absence of polarity of comments. They were also asked to rate the posts on a scale of 5 given the polarity distribution of comments. This data from the experiment was statistically analyzed using one-way ANOVA and paired values t-test measures respectively. The varied results show that the polarity of comments affects readers interest for blogs categorized as ‘technology’ and did not play much role for the other two categories (‘neuroscience’,‘polarity’ and ‘war’). Further, for the posts belonging to ‘technology’ category ,it was also noticed that posts with major negative comments were liked by more readers than posts with major positive comments. Thus,to conclude, polarity of comments was found to effect reader’s interest in blog articles based on the type of posts. One immediate extension to this study is to conduct it on a variety of participants to see if the results are governed by the readers’ background/knowledge.

Abstract

The problem of regression is to estimate the value of a dependent numeric variable based on the values of one or more independent numeric variables. Regression algorithms can be used for prediction (including forecasting of time-series data), inference, hypothesis testing, and modeling of causal relationships. Regression analysis includes any techniques for modelling and analyzing several variables, when the focus is on the relationship between a dependent variable and one or more independent variables. The problem of regression has been extensively in statistics but it has not received much attention from the data mining community. Statistical approaches are not generic in that they require the user to make an intelligent guess about the form of the regression equation. The current set of regression algorithms don’t provide support for incorporating knowledge provided by domain experts. This leads to loss of knowledge that could have been utilized for building an efficient and accurate model. Additionally, these algorithms come up with models which are inefficient and require lot of computation power. There are two major contributions of this thesis. First, we develop a new regression algorithm PAGER: which is based on nearest neighbour paradigm. Our experimental study compares PAGER with fourteen other algorithms on three standard synthetic and five standard real-life datasets, and shows that PAGER is more accurate than all its competitors. Second, we develop an interactive regression framework – GIRAF (Generic, Interactive, Regression Analysis Framework). GIRAF alleviates the task of manually labelling records by selecting a subset of high quality records which now need to be labeled by domain experts for a model with relatively high accuracy. Our experimental results show that a regression model with a comparable accuracy can be constructed in the GIRAF framework using comparatively smaller amounts of training data and thus reducing the effort of domain expert as less data has to be labelled for comparable performance.

Abstract

Active learning is a rapidly growing field of machine learning which aims at reducing the labeling effort of the oracle (human expert) in acquiring informative training samples in domains where the cost of labeling is high. The major difference between this and traditional passive learners lies in the fact that passive classifiers do not query to seek training examples to learn from. However, this non trivial active learning methodology is distinctly preferred in certain domains and applications. Such applications include where either the amount of unlabelled data is voluminous or the cost of labeling is high. Few examples of such applications include video annotation, speech recognition and information extraction. The main actors in active learning are the oracle, sampling framework being used and assessment metrics. The current literature boasts of many innovative and different settings for active learning but most of these are highly statistical based approaches. In this thesis, we devise new active learning strategies which rely on heuristic and pattern mining strategies heavily. The crux of our work revolves on efficiently embedding such emerging data mining models in active learning. The two algorithms which we propose in this context are the Ensemble based active learner and Associative active learner. We present variants of each of these algorithms which can also be applied for real time application purposes with a manual oracle. In addition, we also propose a novel dynamic rule based sampling framework which is used by our Associative active learner.

Abstract

As VLSI circuits move into the era of deep sub-micron (DSM) technologies and gigahertz frequencies, the system performance is increasingly becoming dominated by the interconnect delay. While several delay models exist in literature, they are, by and large, applicable to technologies at and above 130nm. Thus there is a need to evolve techniques that can estimate the interconnect delay with a reasonable accuracy in DSM technologies such as 90nm. The objectives of this thesis are three fold. (i) To develop a novel model order reduction (MOR) to reduce the complexity of large integrated circuits and therefore simplify the estimation of signal delay in interconnects and (ii) To develop novel analytical and statistical techniques for delay modeling of inductance-dominated (RLC) interconnects. The first contribution of the thesis is the development of a novel MOR technique to reduce the complexity of large integrated circuits. The purpose of any MOR technique is to replace a model by its approximation, which, while simplifying the analysis, also preserves essential properties like stability and passivity of the original model within a certain accuracy. The MOR technique proposed in this thesis satisfies these conditions and an analysis of the technique indicates that it performs better than any of the existing techniques. Once the reduced model of large circuit is derived, then analytical or statistical techniques can be applied to estimate the signal delay in interconnect. The second contribution of the thesis is the development of an Erlang distribution-based statistical technique to estimate the delay in inductance-dominated interconnects. It is shown that this technique performs better than other similar techniques for estimation of delay. The third and final contribution of the thesis is the development of a novel analytical delay model based on difference model approach. The model has been applied to an interconnect tree with various combinations of source and load parameters under step input excitation. It is found that the delay estimates obtained using the proposed analytical model are within 2% of SPICE-computed delays. The techniques proposed in this thesis are expected to be useful for efficient interconnect delay analysis.

Abstract

Pipelines are common transportation means for oil and natural gas, which always act as an important lifeline facility for any nation. Generally, these pipelines laid underground for safety and economical reasons. While running through the length and breadth of country pipeline expose to diverse soil conditions. Presently India operates and maintains about 25,000km of gas and other petroleum product pipelines, which are expected to be the double in coming years. Because of major port Kandla and other international ports with refineries at Koyali near Baroda and Jamnagar, western state of India, Gujarat have many major pipeline network which run towards other part of the country and boost up after dreamed Iran Pakistan India pipeline. On the other hand, same region is one of the most seismically active regions (equally like plate boundary region) of the stable continental part of the Indian tectonic plate that has many active faults. Many major pipelines of this region are in vicinity of such active faults e.g. Mundra-Panipat pipeline is in vicinity of the Kachhach Mainland fault. Majority of the sub-ducting Indian tectonic plant’s faults are of thrust in nature hence the pipelines crossing such fault are subjected to compression. Contradictory to this previous work for pipeline fault crossing is done for tension case mainly. Vulnerability of the pipeline due to seismic hazards can be divided in to three categories i.e. hazard due to ground vibration, hazard due to faulting and hazard due to permanent ground deformation (PGD). Though there are no severe damage were observed due ground vibration in the modern buried pipeline. In view of the fact that Indian pipeline network has been developed in recent years and there is no synthetic data of pipeline damage, which is recorded for earlier earthquakes, these notify performance of Indian pipeline as well. Though there are many events of pipeline failure all over the world during past seismic events. In 1971 San Fernando earthquake, over 80-transmission line failures occurred due to shaking and approximately 10 failures occur due to PGD. In 1989, Loma Prieta earthquake has resulted in a program of extensive cast iron pipe replacement using Polyethylene. In1994, Northridge earthquake has lead to 209 repairs to metallic distribution lines and 27 to polyethylene lines. During 1999, Chi-Chi (Taiwan) earthquake 2000mm diameter pipe destroyed by rupture at Chelungpu fault. During 1999, Izmit, Turkey earthquake pipe buckled which was crossing the Anatolian strike slip fault. There are many more acknowledged instances of pipeline damages during an earthquake which includes 1906 San Francisco to recent 2010 Haiti earthquakes. Predominant study for seismic hazard of pipeline started after the 1971 San Fernando earthquake. Newmarks and Hall did the pioneer work for pipeline crossing the fault by assuming pipe as cable model in analytical study to determine the axial strain in the pipe crossing strike slip fault. Numbers of modification were further suggested by many authors in past like Kennedy, Wang and Yeh and recently by Karamitros. However, these models gives satisfactory results for the pipeline crossing strike slip fault under tension but cannot incorporates the large geometric changes. With continuous advancement in computation power and the numerical method recently many researchers are using numerical method to simulate phenomena, which can easily takes care the nonlinear material behaviour. Recently, Takada (1998), LIU (2004) et al are used spring-shell element model to simulate the pipeline fault crossing. However, these models are fine to pipeline but too harsh to the soil behaviour, nevertheless the behaviour of soil has significant impact on the pipeline response. Many analytical models were developed for transverse PGD were pipeline modelled with the assumption of small deformation. For the case of transverse PGD pipeline mainly subjected to the bending. While in case of longitudinal PGD pipeline, expose to the longitudinal tension and compression strains, which is less studied in past. Pipeline subjecting to the large ground deformation itself is a problem of large geometric changes. Especially in case of the pipeline under compression cause to undergo the geometric failure in addition to material failure. Generally, Newton-Raphson technique of nonlinear numerical analysis diverges at snap back and snaps through point. Analysis can be extended by using advance nonlinear techniques like Arc-length method; the same is implemented here for analysis. In this study, more significance is given to the understanding pipeline performance in terms of geometric changes with material nonlinearity. Hence, to reduce the computation efforts and complexity in the analysis it is assumed that bond between the pipe and soil is perfect, which can be added in future study. In this work, a numerical study is carr

Abstract

Security experts often say, users are the weakest link in a security system. Users misunderstand how to use security mechanisms and do not realize the protection and are happy to circumvent the security measures, if security measures try to impede their primary tasks. Attackers on the other hand are experts in usability: they exploit user’s lack of understanding and their tendencies not to comply with security protocols and policies by developing simple yet effective social engineering attacks. Below we explain two main important problems the users are facing in the social networking sites. The first one is identifying between strangers and friends and the second one is adding the people who are interested in the community. Current social networking sites protect user data by making it available only to the restricted set of people often friends. However, the concept of ‘friend’ in social networks is illusory. Adding a person to the friends list without verifying her identity can lead to many serious consequences like identity theft, privacy loss, etc. We propose a novel verification paradigm to ensure that the person who sends you a friend request is actually your friend and not someone who is faking her identity. Our solution is based on what a person might know and can verify about the other person. We work on a premise that a friend can say about her friend’s preferences better than the stranger. The preferences include the interests of a particular person and the big five personality traits 1 . To verify our premise, we did a two stage user study. Results of the user study are quite encouraging. The lifeline of a social networking site is its community relationship model. A community is a group of people having similar tastes, interests and lifestyle. Communities can take the form of an online forum, discussion group where the active participation of a user is required. As of now there is no provision in the social networking sites to measure the interest of the members of a particular community. Inclusion of uninterested users into the community will negatively impact the quality of the community and its activities. Often it so happens that attackers disguised as normal users try to join all the communities even if they are not interested in them. These users

Abstract

Two classes of networks that have been extensively studied in the dynamical analysis of spatially extended systems are: (i) regular networks, wherein each node interacts with a specified number of neighbouring nodes on geometrical lattices, and (ii) random networks, wherein each pair of nodes has a fixed probability of interacting with each other. Recently much attention is being focused on a class of network models that are neither strictly regular nor completely random, but are somewhere in between and exhibit properties of both. Such networks are called small-world networks. Examples for small-world networks are found to occur widely across biological (e.g., neural connection patterns), social (e.g., friendship network, co-authorship) and technological (e.g., the World Wide Web) domains. It has also been observed that a large number of real complex systems such as protein contact networks, protein-protein interaction networks, metabolic networks, exhibit power-law behaviour in their degree distribution, i.e., a few nodes have a very high degree. Such networks are referred to as scale-free networks. To model real physical and biological systems governed by dynamical processes, on such networks the nodes are defined by dynamical systems and the connection between them may be fixed or changing in response to the local dynamics of the nodes, e.g., neuronal excitations. Such networks are called ‗Dynamical Networks‘. Thus, from the point of view of dynamical systems, we have a coupled system of dynamical equations, and we are interested in controlling or manipulating the resulting global dynamics of the system emerging from the interactions between the local dynamics of the individual elements. We propose to use concepts from Graph theory to analyze the coupling structure and its influence in attaining global control of the resulting dynamics in the event of the system exhibiting complex chaotic or excitable dynamics. In an earlier study by Parekh et al, robust control (both global and local) of spatiotemporal dynamics on coupled map lattice (CML) models by applying a constant external perturbation or “pinning‖ has been shown. The advantage of this control approach is that neither any a priori knowledge of the system dynamics, such as stable or unstable fixed points and periodic orbits nor any modification/tracking of the system parameters/variables explicitly is required to suppress chaos. In this study we use the same control approach and analyse the role of connection topologies in achieving global control of the dynamics on small-world and scale-free networks. The analyses have been carried out for dynamics on the nodes governed by (a) logistic map (a one-dimensional nonlinear map exhibiting a wide variety of dynamical behaviour including chaos), and (b) neuron map (a two-dimensional nonlinear map modelling an excitable system, e.g., neuron). The two dynamical systems have been modelled on four different network topologies, viz., regular, random, small-world and scale-free. Since it is practically infeasible to pin all the nodes of the network, here we exploit the geometrical/topological properties of networks to choose nodes for exerting control. We observe that in the case of small-world networks, wherein the connection topology is predominantly local, with a few long range interactions, regularly-spaced controllers provide better control for low pinning densities ~ 20% compared to hubs and other centrality measures which require pinning ~ 50% nodes at similar pinning strengths. The long-range connections only seem to have the effect of spatial noise on small-world network. However, in case of controlling dynamics on the scale-free network, centrality nodes do provide significant advantage in achieving global control. We observe that high-betweenness and high-closeness nodes at very low pinning densities ~ 10 – 15% suffice in suppressing spatiotemporal chaos.