Wednesday, November 28, 2012

This is a technique known as 'shadowing' that I learnt in Japanese class, which I find tremendously helpful for short-term oral fluency improvement.

Watch your favorite English language TV show or movie, and as the characters speak, repeat loudly the exact words they are saying the moment you hear them. In other words, 'shadow' their dialog in real-time. Don't worry about getting every word or sound right - focus on listening carefully, moving along quickly and keeping pace. After the movie ends, repeat the exact same movie and do it again. And again. 

By forcing yourself to speak at native speed, your brain becomes hyper-receptive to what you are hearing, and you will find yourself not only picking up the words quicker and quicker, but also unconsciously mimicking the inflections and vocal nuances that are usually difficult to learn for a non-native. It will also fix the stammer that comes with uncertainty or lack of confidence. In this way, the actors in the movie become your speaking partners.

This will be perfect practice just before your interview. Look for some interview practice videos on YouTube, then shadow the entire conversation. Practice the same dialogs again and again. You will be amazed how that will improve not only your speaking, but also your ability to actively listen and react. Best of luck.

Saturday, November 24, 2012



The Disciplines of Artificial Intelligence

The subject of artificial intelligence spans a wide horizon. It deals with the various kinds of knowledge representation schemes, different techniques of intelligent search, various methods for resolving uncertainty of data and knowledge, different schemes for automated machine learning and many others. Among the application areas of AI, we have Expert systems, Game-playing, and Theorem-proving, Natural language processing, Image recognition, Robotics and many others. The subject of artificial intelligence has been enriched with a wide discipline of knowledge from Philosophy, Psychology, Cognitive Science, Computer Science, Mathematics and Engineering. Thus in fig. , they have been referred to as the parent disciplines of AI. An at-a-glance look at fig. also reveals the subject area of AI and its application areas.

Fig.: AI, its parent disciplines and application areas.

The Subject of Artificial Intelligence

The subject of artificial intelligence was originated with game-playing and theorem-proving programs and was gradually enriched with theories from a number of parent disciplines. As a young discipline of science, the significance of the topics covered under the subject changes considerably with time. At present, the topics which we find significant and worthwhile to understand the subject are outlined below:

FigA: Pronunciation learning of a child from his mother.
Learning Systems: Among the subject areas covered under artificial intelligence, learning systems needs special mention. The concept of learning is illustrated here with reference to a natural problem of learning of pronunciation by a child from his mother (vide figA). The hearing system of the child receives the pronunciation of the character "A" and the voice system attempts to imitate it. The difference of the mother's and the child's pronunciation, hereafter called the error signal, is received by the child's learning system auditory nerve, and an actuation signal is generated by the learning system through a motor nerve for adjustment of the pronunciation of the child. The adaptation of the child's voice system is continued until the amplitude of the error signal is insignificantly low. Each time the voice system passes through an adaptation cycle, the resulting tongue position of the child for speaking "A" is saved by the learning process. The learning problem discussed above is an example of the well-known parametric learning, where the adaptive learning process adjusts the parameters of the child's voice system autonomously to keep its response close enough to the "sample training pattern". The artificial neural networks, which represent the electrical analogue of the biological nervous systems, are gaining importance for their increasing applications in supervised (parametric) learning problems. Besides this type, the other common learning methods, which we do unknowingly, are inductive and analogy-based learning. In inductive learning, the learner makes generalizations from examples. For instance, noting that "cuckoo flies", "parrot flies" and "sparrow flies", the learner generalizes that "birds fly". On the other hand, in analogy-based learning, the learner, for example, learns the motion of electrons in an atom analogously from his knowledge of planetary motion in solar systems.
Knowledge Representation and Reasoning: In a reasoning problem, one has to reach a pre-defined goal state from one or more given initial states. So, the lesser the number of transitions for reaching the goal state, the higher the efficiency of the reasoning system. Increasing the efficiency of a reasoning system thus requires minimization of intermediate states, which indirectly calls for an organized and complete knowledge base. A complete and organized storehouse of knowledge needs minimum search to identify the appropriate knowledge at a given problem state and thus yields the right next state on the leading edge of the problem-solving process. Organization of knowledge, therefore, is of paramount importance in knowledge engineering. A variety of knowledge representation techniques are in use in Artificial Intelligence. Production rules, semantic nets, frames, filler and slots, and predicate logic are only a few to mention. The selection of a particular type of representational scheme of knowledge depends both on the nature of applications and the choice of users.
Planning: Another significant area of artificial intelligence is planning. The problems of reasoning and planning share many common issues, but have a basic difference that originates from their definitions. The reasoning problem is mainly concerned with the testing of the satisfiability of a goal from a given set of data and knowledge. The planning problem, on the other hand, deals with the determination of the methodology by which a successful goal can be achieved from the known initial states. Automated planning finds extensive applications in robotics and navigational problems, some of which will be discussed shortly.
Knowledge Acquisition: Acquisition (Elicitation) of knowledge is equally hard for machines as it is for human beings. It includes generation of new pieces of knowledge from given knowledge base, setting dynamic data structures for existing knowledge, learning knowledge from the environment and refinement of knowledge. Automated acquisition of knowledge by machine learning approach is an active area of current research in Artificial Intelligence. Intelligent Search: Search problems, which we generally encounter in Computer Science, are of a deterministic nature, i.e., the order of visiting the elements of the search space is known. For example, in depth first and breadth first search algorithms, one knows the sequence of visiting the nodes in a tree. However, search problems, which we will come across in AI, are non-deterministic and the order of visiting the elements in the search space is completely dependent on data sets. The diversity of the intelligent search algorithms will be discussed in detail later.
Logic Programming: For more than a century, mathematicians and logicians were used to designing various tools to represent logical statements by symbolic operators. One outgrowth of such attempts is propositional logic, which deals with a set of binary statements (propositions) connected by Boolean operators. The logic of propositions, which was gradually enriched to handle more complex situations of the real world, is called predicate logic. One classical variety of predicate logic-based programs is Logic Program. PROLOG, which is an abbreviation for PROgramming in LOGic, is a typical language that supports logic programs. Logic Programming has recently been identified as one of the prime area of research in AI. The ultimate aim of this research is to extend the PROLOG compiler to handle spatio-temporal models and support a parallel programming environment. Building architecture for PROLOG machines was a hot topic of the last decade.
Soft Computing: Soft computing, according to Prof. Zadeh, is "an emerging approach to computing, which parallels the remarkable ability of the human mind to reason and learn in an environment of uncertainty and imprecision" . It, in general, is a collection of computing tools and techniques, shared by closely related disciplines that include fuzzy logic, artificial neural nets, genetic algorithms, belief calculus, and some aspects of machine learning like inductive logic programming. These tools are used independently as well as jointly depending on the type of the domain of applications.
Management of Imprecision and Uncertainty: Data and knowledgebases in many typical AI problems, such as reasoning and planning, are often contaminated with various forms of incompleteness. The incompleteness of data, hereafter called imprecision, generally appears in the database for i) lack of appropriate data, and ii) poor authenticity level of the sources. The incompleteness of knowledge, often referred to as uncertainty, originates in the knowledge base due to lack of certainty of the pieces of knowledge Reasoning in the presence of imprecision of data and uncertainty of knowledge is a complex problem. Various tools and techniques have been devised for reasoning under incomplete data and knowledge. Some of these techniques employ i) stochastic ii) fuzzy and iii) belief network models. In a stochastic reasoning model, the system can have transition from one given state to a number of states, such that the sum of the probability of transition to the next states from the given state is strictly unity. In a fuzzy reasoning system, on the other hand, the sum of the membership value of transition from the given state to the next state may be greater than or equal to one. The belief network model updates the stochastic / fuzzy belief assigned to the facts embedded in the network until a condition of equilibrium is reached, following which there would be no more change in beliefs. Recently, fuzzy tools and techniques have been applied in a specialized belief network, called a fuzzy Petri net, for handling both imprecision of data and uncertainty of knowledge by a unified approach.

General Problem Solving Approaches in AI

To understand what exactly artificial intelligence is, we illustrate some common problems. Problems dealt with in artificial intelligence generally use a common term called 'state'. A state represents a status of the solution at a given step of the problem solving procedure. The solution of a problem, thus, is a collection of the problem states. The problem solving procedure applies an operator to a state to get the next state. Then it applies another operator to the resulting state to derive a new state. The process of applying an operator to a state and its subsequent transition to the next state, thus, is continued until the goal (desired) state is derived. Such a method of solving a problem is generally referred to as state space approach. We will first discuss the state-space approach for problem solving by a well-known problem, which most of us perhaps have solved in our childhood.
Example: Consider a 4-puzzle problem, where in a 4-cell board there are 3 cells filled with digits and 1 blank cell. The initial state of the game represents a particular orientation of the digits in the cells and the final state to be achieved is another orientation supplied to the game player. The problem of the game is to reach from the given initial state to the goal (final) state, if possible, with a minimum of moves. Let the initial and the final state be as shown in figures 1(a) and (b) respectively.

Fig.: The initial and the final states of the Number Puzzle game, where B denotes the blank space.
We now define two operations, blank-up (BU) / blank-down (BD) and blank-left (BL) / blank-right (BR), and the state-space (tree) for the problem is presented below using these operators. The algorithm for the above kind of problems is straightforward. It consists of three steps, described by steps 1, 2(a) and 2(b) below.
Algorithm for solving state-space problems
Begin
1.     state: = initial-state; existing-state:=state;
2.     While state ≠ final state do
Begin
o        a. Apply operations from the set {BL, BR, BU, BD} to each state so as to generate new-states;
o        b. If new-states ∩ the existing-states ≠ φ
Then do
  • Begin state := new-states - existing-states;
    • Existing-states := existing-states - {states}
    • End;
  • End while;
End.

Fig.: The state-space for the Four-Puzzle problem.
It is thus clear that the main trick in solving problems by the state-space approach is to determine the set of operators and to use it at appropriate states of the problem.
Researchers in artificial intelligence have segregated the AI problems from the non-AI problems. Generally, problems, for which straightforward mathematical / logical algorithms are not readily available and which can be solved by intuitive approach only, are called AI problems. The 4-puzzle problem, for instance, is an ideal AI Problem. There is no formal algorithm for its realization, i.e., given a starting and a goal state, one cannot say prior to execution of the tasks the sequence of steps required to get the goal from the starting state. Such problems are called the ideal AI problems. The wellknown water-jug problem, the Travelling Salesperson Problem (TSP) , and the n-Queen problem are typical examples of the classical AI problems. Among the non-classical AI problems, the diagnosis problems and the pattern classification problem need special mention. For solving an AI problem, one may employ both artificial intelligence and non-AI algorithms. An obvious question is: what is an AI algorithm? Formally speaking, an artificial intelligence algorithm generally means a non-conventional intuitive approach for problem solving. The key to artificial intelligence approach is intelligent search and matching. In an intelligent search problem / sub-problem, given a goal (or starting) state, one has to reach that state from one or more known starting (or goal) states.
For example, consider the 4-puzzle problem, where the goal state is known and one has to identify the moves for reaching the goal from a pre-defined starting state. Now, the less number of states one generates for reaching the goal, the better is the AI algorithm.
The question that then naturally arises is: how to control the generation of states. This, in fact, can be achieved by suitably designing some control strategies, which would filter a few states only from a large number of legal states that could be generated from a given starting / intermediate state. As an example, consider the problem of proving a trigonometric identity that children are used to doing during their schooldays. What would they do at the beginning? They would start with one side of the identity, and attempt to apply a number of formulae there to find the possible resulting derivations. But they won't really apply all the formulae there. Rather, they identify the right candidate formula that fits there best, such that the other side of the identity seems to be closer in some sense (outlook). Ultimately, when the decision regarding the selection of the formula is over, they apply it to one side (say the L.H.S) of the identity and derive the new state. Thus they continue the process and go on generating new intermediate states until the R.H.S (goal) is reached. But do they always select the right candidate formula at a given state? From our experience, we know the answer is "not always". But what would we do if we find that after generation of a few states, the resulting expression seems to be far away from the R.H.S of the identity. Perhaps we would prefer to move to some old state, which is more promising, i.e., closer to the R.H.S of the identity. The above line of thinking has been realized in many intelligent search problems of AI. Some of these well-known search algorithms are:
  • Generate and Test
  • Hill Climbing
  • Heuristic Search
  • Means and Ends analysis
a) Generate and Test Approach: This approach concerns the generation of the state-space from a known starting state (root) of the problem and continues expanding the reasoning space until the goal node or the terminal state is reached. In fact after generation of each and every state, the generated node is compared with the known goal state. When the goal is found, the algorithm terminates. In case there exist multiple paths leading to the goal, then the path having the smallest distance from the root is preferred. The basic strategy used in this search is only generation of states and their testing for goals but it does not allow filtering of states.
(b) Hill Climbing Approach: Under this approach, one has to first generate a starting state and measure the total cost for reaching the goal from the given starting state. Let this cost be f. While f = a predefined utility value and the goal is not reached, new nodes are generated as children of the current node. However, in case all the neighborhood nodes (states) yield an identical value of f and the goal is not included in the set of these nodes, the search algorithm is trapped at a hillock or local extrema. One way to overcome this problem is to select randomly a new starting state and then continue the above search process. While proving trigonometric identities, we often use Hill Climbing, perhaps unknowingly.
(c) Heuristic Search: Classically heuristics means rule of thumb. In heuristic search, we generally use one or more heuristic functions to determine the better candidate states among a set of legal states that could be generated from a known state. The heuristic function, in other words, measures the fitness of the candidate states. The better the selection of the states, the fewer will be the number of intermediate states for reaching the goal. However, the most difficult task in heuristic search problems is the selection of the heuristic functions. One has to select them intuitively, so that in most cases hopefully it would be able to prune the search space correctly. We will discuss many of these issues in a separate chapter on Intelligent Search.
(d) Means and Ends Analysis: This method of search attempts to reduce the gap between the current state and the goal state. One simple way to explore this method is to measure the distance between the current state and the goal, and then apply an operator to the current state, so that the distance between the resulting state and the goal is reduced. In many mathematical theorem- proving processes, we use Means and Ends Analysis.

Friday, November 23, 2012


Intel  8086 Microprocessor  Architecture
Introduction
The 8086 was the first 16-bit Microprocessor to be introduced by Intel Corporation. The word 16-bit means that its arithmetic logical unit, internal registers, and most of its instructions are designed to work with 16-bit binary words. The 8086 has a 16-bit data bus, so it can read data form or write data to memory and ports either 16-bits or 8- bits at a time. The 8086 has a 20-bit address bus, so it can address any one of 220 or 1,048,576 memory locations. Each of the 1,048,576 memory addresses of the 8086 represents a byte-wide location. Words will be stored in two consecutive memory locations. If the first byte of a word is at an even address, the 8086 can read the entire word in one operation. If the first byte of the word is at an odd address, the 8086 will read the first byte of the word in one operation, and the second byte in another operation.

Features:
·              Released by Intel in 1978
·              Produced from 1978 to 1990s
·              A 16-bit microprocessor chip.
·              Max. CPU clock rate:5 MHz to 10 MHz
·              Instruction set:  x86-16
·              Package: 40 pin DIP
·              16-bit Arithmetic Logic Unit
·              16-bit data bus  (8088 has 8-bit data bus)
·              20-bit address bus - 220 = 1,048,576 = 1 meg
·              The address refers to a byte in memory.
·               In the 8088, these bytes come in on the 8-bit data bus.  In the 8086, bytes at even addresses come in on the low half of the data bus (bits 0-7) and bytes at odd addresses come in on the upper  half of the data bus (bits 8-15).
·              The 8086 can read a 16-bit word at an even address in one operation and at an odd address in two operations.  The 8088 needs two operations in either case.
·              The least significant byte of a word on an 8086 family microprocessor is at the  lower address.
The 8086 microprocessor architecture is internally divided into two separate functional units.
·        Bus Interface Unit (BIU)
·        Execution Unit (EU).
(REFER DIAGRAM 1-Figure shows a block diagram of the 8086 internal architecture.)
The BIU fetches instructions, reads data from memory and ports, and writes data to memory and I/O ports. The EU executes instructions that have already been fetched by the BIU. The BIU and EU function independently. The BIU interfaces the 8086 to the outside world. The BIU provides all external bus operations. The BIU contains segment registers, instruction pointer, instruction queue, and address generation bus control circuitry to provide functions such as fetching and queuing of instructions, and bus control.
The BIU’s instruction queue is a First-In First-out (FIFO) group of registers in which up to six bytes of instruction code are perfected from memory ahead of time. This is done in order to speed up program execution by overlapping instruction fetch with execution. This mechanism is known as pipelining. If the queue is full and the EU does not request BIU to access memory, the BIU does not perform any bus cycle. On the other hand, if the BIU’s is not full and if it can store at least two bytes and the EU does not request it to access memory, the BIU may prefect instructions. However, if BIU is interrupted by EU for memory access while the BIU is in the process of fetching an instruction, the BIU first completes fetching and then services the EU : the queue allows the BIU to keep the EU supplied with perfected instructions without typing up the system bus. If an instruction such as Jump or subroutine call is encountered, the BIU will reset the queue and begin refilling after passing the new instruction to the EU.
            The BIU contains a dedicated adder, which is used to produce the 20-bit address. The bus control logic of the BIU generates all the bus control signals such as read and write signals for memory and I/O.
            The BIU has four 16-bit segment registers. These are the Code Segment (CS) register, the Data Segment (DS) register, the Stack Segment (SS) register, and the Extra Segment (ES) register. The 8086’s one-megabyte memory is divided into segments of up to 64K bytes each. The 8086 can directly address four segments (256K byte within the 1 Mbytes memory) at a particular time. Programs obtain access to code and data in the segments by changing the segment register contents to point to the desired segments. All program instructions must be located in main memory pointed to by the 16-bit CS register with a 16-bit offset in the segment contained in the 16-bit instruction pointer (IP). The BIU computes the 20-bit physical address internally using the programmer-provided logical address (16-bit contents of CS and IP) by logically shifting the contents of CS four bits to left and then adding the 16-bit contents of IP. In other words, the CS is multiplied by 1610 by the BIU for computing the 20-bit physical address. This means that all instructions of a program are relative to the contents of the CS register multiplied by 16 and then offset is added provided by the 16-bit contents of IP. For example, if [CS] = 456A16 and [IP] = 162016, then the 10-bit physical address is generated by the BIU as follows:
                                                                                                    
            Four times logically shifted [CS] to left  =  456A016
            + [IP] as offset                                                  =  162016
            20-bit physical address                     =  46CC016
            The BIU always inserts four Zeros for the lowest 4-bits of the 20-bit starting address (physical) of a segment. In the other words, the CS contains the base or start of the current code segment, and IP contains the distance or offset from this address to the next instruction byte to be fetched. Note that immediate data are considered as part of the code segment.
            The SS register points to the current stack. The 20-bit physical stack address is calculated from SS and SP for stack instruction such as PUSH and POP. The programmer
Can use the BP register instead of SP for accessing the stack using the based addressing mode. In this case, the 20-bit physical stack address is calculated from BP and SS.
            The DS register points to the current data segment; operands for most instructions are fetched from this segment. The 16-bit contents of Source Index (SI) or Destination Index (DI) are used as offset for computing the 20-bit physical address.
            The ES register points to the extra segment in which data (in excess of 64k pointed to by DS) is stored. String instructions always use ES and DI to determine the 20-bit physical address for the destination.
            The segment can be continuous, partially overlapped, fully overlapped, or disjoint. An example of how five (segment 1 through segment 5) may be stored in physical memory are shown.
a)Segments are contiguous (adjacent)

 

SEGMENTS 1 an d 2 are partially overlapped, SEGMENTS 2 and 3 are fully overlapped, and SEGMENTS 2 and 4 are disjoint.. Every segment must start on 16-byte memory boundaries.
            Typical examples of values of segments should then be selected based on physical addresses starting at 0000016 , 0001016 , 0002016 , 0003016,  … FFFF016  . A physical memory location may be mapped into (contained in) one or more logical segments. Many applications can be written to simply initialize the segment and then forget them.
           
The 8086 uses segmented memory. A memory address on the 8086 consists of two numbers, usually written in hexadecimal and separated by a colon, representing the segment and the offset. This combination of segment and offset is referred to as a logical address. The segment number refers to a 64 KB block of memory and the offset is an index into the memory segment.

When the processor obtains a logical address (segment and offset), it performs a simple calculation to determine the 20-bit physical address in memory to which the logical address refers:
 physical address = (segment << 4) + offset
This is equivalent to multiplying the segment by 16 and adding the offset (i.e., physical address = segment * 16 + offset). This means that the 64 KB segments overlap, with a new segment starting every 16 bytes. This also means that there can be more than one address for the same memory location. For example, 0000:0100, 0001:00F0, and 0010:0000 all refer to physical address 0x100


The EU decodes and executes instructions. A decoder in the EU control system translates instructions. The EU has a 16-bit ALU for performing arithmetic and logic operations.
            The EU has eight 16-bit general registers. These are AX, BX, CX, DX, SP, BP, SI, and DI. The 16-bit registers AX, BX, CS, and DX can be used as two 8-bit registers (AH, AL, BH, BL, CH, CL, DH, DL). For example, the 16-bit register DX can be considered as two 8-bit registers DH (high byte of DX) and DL (low byte of DX). The general-purpose registers AX, BX, CX, and DX are named after special functions carried out by each one of them. For example, the AX is called the 16-bit accumulator while the AL is the 8-bit accumulator. The use of accumulator registers is assumed by some instructions. The Input/Output (IN or OUT) instructions always use AX or AL for inputting/outputting 16- or 8-bit data to or from and I/O port.
            Multiplication and division instructions also use AX or AL. The AL register is the same as the 8085 A register.
BX  register is called the base register. This is the only general-purpose register, the contents of which can be used for addressing 8086 memory. All memory references utilizing these register contents for addressing use Ds as the default segment register. The BX register is similar to 8085 HL register. In other words, 8086 BH and BL are equivalent to 8085 H and L registers, respectively.
The CX register is known as the counter register. This is because some instructions such as shift rotate, and loop instructions use the contents of CX as a counter. For example, the instruction LOOP START will automatically decrement CX by 1 without affecting flags and will check if [CX]=0. If is zero, the 8086 executes the next instruction; otherwise the 8086 branches to the label START.
The data register DX is used to hold high 16-bit result (data) in 16* 16 multiplication or high 16-bit dividend (data) before a 32 ¸16 division and the 16-bit remainder after the division.
The two pointer registers, SP (stack pointer) and BP (base pointer), are used to access data in stack segment. The SP is used as an offset from the current SS during execution of instructions that involve stack segment in external memory. The SP contents are automatically updated (incremented or decremented) due to execution of POP or PUSH instruction.
The base pointer contains an offset address in the current SS. This offset is used by the instructions utilizing the based addressing mode.
The FLAG register in the EU holds the status flags typically after an ALU operation.
The 8086 have six one-bit flags. AF (Auxiliary carry flag) is used by BCD bit) into the high nibble or a borrow from the high nibble into the low nibble of the low-order 8-bit of a 16-bit number. CF (Carry Flag) is set if there is a carry from addition or borrow from subtraction. OF (Overflow Flag) is set if there is an arithmetic overflow, that is, if the size of the result exceeds the capacity of the destination location. An interrupt on overflow instructions is available which will generate an interrupt in this situation. SF (Sign Flag) is set if the most significant bit of the result is one (Negative) and is cleared to zero for non-negative result. PF (Parity Flag) is set if the result has even parity; PF is zero for odd parity of the result. ZF (Zero Flag) is set if the result is zero; ZF is zero for non-zero result.
The 8086 has three control bits in the flag register which can be set or reset by the programmer: setting DF (Direction Flag) to one causes string instructions to auto decrement and clearing DF to zero causes string instructions to auto increment. Setting IF (Interrupt Flag) to one causes the 8086 to recognize external mask able interrupts; clearing IF to zero disables these interrupts. Setting TF (Trace Flag) to one places the 8086 in the single-step mode. In this mode, the 8086 generate an internal interrupt after execution of each instruction. The user can write a service routine at the interrupt address vector to display the desired registers and memory locations. The user can thus debug a program