Category Archives: Artificial Intelligence

Microscopic computing in cells and with self-assembling DNA tiles

Theory, Evolution, and Games Group

One of the three goals of natural algorithms is to implement computers in non-electronic media. In cases like quantum computing, the goal is to achieve a qualitatively different form of computing, but other times (as with most biological computing) the goal is just to recreate normal computation (or a subset of it) at a different scale or in more natural ways. Of course, these two approaches aren’t mutually exclusive! Imagine how great it would be if we could grow computers on the level of cells, or smaller. For starters, this approach could revolutionize health-care: you could program some of your own cells to sense and record your internal environment and release drugs only when necessary. It could also alter how we manufacture things; if you throught 3D printers are cool, what if you could program nanoscale assemblies?

View original post 841 more words

Knapsack I/O Problem – CSCI 300 Artificial Intelligence

Artificial Brain now Learning from the Internet!

Fake Brain

Wow.

Amazing. This is the next step in artificial intelligence.

A.I. is now being programmed to learn certain aspects, and once these are learned, uses these aspects to learn and interact with the environment.

I find this to be very similar to how our own brain functions. From an Empirical standpoint, we learn certain things about the world through our environment as we grow up with repetition and logic.

This seems to be a very similar process for the A.I., but the A.I. has a greater advantage: It’s storage capabilities.

Our human brains have a limited capacity for memory… With the Internet, these new Artificially Intelligent designs could have a significant “one up”.

Awesome.

View original post

Computer Vision: UAVs and Video Processing

lmahmed22

On Monday, April 29th DC ACM was privileged to host Dr. Larry Davis, Professor at the Institute for Advanced Computer Studies and the Department of Computer Science at the University of Maryland. His presentation, “Computer Vision: UAVs and Video Processing,” chronicled just how far the field has come since it began in the mid 20th century.

Dr. Davis shared that computer vision technology was initially motivated by the problems facing the postal service in sorting mail. Optical character recognition was developed for postal service applications to address problems of data segmentation, representation, character recognition, and matching. Through this technology postal services were able to automatically sort addresses and packages of all kinds. Computer vision technology enabled the recognition of cursive, characters, logos, stamps, text, and different forms of handwriting.

Successes in the field of computer vision were achieved in other industries as well. In medicine, the ability of retina scans…

View original post 612 more words

“The Three R’s of Computer Vision” by Dr. Jitendra Malik

What happens if you over-train a neural net?

S.U.R.F.

opencv4u

Speed Up Robust Feature extraction algorithm. For those who all are hearing this algorithm for the first time please visit wiki and understand a bit about it.

Now, from name you can guess its something about features. Here I am gonna tell you about its implementation.The following is the code in python using Opencv.

############################################################

import cv2

cap = cv2.VideoCapture(0)
ret,img = cap.read()
#im2 = cv2.imread(‘ex1.jpg’)
#im = cv2.cvtColor(im2,cv2.COLOR_BGR2GRAY)
while True:
ret,img = cap.read()
im= cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
surfDetector = cv2.FeatureDetector_create(“SURF”)
surf = cv2.DescriptorExtractor_create(“SURF”)
keypoints = surfDetector.detect(im)
(l,d)= surf.compute(im,keypoints)

for kp in l:
x = int(kp.pt[0])
y = int(kp.pt[1])
cv2.circle(im,(x,y),2,(0,0,255))

cv2.imshow(“features”,im)
cv2.waitKey(1)

#############################################################

View original post

Single-Source Shortest Path (Dijkstra’s Algorithm Implementation in C++)

Suppose you want to fly  a private plane on the shortest path from Saint Johns­ bury, VT to Waco, TX. Assume you know the distances between the airports for all pairs of  cities and towns that are reachable from each other in  one nonstop flight of  your plane. The best-known algorithm to solve this problem, Dijkstra’s Algorithm, finds the shortest path from Saint Johns­ bury to  all other airports, although the search may be halted once the shortest path  to Waco is known.

Dijkstra’s Algorithm conceptually operates in greedy fashion by expanding a set of  vertices, S, for  which the shortest path from s to every vertex VE S is known, but only using paths that include vertices in S. Initially, S  equals the set {s}. To expand S, Dijkstra’s Algorithm  finds the vertex VE V-S whose distance to s is  smallest, and follows v’s edges to see whether a shorter path exists to another  vertex. After processing v2 , for example, the algorithm determines that the distance from s to v3 is  really 17 through the path <s,v2 ,v 3>. Once S  expands to equal V, the algorithm completes.

Input/Output

Input

A  directed, weighted graph G=(V,E) and a source vertex sE V. Each edge e=(u,v) has an associated positive weight in the graph. The quantity n represents the number of  vertices in  G.

Output

Dijkstra’s Algorithm  produces two computed  arrays. The primary result is the array dist[] of  values representing the distance from source vertex s to each vertex in the graph. Note that d ist[ s] is zero. The secondary result is  the array p red [), which can be used to rediscover the actual shortest paths from vertex s to each vertex in the graph.

Assumptions

The edge weights are positive (i.e., greater than zero); if  this assumption is  not true, then dist[u]  may contain  invalid results. Even worse, Dijkstra’s Algorithm will loop forever if a cycle exists whose sum of  all weights is less than zero.

Solution

As  Dijkstra’s Algorithm executes, dis t[v]  represents the maximum length of the shortest path found from the source s to v using only vertices visited within the setS. Also, for  each vES, dist[v] is correct. Fortunately, Dijkstra’s Algorithm does not actually compute and store the setS. It  initially constructs a set  containing the vertices in V, and then it  removes vertices one at a time from the set to compute proper dis t[v] values; for  convenience, we continue to refer to this ever-shrinking set as V-S. Dijkstra’s Algorithm terminates when all vertices are either visited or are shown to not be reachable from the source vertex s.

In the C++ solution shown below, a binary heap stores the vertices in  the set V-S  as a priority queue because, in constant time, one can locate the vertex with smallest priority (where the priority is determined by the vertex’s distance from s). Additionally, when  a shorter  path  from s   to v is found, dist [ v ]   is decreased, requiring the heap to be modified. Fortunately, the decrease Key  opera­tion on  priority queues represented  using binary heaps can be performed  on average in O(log q)  time, where q is the number of verticesin the binary heap, which will always be less than or equal to the number of vertices, n.

//Dijkstra’s Algorithm with priority queue implementation

#include "BinaryHeap.h"
#include "Graph.h"

/** Given directed, weighted graph, compute shortest distance to vertices
* (dist) and record predecessor links (pred) for all vertices. */

void singleSourceShortest(Graph const &g, int s, vector &dist, vector &pred)
{
// initialize dist[] and pred[] arrays. Start with vertex s by setting
// dist[] to 0. Priority Queue PQ contains all v in G.

const int n = g.numVertices( );
pred.assign(n, -1);
dist.assign(n, numeric_limits<int>::max( ));
dist[s] = 0;
BinaryHeap pq(n);

for (int u = 0; u < n; u++)
{
pq.insert (u, dist[u]);
}
// find vertex in ever-shrinking set, V-S, whose dist[] is smallest.
// Recompute potential new paths to update all shortest paths

while (!pq.isEmpty( ))
{
int u = pq.smallest( );
// For neighbors of u, see if newLen (best path from s->u + weight
// of edge u->v) is better than best path from s->v. If so, update
// in dist[v] and re-adjust binary heap accordingly. Compute in
// long to avoid overflow error.

for (VertexList::const_iterator ci = g.begin(u); ci != g.end(u); ++ci)
{
int v = ci->first;
long newLen = dist[u];
newLen += ci->second;

if (newLen < dist[v])
{
pq.decreaseKey (v, newLen);
dist[v] = newLen;
pred[v] = u;
}
}
}
}

Consequences

Arithmetic error also may occur if  the sum of  the individual edge weights exceeds numeric_limits<i n t>: :max () (although the individual values do  not). To avoid this situation, the computed new len uses a long data type.

Analysis

In the implementation of  Dijkstra’s Algorithm, the loop that constructs  the  initial priority  queue  performs  the  insert  operation  V  times, resulting in performance  O(V log V). In   the remaining while loop, each edge is visited once, and thus decrease Key  is called no more than E  times, which contrib­utes O(E log V)  time. Thus, the overall performance is O(( V +E) log V).

The   C++ implementation below is simpler since it avoids the use of  a binary heap. Th e efficiency of   this version is determined by considering how fast the smallest dist [] value in V-S can be retrieved. The while loop is executed n times, since S grows on e vertex at a time. Finding the smallest dist [ u]  in V-S inspects all n vertices. Note that each edge is inspected exactly once in the inner loop within the while loop. Thus, the total running time of  this version is 0 (V 2+E).

//Implementation of Dijkstra’s Algorithm for dense graphs

#include "Graph.h"

void singleSourceShortest(Graph const &graph, int s, vector &dist, vector &pred)
{

// initialize dist[] and pred[] arrays. Start with vertex s by setting
// dist[] to 0.

const int n = graph.numVertices( );
pred.assign(n, -1);
dist.assign(n, numeric_limits<int>::max( ));
vector<bool> visited(n);
dist[s] = 0;

// find vertex in ever-shrinking set, V-S, whose dist value is smallest
// Recompute potential new paths to update all shortest paths

while (true)
{
// find shortest distance so far in unvisited vertices
int u = -1;
int sd = numeric_limits<int>::max( ); // assume not reachable

for (int i = 0; i < n; i++)
{
if (!visited[i] && dist[i] < sd)
{
sd = dist[i];
u = i;
}
}
if (u == -1)
{
break; // no more progress to be made
}

// For neighbors of u, see if length of best path from s->u + weight
// of edge u->v is better than best path from s->v.
visited[u] = true;

for (VertexList::const_iterator ci = graph.begin(u); ci != graph.end(u); ++ci)
{
int v = ci->first; // the neighbor v
long newLen = dist[u]; // compute as long
newLen += ci->second; // sum with (u,v) weight

if (newLen < dist[v])
{
dist[v] = newLen;
pred[v] = u;
}
}
}
}

We can further optimize to remove all  of  the C++ standard template library  objects,  as  shown  below.  By reducing the  overhead of   the supporting classes, we realize impressive performance benefits, as discussed in the “Comparison” section.

/**
* Optimized Dijkstra’s Algorithm for dense graphs
*
* Given int[][] of edge weights in raw form, compute shortest distance to
* all vertices in graph (dist) and record predecessor links for all
* vertices (pred) to be able to recreate these paths. An edge weight of
* INF means no edge. Suitable for Dense Graphs Only.
*/

void singleSourceShortestDense(int n, int ** const weight, int s,int *dist, int *pred)
{
// initialize dist[] and pred[] arrays. Start with vertex s by setting
// dist[] to 0. All vertices are unvisited.
bool *visited = new bool[n];
for (int v = 0; v < n; v++)
{
dist[v] = numeric_limits<int>::max( );
pred[v] = -1;
visited[v] = false;
}

dist[s] = 0;

// find shortest distance from s to all unvisited vertices. Recompute
// potential new paths to update all shortest paths. Exit if u remains -1.
while (true)
{
int u = -1;
int sd = numeric_limits<int>::max( );
for (int i = 0; i < n; i++)
{
if (!visited[i] && dist[i] < sd)
{
sd = dist[i];
u = i;
}
}
if (u == -1)
{
break;
}
// For neighbors of u, see if length of best path from s->u + weight
// of edge u->v is better than best path from s->v. Compute using longs.
visited[u] = true;
for (int v = 0; v < n; v++)
{
int w = weight[u][v];
if (v == u) continue;
long newLen = dist[u];
newLen += w;
if (newLen < dist[v])
{
dist[v] = newLen;
pred[v] = u;
}
}
}
delete [] visited;
}

The Expert System Shell

Maximum Causal Entropy – Adaptive Systems and Intelligence